Algorytm

Algorytm opisuje sposób przekształcania danych wejściowych w dane wyjściowe zgodnie z wyznaczonym celem. Jest to instrukcja rozwiązania danego problemu.

Cechy algorytmu:
• poprawność - algorytm przynosi oczekiwane wyniki
• jednoznaczność - przy tych samych danych wejściowych otrzymuje się zawsze te same wyniki
• skończoność - algorytm wykonuje się w skończonej liczbie kroków
• efektywność - rozwiązanie zadania następuje w jak najmniejszej liczbie kroków

Algorytm optymalny to taki, który dla rozwiązania danego problemu jest bezwzględnie najlepszy.

Metody zapisu algorytmów

• opis słowny
• lista kroków
• schemat blokowy
• drzewo algorytmiczne
• pseudokod
• język algorytmiczny

Schematy blokowe algorytmów

W algorytmach sekwencyjnych kolejne kroki są wykonywane zawsze w tej samej kolejności. Żaden krok nie może zostać pominięty ani powtórzony.

Przed każdym algorytmem powinna zostać umieszczona specyfikacja problemu algorytmicznego zawierająca:
• problem algorytmiczny
• dane wejściowe
• dane wyjściowe

Sposoby konstruowania algorytmów

"dziel i zwyciężaj" - problem jest dzielony na kilka mniejszych problemów, które znów są dzielone na mniejsze - aż do momentu, kiedy otrzymamy problemy łatwe do rozwiązania.

Programowanie dynamiczne - problem jest dzielony na kilka mniejszych problemów, ale w odróżnieniu od "dziel i zwyciężaj" podproblemy w programowaniu dynamicznym nie są rozłączne.

Metoda zachłanna - algorytm w każdym kroku dokonuje zachłannego, tj. najlepiej rokującego w danym momencie wyboru rozwiązania częściowego. Algorytm dokonuje decyzji lokalnie optymalnej.

Poszukiwanie i wyliczanie - zbiór danych jest przeszukiwany aż do znalezienia rozwiązania.

Algorytm heurystyczny – algorytm niedający gwarancji znalezienia rozwiązania optymalnego, umożliwiający jednak znalezienie rozwiązania dość dobrego w rozsądnym czasie.

Złożoność obliczeniowa algorytmu

Złożoność obliczeniowa algorytmu pozwala określić ilość zasobów komputerowych niezbędnych do wykonania czynności opisanych w algorytmie w zależności od rozmiaru danych wejściowych.