• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Złożoność obliczeniowa



    Podstrony: 1 [2] [3] [4]
    Przeczytaj także...
    Rozkład na czynniki lub faktoryzacja – proces, w którym dla danego obiektu znajdują się obiekty, takie że ich iloczyn jest jemu równy, przez co są one w pewnym sensie od niego prostsze.Złożoność oczekiwana : określa złożoność średnią czyli wartość oczekiwaną zmiennej losowej f. Jeśli wszystkie dane są jednakowo prawdopodobne (z prawdopodobieństwem niezerowym) wtedy wyraża się ona wzorem:

    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.

    Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności będąca drugą ważną gałęzią teorii obliczeń.

    Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.Maszyna RAM - w informatyce model abstrakcyjnej maszyny będący odmianą maszyny rejestrowej, bardzo podobnej do maszyny licznikowej, lecz z możliwością niebezpośredniego adresowania jej rejestrów. Model RAM wykorzystywany jest podczas analizy złożoności obliczeniowej algorytmów.

    Wyniki, jakie podaje t.z.o. można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają co i jak można obliczyć, oraz takie, w których dowodzi się czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.

    Definicja intuicyjna: Maszyna Turinga stanowi najprostszy, wyidealizowany matematyczny model komputera, zbudowany z taśmy, na której zapisuje się dane i poruszającej się wzdłuż niej „głowicy”, wykonującej proste operacje na zapisanych na taśmie wartościach.Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego (WMIM UW, MIMUW) – wydział Uniwersytetu Warszawskiego kształcący w trybie dziennym na kierunkach:

    Spis treści

  • 1 Złożoność algorytmów
  • 1.1 Czasowa złożoność obliczeniowa
  • 1.2 Pamięciowa złożoność obliczeniowa
  • 2 Porównywanie złożoności algorytmów
  • 3 Klasy złożoności
  • 4 P vs NP
  • 5 Zobacz też
  • 6 Bibliografia
  • 7 Linki zewnętrzne
  • Złożoność algorytmów[]

    Ilość zasobów niezbędnych do wykonania algorytmu można rozumieć jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej czy też złożoności pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od danych wejściowych z zakresu danego zagadnienia.

    Aksjomat (postulat, pewnik) (gr. αξιωμα [aksíoma] – godność, pewność, oczywistość) – jedno z podstawowych pojęć logiki matematycznej. Od czasów Euklidesa uznawano, że aksjomaty to zdania przyjmowane za prawdziwe, których nie dowodzi się w obrębie danej teorii matematycznej. We współczesnej matematyce definicja aksjomatu jest nieco inna:Rozmiarem wejścia nazywamy cechę danych wejściowych dla algorytmu, będąca zmienną niezależną funkcji opisującej jego złożoność obliczeniową.

    Przykładowo można by rozpatrzyć rozkład liczb na czynniki pierwsze. Przewidzieć można, że (niezależnie od zastosowanego algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Tę cechę podziela większość zagadnień obliczeniowych – im większe rozmiary danych wejściowych, tym więcej zasobów (czasu, procesorów, pamięci) jest koniecznych do wykonania danych obliczeń. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.

    W informatyce, teoria obliczalności to dział teorii obliczeń zajmujący się badaniem jakie problemy są rozwiązywalne przy użyciu komputerów. Nie należy mylić teorii obliczalności z teorią złożoności obliczeniowej, zajmującej się badaniem jak efektywnie da się rozwiązywać różne problemy.Juris Hartmanis (ur. 5 maja 1928 w Rydze) – amerykański informatyk-teoretyk łotewskiego pochodzenia, uważany za współtwórcę (wraz z Richardem E. Stearnsem) teorii złożoności obliczeniowej, za co obaj otrzymali Nagrodę Turinga w 1993.

    Kolejnym problemem jest fakt, iż złożoność zwykle nie zależy wyłącznie od rozmiaru danych, ale może się znacznie różnić dla danych wejściowych o identycznym rozmiarze. Dwoma często stosowanymi sposobami podejścia są:

  • rozpatrywanie przypadków najgorszych – złożoność pesymistyczna
  • zastosowanie określonego sposobu uśrednienia wszystkich możliwych przypadków – złożoność oczekiwana
  • Czasowa złożoność obliczeniowa[]

    Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od rozmiaru wejścia. Pomiar rzeczywistego czasu zegarowego jest mało użyteczny ze względu na silną zależność od sposobu realizacji algorytmu, użytego kompilatora oraz maszyny, na której algorytm wykonujemy. Dlatego w charakterze czasu wykonania rozpatruje się zwykle liczbę operacji podstawowych (dominujących). Operacjami podstawowymi mogą być na przykład: podstawienie, porównanie lub prosta operacja arytmetyczna.

    Problem komiwojażera (TSP - ang. travelling salesman problem) jest to zagadnienie optymalizacyjne, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.Problem P (ang. deterministic polynomial - deterministycznie wielomianowy) to problem decyzyjny, dla którego rozwiązanie można znaleźć w czasie wielomianowym.

    Kolejny problem polega na tym, w jakim języku programowania formułować będziemy algorytmy oraz co można założyć mówiąc o maszynie, na której algorytm ten będzie wykonywany. Istniejące komputery różnią się między sobą istotnymi (z punktu widzenia konstruowania algorytmów) parametrami, jak na przykład liczbą i rozmiarem rejestrów, udostępnianymi operacjami matematycznymi, a ponadto podlegają ciągłym ulepszeniom. Wobec tego algorytmy analizuje się, wykorzystując abstrakcyjne modele obliczeń. Do popularnych modeli należą maszyna RAM, maszyna Turinga i maszyna wskaźnikowa (ang. pointer machine).

    Stała – pewien symbol, któremu przyporządkowana jest określona zdefiniowana wartość. Ścisła definicja uzależniona jest od dziedziny matematyki, w której obiekt jest stosowany.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.

    Pamięciowa złożoność obliczeniowa[]

    Podobnie jak złożoność czasowa jest miarą czasu działania algorytmu, tak złożoność pamięciowa jest miarą ilości wykorzystanej pamięci. Jako tę ilość najczęściej przyjmuje się użytą pamięć maszyny abstrakcyjnej (na przykład liczbę komórek pamięci maszyny RAM) w funkcji rozmiaru wejścia. Możliwe jest również obliczanie rozmiaru potrzebnej pamięci fizycznej wyrażonej w bitach lub bajtach.

    Problem spełnialności to pytanie rachunku zdań - czy dla danej formuły logicznej istnieje takie podstawienie (wartościowanie) zmiennych zdaniowych, żeby formuła była prawdziwa. Jest równoważne negacji odpowiedzi na pytanie czy "negacja tej formuły jest tautologią".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.


    Podstrony: 1 [2] [3] [4]



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

    Warto wiedzieć że... beta

    Język programowania – zbiór zasad określających, kiedy ciąg symboli tworzy program komputerowy oraz jakie obliczenia opisuje.
    Algorytm in situ (łac. in situ - w miejscu) - jest to algorytm, który do wykonania potrzebuje stałej ilości pamięci komputera, niezależnej od rozmiaru danych wejściowych. Wszelkie potrzebne do otrzymania wyniku obliczenia są wykonywane w pamięci, do której zostały załadowane dane.
    Złożoność Kołmogorowa – dla łańcucha symboli, skończonego lub nieskończonego, to długość najkrótszego programu, który generuje dany łańcuch. Nazwa pojęcia pochodzi od nazwiska Andrieja Kołmogorowa.
    Problem obliczeniowy, zadanie obliczeniowe – zadanie, które może być rozwiązane za pomocą komputera lub innej maszyny liczącej. Na opis p.o. 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 p.o. 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 p.o.
    Problem NP (niedeterministycznie wielomianowy, ang. nondeterministic polynomial) to problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
    W teorii obliczeń klasa złożoności to zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej. Najbardziej pospolitą definicją klasy złożoności jest:
    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.

    Reklama

    Czas generowania strony: 0.029 sek.