Specyfikacja problemu algorytmicznego

Każdy, nawet najprostszy algorytmalgorytmalgorytm, ma swoją specyfikacjęspecyfikacja problemu algorytmicznego (specyfikacja algorytmu)specyfikację i rozwiązuje pewien problem. Każdy problem musi być jasno określony. Przykładowym rozwiązaniem może być obliczenie pierwiastka kwadratowego lub posortowanie listy jednowymiarowej. Problemy te mogą być ogólne, jak podane wcześniej, lub dużo bardziej specyficzne, jak choćby posortowanie listy jednowymiarowej, składającej się z liczb całkowitych dodatnich z przedziału od zera do pięciu tysięcy.

Dla każdego problemu musimy również wyznaczyć dane wejściowedane wejściowe (dane)dane wejściowe oraz wyjściowedane wyjściowe (wynik)wyjściowe. Należy to zrobić w formalny sposób.

Najpierw jednak zastanówmy się nad tym, czy można przenieść te pojęcia do życia codziennego.

Przykłady specyfikacji algorytmu

Załóżmy, że jesteśmy inwestorami, którzy chcą postawić kilka domów. Problemem jest więc postawienie szeregu domów jednorodzinnych na danej działce budowlanej. W tym momencie, zależnie od poszczególnych kroków algorytmu, potrzebowalibyśmy zapewne co najmniej kilku informacji wejściowych.

Po pierwsze, musimy do algorytmu dostarczyć samą działkę budowlaną. Następnie powinniśmy dostarczyć projekt domków, będący osobnym algorytmem, który z kolei dla formy algorytmu nie ma znaczenia. Gdy już mamy projekt, musimy sobie zapewnić łańcuch dostaw materiałów budowlanych oraz podwykonawców – dla uproszczenia załóżmy, że wykonawca dostarczy wszystkie niezbędne materiały.

Wynikiem algorytmu będzie postawienie szeregu domów jednorodzinnych na wskazanej przez nas działce. Spróbujmy zapisać to w sposób formalny.

Specyfikacja algorytmu jest bardzo uproszczona. Jednak wymienione przez nas elementy w danych wejściowych i wyjściowych są z pewnością konieczne.

Do samej specyfikacji problemu algorytmicznego nie musimy dostarczać kompletnej listy kroków – bardzo często to właśnie my, jako informatycy, taką listę kroków musimy sporządzić. Warto tutaj dodać, że jednym z typów zadań maturalnych jest zadanie, w którym do podanej specyfikacji algorytmu należy przygotować listę kroków.

Algorytm na obliczanie pola prostokąta jest jednym z najbardziej podstawowych.  Sprecyzowaliśmy, że a oraz b jako dane wejściowe muszą spełniać pewne warunki, w tym przypadku muszą być liczbami rzeczywistymi dodatnimi. Dodanie tej informacji może wydawać się zbędne, jednak określamy w ten sposób, że tylko takie dwie liczby a i b uznajemy za poprawne dane wejściowe.

Oczywiście możemy uwzględnić w algorytmie sytuację, w której ktoś podałby inne dane i wtedy moglibyśmy również inaczej sformułować specyfikację algorytmu.

Pamiętajmy, że dla niepoprawnych danych wejściowych wynik działania algorytmu może nie być poprawny.

W powyższym przykładzie mamy dane wejściowe, co do których można mieć wątpliwości. Zapis liczba całkowita nie implikuje, że liczba ma być dodatnia.
Dlatego uzasadnione jest pytanie, czy algorytm w tej postaci zwróci poprawny wynik dla pierwiastka z liczby ujemnej.

Jednakże, z punktu widzenia formalnego, nie mamy podstaw do wątpliwości, ponieważ możemy obliczyć pierwiastek z liczby ujemnej (z użyciem liczb urojonych). Dlatego też algorytm z taką specyfikacją może istnieć i zwracać poprawne wyniki.

Słownik