Algorytmy i ich „pochodne” – trochę historii


Zastanawiałem się nad tematem kolejnego artykułu, chcąc aby był on nieco lżejszy od poprzedniego, ale by jednocześnie posiadał wartość dodaną. Dlatego warto przyjrzeć się podstawom, czyli wynalazkom oraz algorytmom, które – jak dobrze wiemy – stanowią obecnie trzon nauk informatycznych. Posiłkował się będę kilkoma przykładami z historii, obrazującymi aspekty bardziej mechaniczne aniżeli za pomocą linijek zapisanego kodu. Postaram się nieco przybliżyć genezę tych schematów i przedstawić krótko ich założenia oraz cechy. Chciałbym, aby tekst ten był pierwszą częścią całości składającej się z dwóch publikacji. W tej kolejnej skupię się na aspektach dzisiejszej technologii jak i bardziej oryginalnych przykładach, chociażby takich jak ugotowanie ulubionej potrawy.

Algorytmy znano (lub raczej praktykowano) już bardzo dawno temu. Najpewniej były po prostu inaczej nazywane i występowały jeszcze przed pierwszym przykładem, który podam. Jest nim algorytm Euklidesa. Jak pisałem wyżej, wobec niego stosowano również inną etymologię od tej, jaką znamy dziś. Został opracowany przez greckiego matematyka Euklidesa. Można przyjąć, że miało to miejsce w IV lub III wieku p.n.e., bo wtedy właśnie żył Euklides (z dużym prawdopodobieństwem około roku 300 p.n e.). Opisuje on sposób odszukania największego wspólnego dzielnika dwóch zestawianych ze sobą liczb. Bazuje na założeniu, że jeśli od większej liczby odejmiemy mniejszą, wytworzy się różnica, która rekurencyjnie odjęta od poprzedniej mniejszej liczby, spowoduje, że powstanie taki sam największy wspólny dzielnik jak w przypadku pierwotnych liczb. Poniżej widać przykład działania takiego schematu. Podaję te liczby nieprzypadkowo, ponieważ wynik algorytmu wskaże, że są one do siebie względnie pierwsze, co ma duże zastosowanie w kryptografii klasycznej. Dla przypomnienia, liczby względnie pierwsze to takie, gdzie ich największym wspólnym dzielnikiem jest liczba 1.

NWD (35, 23) = ?

35 / 23 = 1 reszty 12

23 / 12 = 1 reszty 11

12 / 11 = 1 reszty 1

11 / 1 = 11 reszty 0

NWD (35, 23) = 1

Kiedy powstało pojęcie „algorytm”? Początki tego terminu sięgają IX wieku n.e. Trzeba tu zaznaczyć, że mowa tu o samej terminologii, ponieważ ich używanie świadome lub nie było znacznie wcześniej. Czy to w aspekcie badań i projektowania oraz rozwiązywania aspektów matematycznych, czy wykonywania codziennych czynności prowadzących do osiągnięcia jakiegoś określonego celu. Przykładem pierwszej sytuacji może być chińskie twierdzenie o resztach, a w tym rozwiązywanie układu kongruencji (używane w kryptografii). Przykładem drugiej – przygotowanie posiłku (zebranie składników à przyprawienie à ugotowanie ich). Samo słowo „algorytm” pochodzi od nazwiska arabskiego matematyka Muhammada ibn Musa al-Chuwarzniego, od zlatynizowanej formy jego nazwiska. Z łaciny Algorismus, Algorithmus lub po prostu Algorism.

Przeniesiemy się teraz nieco w czasie w przód i przyjrzyjmy się maszynie o nazwie Step Reckoner. Została zaprojektowana w roku 1671, a zbudowana w roku 1673 przez matematyka i filozofa, Gootfrieda Wilhelma von Leibniza. Koncepcja ta była pewnego rodzaju rozwinięciem idei zapoczątkowanej przez Blaise Pascala, którego można znać z „Traktatu o trójkącie arytmetycznym” kojarzonym dziś z trójkątem Pascala. Warto wspomnieć, że jest to trójkąt, w których liczba jest sumą dwóch liczb znajdujących się powyżej niej i bezpośrednio ze sobą sąsiadujących. Jak niżej:

Powróćmy do urządzenia Step Reckoner. Tak jak wspominałem, jest to rozwinięcie maszyny o nazwie Pascalina, która była sumatorem i potrafiła mechanicznie dodawać oraz odejmować liczby. Step Reckoner posiadał dodatkowo funkcję mnożenia i dzielenia. Liczby przedstawione były w postaci dziesiętnej na dziesięciopozycyjnych wskaźnikach, co umożliwiało bardziej szczegółowe obliczenia. Mimo, że jej używanie wymagało podejścia mechanicznego, algorytmem będzie tu wykonywanie podstawowych działań matematycznych w celu uzyskania interesującego nas wyniku. Wizualnie maszyna prezentuje się następująco:

Step Reckoner (źródło commons.wikimedia.org)

Idąc dalej chronologicznie, warte naszej uwagi jest urządzenie z dziedziny tkactwa. Utworzył ją w 1805 roku Joseph Marie Jacquard, francuski tkacz i wynalazca. Była to maszyna przesmykowa doskonaląca dotychczasowe działanie standardowego krosna. Zlikwidowano w ten sposób ograniczenia w postaci możliwych wzorów poprzez tkanie wielobarwne. Nakładane na karty perforowane były dedykowane wzory, gdzie następowało sterowanie tworzenia przesmyku. Było to czymś w rodzaju programowania, gdzie poprzez implementowanie wzorów fizycznych tworzony był określony produkt. Krótko później  zaczęto produkować wiele takich maszyn, a współcześnie tkaniny tworzone w ten sposób nazywamy żakardowymi.

Kolejnym ważnym momentem, o którym chciałbym wspomnieć, jest końcówka wieku XVII i początki rewolucji przemysłowej, kiedy to z gospodarki manufakturowej zaczęto przechodzić na mechaniczną produkcję fabryczną. Formowano zbiory reguł, które wykorzystywano w tworzeniu maszyn i ich właściwości. Pozwoliło to na automatyzację, początkowo przy zastosowaniu prostych obliczeń, a z czasem coraz bardziej zaawansowanych. W efekcie to maszyny wykonywały określone zadania.

W roku 1842 Charles Babbage – angielski matematyk, twórca tablic logarytmicznych, który przyczynił się do powstania informatyki – sformułował koncepcję maszyny analitycznej, której zadaniem miało być wykorzystywanie złożonych algorytmów matematycznych. Jednym z elementów tej układanki były liczby Bernoulliego, ułatwiające wyliczanie sum ustalonych potęg dla kolejnych liczb naturalnych. Metodę na obliczenie tejże liczby zaproponowała Ada Lovelace, brytyjska matematyczka i poetka. Składowe opisu implementacji wyników tych prac na układ fizyczny w postaci maszyny różnicowej, można porównać do języka programowania. Mimo, że wtedy ostatecznie nie udało się zbudować docelowego narzędzia, w XX wieku prawidłowość tych programów została potwierdzona, a sama maszyna wytworzona. Jej koncepcja opiera się na wyliczaniu wartości dla wielomianów, a budowa pozwala na osiągania obliczeń z dokładnością do 31 cyfr po przecinku. Projekt maszyny różnicowej w sposób znaczący przyczynił się do powstania komputerów, jakie znamy dziś.

Pierwsze algorytmy pracujące liniowo do informatyki teoretycznej można było zaobserwować na początku lat 30. XX wieku. Szczególnym przykładem będzie tu Maszyna Turinga zaprojektowana przez Alana Turinga, który uznawany jest za protoplastę dziedziny, jaką jest sztuczna inteligencja. Jest to urządzenie zbudowane z taśmy, głowicy oraz układu sterowania – składowych, które dziś odpowiadają kolejno pamięci, urządzeniom wejścia/wyjścia oraz procesorowi. Realizuje ona trywialne zadania na podstawie zaimplementowanej logiki oraz opiera się o przetwarzanie symboli zapisanych w komórkach taśmy w inne dane, tworząc wyniki i zapisując je w tym samym miejscu. Dzięki wbudowanemu układowi sterującemu istnieje możliwość dowolnego programowania, od czego jednoznacznie zależy jaka operacja zostanie wykonana. Pomimo swej prostoty, również dziś ma ona ogromną wartość teoretyczną ze względu na to, że aktualnie wytwarzane i używane nowoczesne komputery mogą być do niej sprowadzone. Ma to związek z faktem, że operując na podstawowych bitach i tak są wstanie obejmować bardziej skomplikowane informacje, a w tym odtwarzanie wideo.

Poniżej postarałem się w bardzo trywialny sposób zaprezentować część działania symulacji maszyny:

Taśma 1

#   1   0   0   0   1    e   …

Głowica na podstawie stanu i wartości pobranej z aktualnie czytanej komórki wykonuje akcję podmiany (pogrubiona wartość)

#   1   0   1   0   1    e   …

Po wykonaniu tej akcji następuje zmiana stanu i przesunięcie głowicy (w dalszej części akcje następują analogicznie jak wyżej)

#   1   0   1   0   1    e   …

#   1   1   1   0   1    e   …

……………………………………………………………………………………………………………………………………………………………………………………………………..

Ostatni przykład, już typowo ‘słowny’, będzie myślę dobrze znany, ponieważ jest bardzo chętnie implementowany do dzisiejszych systemów informatycznych. Mowa tu o algorytmie sortowania szybkiego – z angielskiego Quicksort. W roku 1960 wynalazł go brytyjski informatyk, Sir Charles Anthony Richard Hoare. Za te i inne osiągnięcia informatyczne naukowiec otrzymał w 1980 roku nagrodę Turinga. Algorytm Quicksort to jeden z najszybszych sposobów sortowania. Opiera się na technice ‘dziel i zwyciężaj’. ‘Dzielenie’ obrazuje podział głównego zadania na podzadania. Podany zbiór dzielimy względem elementu ‘środkowego’ (zwanego pivotem, wybieranego losowo lub zgodnie z założonym schematem) na dwa mniejsze. Pamiętać należy o tym, aby elementy zbioru lewego były mniejsze lub równe każdemu elementowi zbioru prawego, co skutkuje pierwszym sortowaniem algorytmu. Tutaj czas na ‘Zwyciężaj’, gdzie rekurencyjnie wykonujemy tą samą akcję na powstałych przedziałach. Po zakończeniu sortowań następuje połączenie podzbiorów, co tworzy docelowe rozwiązanie zadania w postaci jednego, pełnego, posortowanego zbioru. Sortowanie szybkie w założeniu pesymistycznym ma złożoność obliczeniową na poziomie 0(n^2), natomiast założenie optymistyczne jest równe 0(n log n). Quicksort ma jednak wadę, która uwidacznia się, kiedy ułożenie danych wejściowych jest niekorzystne lub pivot został wybrany nieoptymalnie. Wtedy właśnie złożoność wchodzi w obszar pesymistyczny, a działający algorytm może przepełnić stos i zablokować pracę komputera. Podsumowując – przedstawiony model, stosowany na odpowiednich danych wejściowych, pozwoli na wykonanie sortowania zbioru przy zachowaniu bardzo dobrej wydajności.

Poniżej podaję dosyć prosty przykład tego, jak ja rozumiem ten algorytm:

Zbiór (3 , 1 , 5 , 10  , 7 , 15 , 17 , 8 )

Jako pivot wybieramy liczbę 8 i dzielimy listę na dwa podzbiory. Po lewej stronie są liczby mniejsze lub równe 8, natomiast po prawe – większe lub równe 8

Podzbiór pierwszy (3 , 1 , 5 , 7) , 8 , Podzbiór drugi (10 , 15 , 17)

Na ten moment prawy podzbiór jest posortowany, tak więc trzeba posortować podzbiór lewy. W tym celu wybieramy nowy pivot, np. liczbę 1.

Po wykonaniu czynności jak wyżej otrzymujemy:

1, Podzbiór pierwszy (3 , 5 , 7) , 8 , Podzbiór drugi (10 , 15 , 17)

Po połączeniu podzbiorów powstaje jeden wspólny, posortowany zbiór, jak niżej:

Zbiór (1 , 3 , 5  , 7 , 8 , 10 , 15 , 17)

Posiłkując się ostatnim przykładem, widać podstawowy schemat wykorzystywania i działania algorytmów. Przygotowanie danych, poprzez wykonanie określonych czynności (często powtórzeniowo),  doprowadza do rozwiązania zadania poprzez uzyskanie wyniku finalnego. Poprawne wykorzystanie tej metodyki, czy to za pomocą urządzeń mechanicznych czy systemów technologicznych, umożliwia procedowanie akcji w sposób szybszy i bardziej efektywny.

Jest to zaledwie kilka przykładów rozwoju, szablonów czy wynalazków, które przyczyniły się do tego, jak wygląda dzisiejsza informatyka. Myślę jednak, że dobrze obrazują one kontrast pomiędzy dzisiejszą technologią a zarazem wskazują solidne podstawy, na których ta technologia jest zbudowana. Niekiedy te podstawowe oraz, wydawałoby się, proste schematy znajdują zastosowanie również dzisiaj. W kolejnym artykule przedstawię współczesne przykłady urządzeń i schematów algorytmicznych, które jednak posiadają podobny cel: wykonanie określonych bloków zadań dla automatyzacji procesów.

……………………………………………………………………………………………………………………………………………………………………………………………………..

BIBLIOGRAFIA

  • Anglojęzyczna encyklopedia powszechna Britannica

https://www.britannica.com

  • Encyklopedia PWN

https://encyklopedia.pwn.pl

  • Serwis edukacyjny

https://eduinf.waw.pl

  • Serwis programistyczny

 http://www.algorytm.edu.pl/

  • Platforma edukacyjna

https://szkolnictwo.pl

  • Serwis edukacyjno-informacyjny o algorytmach

https://slonie354.prv.pl

  • platforma z instrumentami dla publikacji i wymiany informacji

https://docplayer.pl/


Mateusz Rogala

O Mateusz Rogala

Pracuję w Atenie jako młodszy tester oprogramowania. Ukończyłem studia podyplomowe na Politechnice Gdańskiej z kierunkiem Programowanie i bazy danych. Obecnie studiuję Informatykę na kierunku inżynieskim ze specjalizacją z programowania w Wyższej Szkole Bankowej. Poza 'kodowaniem' interesuję się tematem materii, fizyką i informatyką kwantową. W wolnych chwilach zajmuję się kalisteniką, czytam książki fantastyczne oraz poszerzam wiedzę w różnych dziedzinach.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *