mfranczak.pl

Poprawność i skończoność algorytmów

Najważniejsze własności algorytmów:
– poprawność
– skończoność
– złożoność
– efektywność

———————————————————————————————
POPRAWNOŚĆ , SKOŃCZONOŚĆ
———————————————————————————————

Poprawność algorytmu

Algorytm jest poprawny jeżeli rozwiązuje problem zgodnie ze specyfikacją problemu (zadania) czyli jeśli dla poprawnych danych daje poprawne wyniki

Dowód poprawności algorytmu jest rozumowaniem matematycznym prowadzącym do formalnego wykazania, że dany algorytm przy poprawnych danych wejściowych da nam wynik spełniający wymagania, np. że algorytm quicksort po podaniu mu niepustej tablicy elementów porównywalnych na wyjściu da nam tablicę zawierającą te same elementy, ale uporządkowane w kolejności od najmniejszego do największego.

Dowód poprawności algorytmu zawsze składa się z dwóch części:

• dowód, że jeśli algorytm się zakończy, to da poprawny wynik,
• dowód, że przy poprawnych danych wejściowych algorytm zawsze się zakończy.

Algorytm:

– całkowicie poprawny -> dla wszystkich danych wejściowych spełniających warunki początkowe wyprowadzi wyniki spełniające warunki końcowe i zakończy swoje działanie.
– częściowo poprawny -> jeśli dla obliczeń które się zakończą ich warunki są poprawne względem warunków początkowych i końcowych (nie jest konieczne wykazanie ze obliczenia kończą się na wszystkich poprawnych danych, że może być ich nieskończenie wiele.
– dobrze określony -> występująca w nim polecenia i operacje są zrozumiałe dla użytkownika a kolejność ich wykonywania jest jednoznacznie określona
– uniwersalny -> wiąże się z problemem jaki ten algorytm rozwiązuje i chodzi o te aby ten algorytm umożliwiał rozwiązanie wszystkich zadań zgodnych ze specyfikacją problemu, a różniących się jedynie danymi początkowymi.

Błędy w programach:
– składniowe
– logiczne

Skończoność algorytmów

Algorytm jest skończony, jeżeli gwarantuje wyznaczenie wyniku w skończonej liczbie kroków.

ALGORYTM KTÓRY NIE JEST SKOŃCZONY NIE MOŻE ZOSTAĆ UZNANY ZA POPRAWNY.