Specyfikacja i poprawność algorytmu
Specyfikacja algorytmu – dane wejściowe, wynik i warunki – oraz co znaczy, że algorytm jest poprawny i skończony.
Opis
Specyfikacja to precyzyjny opis zadania, które algorytm ma wykonać – zanim jeszcze powstanie choć jedna linia kodu. Składa się z dwóch części.
Dane wejściowe: co algorytm dostaje, jakiego są typu i jakie warunki spełniają. Nie wystarczy napisać „liczba" – trzeba określić, czy jest całkowita, czy dodatnia, w jakim zakresie. Wynik: co algorytm ma zwrócić i w jakiej postaci.
Osobno mówi się o własnościach dobrego algorytmu. Musi być skończony, czyli kończyć się dla każdych poprawnych danych wejściowych. Musi być jednoznaczny – każdy krok da się wykonać tylko w jeden sposób. Musi być poprawny, czyli dawać właściwy wynik dla wszystkich dopuszczalnych danych. I powinien być efektywny.
Kluczowe jest słowo „wszystkich". Algorytm działający dla większości przypadków, ale zawodzący dla pustego zbioru albo liczby zero, nie jest poprawny.
Jak to działa
Przykładowa specyfikacja dla wyszukiwania największej liczby:
- Dane wejściowe: niepusty ciąg liczb całkowitych o długości n, gdzie n jest większe od zera
- Wynik: największa liczba występująca w tym ciągu
Zwróć uwagę na warunek „niepusty". Bez niego algorytm nie miałby czego zwrócić – i to jest właśnie przypadek brzegowy, o którym najczęściej się zapomina.
Przy sprawdzaniu poprawności warto przetestować: zbiór jednoelementowy, wartości równe, wartości ujemne i największą wartość na pierwszej oraz ostatniej pozycji.
Na maturze
Specyfikacja bywa osobno punktowanym podpunktem – zadanie prosi o jej podanie przed napisaniem algorytmu. Punkt traci się najczęściej za pominięcie warunków, które dane muszą spełniać.
Drugi typ pytania dotyczy własności algorytmu: trzeba wymienić skończoność, jednoznaczność i poprawność, ewentualnie uzasadnić, dlaczego dany zapis nie jest algorytmem.
Zapamiętaj
- Specyfikacja opisuje dane wejściowe i oczekiwany wynik, zanim powstanie kod.
- Przy danych trzeba podać nie tylko typ, ale i warunki, jakie spełniają.
- Algorytm musi być skończony, jednoznaczny i poprawny dla wszystkich poprawnych danych.
- Przypadki brzegowe – zbiór pusty, jednoelementowy, wartości równe – testuje się zawsze.
Najczęściej zadawane pytania
Po co pisać specyfikację, skoro wiem, co robić?
Bo wymusza rozstrzygnięcie przypadków granicznych, zanim zaczniesz kodować. Większość błędów bierze się właśnie z niedookreślonego zadania, a nie z pomyłki w składni.
Czy pętla nieskończona to algorytm?
Nie. Skończoność jest warunkiem koniecznym – zapis, który nigdy się nie kończy, nie spełnia definicji algorytmu.
Czym różni się poprawność od efektywności?
Poprawność mówi, że wynik jest właściwy. Efektywność mówi, jakim kosztem czasu i pamięci został osiągnięty. Algorytm poprawny może być bardzo wolny.
Przećwicz w zadaniach maturalnych
Do tego hasła nie mamy jeszcze przypisanych pojedynczych zadań. Cały spis zadań maturalnych z tego działu jest tutaj:
Powiązane zagadnienia
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: