Poprawność algorytmów(1),
[ Pobierz całość w formacie PDF ]
Jerzy Pejaś: Algorytmy i struktury danych
POPRAWNO
ŚĆ
ALGORYTMÓW
Reguły dowodzenia
- 1 -
Jerzy Pejaś: Algorytmy i struktury danych
POPRAWNO
ŚĆ
ALGORYTMU
Bezbłędny program jest abstrakcyjnym pojęciem teoretycznym
(Dennie van Tassel)
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.
Błędy w sformułowaniu zadania
Często zdarza się, że po napisaniu programu użytkownik stwierdza, iż wyniki nie są takie,
jakich by sobie życzył. Może się to zdarzyć dlatego, że programista i użytkownik nie
zrozumieli się nawzajem, bądź też dlatego, że użytkownik nie wiedział tak naprawdę, czego
chce.
Niekiedy można sformułować zadanie ponownie dopiero po otrzymaniu niewłaściwych
wyników. Wadliwe sformułowanie zadania sprawia, że program poprawnie rozwiązuje nie to
zadanie, co trzeba.
Gdy pisze się program dla kogoś innego, wówczas uczucie, że zadanie jest niejasne, stanowi
ostrzeżenie, iż program może nie być tym, o który chodzi.
- 2 -
Jerzy Pejaś: Algorytmy i struktury danych
Niewłaściwy algorytm
Z chwilą, gdy zadanie jest sformułowane właściwie, projektant programu zaczyna szukać
algorytmu rozwiązania zadania. Niestety, może on wybrać algorytm niewłaściwy bądź
niedobry i będzie zmuszony wtedy do powtórzenia procesu.
Błędy analizy
Błędy analizy polegają albo na tym, że nie dostrzega się pewnych możliwości, albo na tym,
że rozwiązuje się zadanie niepoprawnie. Oto kilka ewentualności: brak nadania wartości
początkowych zmiennym, niewłaściwe zakończenie pętli, niewłaściwe indeksowanie pętli,
opuszczanie inicjalizacji pętli, zamiana dwóch lub więcej dróg po instrukcji wyboru.
Dobry projekt funkcjonalny, a następnie jego opis, np. w postaci graficznej, zapewniają w
efekcie lepszy test programu. Opis algorytmu (w postaci opisującej, graficznej lub
programowej) pozwalają zapobiec wielu błędom. Można się też nim posłużyć podczas
uruchamiania programu w celu sprawdzenia, czy wystąpiły jakieś błędy.
Błędy ogólne
W czasie programowania można popełnić pięć następujących błędów, bez względu na to, w
jakim języku się programuje:
- 3 -
Jerzy Pejaś: Algorytmy i struktury danych
(1) Błędy może spowodować niewiedza albo niezrozumienie języka lub komputera. Za przykład
niech posłuży programista stosujący instrukcję lub funkcję, która jest wykonywana inaczej
niż sądzi (tzw. błędy semantyczne), np.:
programista sądził, że po zakończeniu iteracji
for
i
:
= 1
to
N
do
X
[
i
]
:
=
i
zmienna
i
ma
wartość
N
, a nie
N
+ 1. Skutki:
program nie realizuje poprawnie algorytmu
trudne do przewidzenia i potencjalnie groźne, ale te błędy są do uniknięcia przy większej
trosce o znaczenie używanych instrukcji
(2) Błędem ogólnym jest błąd w programowaniu algorytmu. Instrukcje programu mogą być
niezgodne z ciągiem zdarzeń przewidzianych przez algorytm.
(3) Zdarzają się także błędy składniowe.
zamiast
for
i
:
= 1
to
N
do
X
[
i
]
:
=
i
;
napisano
for
i
:
= 1
do
N
do
X
[
i
]
:
=
i
;
Powstają w wyniku naruszenia składni
języka programowania, którego używamy do
zapisania algorytmu. Skutki:
zatrzymanie kompilacji lub interpretacji z komunikatem lub bez
przerwanie realizacji programu nawet jeśli kompilator błędu nie wykrył
nieprzyjemne, ale zwykle niezbyt poważne - błędy stosunkowo łatwe do poprawienia
- 4 -
Jerzy Pejaś: Algorytmy i struktury danych
(4) Instrukcje poprawne składniowo mogą powodować błędy wykonania; przykładami są:
dzielenie przez zero i pierwiastkowanie liczby ujemnej.
np. w algorytmie zliczania zdań, w których występuje słowo „algorytm” nie zauważono, że
sekwencja znaków „. ”, której użyto do wyszukiwania końca zdania, może (omyłkowo)
występować także wewnątrz zdania. Skutki:
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. dzielenia przez 0)
bardzo groźne - błędy mogą być trudne do znalezienia i pozostawać długo w ukryciu
nawet w trakcie używania programu
(5) Piąty błąd ogólny to błąd w danych, spowodowany przez nieprawidłowe dane.
algorytm dla pewnych dopuszczalnych danych wejściowych daje niepoprawny wynik lub
wykonanie programu realizującego algorytm jest przerywane lub
program realizujący algorytm nie kończy swego działania
Złożone programy wymagają:
testowania na licznych danych (zestawy testowe)
- 5 -
[ Pobierz całość w formacie PDF ]