Problem obliczeniowy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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.

Informatyka – dyscyplina nauki zaliczana do nauk ścisłych oraz techniki zajmująca się przetwarzaniem informacji, w tym również technologiami przetwarzania informacji oraz technologiami wytwarzania systemów przetwarzających informację. Początkowo stanowiła część matematyki, później rozwinęła się do odrębnej dyscypliny – pozostaje jednak nadal w ścisłej relacji z matematyką, która dostarcza informatyce podstaw teoretycznych.W teorii obliczeń problem optymalizacyjny jest to problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia pewną własność. Parametr, którego największej bądź najmniejszej wartości szukamy nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym jeśli polega on na znalezieniu największej wartości funkcji kosztu i minimalizacyjnym jeśli szukana jest najmniejsza wartość funkcji kosztu.

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 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.

Funkcja (łac. functio, -onis, „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.Problem decyzyjny – pytanie sformułowane w systemie formalnym, na które możliwe są odpowiedzi tak i nie. Przykładowo problem "Dla danych liczb x i y, czy x jest dzielnikiem y?" jest problemem decyzyjnym. Odpowiedzią może być tak lub nie w zależności od wartości x i y.

Typy problemów obliczeniowych[ | edytuj kod]

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.

    Algorytm – w matematyce skończony ciąg jasno zdefiniowanych czynności, koniecznych do wykonania pewnego rodzaju zadań. Słowo "algorytm" pochodzi od starego angielskiego słowa algorism, oznaczającego wykonywanie działań przy pomocy liczb arabskich (w odróżnieniu od abacism – przy pomocy abakusa), które z kolei wzięło się od nazwiska, które nosił Muhammad ibn Musa al-Chuwarizmi (أبو عبد الله محمد بن موسى الخوارزمي), matematyk perski z IX wieku.Optymalizacja - metoda wyznaczania najlepszego (optymalnego) rozwiązania (poszukiwanie ekstremum funkcji) z punktu widzenia określonego kryterium (wskaźnika) jakości (np. kosztu, drogi, wydajności).

    Zobacz też[ | edytuj kod]

  • moc obliczeniowa




  • Warto wiedzieć że... beta

    Algorytmika, teoria algorytmów – nauka o algorytmach. Jest działem informatyki, cybernetyki, a także, dla większości nauk matematyczno-przyrodniczych, ekonomii i techniki. Algorytmika zajmuje się badaniem algorytmów. Jej częścią jest natomiast algorytmizacja, czyli proces budowy konkretnego algorytmu.

    Reklama