Algorytmy są dziś obecne w każdej sferze naszego życia. Samo słowo we współczesnych mediach jest odmieniane przez wszystkie przypadki. Przecież nikt sobie już nie wyobraża poruszania się w nieznanym terenie bez odbiornika GPS i aplikacji, która wyznacza najkrótszą ścieżkę do najbliższej kawiarni. Co więcej, taka aplikacja może nam zasugerować najlepszą kawiarnię na podstawie ocen innych użytkowników. Wszyscy wirtualni asystenci, z którymi możemy porozmawiać również wykorzystują zaawansowane algorytmy rozpoznawania mowy. Film czy serial, przy którym spędzamy wieczór również jest nam sugerowany przez algorytmy sztucznej inteligencji, które analizują nasz gust na podstawie dotychczas obejrzanych pozycji. Nawet lodówki są w stanie przeanalizować swoją zawartość i zasugerować listę zakupów. Nie wspominając nawet o takich banałach jak termostat czy klimatyzator, na których ustawiamy oczekiwaną temperaturę, a algorytmy sterują parametrami działania urządzeń w taki sposób, abyśmy czuli się komfortowo w naszych mieszkaniach.
 

Te i inne zastosowania wszechobecnych algorytmów mogłyby sugerować ich ścisły związek ze współczesną technologią i komputerami, bez których nawet lodówka nie działałby zgodnie z naszymi wysokimi wymaganiami.
 

Ale nie zawsze tak było. Samo słowo algorytm jest bardzo stare. W świadomości Europejczyków pojawiło się na wiele wieków przed skonstruowaniem pierwszego komputera, który wykorzystywał tranzystory. Bo historia maszyn liczących jest bardzo długa i zasługuje na własny artykuł. Ale wróćmy do algorytmów. Samo słowo pochodzi od nazwiska perskiego matematyka محمد بن موسی خوارزمی, które w alfabecie łacińskim można zapisać: Muḥammad ibn Mūsā al-Khwārizmī. Ostatni człon nazwiska to przydomek oznaczający jego pochodzenie, które zostało zlatynizowane jako Algoritmi. Zasłyną on jako autor traktatu w języku arabskim, w którym opisał cyfry znane dziś w Europie jako arabskie (warto podkreślić, że koncept ten pojawił się w świadomości Europejczyków dzięki Leonardowi z Pizy, który w pop-kulturze jest znany jako Fibonacci). I to właśnie działania na cyfrach arabskich zaczęto w Europie określać słowem algorismus.
 

Później, pod wpływem języka greckiego, słowo zostało zniekształcone do algorithmus. Wraz z upływem czasu zmieniło się też znaczenie słowa. Współcześnie możemy rozumieć je jako określenie skończonego ciągu ściśle określonych instrukcji, który przekształca dane wejściowe w wynik. Najprostszym możliwym przykładem jest przepis kucharski. Możemy na wejściu położyć surowe jajko. Po wykonaniu ciągu prostych czynności (takich jak włożenie jajka do garnka, nalanie do garnka wody, postawienie garnka na kuchence, zagotowanie wody w garnku i następnym gotowaniu jajka przez 10 minut) dostajemy jajko ugotowane na twardo, które jest wynikiem działania algorytmu.
 

Warto mieć na uwadze, że takie schematy wykonywania obliczeń zostały opisane na długo przed tym jak  al-Khwārizmī napisał traktat o cyfrach arabskich. Przykładem takich obliczeń może być procedura opisana przez Euklidesa w jego Elementach (które powstały około 300 roku przed naszą erą) służąca do znajdowania największego wspólnego podzielnika dwóch liczb całkowitych. Obliczenia te są nazywane dziś algorytmem Euklidesa. Jest on wciąż szeroko używany. Począwszy od uczenia adeptów programowania, na czym polega rekurencja, a skończywszy na zaawansowanych algorytmach kryptograficznych (takich jak RSA), z których być może (zupełnie nieświadomie) skorzystałeś wchodząc na stronę zawierającą ten tekst.
 

No właśnie, udało się nam dojść do pierwszego słowa kluczowego tego artykułu – rekurencja. Rekurencja to jest taki sposób definiowania obiektów czy funkcji, w którym w definicji odwołujemy się do niej samej. Jako przykład rozważmy uwspółcześnioną wersję algorytmu Euklidesa. Algorytm na wejściu dostaje parę liczba a i b. Algorytm definiuje tak naprawdę tylko jedną operację – jest to obserwacja, że największy wspólny podzielnik liczb a i b jest taki sam jak największy wspólny podzielnik liczb b oraz reszty z dzielenia liczby a przez b. Można to opisać nieco ściślej za pomocą pseudokodu:
 

def gcd (a: integer, b:integer) => integer:

    return gcd(b, a%b)
 

Jest jedno „ale” – taka funkcja oznaczałaby, że mamy do czynienia z nieskończoną definicją. To by było sprzeczne z definicją algorytmu, o której napisałem wcześniej – że algorytm to skończona lista kroków. Tutaj warto zauważyć, że jeżeli liczba b czyli tak naprawdę reszta z dzielenia a przez b policzona w poprzednim kroku jest równa zeru, to oznacza, że b dzieli a bez reszty – więc to właśnie to b (z poprzedniego kroku) jest poszukiwanym podzielnikiem. A to prowadzi nas do poprawionego (i poprawnego) opisu algorytmu Euklidesa:
 

def gcd (a: integer, b:integer) => integer:

    if b == 0 then

        return a

    else

        return gcd(b, a%b)
 

Dlaczego o tym piszę? Od Euklidesa już tylko krok do wspomnianego w tytule tekstu Rzymu. A Rzymianie, podobnie jak Grecy, położyli podwaliny pod całą dzisiejszą cywilizacjęA ja chciałbym się skupić na wpływie Rzymian na współczesną informatykę. I nie mam teraz na myśli szyfru Cezara, który miał naprawdę ogromny wpływ na kształt dzisiejszego świata i Polski (ale o tym napisałem artykuł jakiś czas temu: https://zielony-backlog.pl/blog/2020/11/12/jak-grzebien-wplynal-na-historie-polski/).
 

Czy zastanawiałeś się kiedyś, jak Rzymianie byli w stanie rządzić tak wielkim imperium? Przecież takich rodowitych Rzymian było stosunkowo niewielu. Wszystko dzięki ich maksymie: divide et impera, którą można przetłumaczyć na polski jako dziel i rządź. Gdy Rzymianie podbijali jakiś obszar, to nazywali jego mieszkańców swoimi sprzymierzeńcami. Jednocześnie zabraniali podpisywać jakichkolwiek umów z innymi, podbitymi przez Rzymian ludami. Dodatkowo wzbudzali konflikty pomiędzy sąsiadami, co bardzo utrudniało ich sprzymierzenie się przeciwko najeźdźcom. Ta maksyma przyświecała wielu późniejszym politykom.


Całe szczęście nie tylko politycy wyciągnęli naukę z polityki Rzymian. Każdy z nas może wyciągnąć z tego lekcję dla siebie. Jeżeli masz do rozwiązania duży problem, lub jakieś duże zadanie do wykonania – podziel je na mniejsze pod problemy lub podzadania – będzie Ci łatwiej z nimi sobie poradzić. Takie podejście znajduje swoje zastosowanie w informatyce. Komputerowi łatwiej sobie poradzić z mniejszym problemem. A jeżeli sprytnie podzielimy problem obliczeniowy na mniejsze podproblemy, to uda nam się później znaleźć rozwiązanie dużego problemu na podstawie rozwiązań tych mniejszych podproblemów. Takie podejście do konstruowania algorytmów ma swoją nazwę. Dokładnie taką samą jak polityka Rzymian w podejściu do podbitych ludów.
 

Przecież gdy ciąg do posortowania składa się z jednego elementu, to już jest posortowany. A jak mamy obok siebie dwa posortowane ciągi, to łatwo na ich podstawie utworzyć posortowany ciąg złożony z elementów dwóch krótszych ciągów. Metoda dziel i rządź (albo dziel i zwyciężaj) ma naprawdę szerokie zastosowanie we współczesnej informatyce. Dokładne omówienie tego przykładu z sortowaniem, oraz wielu innych algorytmów, a także wytłumaczenie, jaki jest związek rekurencji z metodą dziel i zwyciężej, znajdziesz w moim kursie video dostępnym na platformie videopoint.

 

Nawet jeżeli Cię nie przekonałem do zapoznania się z treścią kursu, to mam nadzieję, że jeszcze bardziej doceniłeś wpływ antycznego świata na nasze wygodne współczesne życie.

 

Sprawdź kursy autorstwa Pawła Bogdana: