„Dwie «nogi» programów komputerowych: algorytm i heurystyka” – felieton

Informatyka tak się rozrosła i rozpowszechniła, że w setkach codziennych potrzeb, zarówno tych służbowych jak i prywatnych, korzystamy z komputerów, laptopów, smartfonów, a te urządzenia elektroniczne są w stanie nam pomagać, gdy wyposażone są w programy, określające co i jak powinny robić, żeby zaspokoić nasze potrzeby. Praca programistów jest więc bardzo ważna, bo bez ich dzieł większość urządzeń elektronicznych z których korzystamy, byłaby bezużyteczna. Dlatego warto przyjrzeć się metodom ich pracy.

Oczywiście praca ta wymaga obszernych umiejętności – na przykład znajomości różnych metodyk programowania (strukturalne, obiektowe) oraz biegłości w stosowaniu języków algorytmicznych (na przykład C++, Java, Python), jednak sięgając do najgłębszej warstwy możemy stwierdzić, że praca ta opiera się na algorytmach albo na heurystykach. Spróbuję wyjaśnić co te słowa znaczą.

Algorytm jest ścisłym opisem czynności, jakie trzeba wykonać, żeby osiągnąć pożądany cel. Czynności tych jest skończona ilość i każda z nich jest na tyle prosta, że jej wykonanie nie wiąże się z żadnymi szczególnymi kłopotami, a ponadto czynność ta jest tak jednoznacznie opisana, że wynik jest zawsze taki sam, niezależnie od tego, kto tę czynności wykonuje. Następstwo wykonywanych czynności musi być dokładnie określone, chociaż czasem wybór następnej czynności do wykonania zależy od wyniku czynności, która była wykonana wcześniej. Zapisane w algorytmie czynności mogą być wykonywane wielokrotnie, ale twórca algorytmu musi zagwarantować, że po wykonaniu skończonej liczby czynności algorytm się zatrzyma – najwyżej nie osiągając celu.

Nazwa algorytm pochodzi od nazwiska perskiego matematyka nazywanego w Europie Al-Chorezmi (naprawdę nazywał się Abu Abdullah Muhammad ibn Musa al-Chuwarizmi i żył w Bagdadzie w IX wieku). Teksty Al-chorezmiego i innych matematyków arabskich dotarły do Europy i przywróciły wiedzę o osiągnięciach starożytnych matematyków greckich, całkowicie zapomnianych w okresie średniowiecza. Prace Al-chorezmiego przetłumaczył na łacinę w XII wieku Robert z Chester i od tej pory pojęcie algorytmu było znane powszechnie, chociaż jego znaczenie ogromnie wzrosło w połowie XX wieku, gdy powstały pierwsze komputery, które trzeba było programować. Początkowo wszystkie programy oparte były na algorytmach, które jednak w niektórych przypadkach były tak skomplikowane, że trudne było ich wyrażanie w językach algorytmicznych (pojawiały się błędy programów) a także czas potrzebny do uzyskania przez komputer był nieakceptowalny.

Potrzebne było coś nowego – i tą nowością okazała się heurystyka.

Heurystyka jest oparta na odmiennym podejściu, które okazało się owocne głównie w kontekście złożonych problemów sztucznej inteligencji. Jako metoda rozumowania heurystyka narodziła się w starożytnej Grecji (zapewne w słynnej Bibliotece Aleksandryjskiej) a jej nazwa wywodzi się ze słowa „heuriskein” – znajdować, okrywać. W metodzie tej stosuje się metody prowadzące do znajdowania rozwiązań, tym się charakteryzujące, że działają szybko i pozwalają rozwiązywać bardzo skomplikowane problemy (również takie, na których algorytmy „połamały zęby”). Niestety podejście heurystyczne niczego nie gwarantuje: nie ma pewności, że rozwiązanie zostanie znalezione, a także nie ma gwarancji, że będzie to rozwiązanie najlepsze z możliwych. Starożytną koncepcją heurystyki, która początkowo tkwiła wyłącznie w mętnych rozważaniach filozofów, do współczesnej nauki przeniósł w roku 1945 matematyk węgierski George Polya. Zdołał on zasady heurystyki na tyle uporządkować, że w książce How to Solve it (Jak to rozwiązać) podał zasady użycia heurystyk i opisy najważniejszych z nich.

No i teraz informatycy mogą swobodnie sięgać albo do algorytmów (gdy chcą coś rozwiązać bardzo systematycznie i z gwarancją końcowego wyniku) albo do heurystyki (gdy problem wymaga rozwiązania szybko, ale niekoniecznie optymalnie). I robią to – a pożytek mamy my wszyscy!

Skrócona wersja powyższego felietonu autorstwa prof. Ryszarda Tadeusiewicza została opublikowana w „Dzienniku Polskim” oraz „Gazecie Krakowskiej” 19.1.2024 r.

Wykaz wszystkich publikacji popularnonaukowych prof. Tadeusiewicza wraz z odnośnikami do ich pełnych wersji