#informatyka — Public Fediverse posts

Jak pokonać króla po 66 latach? Matematyczny przewrót w teorii najkrótszej ścieżki

Za każdym razem, gdy uruchamiasz Google Maps, by znaleźć trasę do nowej kawiarni, Twój telefon wykonuje matematyczny taniec, którego kroki opracowano w 1959 roku.

Przez ponad sześć dekad algorytm Dijkstry był niekwestionowanym władcą dróg, światłowodów i rezerwacji lotniczych. Aż do teraz, kiedy grupa naukowców z Chin udowodniła, że przez wiele lat wszyscy zadawaliśmy złe pytanie.

Certyfikat nietykalności

Algorytm Dijkstry to fundament informatyki. Jest tak dobry, że jeszcze w 2024 roku Robert Tarjan (legenda teorii grafów, laureat Nagrody Turinga w 1986 roku) wraz ze współpracownikami zdobył prestiżową nagrodę na konferencji FOCS za udowodnienie, że Dijkstra jest optymalny. Oznaczało to, że matematycznie nie da się znaleźć najkrótszej ścieżki szybciej. Wydawało się, że temat jest zamknięty.

Jednak zaledwie osiem miesięcy później zespół z Uniwersytetu Tsinghua pod kierownictwem Rana Duana opublikował artykuł, który zburzył ten mur. To praca z 2025 roku, ale uznaliśmy, że temat ciekawy, w sam raz na weekend.

Pułapka definicji: co właściwie liczymy?

Jak to możliwe, że ktoś pobił algorytm uznany za „najlepszy z możliwych”? Okazało się, że Tarjan i cała reszta świata wpadli w pułapkę definicji.

Dowód na optymalność Dijkstry zakładał, że algorytm musi nie tylko podać odległość, ale też wyprowadzić wszystkie punkty na trasie posortowane według dystansu. Grupa z Tsinghua zauważyła coś, co w akademickich kuluarach przyjmowano już od 1984 roku: znalezienie najkrótszej ścieżki wcale nie wymaga sortowania wszystkiego po drodze. Problem brzmi „znajdź odległość”, a nie „posortuj miasto”.

Nowa granica prędkości

Chiński zespół połączył stare metody (algorytm Bellmana-Forda) z nowatorskim trikiem „rekurencyjnego częściowego porządkowania”. Zamiast sprawdzać każdą uliczkę po kolei, zaczęli grupować węzły i badać tylko ich „reprezentantów”. Wynik to nowa złożoność obliczeniowa. To pierwszy taki wyłom w „suficie” wydajności wyznaczania trasy od dekad.

Warto jednak postawić tu ważną gwiazdkę: to odkrycie to przede wszystkim trzęsienie ziemi w teorii algorytmów. W świecie rzeczywistym – tym, w którym działają serwery Google czy systemy routingowe (bo nie tylko o nawigację tu chodzi, także wyznaczanie tras pakietów danych i wiele więcej) – od dawna rzadko używa się „czystego” Dijkstry. Inżynierowie stosują tam heurystyki (jak A*; jeden z najpopularniejszych algorytmów heurystycznych wyszukiwania ścieżki w grafie, stosowany powszechnie w nawigacji GPS, ale też np. w sztucznej inteligencji w grach wideo), hierarchie grafów i zaawansowany precomputing, które w praktycznych zastosowaniach i tak wykraczają poza ramy tego odkrycia. Chiński zespół udowodnił jednak coś ważniejszego: matematyczny mur, który uważaliśmy za nieprzekraczalny, właśnie runął.

Lekcja dla nas wszystkich

Ta historia to coś więcej niż ciekawostka dla programistów. To mocna lekcja o tym, jak ramy, w których osadzamy problem, stają się naszymi ograniczeniami. Dijkstra był najlepszy w rozwiązywaniu zadania „najkrótsza ścieżka z posortowanym wynikiem”. Świat potrzebował po prostu „najkrótszej ścieżki”.

Traktowaliśmy te dwa problemy jako jedność przez dekady tylko dlatego, że nikt nie zapytał: „czy to sortowanie jest nam w ogóle potrzebne?”. Najbardziej ugruntowany algorytm świata został pokonany nie przez potężniejszy procesor, ale przez kogoś, kto zakwestionował samą definicję limitu.

Największa mapa Wszechświata gotowa. Właśnie zaczyna się trzęsienie ziemi w świecie fizyki

Oferujemy:
- elastyczny grafik – bez problemu połączysz naukę z pracą u nas
- realne zadania – rozwiązujesz biznesowe potrzeby klientów
- świetna atmosfera – komfortowe warunki pracy, wspierający zespół (mamy doborowe towarzystwo, co widać na zdjęciach)
- perspektywy – dla najlepszych przewidujemy możliwość stałej współpracy

Aplikować można przez mail [email protected]. Więcej: wildasoftware.pl.

Zapraszamy!

(3/3)

#PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Będziesz też wykorzystywał nasz autorski projekcie #Feedybacky, odkrywając, dlaczego jest lepszy od Jiry, a nawet jeśli nie jest, to i tak jest.

Poznasz know-how, tworzenie systemów IT od kuchni i będziesz miał(a) szansę współtworzyć kod ramię w ramię z doświadczonymi programistami, którzy mogą udzielić cennych rad.

(2/3)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Nieśmiało chcemy ogłosić, że ponieważ na uczelniach zaczyna się okres praktyk studenckich, to serdecznie zapraszamy do miejsca, gdzie można poczynić pierwszy krok w swojej karierze IT. Czyli do nas, do Wilda Software.

Tworząc aplikacje webowe oraz hybrydowe popracujesz w:

- backendzie: #PHP (#Laravel oraz Yii 2.0)
- frontendzie: #Angular (i JavaScript)
- bazach danych: #MySQL, #PostgreSQL

(1/3)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Nieśmiało chcemy ogłosić, że ponieważ na uczelniach zaczyna się okres praktyk studenckich, to serdecznie zapraszamy do miejsca, gdzie można poczynić pierwszy krok w swojej karierze IT. Czyli do nas, do Wilda Software.

Tworząc aplikacje webowe oraz hybrydowe popracujesz w:

- backendzie: #PHP (#Laravel oraz Yii 2.0)
- frontendzie: #Angular (i JavaScript)
- bazach danych: #MySQL, #PostgreSQL

(1/X)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Nieśmiało chcemy ogłosić, że ponieważ na uczelniach zaczyna się okres praktyk studenckich, to serdecznie zapraszamy do miejsca, gdzie można poczynić pierwszy krok w swojej karierze IT. Czyli do nas, do Wilda Software.

Tworząc aplikacje webowe oraz hybrydowe popracujesz w:

- backendzie: #PHP (#Laravel oraz Yii 2.0)
- frontendzie: #Angular (i JavaScript)
- bazach danych: #MySQL, #PostgreSQL

(1/3)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Nieśmiało chcemy ogłosić, że ponieważ na uczelniach zaczyna się okres praktyk studenckich, to serdecznie zapraszamy do miejsca, gdzie można poczynić pierwszy krok w swojej karierze IT. Czyli do nas, do Wilda Software.

Tworząc aplikacje webowe oraz hybrydowe popracujesz w:

- backendzie: #PHP (#Laravel oraz Yii 2.0)
- frontendzie: #Angular (i JavaScript)
- bazach danych: #MySQL, #PostgreSQL

(1/3)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Nieśmiało chcemy ogłosić, że ponieważ na uczelniach zaczyna się okres praktyk studenckich, to serdecznie zapraszamy do miejsca, gdzie można poczynić pierwszy krok w swojej karierze IT. Czyli do nas, do Wilda Software.

Tworząc aplikacje webowe oraz hybrydowe popracujesz w:

- backendzie: #PHP (#Laravel oraz Yii 2.0)
- frontendzie: #Angular (i JavaScript)
- bazach danych: #MySQL, #PostgreSQL

(1/3)

#programowanie #PraktykiIT #Poznań #PolitechnikaPoznańska #Informatyka #KarieraIT

Znalezienie dobrych list blokad dla serwerów DNS bywa problematyczne - często są nieaktualne albo pełne fałszywych trafień.

Dlatego powstał generator list blokad, który umożliwia łatwe dopasowanie listy do własnych potrzeb. Listy są regularnie aktualizowane, a projekt jest w pełni open source.

Generator: https://sefinek.net/blocklist-generator

Strona: https://blocklist.sefinek.net

GitHub: https://github.com/sefinek/Sefinek-Blocklist-Collection

#dns #informatyka #pihole #adguard #sieć #network #serwer #ochrona #bezpieczeństwo

Znalezienie dobrych list blokad dla serwerów DNS bywa problematyczne - często są nieaktualne albo pełne fałszywych trafień.

Dlatego powstał generator list blokad, który umożliwia łatwe dopasowanie listy do własnych potrzeb. Listy są regularnie aktualizowane, a projekt jest w pełni open source.

Generator: https://sefinek.net/blocklist-generator
Strona: https://blocklist.sefinek.net
GitHub: https://github.com/sefinek/Sefinek-Blocklist-Collection

#dns #informatyka #pihole #adguard #sieć #network #serwer #ochrona #bezpieczeństwo

Czy robisz #backup swoich danych cyfrowych? 💾

🔄 Podbij, dziękuje.
#miniankiety #kopiazapasowa #technika #technologia #informatyka