Problem poprawności algorytmu

PROBLEM POPRAWNOŚCI ALGORYTMU

Potrzeba dowodzenia poprawności algorytmu wynika stąd, iż żaden test programu (eksperymentalne badanie poprawności) nie może zagwarantować jego poprawności.

Rozróżniamy poprawność częściowa i całkowita:

Poprawność częściowa

gdy po uruchomieniu z poprawnymi danymi algorytm jeśli zakończy pracę to dostarczy wyników — wówczas wyniki zawsze poprawne. Przy poprawności częściowej algorytm może zatrzymać się przed końcem nie dostarczając rozwiązania.

Poprawność całkowita

gdy dla poprawnych danych algorytm zawsze dojdzie do końca dostarczając wyników, oczywiście poprawnych

Uwagi:

1.    Skąd innąd i tak nieliczne techniki badania poprawności algorytmów pozwalają ustalić jedynie poprawność częściową. Dovyód poprawności całkowitej jest możliwy jedynie w pojedynczych przypadkach niektórych prostych i zwykle mało użytecznych praktycznie algorytmów.

2.    Dowodzenie poprawności algorytmów nie może być zrealizowana algorytmicznie. Niemożliwe jest zbudowanie superalgorytmu weryfikującego inne algorytmy.

3.    Algorytm nie jest nigdy poprawny absolutnie. Może o być poprawny względem konkretnego zadania algorytmicznego.

4.    Przy tworzeniu prawdziwych zaawansowanych systemów informatycznych niezwykle rzadko stosuje się jakiekolwiek formalne techniki dowodzenia ich poprawności. Zwykle testuje sie ie empirycznie.