Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami
m Zastępowanie tekstu – „,↵</math>” na „</math>,” |
|||
(Nie pokazano 10 wersji utworzonych przez 3 użytkowników) | |||
Linia 4: | Linia 4: | ||
{{cwiczenie|1|| | {{cwiczenie|1|| | ||
W trakcie wykładu rozważaliśmy język | W trakcie wykładu rozważaliśmy język | ||
<center><math> | <center><math> | ||
L= | L=\{3^k\ : : \ : k=i\cdot j\text{ dla pewnych } i,j> 1\}</math>,</center> | ||
</math></center> | |||
wykazując, że <math> | wykazując, że <math>L\in</math> '''NP''' . | ||
Uzasadnij, że także <center><math> | Uzasadnij, że także <center><math>L\in</math> '''P''' <math></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"> | <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> | Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie <math>i,j>1</math>, dla których | ||
<math> | <math>k=i\cdot j</math>. | ||
</div></div> | </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"> | <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> | Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie <math>k^2</math> (wielomianową ilość) mnożeń. Sama weryfikacja | ||
zależności <math> | zależności <math>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 | Pozostaje zaprojektować deterministyczną maszynę generującą ciągi. Można to zrobić według schematu | ||
(maszyna czterotaśmowa): | (maszyna czterotaśmowa): | ||
# Taśma nr <math> | # Taśma nr <math>1</math> jest tylko do odczytu. Mamy na niej słowo <math>3^k</math>. | ||
# Rozpocznij od zapisania słowa <math> | # Rozpocznij od zapisania słowa <math>11</math> na taśmie nr <math>2</math> i słowa <math>22</math> na taśmie nr <math>3</math>. | ||
# {{kotwica|prz.3|}}Przepisz słowa na taśmę nr <math> | # {{kotwica|prz.3|}}Przepisz słowa na taśmę nr <math>4</math> według kolejności taśm <math>2,3,1</math>. | ||
# Sprawdź na taśmie nr <math> | # Sprawdź na taśmie nr <math>4</math> czy <math>k=i\cdot j</math>. Jeśli tak, to akceptuj. Inaczej krok następny. | ||
# Dopisz symbol <math> | # Dopisz symbol <math>1</math> na taśmie nr <math>2</math>. Gdy powstało słowo dłuższe niż <math>k</math>, dopisz symbol <math>2</math> na taśmie nr <math>3</math>, a słowo na taśmie nr <math>2</math> usuń i zapisz na niej słowo <math>11</math>. | ||
# Jeśli słowo na taśmie nr <math> | # Jeśli słowo na taśmie nr <math>3</math> jest dłuższe niż <math>k</math>, to odrzuć. W przeciwnym przypadku przejdź do kroku [[#prz.3|3]]. | ||
Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr <math> | Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr <math>2</math> (licznik 1) i <math>3</math> (licznik 2) jako liczniki, a na taśmie <math>4</math> wykonuj symulacje. | ||
Zacznij od stanu liczników na <math> | Zacznij od stanu liczników na <math>2</math> i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej <math>2</math>) | ||
i zwiększ licznik <math> | i zwiększ licznik <math>2</math>. Gdy on także się przepełni, to iloczyn stanów liczników przekracza <math>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> | W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych <math>n</math>). | ||
Dla małych <math> | Dla małych <math>n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. | ||
Zatem <math> | Zatem <math>L\in</math> '''P''' . | ||
</div></div> | </div></div> | ||
{{cwiczenie|2|| | {{cwiczenie|2|| | ||
Uzasadnij, że funkcja <math> | Uzasadnij, że funkcja <math>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"> | <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> | Przypomnij sobie uzasadnienie dla funkcji <math>2n</math> z wykładu. | ||
</div></div> | </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"> | <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> | Bierzemy maszynę <math>MT_4</math> z wykładu konstruującą funkcję <math>2n</math>. Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez <math>I</math> oraz <math>S</math>). | ||
Drugą taśmę realizujemy poprzez rozszerzenie alfabetu. Jest to spowodowane faktem, że w definicji konstruowalności | 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. | pamięciowej wymagane jest istnienie jednotaśmowej deterministycznej maszyny Turinga. | ||
Konstruujemy maszynę <math> | Konstruujemy maszynę <math>\mathcal{M}</math> według schematu: | ||
# Jeśli słowo wejściowe jest puste, to stop. | # Jeśli słowo wejściowe jest puste, to stop. | ||
# Jeśli słowo wejściowe jest inne niż <math> | # Jeśli słowo wejściowe jest inne niż <math>1^n</math>, to odrzuć. | ||
# Przepisz słowo wejściowe tak, aby znajdowało się na taśmie <math> | # Przepisz słowo wejściowe tak, aby znajdowało się na taśmie <math>I</math>, a taśma <math>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> | # Kopiujemy słowo wejściowe na taśmę <math>S</math>. | ||
# Symulujemy maszynę <math> | # Symulujemy maszynę <math>MT_4</math> na taśmie <math>S</math>. | ||
# Dopisujemy do taśmy <math> | # Dopisujemy do taśmy <math>S</math> słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie <math>3n</math> komórek taśmy. | ||
# Zamieniamy symbole na <math> | # Zamieniamy symbole na <math>1</math> (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej <math>s_1\in S_F</math>. | ||
Po zakończeniu cyklu doszliśmy do konfiguracji <math> | Po zakończeniu cyklu doszliśmy do konfiguracji <math>\sharp s_1 1^{3n} \sharp</math>, co było wymagane w definicji. | ||
</div></div> | </div></div> | ||
{{cwiczenie|3|| | {{cwiczenie|3|| | ||
Uzasadnij, że funkcja <math> | Uzasadnij, że funkcja <math>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"> | <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> | Wykorzystaj konstruowalność pamięciową funkcji <math>g(n)=3n</math>. | ||
</div></div> | </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"> | <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> | Wykorzystujemy trzy taśmy (<math>I</math>, <math>C</math>, <math>S</math>) oraz maszynę <math>\mathcal{M}</math> konstruującą pamięciowo funkcję <math>g(n)=3n</math>. | ||
Docelowa maszyna <math> | Docelowa maszyna <math>\mathcal{N}</math> działa według schematu. | ||
# Jeśli słowo początkowe jest puste, wypisz <math> | # Jeśli słowo początkowe jest puste, wypisz <math>1</math> i zatrzymaj się. W przeciwnym wypadku, wykonaj następny krok. | ||
# Jeśli słowo wejściowe jest inne niż <math> | # Jeśli słowo wejściowe jest inne niż <math>1^n</math>, to odrzuć. | ||
# Na taśmie <math> | # Na taśmie <math>I</math> wypisz słowo wejściowe, na taśmach <math>C</math> i <math>S</math> wypisz słowo <math>1</math>. | ||
# {{kotwica|prz.4|}}Wykonaj symulację maszyny <math> | # {{kotwica|prz.4|}}Wykonaj symulację maszyny <math>\mathcal{M}</math> na taśmie <math>S</math> oraz dopisz symbol <math>1</math> do taśmy <math>C</math> (po jednym przebiegu ilość symboli na taśmie <math>S</math> wzrasta trzykrotnie) | ||
# Jeśli słowo na taśmie <math> | # Jeśli słowo na taśmie <math>C</math> jest krótsze niż słowo na taśmie <math>I</math>, wykonaj ponownie krok [[#prz.4|4]]. | ||
# W tym momencie na taśmie <math> | # W tym momencie na taśmie <math>S</math> zostało zaznaczone <math>3^n</math> komórek. | ||
Zamieniamy wypisane symbole na <math> | Zamieniamy wypisane symbole na <math>1</math> (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) | ||
i przechodzimy do konfiguracji końcowej <math> | i przechodzimy do konfiguracji końcowej <math>s_1\in S_F</math>. | ||
Po zakończeniu cyklu doszliśmy do konfiguracji <math> | Po zakończeniu cyklu doszliśmy do konfiguracji <math>\sharp s_1 1^{3^n} \sharp</math>, co było wymagane w definicji konstruowalności | ||
pamięciowej. | pamięciowej. | ||
</div></div> | </div></div> | ||
Linia 91: | Linia 90: | ||
{{cwiczenie|4|| | {{cwiczenie|4|| | ||
Zadanie domowe | Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga | ||
<math> | <math>\mathcal{MT}</math> akceptującej język: | ||
<center><math> | <center><math> | ||
L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\} | L_1=\left\{www\ : : \ : w\in \left\{\circ,\bullet,\star\right\}^*\right\}</math></center> | ||
</math></center> | |||
Zmodyfikuj, ewentualnie, tę konstrukcję <math> | Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{MT}</math>, aby udowodnić <math>L_1 \in</math> '''P''' . | ||
}} | }} | ||
{{cwiczenie|5|| | {{cwiczenie|5|| | ||
Zadanie domowe | Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga | ||
<math> | <math>\mathcal{NMT}</math> akceptującej język: | ||
<center><math> | <center><math> | ||
L_2=\left\{w_1 w_1 w_2 w_2 \dots w_n w_n \: : \: w_i \in \left\{\circ,\bullet\right\}^+, n>0 \right\} | L_2=\left\{w_1 w_1 w_2 w_2 \dots w_n w_n \ : : \ : w_i \in \left\{\circ,\bullet\right\}^+, n>0 \right\}</math></center> | ||
</math></center> | |||
Zmodyfikuj, ewentualnie, tę konstrukcję <math> | Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{NMT}</math> aby udowodnić, że | ||
<math> | <math>L_2 \in</math> '''NP''' .<br> | ||
''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math> | ''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>w</math> | ||
przeprowadź weryfikację w trzech | przeprowadź weryfikację w trzech | ||
etapach: konstrukcja słów <math> | etapach: konstrukcja słów <math>w_1, \dots ,w_n</math>, gdzie <math>n< |w|</math> (wyrocznia), sklejanie, weryfikacja, czy <math>w=w_1w_1 w_2 w_2 \dots w_n w_n</math>. | ||
}} | }} | ||
Linia 120: | Linia 117: | ||
{{cwiczenie|6|| | {{cwiczenie|6|| | ||
Uzasadnij, że jeśli funkcja <math> | Uzasadnij, że jeśli funkcja <math>s(n)</math> jest konstruowalna pamięciowo, to obliczenie <math>d_1 \mapsto^* d_2</math> z definicji | ||
konstruowalności pamięciowej (tzn. <math> | konstruowalności pamięciowej (tzn. <math>d_1=\sharp s_0 1^n \sharp</math>, | ||
<math> | <math>d_2=\sharp s_1 1^{s(n)} w \sharp</math>) następuje w co najwyżej <math>c 2^{s(n)}</math> krokach, gdzie <math>c</math> jest pewną | ||
stałą niezależną od <math> | stałą niezależną od <math>n</math>.<br> | ||
''Podpowiedź:'' przeanalizuj ilość możliwych konfiguracji. | ''Podpowiedź:'' przeanalizuj ilość możliwych konfiguracji. | ||
}} | }} | ||
{{cwiczenie|7|| | {{cwiczenie|7|| | ||
Uzasadnij, że funkcja <math> | Uzasadnij, że funkcja <math>n^3</math> jest konstruowalna pamięciowo. | ||
}} | }} |
Aktualna wersja na dzień 21:46, 11 wrz 2023
Ćwiczenia 13
Ćwiczenie 1
W trakcie wykładu rozważaliśmy język
wykazując, że NP .
Uzasadnij, że takżeĆwiczenie 2
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 3
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 4
Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję , aby udowodnić P .
Ćwiczenie 5
Zadanie domowe - cwiczenie 7 - 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 6
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 7
Uzasadnij, że funkcja jest konstruowalna pamięciowo.