Pojęcie algorytmu 1

POJĘCIE ALGORYTMU

Algorytm to podanie pewnej sekwencji czynności, które zgodnie z przyjętym planem maia doprowadzić do pewnego celu. Nazwa algorytmu pochodzi od nazwiska matematyka arabskiego Muhammeda il>n Musy al — Chorezmi (lub al — Chwarizmi, czyli z Chorezmu), który około 820 i. n. e. opisał pozycyjny system kodowania dziesiętnego liczb i sztukę rachunku w tym systemie używanym przedtem wyłącznie w Indiach. Jego książka przetłumaczona na łacinę w XII w. zapoczątkoyyała w Europie sztukę obliczeń pisanych (t.j. piórem na papierze). Łacińska transkrypcja jego nazwiska to Aldoiismus. stąd algorytm. Zwolenników tej metody obliczeń nazywano algorytmikami. Inni posługiwali się do obliczeń kamykami (kalkulatory) lub liczydłami — abacyści (abacus — liczydło).

Co prawda pierwszy znany algorytm pochodzi od Euklidesa (między 400 a 300 p. n. e.), który wynalazł algorytm znajdowania nwd (największego wspólnego dzielnika) dwóch liczb dodatnich całkowitych. Np. nwd dla 32 i 80 jest 16.

Rodzaj wykonywanych czynności zależy od przeznaczenia algorytmu i nie może być dyskutowany w oderwaniu od tego przeznaczenia. Każdy algorytm zawiera jednak pewne składniki, które mają charakter uniwersalny, są, jak gdyby budulcem algorytmu. Sa to struktury sterujące. Sterują one przebiegiem wykonania algorytmu.

Można wyróżnić następujące struktury sterujące:

•    bezpośrednie następstwo (wykonaj A potem B)

•    wybór warunkowy (jeśli Q to wykonaj A)

•    wybór warunkowy z alternatywą czyli rozgałęzienie warunkowe (jeśli Q to wykonaj A, inaczej wykonaj B)

•    iteracje (zwroty pętlące lub po prostu pętle)

•    iteracja ograniczona (wykonaj A. dokładnie N razy)

•    iteracja nieograniczona z warunkiem wyjścia (wykonaj A aż prawdziwe stanie się Q)

•    iteracja nieograniczona z warunkiem wejścia (dopóki zachodzi Q wykonuj A)

Dzięki iteracjom możliwe jest zwięzłe zapisanie bardzo długotrwałych procesów.

Struktury iterujące mogą być zagnieżdżane. Mamy zatem pętle w pętli. Np. pętla "wykonaj A dokładnie N razy", gdzie A samo jest pętlą np. "wykonaj B aż prawdziwe stanie się Q". Wtedy procesor za każdym razem kiedy wykonuje A w pętli zewnętrznej musi wykonać pętlę wewnętrzną aż do spełnienia warunku Q. Pętla zewnętrzna jest tutaj ograniczona, zaś wewnętrzna warunkowa, ale może być różnie. Zagnieżdżenie pętli może być wielokrotne (dawniej prymitywne wersje języków np. Fortran II miały ograniczenia na liczbę zagnieżdżanych pętli, potem ograniczenie to usuwano w nowych wersjach). W pętlach mogą występować struktury następstwa wyboru itd. Nie ma granic zawiłości algorytmu.

Podprogramy i procedury. Rekurencja.

Algorytm może być złożony z jednego bloku lub z wielu oddzielnych współpracujących ze sobą modułów czyli procedur fpodprogramówl Podprogramy mogą być wykonywane wielokrotnie. Mogą także wywoływać same siebie. Taką zdolność nazywamy lekuiencia. Rekurencja jest silniejszą strukturą sterującą niż iteracja. Można dowieść, że istnieją algorytmy, które można wyrazić wyłącznie za pomocą rekurencii, choć na ogół iteracje i rekurencie można stosować zamiennie. Podobnie jak iteracje, rekurencje są sposobem odwzorowania długotrwałych procesów na krótkie algorytmy. Nazwa procedury zastępuje wiele czynności wykonywanych w jej ramach, co poprawia czytelność algorytmu.

Wśród struktur sterujących niektóre sa nieodzowne, inne dają się łatwo zastępować innymi. I tak nieodzowna jest struktura bezpośredniego następstwa. Podobnie struktura wyboru warunkowego. Wśród struktur iteracyinych najbardziej użyteczna wydaje się być iteracja nieograniczona z warunkiem yyeiścia. Może ona być wykonywana wielokrotnie, ale też nie wykonana ani razu (gdy warunek Q nie jest spełniony przy pierwszym wejściu do pętli). W odróżnienie od niej iteracja z warunkiem yyyiścia musi być wykonana choć raz, bo warunek jest sprawdzony na końcu.