Specyfikacja algorytmu – dane wejściowe, wynik i warunki – oraz co znaczy, że algorytm jest poprawny i skończony.
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.
Przykładowa specyfikacja dla wyszukiwania największej liczby:
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.
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.
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.
Nie. Skończoność jest warunkiem koniecznym – zapis, który nigdy się nie kończy, nie spełnia definicji algorytmu.
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.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: