Lekcja 13: Sprawdzanie poprawnosci algorytmow dla przykladowych danych

Dlaczego sprawdzamy poprawnosc algorytmow?

Napisanie algorytmu to dopiero polowa sukcesu. Musimy upewnic sie, ze dziala on poprawnie dla wszystkich dopuszczalnych danych wejsciowych. Bledny algorytm moze dawac pozornie dobre wyniki dla niektorych danych, ale zawiesc w innych przypadkach. W profesjonalnym programowaniu bledy w algorytmach moga prowadzic do powaznyz konsekwencji - od strat finansowych po zagrozenie ludzkiego zycia (np. w systemach sterowania samolotami lub urzadzeniach medycznych).

Weryfikacja algorytmow jest kluczowa umiejetnoscia kazdego programisty. Istnieja rozne metody sprawdzania poprawnosci - od recznego sledzenia krokowego, przez testowanie na przykladowych danych, az po formalne dowody matematyczne. Na naszym poziomie skupimy sie na praktycznych metodach testowania, ktore pozwola nam skutecznie wykrywac bledy w algorytmach.

Metody sprawdzania poprawnosci

1. Sledzenie krokowe (trace) - reczne wykonanie algorytmu krok po kroku, notujac wartosci wszystkich zmiennych po kazdej operacji. To podstawowa metoda weryfikacji.
2. Testowanie na przykladowych danych - uruchomienie algorytmu dla wybranych danych i porownanie wynikow z oczekiwanymi wartosciami.
3. Testowanie przypadkow brzegowych - sprawdzenie algorytmu dla danych ekstremalnych, granicznych i nietypowych.
4. Analiza logiczna - rozumowanie dlaczego algorytm musi dac poprawny wynik w kazdym przypadku.

Przypadki brzegowe (edge cases)

Przypadki brzegowe to dane wejsciowe, ktore sa w jakis sposob specjalne lub ekstremalne. To wlasnie dla takich danych algorytmy najczesciej zawieraja bledy. Dobry programista zawsze testuje swoj algorytm na przypadkach brzegowych:

• Pusta tablica lub tablica jednoelementowa (przy sortowaniu i wyszukiwaniu)
• Liczba 0, 1, 2 (przy badaniu pierwszosci, silni, Fibonacciego)
• Dwie identyczne liczby (przy obliczaniu NWD)
• Liczby ujemne (czy algorytm poprawnie je obsluguje?)
• Dane juz posortowane lub posortowane odwrotnie (przy sortowaniu)
• Tablica z powtorzeniami (czy stabilnosc sortowania jest zachowana?)
• Bardzo duze liczby (czy nie nastapi przepelnienie?)

Tabela sledzenia (trace table)

Tabela sledzenia to systematyczne narzedzie do recznego przesledzenia algorytmu. Tworzymy tabele z kolumnami dla kazdej zmiennej i wpisujemy ich wartosci po kazdym kroku algorytmu:

Przyklad: Sledzenie algorytmu silni dla n=4

ALGORYTM Silnia(n):        | Krok | i | wynik
  wynik = 1                |------|---|-------
  DLA i OD 1 DO n:        |  0   | - |   1
    wynik = wynik * i      |  1   | 1 |   1
  ZWROC wynik              |  2   | 2 |   2
                            |  3   | 3 |   6
                            |  4   | 4 |  24
                            | Wynik: 24 (4! = 24, OK)

Strategia testowania algorytmow

Aby skutecznie testowac algorytmy, nalezy przygotowac zestaw przypadkow testowych pokrywajacy rozne kategorie danych. Kazdy test powinien zawierac: dane wejsciowe, oczekiwany wynik i typ testu. Dobrze zaprojektowany zestaw testow powinien obejmowac cztery kategorie:

1. Test typowy - dane "normalne", latwe do recznej weryfikacji
2. Test brzegowy - przypadki specjalne (minimalne i maksymalne wartosci)
3. Test negatywny - dane niepoprawne (czy algorytm je poprawnie odrzuci?)
4. Test wydajnosciowy - duze dane (czy algorytm zakonczy sie w rozsadnym czasie?)

Przyklad: Testowanie algorytmu badania pierwszosci

ALGORYTM CzyPierwsza(n):
  JESLI n <= 1 ZWROC "NIE"
  JESLI n = 2 ZWROC "TAK"
  JESLI n MOD 2 = 0 ZWROC "NIE"
  DLA i OD 3 DO sqrt(n), KROK 2:
    JESLI n MOD i = 0 ZWROC "NIE"
  ZWROC "TAK"

Zestaw testow:
| Dane  | Oczekiwany | Typ testu     |
|-------|------------|---------------|
| n=0   | NIE        | brzegowy      |
| n=1   | NIE        | brzegowy      |
| n=2   | TAK        | brzegowy      |
| n=7   | TAK        | typowy        |
| n=25  | NIE        | typowy (5*5)  |
| n=97  | TAK        | duza pierwsza |
| n=-5  | NIE        | negatywny     |