TEORIA ZŁOŻONOŚCI OBLICZENIOWEJ
= {cyfry systemu, #} cyfry systemu, np 0..9 w systemie dziesiętnym, 0-1 w binarnym, 1 w unarnym; # - separator
Słowa dziesiętne: 1234, 1372, 1254; słowa binarne: 0, 1, 1100, 1010, 01; słowa unarne: 1, 11, 111
Język binarny: 0#101#01001
Kodowanie danych
Reguła kodowania danych
Każdą daną problemu przedstawiamy za pomocą jednego słowa danego języka .
Kolejne dane (słowa) są oddzielone pojedynczym separatorem # i są w ustalonej kolejności
Jeżeli wartość dwóch danych x1 i x2 jest taka sama (x1=x2) to zarówno x1, jak i x2 są kodowane tym samym słowem.
Rozmiar instancji problemu. Nieefektywność.
N(I) = O(nlogb(MAX(I))), gdzie: N1(I) = O(nMAX(I)) - kodowanie unarne daje wykładniczy wzrost rozmiaru problemu w stosunku do kodowania w systemie o podstawie b=2. Musimy je odrzucić ze względu na jego nieefektywność.
N(I) - długość łańcucha - rozmiar instancji I
b - podstawa systemu
MAX(I) - największa wartość w danej instancji (I)
Problemy decyzyjne i optymalizacyjne
Problem optymalizacyjny - problem, w którym mamy za zadanie znaleźć ekstremum jakiejś funkcji, np. problem programowania liniowego, problem plecakowy(rozmiar plecaka B, zadania j - rozmiar zadania+wartość zadania, znaleźć takie rozw, aby plecak miał jak najwyższą wartość), problem komiwojażera(N miast, macierz odległości między nimi, poruszać się tak, aby przejechać wszystkie miasta i wrócić z ostatniego do pierwszego po jak najkrótszej drodze, aby miasta nie powtarzały się)
Problem decyzyjny (rozpoznania) - problem, w którym mamy za zadanie odpowiedzieć na pytanie zadane w taki sposób, że jedynymi odpowiedziami są TAK bądź NIE, np. czy dana liczba naturalna n jest liczbą pierwszą, problem podziału, problem spełnialności wyrażeń logicznych
Twierdzenie odwrotne nie jest prawdziwe.
Jeżeli mamy parę problemów Po( problem optymalizacyjny) i Pd (odpowiadający mu problem decyzyjny, to prawdziwe są zależności:
Jeżeli problem Pd jest łatwy, to Po również jest łatwy
Jeżeli problem Pd jest trudny, to Po też jest trudny.
Problem maksymalizacji pr. decyzyjny , y=const
Problem minimalizacji pr. decyzyjny Maszyna Turinga
DTM - deterministyczna maszyna Turinga
Budowa:
Taśma nieskończonej długości, podzielona na pola, w których można zapisywać pojedyncze symbole
Głowica zapisująco - odczytująca przesuwająca się nad taśmą
Układ sterujący
... zobacz całą notatkę
Komentarze użytkowników (0)