Złożoność obliczeniowa: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
drobne merytoryczne |
m drobne redakcyjne |
||
Linia 1:
{{disambigR|2='''[[Asymptotyczne tempo wzrostu]]''' (miara określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów, określana '''notacją dużego O''')}}
'''Teoria złożoności obliczeniowej'''
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 [[
Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak da się 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ć [[algorytm]]u rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.
Linia 10:
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ż 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.
Przykładowo rozpatrzmy rozkład liczb na czynniki pierwsze. Domyślamy się, ż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 [[
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]]) oraz zastosowanie określonego sposobu uśrednienia wszystkich możliwych przypadków ([[złożoność oczekiwana]]).
Linia 22:
Przyjętą miarą złożoności czasowej jest liczba operacji podstawowych w zależności od [[rozmiar wejścia|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.
Kolejny problem polega na tym, w jakim [[język programowania|języku programowania]] formułować będziemy algorytmy oraz co można założyć 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 liczba i rozmiar 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).
Linia 41:
== Klasy złożoności ==
[[Klasa złożoności]] to klasa zagadnień obliczeniowych o podobnej złożoności obliczeniowej
Podobne określenia stosujemy do algorytmów.
Stosujemy też szersze pojęcia takie jak klasa [[problem P|P]], czy [[problem NP|NP]] mając odpowiednio na uwadze [[problem decyzyjny (teoria obliczeń)|decyzyjne problemy]] wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
== P vs NP ==
Pytanie, czy klasa [[Problem P|P]] jest tym samym, co [[problem NP|NP]] jest jednym z [[
Są trzy możliwe rozwiązania:
Linia 66:
* Christos H. Papadimitriou: ''Złożoność obliczeniowa'', nowy przekład (tłum. Zdzisław Płoski). Helion 2012.
* T. H. Cormen, C. E. Leiserson, C. Stein i R. L. Rivest, ''Introduction to Algorithms'', The MIT Press/McGraw-Hill Company 1990 (wydanie polskie: ''Wprowadzenie do algorytmów'', WNT 2004).
* Marek Kubale
== Linki zewnętrzne ==
* [http://qwiki.stanford.edu/index.php/Complexity_Zoo Complexity Zoo]
* [http://wazniak.mimuw.edu.pl/index.php?title=Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa Złożoność obliczeniowa] (materiały dydaktyczne [[Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego|MIMUW]] na studia informatyczne II stopnia)
[[Kategoria:Teoria obliczeń]]
|