Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami
Linia 1: | Linia 1: | ||
==Ćwiczenia 13== | ==Ćwiczenia 13== | ||
{{cwiczenie|3|| | |||
W trakcie wykładu rozważaliśmy język | |||
<center><math>\displaystyle | |||
L=\left\{3^k\: : \: k=i\cdot j </math> dla pewnych <math>\displaystyle i,j> 1\right\}, | |||
</math></center> | |||
wykazując, że <math>\displaystyle L\in </math> '''NP''' . | |||
Uzasadnij, że także <center><math>\displaystyle L\in </math> '''P''' <math>\displaystyle .</math></center> | |||
}} | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | |||
Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie <math>\displaystyle i,j>1</math>, dla których | |||
<math>\displaystyle k=i\cdot j</math>. | |||
</div></div> | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | |||
Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie <math>\displaystyle k^2</math> (wielomianową ilość) mnożeń. Sama weryfikacja | |||
zależności <math>\displaystyle k=i\cdot j</math> (według uzasadnienia z wykładu) jest wykonywana w czasie wielomianowym. | |||
Pozostaje zaprojektować deterministyczną maszynę generującą ciągi. Można to zrobić według schematu | |||
(maszyna czterotaśmowa): | |||
# Taśma nr <math>\displaystyle 1</math> jest tylko do odczytu. Mamy na niej słowo <math>\displaystyle 3^k</math>. | |||
# Rozpocznij od zapisania słowa <math>\displaystyle 11</math> na taśmie nr <math>\displaystyle 2</math> i słowa <math>\displaystyle 22</math> na taśmie nr <math>\displaystyle 3</math>. | |||
# {{kotwica|prz.3|}}Przepisz słowa na taśmę nr <math>\displaystyle 4</math> według kolejności taśm <math>\displaystyle 2,3,1</math>. | |||
# Sprawdź na taśmie nr <math>\displaystyle 4</math> czy <math>\displaystyle k=i\cdot j</math>. Jeśli tak, to akceptuj. Inaczej krok następny. | |||
# Dopisz symbol <math>\displaystyle 1</math> na taśmie nr <math>\displaystyle 2</math>. Gdy powstało słowo dłuższe niż <math>\displaystyle k</math>, dopisz symbol <math>\displaystyle 2</math> na taśmie nr <math>\displaystyle 3</math>, a słowo na taśmie nr <math>\displaystyle 2</math> usuń i zapisz na niej słowo <math>\displaystyle 11</math>. | |||
# Jeśli słowo na taśmie nr <math>\displaystyle 3</math> jest dłuższe niż <math>\displaystyle k</math>, to odrzuć. W przeciwnym przypadku przejdź do kroku [[#prz.3|3]]. | |||
Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr <math>\displaystyle 2</math> (licznik 1) i <math>\displaystyle 3</math> (licznik 2) jako liczniki, a na taśmie <math>\displaystyle 4</math> wykonuj symulacje. | |||
Zacznij od stanu liczników na <math>\displaystyle 2</math> i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej <math>\displaystyle 2</math>) | |||
i zwiększ licznik <math>\displaystyle 2</math>. Gdy on także się przepełni, to iloczyn stanów liczników przekracza <math>\displaystyle k</math>, zatem można zakończyć generowanie ciągów. | |||
W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych <math>\displaystyle n</math>). | |||
Dla małych <math>\displaystyle n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. | |||
Zatem <math>\displaystyle L\in </math> '''P''' . | |||
</div></div> | |||
{{cwiczenie|4|| | |||
Uzasadnij, że funkcja <math>\displaystyle s(n)=3n</math> jest konstruowalna pamięciowo. | |||
}} | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | |||
Przypomnij sobie uzasadnienie dla funkcji <math>\displaystyle 2n</math> z wykładu. | |||
</div></div> | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | |||
Bierzemy maszynę <math>\displaystyle MT_4</math> z wykładu konstruującą funkcję <math>\displaystyle 2n</math>. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez <math>\displaystyle I</math> oraz <math>\displaystyle S</math>). | |||
Drugą taśmę realizujemy poprzez rozszerzenie alfabetu. Jest to spowodowane faktem, że w definicji konstruowalności | |||
pamięciowej wymagane jest istnienie jednotaśmowej deterministycznej maszyny Turinga. | |||
Konstruujemy maszynę <math>\displaystyle \mathcal{M}</math> według schematu: | |||
# Jeśli słowo wejściowe jest puste, to stop. | |||
# Jeśli słowo wejściowe jest inne niż <math>\displaystyle 1^n</math>, to odrzuć. | |||
# Przepisz słowo wejściowe tak, aby znajdowało się na taśmie <math>\displaystyle I</math>, a taśma <math>\displaystyle S</math> była pusta (gdy zaczynamy symulować dwie taśmy musimy przejść do innego zestawu symboli, w którym rozróżniamy taśmy). | |||
# Kopiujemy słowo wejściowe na taśmę <math>\displaystyle S</math>. | |||
# Symulujemy maszynę <math>\displaystyle MT_4</math> na taśmie <math>\displaystyle S</math>. | |||
# Dopisujemy do taśmy <math>\displaystyle S</math> słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie <math>\displaystyle 3n</math> komórek taśmy. | |||
# Zamieniamy symbole na <math>\displaystyle 1</math> (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej <math>\displaystyle s_1\in S_F</math>. | |||
Po zakończeniu cyklu doszliśmy do konfiguracji <math>\displaystyle \sharp s_1 1^{3n} \sharp</math>, co było wymagane w definicji. | |||
</div></div> | |||
{{cwiczenie|5|| | |||
Uzasadnij, że funkcja <math>\displaystyle s(n)=3^n</math> jest konstruowalna pamięciowo. | |||
}} | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> | |||
Wykorzystaj konstruowalność pamięciową funkcji <math>\displaystyle g(n)=3n</math>. | |||
</div></div> | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> | |||
Wykorzystujemy trzy taśmy (<math>\displaystyle I</math>, <math>\displaystyle C</math>, <math>\displaystyle S</math>) oraz maszynę <math>\displaystyle \mathcal{M}</math> konstruującą pamięciowo funkcję <math>\displaystyle g(n)=3n</math>. | |||
Docelowa maszyna <math>\displaystyle \mathcal{N}</math> działa według schematu. | |||
# Jeśli słowo początkowe jest puste, wypisz <math>\displaystyle 1</math> i zatrzymaj się. W przeciwnym wypadku, wykonaj następny krok. | |||
# Jeśli słowo wejściowe jest inne niż <math>\displaystyle 1^n</math>, to odrzuć. | |||
# Na taśmie <math>\displaystyle I</math> wypisz słowo wejściowe, na taśmach <math>\displaystyle C</math> i <math>\displaystyle S</math> wypisz słowo <math>\displaystyle 1</math>. | |||
# {{kotwica|prz.4|}}Wykonaj symulację maszyny <math>\displaystyle \mathcal{M}</math> na taśmie <math>\displaystyle S</math> oraz dopisz symbol <math>\displaystyle 1</math> do taśmy <math>\displaystyle C</math> (po jednym przebiegu ilość symboli na taśmie <math>\displaystyle S</math> wzrasta trzykrotnie) | |||
# Jeśli słowo na taśmie <math>\displaystyle C</math> jest krótsze niż słowo na taśmie <math>\displaystyle I</math>, wykonaj ponownie krok [[#prz.4|4]]. | |||
# W tym momencie na taśmie <math>\displaystyle S</math> zostało zaznaczone <math>\displaystyle 3^n</math> komórek. | |||
Zamieniamy wypisane symbole na <math>\displaystyle 1</math> (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) | |||
i przechodzimy do konfiguracji końcowej <math>\displaystyle s_1\in S_F</math>. | |||
Po zakończeniu cyklu doszliśmy do konfiguracji <math>\displaystyle \sharp s_1 1^{3^n} \sharp</math>, co było wymagane w definicji konstruowalności | |||
pamięciowej. | |||
</div></div> | |||
Wersja z 16:38, 3 wrz 2006
Ćwiczenia 13
Ćwiczenie 3
W trakcie wykładu rozważaliśmy język
wykazując, że NP .
Uzasadnij, że takżeĆwiczenie 4
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 5
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 1
Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję , aby udowodnić P .
Ćwiczenie 2
Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję aby udowodnić, że
NP .
Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego przeprowadź weryfikację w trzech etapach: konstrukcja słów , gdzie (wyrocznia), sklejanie, weryfikacja, czy .
Ćwiczenie 3
Uzasadnij, że jeśli funkcja jest konstruowalna pamięciowo, to obliczenie z definicji
konstruowalności pamięciowej (tzn. ,
) następuje w co najwyżej krokach, gdzie jest pewną
stałą niezależną od .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.
Ćwiczenie 4
Uzasadnij, że funkcja jest konstruowalna pamięciowo.