ALGORYTMY

Algorytm jest ściśle zdefiniowaną procedurą obliczeniową, która dla właściwych danych wejściowych produkuje żądane wyniki, zgodnie z warunkami zdefiniowanymi przez problem obliczeniowy.

Algorytm to przepis w postaci ściśle określonych reguł na rozwiązanie określonego zadania w skończonej licznie kroków.

Algorytm jest przepisem opisującym krok po kroku rozwiązanie jakiegoś problemu. 

Słowo algorytm pochodzi od brzmienia fragmentu nazwiska arabskiego matematyka żyjącego na przełomie VIII i IX wieku - Muhammad ibn Musa al.-Chorezmi. Za prekursora algorytmów komputerowych jest uznawana Ada August (1815-1852), córka Byrona. Po raz pierwszy tego terminu użył Dawid Harel w tytule swojej książki Rzecz o istocie informatyki - algorytmika. Najstarszy algorytm, który jest opisywany, algorytm Euklidesa, ma ponad 2000 lat.

Większość problemów z którymi spotykamy się w świecie komputerów wymaga zwrócenia uwagi na istotne cechy: algorytm musi być poprawny (zawsze daje poprawne wyniki), skończony (daje jakieś rozwiązanie), wykonalny i efektywny, tzn. musi dawać rozwiązanie w „rozsądnym” czasie. Mimo ogromnej i rosnącej wciąż mocy i szybkości komputerów są problemy których rozwiązanie jest zupełnie niewykonalne.

Przyjrzyjmy się następującemu problemowi: Zaplanowano spotkanie premiera z mieszkańcami wszystkich województw, jedno spotkanie w województwie. Przypuśćmy, że nie dysponujemy żadnym algorytmem i jedyne rozwiązanie jakie przychodzi nam do głowy to przejrzenie wszystkich możliwych ustawień województw po kolei. Jeśli mamy n województw to istnieje (n-1)! rozwiązań, gdyż poza stolicą, z której wyrusza jest tyle ustawień tras. Przypuśćmy, że dysponujemy superkomputerem, który wykonuje 100 miliardów operacji na sekundę - 10¹¹. Jak długo będzie trwało wyszukanie optymalnej drogi. Przy 49 województwach - 4*10⁴²lat !!!, przy 25 województwach - 2*10⁵ lat, a przy 17 - 3,5 minuty. Bez znalezienia jakiegoś innego rozwiązania (algorytmu) jest to więc zadanie prawie niemożliwe do zrealizowania. Oczywiście takie algorytmy istnieją!

Lista kroków jest częściej stosowanym sposobem opisu algorytmu. Poszczególne kroki zawierają opis operacji, które mają być wykonane. Graficznym sposobem opisu algorytmu jest schemat blokowy. Składa się z klatek i połączeń między nimi. w klatkach są zapisane operacje, a połączenia pokazują kolejność ich wykonania. Jest jednym z najpopularniejszych sposobów przedstawiania algorytmów, za pomocą układu umownych symboli.

    blok rozpoczęcia działania algorytmu

   blok wprowadzania i wyprowadzania danych
z reguły przypisanie do zmiennych

    blok podstawowy
blok zawierający operacje na danych, w wyniku których ulegają one zmianie

Blok wprowadzania danych i blok podstawowy są w różnych źródłach traktowane z reguły podobnie i dlatego na użytek tego opracowania będziemy stosować głównie blok podstawowy (prostokąt)

   blok warunkowy
na podstawie warunku sprawdzanego w tym bloku wybierana jest jedna z dwóch dróg działania algorytmu. Jedna jest wybierana, gdy warunek jest spełniony, a druga, gdy nie spełniony.

   blok zakończenia działania algorytmu

Gdyby na przykład chcieć opisać algorytm rozwiązywania równania kwadratowego wyglądał by on w następujący sposób:

Wiele problemów komputerowych można rozwiązać wykonując wielokrotnie te same operacje. Istnieją dwa podejścia do rozwiązywania takich problemów: iteracja i rekurencja.

Iteracja to wielokrotne wykonywanie ciągu instrukcji, które w kodzie programu zapisane są tylko jeden raz. Iteracja składa się z trzech elementów: bloku powtarzanych instrukcji, zmiennej sterującej, warunku iteracji, w którym następuje porównanie zmiennej sterującej. Rekurencja składa się z podania warunków brzegowych, kończących rekurencję i równania wyrażającego wartość ogólną za pomocą wartości wcześniejszych. W matematyce podobne znaczenie ma indukcja (wartość elementu zależy od wartości elementu poprzedniego).