95926

liczbą pierwszą, problem podziału, problem spełnialności wyrażeń logicznych

Twierdzenie 2 Z każdym problemom optymalizacyjnym można związać odpowiadający mu problem decyzyjny.

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.

niax_a;ex/(^)>

Problem maksymalizacji    pr. decyzyjny

Czy istnieje e X takie, że /(x*) > y?

, y=const

Problem minimalizacji    /(**0* pr. decyzyjny

Czy istnieje x* e X takie, że /(x*) < y?

3. Maszyna Turinga

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

Program ra DTM składa się z:

-    alfabetu E z wyróżnionym separatorem # (symbolem pustym),

-    skończonego zbioru m stanów Q = {<*),.z wyróżnionym stanem początkowym qq >zQ oraz dwoma wyróżnionymi stanami końcowymi qy e Q i g,v € Q,

- funkcji przejść S :    x E -» Q x E x {—1,+1}.

Definicja 10 Jeżeli czas działania algorytmu At jest ograniczony wielomianem rależnym od długość! Jeżyka T. (tzn. czas działania l < f<|L|) dla każdego L I pewnego wielomianu p), to m&wimy Ze algorytm Af jest algorytmem wielomianowym.

Definicja 11 Jeżeli algorytm M nie jest algorytmem wielomianowym, to mówimy, że jest algorytmem ponadwlelomianowym. b) NDTM - niedeterministyczna maszyna Turinga Budowa:

•    DTM

•    Moduł zgadujący sterujący głowicą zapisują (Układ zgadujący + głowica zapisująca) - zapisanie na taśmie pewnego odgadniętego rozwiązania (upakowanie plecaka, min funkcji...)

Wykonanie problemu:

•    Etap zgadywania

W czasie pierwszego etapu (zgadywania), moduł zgadujący generuje rozwiązanie, tzr. pewien łańcuch symboli S w całkowicie dowolny sposób, a następnie zapisuje ten łańcuch w odpowiednich komórkach taśmy (np. od -|S| do -1).

•    Etap sprawdzania