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.

Przykład 1

Zapisz algorytm postawienia szeregu domów jednorodzinnych na wskazanej działce budowlanej.

Specyfikacja problemu:

Dane:
m - miejsce, na którym chcemy wybudować domki
p - plan budowy domów oraz rozlokowania ich na działce
b - podwykonawcy oraz materiały przez nich dostarczone

Wynik:
d - domy wybudowane na działce
n - liczba domów

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.

Przykład 2

Zapisz algorytm obliczania pola prostokąta.

Specyfikacja problemu:

Dane:
a - dłuższy bok prostokąta, liczba rzeczywista dodatnia
b - krótszy bok prostokąta, liczba rzeczywista dodatnia

Wynik:
p - pole prostokąta.

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.

Przykład 3

Zapisz algorytm obliczania pierwiastka kwadratowego.

Specyfikacja problemu:

Dane:
a - liczba całkowita

Wynik:
p - pierwiastek kwadratowy z liczby a

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.

Ważne!

Czasami obok danych wejściowych i wyjściowych wymienia się również dane pomocnicze, które ułatwiają implementację algorytmu.

Słownik

algorytm
algorytm

przepis postępowania prowadzący (w skończonym czasie) do rozwiązania ustalonego problemu

dane wejściowe (dane)
dane wejściowe (dane)

zbiór danych potrzebnych do rozpoczęcia pracy algorytmu; na ich podstawie oraz po wykonaniu kolejnych kroków algorytmu, otrzymywane są dane wyjściowe; definicja danych wejściowych podaje również ograniczenia dla tych danych, jeśli takie ograniczenia istnieją; dla algorytmu obliczania pola figury byłyby to liczby rzeczywiste dodatnie, oznaczające długości boków

dane wyjściowe (wynik)
dane wyjściowe (wynik)

zbiór danych będący wynikiem algorytmu; dla algorytmu obliczania pola figury byłoby to pole figury

specyfikacja problemu algorytmicznego (specyfikacja algorytmu)
specyfikacja problemu algorytmicznego (specyfikacja algorytmu)

opis problemu, który ma zostać rozwiązany wraz z danymi wejściowymi i danymi wyjściowymi