Ekspert wyjaśnia, czego o informatyce powszechnie nie wiadomo

Mieścicki przypomniał, że zanim wynaleziono komputery ludzie radzili sobie z różnymi problemami na sposób analogowy. Na przykład pomiary odległości przeprowadzano za pomocą sznurka, rozwiązywano zadania - np. wyznaczanie miejsca położenia statku na morzu i wyznaczanie na mapie jego kursu - wyłącznie z użyciem cyrkla i linijki. Technika "przedkomputerowa" - opowiadał - posługiwała się wykresami i nomogramami, a podstawowym narzędziem pracy inżyniera był do niedawna suwak logarytmiczny, będący - poza komputerami pokładowymi - na wyposażeniu amerykańskich statków kosmicznych Apollo.

"Dziś obliczeń dokonuje komputer. Maszyna realizuje program oparty na wybranym algorytmie. Zadanie rozwiązuje najpierw człowiek rozpisując je na poszczególne kroki. Komputerowi powierza ich wykonanie według zadanego schematu. Czy każdy realny problem da się w ten sposób zapisać? Nie. Czy istnieje jakiś algorytm układania algorytmów? Nie. A gdy algorytm jest już znany (ktoś go wcześniej wymyślił) to kończą się kłopoty. Niestety nie" - mówił. Jako przykład podał tzw. problem komiwojażera.

Niech zadaniem komiwojażera będzie na przykład znalezienie najkrótszej drogi z Warszawy i z powrotem uwzględniającej jednokrotne odwiedzenie trzech miast - Gdańska, Poznania i Rzeszowa (informatyk formułuje to inaczej: znaleźć najkrótszy cykl w zadanym grafie) - zaproponował wykładowca. Jak wyjaśnił, problem sprowadza się do porównania sześciu tras (gdyby miast było 4 tras byłoby 4! czyli 24, gdyby miast było 5 tras byłoby 5! czyli 120 itd.). Jak łatwo wykazać najkrótsza droga prowadzi trasą: Warszawa- Gdańsk -Poznań - Rzeszów - Warszawa lub Warszawa - Rzeszów - Poznań- Gdańsk-Warszawa i liczy 1529 km. Najdłuższa: Warszawa - Gdańsk - Rzeszów - Poznań - Warszawa lub Warszawa - Poznań - Rzeszów - Gdańsk - Warszawa ma 1817 km.

Komputer - zauważył dr Mieścicki - który potrafi wyliczać i porównywać milion tras na sekundę przeprowadziłby takie zadanie w mgnieniu oka. Gdyby dać mu do przeanalizowania trasy 10 miast uporałby się z tym w 3,6 sekundy, a zadanie dla komiwojażera na 12 miast ukończyłby w 8 minut. Ale dalej działo by się coś dziwnego - wyliczenie tras dla 14 miast zajęłoby mu ponad dobę (czyli ponad 86 400 sekund), dla 15 miast ponad 2 tygodnie, 17 miast - około 11 lat, 18 - ok. 200 lat, a 20 miast - 78 tysięcy lat - zaznaczył naukowiec.

Jak tłumaczył, ten gwałtowny wzrost złożoności obliczeniowej i czasu potrzebnego na ukończenie zadania nosi nazwę "eksplozji wykładniczej". Jest on przykładem problemu o takiej złożoności, którego nie rozwiąże w sensownym czasie żaden komputer, ani teraz ani w przyszłości. Podobnych problemów o wielkiej obliczeniowej złożoności i niewiarygodnie długim czasie poszukiwania najlepszego rozwiązania jest w informatyce o wiele więcej. Nad ich rozwiązaniem głowią się setki i tysiące informatyków. Z niektórymi sobie poradzili, inne pozostają nierozwiązane, istnienia jeszcze innych nawet jeszcze nie podejrzewamy - dodał.

Zwrócił przy tym uwagę, że szukając rozwiązań ludzie, niejako po drodze, wynaleźli nowe klasy przydatnych algorytmów - probabilistycznych (z rozwiązaniami przybliżonymi), rekurencyjnych, iteracyjnych, heurystycznych, ewolucyjnych i genetycznych, czy algorytmów sieci neuronowych. "Bo informatyka to pole do działania dla twórczych ludzi" - podsumował dr Mieścicki, zwracając się do słuchaczy, których zdecydowaną większość stanowili uczniowie z warszawskich szkół średnich.(PAP)