Problem obliczeniowy
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
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
Problemy obliczeniowe można podzielić, ze względu na typ udzielanej odpowiedzi, następująco:
- Problemy decyzyjne wymagają udzielenia odpowiedzi tak lub nie.
- Problemy optymalizacyjne wymagają znalezienia rozwiązania optymalnego.
- Problemy przeszukiwania wymagają znalezienia jakiegokolwiek rozwiązania spełniającego pewne warunki lub stwierdzenia, że takie rozwiązanie nie istnieje.
- Problemy funkcyjne wymagają obliczenia wartości pewnej funkcji.
Ilością zasobów potrzebnych do rozwiązania problemów obliczeniowych zajmuje się teoria złożoności obliczeniowej.