Problem obliczeniowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej. Na opis problemu obliczeniowego 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 problem obliczeniowy możemy rozumieć 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 problem obliczeniowy.

Metody rozwiązywania problemów obliczeniowych nazywamy algorytmami, a dziedzina nauki, która zajmuje się ich konstrukcją i badaniem, to teoria algorytmów.

Problemy, a ich instancje[edytuj | edytuj kod]

Należy odróżnić problem, czyli ogólny opis pewnego zadania, od jego wystąpienia (instancji), czyli problem obliczeniowy 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.

Typy problemów obliczeniowych[edytuj | edytuj kod]

Problemy obliczeniowe można podzielić, ze względu na typ udzielanej odpowiedzi, następująco:

Ilością zasobów potrzebnych do rozwiązania problemów obliczeniowych zajmuje się teoria złożoności obliczeniowej.