Poprawność algorytmów
Jeśli uważasz, że jakiś program komputerowy jest
bezbłędny, to się mylisz
- po prostu nie zauważyłeś
jeszcze skutków błędu, który jest w nim zawarty.
M.Rawski Wstęp do Informatyki
Jakie błędy można popełnić?
Z' Błędy językowe
:
Z' np. zamiast for i = 1 to N do X[i] := i ;
:
Z' napisano for i = 1 do N do X[i] := i ;
Z' Powstają w wyniku naruszenia składni języka (programowania),
którego używamy do zapisania algorytmu.
Z' Możliwe skutki i znaczenie:
Ę% zatrzymanie kompilacji lub interpretacji z komunikatem lub bez,
Ę% przerwanie realizacji programu nawet jeśli kompilator błędu nie
wykrył,
Ę% błędy nieprzyjemne, ale zwykle niezbyt poważne - są względnie
łatwe do poprawienia.
M.Rawski Wstęp do Informatyki
Jakie błędy można popełnić?
Z' Błędy semantyczne
Z' np. sądziliśmy, że po zakończeniu iteracji
:
for i = 1 to N do X[i] := i
zmienna i ma wartość N, a nie N + 1
Z' Wynikają z niezrozumienia semantyki używanego języka
programowania.
Z' Możliwe skutki i znaczenie:
Ę% program nie realizuje poprawnie algorytmu,
Ę% błędy trudne do przewidzenia i potencjalnie groz
ne, ale są do
uniknięcia przy większej wiedzy i starannym sprawdzaniu
znaczenia używanych instrukcji.
M.Rawski Wstęp do Informatyki
Jakie błędy można popełnić?
Z' Błędy logiczne
Z' np. w algorytmie zliczania zdań, w których występuje słowo
 algorytm nie zauważyliśmy, że sekwencja znaków  .  może
występować także wewnątrz zdania ( Na rys. 2 pokazano
schemat... ), a używaliśmy jej do wyszukiwania jego końca.
Z' Możliwe skutki i znaczenie:
Ę% algorytm przestaje być poprawnym rozwiązaniem zadania
algorytmicznego,
Ę% dla pewnych zestawów danych wejściowych algorytm podaje wyniki
niezgodne z oczekiwanymi,
Ę% procesor może nie być w stanie wykonać pewnych instrukcji (np. żądamy
dzielenia przez 0),
Ę% błędy bardzo groz
ne - mogą być trudne do znalezienia i pozostawać
długo w ukryciu nawet w trakcie używania programu w postaci kodu.
M.Rawski Wstęp do Informatyki
Jakie błędy można popełnić?
Z' Błędy algorytmiczne
Z' wynikają z wadliwie skonstruowanych struktur sterujących np.
niewłaściwych zakresów iteracji, niewłaściwych warunków użytych do
zatrzymywania iteracji warunkowych lub przeniesienia sterowania w
niewłaściwe miejsce procesu w wyniku zastosowania wyboru
warunkowego (lub instrukcji skoku).
Z' Możliwe skutki i znaczenie:
Ę% algorytm dla pewnych dopuszczalnych danych wejściowych daje
niepoprawny wynik,
Ę% wykonanie programu realizującego algorytm jest przerywane w
trybie awaryjnym,
Ę% program realizujący algorytm nie kończy w normalnym trybie
swego działania.
M.Rawski Wstęp do Informatyki
Co to oznacza?
Rozmaitość z
ródeł błędów różnych typów
Złożone programy wymagają:
" testowania na licznych danych (zestawy testowe)
" uruchamiania (badanie wyników końcowych i pośrednich)
DEBUGGING - odpluskwianie
M.Rawski Wstęp do Informatyki
 Przykład błędu algorytmicznego
start
Z' Algorytm sumowania
S 0;
�! zarobków pracowników, którzy
ITERACJA
I 1
�!
ZEWN
TRZNA zarabiają więcej niż ich
ITERACJA
bezpośredni przełożeni:
J 1
�!
WEWN
TRZNA
Z' N jest zmienną o wartości
Czy J jest
równej liczbie pracowników,
TAK
bezpośrednim
kierownikiem
Z' zmienne (indeksowe) I i J
I?
wskazują pracowników
NIE
NIE
Czy
P(I) > P(J)?
(kolejne elementy tablicy
NIE
Czy
J J + 1
�!
jednowymiarowej P(X), która
J = N ?
TAK
zawiera płace pracowników), a
TAK S S + P(I)
�!
zmienna S zawiera sumę
zarobków;
Czy
TAK NIE
I I + 1
�!
I = N ?
Wypisz wartość S
stop
M.Rawski Wstęp do Informatyki
 Przykład błędu algorytmicznego
Z' Pętla nieskończona:
Na tym etapie
działania
algorytmu
X = 3,1415
TAK
Czy X = 100?
NIE
stop
X X + 1
�!
M.Rawski Wstęp do Informatyki
 Algorytmy poprawne częściowo i całkowicie
(ścisła definicja)
Dowolne Dowolne
dopuszczalne dopuszczalne
dane dane
ALGORYTM ALGORYTM
częściowo całkowicie
poprawny poprawny
Prawdziwa jest
implikacja:
Prawdziwe jest
? !
jeśli to miejsce
stwierdzenie:
osiągnięto,
to miejsce
Poprawny to wynik Poprawny
osiągnięto i wynik
wynik jest poprawny wynik
jest poprawny
M.Rawski Wstęp do Informatyki
Metoda niezmienników i zbieżników
Z' Częściowej poprawności algorytmu można dowodzić poprzez:
" wybranie punktów kontrolnych
" związanie z każdym punktem asercji (funkcji logicznej reprezentującej
przypuszczenie)
" ustalenie niezmienników w obrębie iteracji
" dowiedzenie, że z prawdziwość jednej asercji wynika prawdziwość
następnej, że niezmiennik pozostaje prawdziwy w kolejnych iteracjach i
pociąga za sobą prawdziwość ostatniej asercji.
Z' Całkowitej poprawności algorytmu można dowodzić poprzez:
" dodatkowe ustalenie zbieżnika (wielkości zależnej od zmiennych i danych,
która jest zbieżna)
" dowiedzenie, że po skończonej liczbie iteracji algorytm się zatrzyma w
ostatnim punkcie kontrolnym.
M.Rawski Wstęp do Informatyki
Przykład zastosowania metody
Z' Algorytm odwracający dowolny napis (procedura odwrócone):
X' odwrócone( alama2koty ) =  ytok2amala
Z' - pomocnicze funkcje:
X' głowa( alama2koty ) =  a
i
X' ogon( alama2koty ) =  lama2koty
Z' - operator konkatenacji (złożenia napisów):
X'  alama &  2koty =  alama2koty
Z' czyli dla dowolnego napisu T zachodzi:
X' głowa(T) & ogon(T) = T
M.Rawski Wstęp do Informatyki
Przykład zastosowania metody
start
start
Asercja 1:
T jest napisem
X T
�!
X T
�!
Y �!  
Y �!  
Z' przydział asercji
Asercja 2:
T = odwrócone(Y) & X
TAK
TAK
Czy X =   ?
Czy X =   ?
Asercja 3:
Y = odwrócone(T)
NIE
NIE
stop
stop
Y głowa(X) & Y
�!
Y głowa(X) & Y
�!
X ogon(X )
�!
X ogon(X )
�!
M.Rawski Wstęp do Informatyki
Przykład zastosowania metody cd
Z' Aby wykazać częściową poprawność
start
algorytmu należy udowodnić:
Asercja 1:
T jest napisem
1. Jeśli asercja 1 jest prawdziwa, to 2 też
X T
�!
Y �!  
jest prawdziwa (przed rozpoczęciem
Asercja 2:
iteracji)
T = odwrócone(Y) & X
TAK
Czy X =   ?
2. Jeśli w pewnym kroku iteracji asercja 2 Asercja 3:
Y = odwrócone(T)
jest prawdziwa, to w następnym kroku
NIE
też jest ona prawdziwa (warunek z
stop
Y głowa(X) & Y
�!
asercji 2 jest niezmiennikiem iteracji)
X ogon(X )
�!
3. Jeśli w ostatnim kroku iteracji asercja 2
jest prawdziwa, to 3 jest też prawdziwa
M.Rawski Wstęp do Informatyki
Przykład zastosowania metody cd
Z' Ad 1.: oczywiście zachodzi równość odwrócone(  ) & T = T
Z' Ad 2.: trzeba sprawdzić czy
odwrócone(Y) & X = odwrócone(głowa(X) & Y) & ogon(X)
dla każdego Y i X `"  
Y: AMALA X: 2KOTY
odwrócone(Y) & X: ALAMA 2KOTY
odwrócone(głowa(X) & Y) & ogon(X): ALAMA2 KOTY
głowa(X) & Y: 2AMALA ogon(X): KOTY
głowa(X): 2 Y: AMALA
Z' Ad 3.: oczywiście zachodzi równość
odwrócone(odwrócone(Y) &   ) = Y
M.Rawski Wstęp do Informatyki
Przykład zastosowania metody cd
Z' Aby wykazać całkowitą poprawność algorytmu należy jeszcze
dodatkowo udowodnić,
Z' że dla każdego napisu T punkt kontrolny 2 jest przechodzony tylko
skończoną liczbę razy tzn. 3 punkt kontrolny jest zawsze osiągany.
" długość napisu X jest zbieżnikiem, który może być w tym
celu wykorzystany - w każdej iteracji długość X maleje o
jeden znak i nie może stać się mniejsza od 0!
M.Rawski Wstęp do Informatyki
Problem z 1852 r.:
Z' Rozwiązanie z 1976 r.:
Z' Twierdzenie:
Z' Cztery barwy wystarczą do pokolorowania
dowolnej płaskiej mapy, tak aby każdy z dwóch
sąsiadujących obszarów różnił się kolorem.
Z' Dowód
Z' Algorytmiczne rozwiązanie bardzo wielu
podprzypadków szczególnych, które wyczerpują
wszystkie możliwości.
Z' Nikt formalnie nie dowodził poprawności
tych algorytmów!
M.Rawski Wstęp do Informatyki
Co z rekurencją ?
Z' Metoda niezmienników i zbieżników może być zastosowana
także dla dowodzenia poprawności algorytmów rekurencyjnych
Z' Ale łatwiej jest skorzystać z tej metody po usunięciu rekurencji i zastąpieniu
jej iteracją.
Z' procedura przenieś N z X na Y używając Z;
(1) jeśli N = 1, to wypisz  X Y ;
(2) w przeciwnym razie (tj. jeśli N > 1) wykonaj co następuje:
(2.1) wywołaj przenieś N - 1 z X na Z używając Y;
(2.2) wypisz  X Y ;
(2.3) wywołaj przenieś N -1 z Z na Y używając X;
(3) wróć do poziomu wywołania
M.Rawski Wstęp do Informatyki
Wieże Hanoi (raz jeszcze)
Z' Algorytm iteracyjny równoważny algorytmowi rekurencyjnemu!
Z' Ustaw trzy kołki w kółko.
1. powtarzaj co następuje, aż do uzyskania po kroku 1.1 rozwiązania
problemu:
1.1. przenieś najmniejszy z dostępnych krążków z kołka, na
którym się znajduje, na kołek następny w kierunku ruchu
wskazówek zegara,
1.2. wykonaj jedyne możliwe przeniesienie nie zmieniające
położenia najmniejszego krążka, który został przeniesiony
w kroku 1.1.
M.Rawski Wstęp do Informatyki
Wieże Hanoi (raz jeszcze)
A A A A
1.2. 3. 4.
C B C B C B C B
(1.1) (1.2) (1.1)
A B A C B C
A A A A
5. 6. 7. 8.
C B C B C B C B
(1.2) (1.1) (1.2) (1.1)
A B C A C B A B
M.Rawski Wstęp do Informatyki