Złożoność obliczeniowa
Z Wikipedii
Teoria złożoności obliczeniowej to dział teorii obliczeń. Głównym jej 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 i wiele innych, jednak takich, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, która jest drugą ważną gałęzią teorii obliczeń.
Wyniki, jakie podaje t.z.o. można podzielić na dwie kategorie: pozytywne i negatywne; w uproszczeniu 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ć algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.
Spis treści |
[edytuj] Złożoność algorytmów
Ilość zasobów potrzebnych dla działania algorytmu może być rozumiana jako jego złożoność. W zależności od rozważanego zasobu mówimy o złożoności czasowej lub pamięciowej. Oczywiście w większości wypadków ilość potrzebnych zasobów będzie się różnić w zależności od instancji problemu.
Jako przykład może nam posłużyć problem rozkładu liczb na czynniki pierwsze. Domyślamy się, że (niezależnie od algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Taką własność ma znakomita większość problemów obliczeniowych: im większy rozmiar danych wejściowych tym więcej zasobów (czasu, procesorów, pamięci) jest potrzebnych do jego rozwiązania. Złożoność algorytmu jest więc funkcją rozmiaru danych wejściowych.
Kolejnym problemem jest fakt, iż złożoność zwykle nie zależy tylko i wyłącznie od rozmiaru danych, ale może się znacznie różnić dla instancji o identycznym rozmiarze. Dwa często spotykane sposoby radzenia sobie z tym problemem to: branie pod uwagę przypadków najgorszych (złożoność pesymistyczna) i pewien sposób uśrednienia wszystkich możliwych przypadków (złożoność oczekiwana).
[edytuj] Złożoność czasowa
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 implementacji algorytmu, użytego kompilatora, maszyny na której algorytm wykonano, a także umiejętności programisty. Dlatego w charakterze czasu wykonania rozpatrujemy 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ęzyku programowania formułować 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).
[edytuj] Złożoność pamięciowa
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.
[edytuj] Porównywanie złożoności algorytmów
Porównując złożoność algorytmów bierzemy pod uwagę asymptotyczne tempo wzrostu, czyli to jak zachowuje się funkcja określająca złożoność dla odpowiednio dużych, granicznych argumentów (rozmiarów danych wejściowych) ignorując zachowanie dla małych danych. Ponadto złożoności algorytmów różniące się o stałą uważamy za takie same, co eliminuje wpływ szybkości działania komputera, na którym dany algorytm ma być wykonany, oraz wybór operacji podstawowej, która na jednym komputerze może wykonywać się błyskawicznie, na innym zaś musi być zastąpiona szeregiem instrukcji.
[edytuj] Klasy złożoności
Klasa złożoności to zbiór problemów obliczeniowych o podobnej złożoności obliczeniowej - innymi słowy problemy do których rozwiązania potrzebna jest podobna ilość zasobów łączymy w klasy. Przykładowo mówimy o problemach o liniowej złożoności pamięciowej, jeśli ilość potrzebnej pamięci rośnie liniowo względem rozmiaru danych; czy też o problemach o kwadratowej złożoności czasowej, jeśli liczba operacji podstawowych rośnie z kwadratem rozmiaru danych. Podobne określenia stosujemy do algorytmów.
Stosujemy też szersze pojęcia takie jak klasa P, czy NP mając odpowiednio na uwadze decyzyjne problemy wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
[edytuj] Czy P = NP?
Pytanie, czy klasa P jest tym samym, co NP jest prawdopodobnie najważniejszym otwartym problemem w całej teorii informatyki. Każdy problem z klasy P jest również w klasie NP, nie wiemy jednak, czy istnieją problemy klasy NP, które nie są problemami klasy P.
Są trzy możliwe rozwiązania:
- P = NP,
- P ≠ NP,
- Problem jest w przyjętej aksjomatyce nierozwiązywalny.
Przy czym pierwsze z nich wydaje się być mało prawdopodobne.
Dla pierwszej osoby, która rozwiąże ten problem przewidziano nagrodę w wysokości miliona dolarów [1].
[edytuj] Zobacz też
- Przegląd zagadnień z zakresu matematyki
- Problem komiwojażera
- Algorytm in situ
- Maszyna Turinga
- Asymptotyczne tempo wzrostu
[edytuj] Linki zewnętrzne
- The Complexity Zoo
- Złożoność obliczeniowa (materiały dydaktyczne MIMUW na studia informatyczne II stopnia)
[edytuj] Literatura
- Christos H. Papadimitriou: Złożoność obliczeniowa, WNT 2002.
- 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 : Łagodne wprowadzenie do analizy algorytmów, Gdańsk 2004.
