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 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 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 i 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]

P.o. możemy podzielić ze względu na typ udzielanej odpowiedzi:

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