• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Problem obliczeniowy

    Przeczytaj także...
    Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.Instancja (z łac. instantia) - pojedyncze wystąpienie niezależnego bytu zgodnego z danym wzorcem. Najpopularniejszym przykładem jest instancjowanie klas w programowaniu obiektowym, czyli tworzenie obiektów (niezależnych bytów danej klasy, zajmujących określone miejsce w pamięci). Innym przykładem jest instancja danego programu, czyli wystąpienie w pamięci komputera aktualnie wykonywanej sekwencji kodu komputerowego.
    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.

    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.

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

    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.

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

    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.

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

    Zobacz też[]

  • moc obliczeniowa



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.008 sek.