Problem obliczeniowy
Z Wikipedii
Problem obliczeniowy (lub zadanie obliczeniowe) to inaczej zadanie, które może być rozwiązane przy pomocy komputera lub innej maszyny liczącej. Na opis p.o. składają się: zbiór danych wejściowych (ang. input) oraz warunki, jakie ma spełniać wynik, czyli dane wyjściowe (ang. output). Bardziej formalnie przez p.o. możemy rozmumieć funkcję, która przekształca zbiór danych wejściowych na zbiór danych wyjściowych. Pojęcie problemu obliczeniowego leży u podstaw informatyki rozumianej jako nauki zajmującej się przetwarzaniem informacji, gdyż praktycznie każde zadanie informatyczne można rozważać jako p.o.
Metody rozwiązywania problemów obliczeniowych nazywamy algorytmami, a dziedzina nauki, która zajmuje się ich konstrukcją i badaniem to teoria algorytmów.
[edytuj] Problemy i ich instancje
Należy odróżnić problem, czyli ogólny opis pewnego zadania od jego wystąpienia (instancji), czyli p.o. wraz z konkretnymi danymi wejściowymi. Przykład: "Mając dane dwie liczby x i y znajdź ich sumę" jest problemem obliczeniowym, natomiast "oblicz 3 + 6" jest wystąpieniem tego problemu.
[edytuj] Typy problemów obliczeniowych
P.o. możemy podzielić ze względu na typ udzielanej odpowiedzi. Jeśli wymagana odpowiedź jest tak lub nie, to problem nazwiemy problemem decyzyjnym, w przeciwnym wypadku mówimy o problemach optymalizacyjnych lub problemach funkcyjnych. Ilością zasobów potrzebnych do rozwiązania p.o. zajmuje się teoria złożoności obliczeniowej.
