Właściwości
algorytmów

Właściwości algorytmów

Raz opracowany algorytm dla danego problemu może służyć do rozwiązywania wszystkich problemów tej samej klasy, dla której był opracowany, różniących się jedynie doborem konkretnych danych wejściowych. Przed opracowaniem algorytmu powinniśmy sprawdzić, czy dany problem jest rozwiązywalny, a jeśli tak, to czy rozwiązanie to jest jednoznaczne. Algorytm powinien uwzględniać wszystkie możliwe teoretycznie warianty przebiegu obliczeń zaistniałe z powodu różnego doboru danych wejściowych.

Cechy algorytmu:

• wykonalność – polecenia zawarte w algorytmie sąwykonywalne, tzn. dostępne, a pisząc algorytm wystarczy się nimi tylko posłużyć.
• posiadanie wejścia i wyjścia – wejście oznacza zwykle pewne dane pobierane przez algorytm w celu ich przetworzenia, wyjście odnosi się do wyniku działania algorytmu.
• skończoność– algorytm powinien zakończyć swoje działanie po skończonej liczbie kroków.
• określoność - każda operacja w algorytmie powinna byćsformułowana tak, aby zapewnić jej jednoznacznąinterpretację.

Algorytm jest poprawny, jeśli dla każdego dowolnego zestawu danych wejściowych zgodnych ze specyfikacją spełnia następujące warunki:

• jest skończony
• wyprowadza wyniki zgodne z warunkami zawartymi w specyfikacji
• jest dobrze określony
• jest uniwersalny

O całkowitej poprawności mówimy wtedy, gdy algorytm jest poprawny dla wszystkich danych wejściowych zgodnych ze specyfikacją.

Algorytm jest częściowo poprawny, gdy po jego zakończeniu uzyskujemy dla poprawnych danych poprawne wyniki. W tym przypadku nie sprawdzamy, czy dana metoda jest skończona dla wszystkich danych wejściowych spełniających warunki specyfikacji.

Algorytm jest skończony, jeśli dla dowolnych danych wejściowych spełniających warunkami specyfikacji generuje wyniki w skończonej liczbie kroków.

Algorytm jest uniwersalny, jeżeli działa dla dowolnych danych spełniających warunki specyfikacji.

Algorytm jest optymalny, jeżeli rozwiązuje określony problem w najkrótszym czasie, czyli przez wykonanie najmniejszej liczby operacji. Jeżeli algorytm rozwiązuje problem w sposób optymalny, to nie istnieje lepsza metoda rozwiązująca postawiony problem.