#algorytmy — 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

Google wprowadza AI Mode w Chrome. Przeglądarka przestaje być tylko oknem na świat, a staje się jego filtrem

Szukasz idealnego ekspresu do kawy, sprawdzasz parametry i nagle orientujesz się, że masz otwarte dwadzieścia różnych kart, między którymi nieustannie przeskakujesz. Google postanowiło naprawić ten zgubny nawyk i wprowadza do Chrome nową funkcję AI Mode.

Zamiast otwierać kolejne okna, wbudowany asystent analizuje treść witryn i przeszukuje otwarte karty w jednym, połączonym widoku. Za tą niesamowitą wygodą kryje się jednak potężna zmiana – Chrome przestaje być zwykłą przeglądarką, a zaczyna być filtrem, przez który patrzysz na cały internet.

Asystent na bocznym pasku zamiast chaosu w kartach

Główną nowością zaserwowaną przez giganta z Mountain View jest sprytne wykorzystanie podzielonego ekranu. Gdy klikniesz interesujący link w wyszukiwarce, strona otworzy się tuż obok panelu AI Mode. Dzięki temu nie tracisz kontekstu swoich poszukiwań i możesz na bieżąco zadawać pytania do czytanego tekstu. Będąc na stronie sklepu z konkretnym urządzeniem, możesz zapytać asystenta na bocznym pasku, czy np. ten model łatwo się czyści. Algorytmy przeanalizują treść otwartej witryny oraz resztę sieci i podadzą ci gotową odpowiedź. Oznacza to szybkie skanowanie długich artykułów czy analizowanie ofert handlowych bez konieczności ciągłego wracania do głównej strony Google.

Zmiana paradygmatu, czyli Chrome jako warstwa interpretacyjna

Prawdziwa rewolucja kryje się jednak w możliwości przeszukiwania materiałów, które masz już uruchomione w tle. Nowe menu pozwala dodać do zapytania wybrane, otwarte karty, a następnie miksować je z plikami z dysku (np. z dokumentami PDF) czy obrazami.

To nie jest już tylkopodręczne narzędzie dla studentów zakuwających przed sesją. To moment, w którym przeglądarka staje się warstwą interpretacyjną nad twoimi prywatnymi danymi i źródłami zewnętrznymi. Zlecasz maszynie wyciągnięcie wspólnych wniosków z kilku różnych tekstów, a ona przetwarza je i podaje ci gotową, cyfrową syntezę. Zamiast czytać – prosisz o wnioski.

Płacimy za wygodę (i to w konkretnej walucie)

Na nowość będziemy musieli jeszcze chwilę poczekać – obecnie AI Mode debiutuje wyłącznie w USA, ale Google zapowiada szybką ekspansję na kolejne rynki. Warto jednak już teraz spojrzeć na ten ruch z szerszej perspektywy, która ujawnia nie tylko pozytywy.

Przeglądarki internetowe przestają być pasywnymi programami służącymi do wyświetlania kodu HTML, a stają się proaktywnymi asystentami, przejmującymi kontrolę nad przepływem informacji. To niewątpliwie wygodne narzędzie, ale oznacza również, że powoli przestajemy czytać i analizować internet bez bezpośredniego pośrednictwa wszechwiedzącego algorytmu. Dostajemy gotowe odpowiedzi, oddając w zamian proces samodzielnego wyciągania wniosków. Jak to wpłynie na nasze funkcje poznawcze i czy nie zdegraduje naszych umysłów?

Niedawno uczestniczyliśmy w otwarciu nowego ośrodka warszawskiego Fundacji Sensus Vitae. Zapadły nam w pamięć słowa zaproszonej eksperki, psychoterapeutki dr Agnieszki Gąstoł. Zwróciła ona uwagę na niepokojący trend – po raz pierwszy w historii współczesnej najmłodsze pokolenie osiąga słabsze wyniki w testach zdolności poznawczych (takich jak pamięć czy koncentracja) niż ich rodzice. Granicą tego załamania wydaje się być rok 2011, kiedy to smartfony przestały być biznesowym gadżetem, a stały się masowo dostępnym produktem dla każdego. Teraz rozwiązanie Google’a jeszcze bardziej będzie filtrować cyfrową rzeczywistość uwalniając nas – w imię wygody – od trenowania szarych komórek…

Technologia pod kontrolą. Warszawa zyskuje ważne miejsce na mapie cyfrowej edukacji

Przeglądam moją "stronę główną" i sprawdzam, ile wpisów ma hasztagi. Bardzo niewiele. To jak niby mam skonstruować dla siebie mój ulubiony algorytm? 😠

P.S. chodzi mi o to, że nie mogę odfiltrować wpisów o technologii, gadżetach i grach komputerowych (bo te tematy mnie nie interesują).

#algorytm #algorytmFedi #Fediwersum #UX #hasztagi #technologia #StronaGłówna #feed #algorytmy

Jest już nowy odcinek techspress.cafe
https://www.youtube.com/watch?v=CTtHChEqnLs

ostrzegam, że grozi zakupieniem omawianej książki ;)

#algorytmy #BigTechy #socialmedia

📻 Odsłuchałem reportaż audio Panoptykonu - to jest absolutna rewelacja!!! 💚 💙 ❤️ Zdecydowanie polecam!

Czegoś takiego jeszcze nie było: połączenie treści o #prywatność.i, wysokiej jakości merytorycznej z ciekawą, wręcz wciągającą formą reportażu. Strzał w dziesiątkę. 👌

"Algorytmy Traumy. Jak Facebook karmi się twoim lękiem"

https://panoptykon.org/algorytmy-traumy-2-podcast

Do litanii superlatyw chcę jednak dodać, że jedna rzecz mnie rozczarowała: wypowiedź bohaterki reportażu "nie ma realnej alternatywy dla Facebooka" nie spotkała się z żadnym komentarzem ze strony @panoptykon czy informacją o tym, że istnieje #Fediwersum. Oczywiście można się spierać, czy Fedi jest _realną_ alternatywą dla FB. Ale fakt, że sam Panoptykon jest na Fedi wskazuje, że jakaś nadzieja chyba jest. 😉 Jest, prawda? 🙏 Szkoda, że nie dowiedzą się o tym słuchacze i słuchaczki reportażu.

P.S. Dyskusja o tym reportażu na profilu Panoptykonu jest tu: https://eupolicy.social/@panoptykon/111540478599388959

#podcast #reportaż #audycja #słuchowisko #Facebook #algorytmy #AlgorytmyTraumy #trauma #psychika #bezFacebooka