Wstęp.
Dział, który właśnie rozpoczynamy, będzie prawił o algorytmach. Będziemy mówić o ich podstawach, będziemy mówić o ich typach oraz istocie, analizach, podejściach, modelach obliczeniowych itd. Jednakże, czym tak naprawdę są? Pojęcia tego używamy na co dzień, ale czy kiedykolwiek, ktokolwiek z was, zastanowił się, co tak w ogóle to pojęcie znaczy? Postaramy się dziś odpowiedzieć na to pytanie, zarówno od strony językowej jak i informatycznej. Zapraszam serdecznie.
Rzecz pierwsza. Etymologia - czyli skąd to słowo?
Dobre pytanie. Okazuje się bowiem, że jest to efekt próby przełożenia języka arabskiego, na łacinę. W jaki sposób? Już tłumaczę.
Otóż, był sobie kiedyś pewien perski matematyk Muḥammad ibn Mūsā al-Khwārizmī, którego życie przypada na 780-850 lata naszej ery. Był on autorem pewnej rozprawy, która to miała treścią pokryć system liczb hindusko-arabskich. Co to za liczby? Ano są to liczby, których używamy po dziś dzień. Mowa oczywiście o cyfrach arabskich. O jej hinduskim przedrostu zapominano, ze względu na fakt, że liczby te do naszych zachodnich rejonów świata, przybyły wraz z arabskimi kupcami jeszcze tego samego wieku (9'tego), toteż w naszych umysłach cyfry są arabskie.
Wracając do owej rozprawy. Była ona na tyle ciekawa dla europejskich naukowców 12 wieku, że postanowili ją przetłumaczyć na język dla nich powszechny. Kolebką nauki w tychże wiekach stanowił kler, a powszechnym wtedy językiem kościoła była łacina, toteż na łacinę próbowano tę rozprawę tłumaczyć. Oczywistym jest faktem, że łacina i języki arabskie są bardzo od siebie różne, toteż trzeba było pójść na ustępstwa już od samego początku tłumaczenia i tak imię autora, którego wymowa brzmi z arabskiego tak, została przez tłumaczy przetłumaczona na Algorismus. Sama praca to z angielskiego "Al-Khwarizmi on the Hindu Art of Reckoning" (nie znalazłem arabskiego tytułu. Jeżeli ktoś ma to proszę napisać do mnie dowolnym kanałem komunikacyjnym.), a jako że tłumacze chcieli w tytule zawrzeć coś w rodzaju "Rozprawa al-Khwārizmī'ego o hinduskiej sztuce rachunków" przenieśli tytuł na łacinę w brzmieniu: "Algoritmi de numero Indorum". Algorismus zostało w poprzez deklinację zmienione na Algoritmi.
Samo słowo Algorismus wędrowało po świecie by spotkać się z greckim Arithmos, które oznacza liczbę i wraz z angielskim Algorism, które oznacza arytmetykę na liczbach arabskich, które wywodzi się od Algorismus właśnie, powstało francuskie Algorithme a ono przeniknęło do innych języków, np. w angielskich jako Algorithm, a w polskim Algorytm.
Rzecz druga. Definicja.
Algorytm. Jak wiele dziedzin, jak wiele autorów, tak wiele definicji. Zacznijmy więc od dosyć intuicyjnej dla osoby nietechnicznej, nie mającej z informatyką nic wspólnego, a mianowicie od definicji ze słownika języka polskiego:
"Ściśle określony ciąg czynności, których wykonanie prowadzi do rozwiązania jakiegoś zadania" - https://sjp.pwn.pl/szukaj/algorytm.html
Definicja trywialna wręcz. Robimy coś, żeby zrobić coś. Wedle tej definicji algorytmem może być np. przepis na zrobienie jajecznicy, instrukcja ćwiczenia na orbitreku, albo dodawanie pisemne. Definicja ta jest więc bardzo szeroka, obejmująca niemal wszystko co nas otacza, od algorytmu komiwojażera do algorytmu kucia miecza przez kowala.
Po chwili zastanowienia jednak taka definicja może być problematyczna, z punktu widzenia informatycznego, bo jak np. formalnie matematycznie opisać taki algorytm? W jaki sposób liczyć jego efektywność? Jak porównywać z innymi algorytmami? Jak zdefiniować operację w takim algorytmie? To są pytania, na które odpowiedź znajdziemy w definicji następnej, a na które odpowiedzi szukać w poprzedniej nie ma sensu.
Poszukajmy więc definicji, która "formalnie" opisze czym algorytm jest. Ciekawym faktem jest to, że takowa nie istnieje. Wielu autorów podaje swoją. Taki np. Thomas Cormen powiada:
"Nieformalnie, algorytm jest pewną ściśle określoną procedurą obliczeniową, która dla właściwych danych wejściowaych "produkuje" żądane dane wyjściowe, zwane wynikiem działania algorytmu. Algorytm jest więc ciągiem kroków obliczeniowych przekształcających dane wejściowe w wyjściowe." - Thomas Cormen - Wprowadzenie do algorytmów (Wydanie VII PWN str. 4)
Definicja niewątpliwie ciekawa, miła w rozumieniu jak i w brzmieniu. Bliska, a wręcz tożsama definicji matematycznej funkcji. Mamy jakieś dane i jakaś procedura coś z nimi robi dając wynik. Np. weźmie ciąg liczb i zwróci nam największą z nich, lub, co ciekawsze, zwróci nam sekwencję gdzie będą one posortowane rosnąco.
Dokładnie tak należy rozumieć algorytm, jak matematyczną funkcję. Dostaje jakieś wejście, robi coś, daje nam wyjście, mając przy tym ściśle zdefiniowane kroki, które musi podjąć, żeby owe "coś" wykonać. (W odniesieniu do programowania, nie ma znaczenia czy zwraca czy nie zwraca (void), bo zawsze można zrobić tak, żeby zwróciło. Np. zamiast sortować podaną tablicę, zwróci posortowaną. Sortowanie wewnętrzne samej tablicy jest optymalizacją, która w matematyce nie ma znaczenia.)
Rzecz trzecia. Reprezentacje.
Algorytmy możemy przedstawiać na różne sposoby. Co to znaczy? Otóż, jeżeli chcemy przedstawić jakąś idee, można ją np. napisać słownie, albo jako wiersz, piosenkę, przepis, albo po prostu wypisać kroki lub je narysować. Widzimy więc, że algorytm można przedstawiać na różne sposoby, a jakie sposoby wybierzemy, zależy od naszej wyobraźni i chęci osób postronnych do ich interpretacji. Najczęściej jednak algorytmy opisuje się na 3 sposoby:
- Jako zwykły tekst, wypisując słownie kroki jakie trzeba podjąć, np:
- Wybierz losowo liczbę pierwszą,
- Pomnóż ją przez 45,
- Wybierz kolejną losową liczbę pierwszą,
- Dodaj do niej poprzednio wylosowaną liczbę pierwszą.
- Pseudokodem, tj. kodem, który ma pokazywać formalnie jak algorytm wykonać, imitując przy tym język programowania, ale nie będącym nim. Pozwala to na generalizacje pomysłu na elementy wspólne wszystkim językom programowania, nie wchodząc jednocześnie w szczegóły związane z żadnym z nich. Pozwala to na opis implementacji w dowolnym języku jaki zna czytelnik. Np:
dla każdego elementu x w zbiorze X y = x * 2 do zbioru Y dodaj y zwróć Y
- Graficznie w postaci schematu. Można dzięki temu pokazać w postaci diagramu/rysunku jak przebiegają kolejne kroki algorytmu. Jako że większość ludzi jest wzrokowcami i łatwo przychodzi im zapamiętanie i zrozumienie obrazków, jest to dosyć popularna forma. Np. realizacja schematu algorytmu dzielenia może być przedstawiona tak:
Sposobów oczywiście jest masę. Jak dużo problemów, jak dużo zadań, tak dużo typów i odpowiadających im najlepszych form prezentacji. Np. sortowanie najlepiej pokazać pisząc po prostu kod programu, schemat postępowania przy gotowaniu najlepiej wypisać, algorytm świateł drogowych najlepiej pokazać na schemacie graficznym, a wynik funkcji logicznych najlepiej podać jako tabelę reakcji na wejścia, zamiast wypisywać programistyczne if'y.
Rzecz czwarta. Podejście informatyczne.
W informatyce algorytm będzie jednoznacznie kojarzony z funkcją, która jest realizowalna przez jakąś maszynę. Mówić będziemy o algorytmie sortowania, algorytmie szukania największego wspólnego dzielnika, algorytmie komiwojażera, algorytmie mnożenia, pierwiastkowania. Jest to o tyle ważne, że algorytm w sensie językowym odnosić się będzie do wszystkiego, a komputer nie jest w stanie zrealizować wszystkiego, dlatego nie będziemy dotykać innych dziedzin niż tylko liczbowe/obliczeniowe.
Jako że algorytmy będą robić coś, będą mogły zrobić to poprawnie, albo niepoprawnie, dlatego do każdego algorytmu, należy sformułować dowód jego poprawności i robi się to na różne sposoby. Temat dowodzenia poprawności algorytmów zostawimy sobie na potem, bo jest to zadanie dosyć trudne na początek.
Algorytmy jako, że będą realizowane przez komputery, należy je również zaimplementować, więc wszelkie propozycje ich przedstawienia będą musiały dać się odwzorować w modelu obliczeniowym, jaki wybierzemy, tak, żeby dało się go zrealizować, np. jako kod programu, albo układ elektroniczny. Modele obliczeniowe opiszemy sobie w następnych artykułach.
Algorytmy będziemy analizować pod względem czasu ich działania (złożoność obliczeniowa czasowa) oraz pod względem użytych przez nich zasobów (złożoność obliczeniowa czasowa), opis tych również zrealizujemy sobie później.
Projektowanie algorytmów, będzie również cechowało się podejściem do ich realizacji, np. dziel i rządź, nawrotowy, podejściem w implementacji, np: rekurencyjny, współbieżny, itd. Każde z tych rzeczy opiszemy później.
Później, później, później, czemu nie teraz? Ano dlatego, że musiałoby się tu pojawić masę pojęć i wzorów, których na ten czas nie znamy i nie wiemy co znaczą, a ich wyjaśnienie potrzebuje masę teksu i czasu, dlatego teraz delikatnie opisałem, na co jeszcze będziemy wyczekiwać i co będziemy musieli zrozumieć żeby wiedzieć co owe "później" rzeczy będą znaczyły.
Podsumowanie.
Wiemy już czym jest algorytm, skąd pochodzi i co oznacza. Nie wiemy jednak jeszcze dużo o jego właściwościach oraz realizacjach, typach, analizach, cechach. Niedopowiedzenia te będą wyjaśniane wraz z następnymi artykułami, przez co delikatnie i płynnie wprowadzać będziemy następne pojęcia, by dokładnie zrozumieć jak do każdego algorytmu podejść.
Dziękuję za uwagę i do zobaczenia w następnych artykułach :)
Źródła.
- https://www.dictionary.com/browse/algorism
- https://ioinformatics.org/journal/v11si_2017_71_74.pdf
- https://en.wikipedia.org/wiki/Muhammad_ibn_Musa_al-Khwarizmi
- https://en.wikipedia.org/wiki/Hindu%E2%80%93Arabic_numeral_system
- http://www-history.mcs.st-andrews.ac.uk/Biographies/Al-Khwarizmi.html
- https://en.wikipedia.org/wiki/Algorithm#cite_note-12
- Thomas Cormen - Introduction to Algorithms - ISBN 9788301169114
Komentarze