Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:46, 11 wrz 2023

Ćwiczenia 13

Ćwiczenie 1

W trakcie wykładu rozważaliśmy język

L = {3^{k} : : : k = i \cdot j dla pewnych i, j > 1}

,

wykazując, że $L \in$ NP .

Uzasadnij, że także

L \in

P

.

Wskazówka

Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie $i, j > 1$ , dla których $k = i \cdot j$ .

Rozwiązanie

Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie $k^{2}$ (wielomianową ilość) mnożeń. Sama weryfikacja zależności $k = i \cdot j$ (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 $1$ jest tylko do odczytu. Mamy na niej słowo $3^{k}$ .
Rozpocznij od zapisania słowa $11$ na taśmie nr $2$ i słowa $22$ na taśmie nr $3$ .
Przepisz słowa na taśmę nr $4$ według kolejności taśm $2, 3, 1$ .
Sprawdź na taśmie nr $4$ czy $k = i \cdot j$ . Jeśli tak, to akceptuj. Inaczej krok następny.
Dopisz symbol $1$ na taśmie nr $2$ . Gdy powstało słowo dłuższe niż $k$ , dopisz symbol $2$ na taśmie nr $3$ , a słowo na taśmie nr $2$ usuń i zapisz na niej słowo $11$ .
Jeśli słowo na taśmie nr $3$ jest dłuższe niż $k$ , to odrzuć. W przeciwnym przypadku przejdź do kroku 3.

Idea tej maszyny jest bardzo prosta. Wykorzystaj taśmy nr $2$ (licznik 1) i $3$ (licznik 2) jako liczniki, a na taśmie $4$ wykonuj symulacje. Zacznij od stanu liczników na $2$ i zwiększaj kolejno licznik 1, a po jego przepełnieniu zeruj go (do wartości początkowej $2$ ) i zwiększ licznik $2$ . Gdy on także się przepełni, to iloczyn stanów liczników przekracza $k$ , 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 $n$ ). Dla małych $n$ możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania. Zatem $L \in$ P .

Ćwiczenie 2

Uzasadnij, że funkcja $s (n) = 3 n$ jest konstruowalna pamięciowo.

Wskazówka

Przypomnij sobie uzasadnienie dla funkcji $2 n$ z wykładu.

Rozwiązanie

Bierzemy maszynę $M T_{4}$ z wykładu konstruującą funkcję $2 n$ . Dodajemy jedną dodatkową taśmę (oznaczmy taśmy przez $I$ oraz $S$ ). 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ę $ℳ$ według schematu:

Jeśli słowo wejściowe jest puste, to stop.
Jeśli słowo wejściowe jest inne niż $1^{n}$ , to odrzuć.
Przepisz słowo wejściowe tak, aby znajdowało się na taśmie $I$ , a taśma $S$ 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ę $S$ .
Symulujemy maszynę $M T_{4}$ na taśmie $S$ .
Dopisujemy do taśmy $S$ słowo wejściowe. W tym momencie zaznaczyliśmy dokładnie $3 n$ komórek taśmy.
Zamieniamy symbole na $1$ (zapominamy o symulacji taśm), wracamy do lewego markera i przechodzimy do konfiguracji końcowej $s_{1} \in S_{F}$ .

Po zakończeniu cyklu doszliśmy do konfiguracji $♯ s_{1} 1^{3 n} ♯$ , co było wymagane w definicji.

Ćwiczenie 3

Uzasadnij, że funkcja $s (n) = 3^{n}$ jest konstruowalna pamięciowo.

Wskazówka

Wykorzystaj konstruowalność pamięciową funkcji $g (n) = 3 n$ .

Rozwiązanie

Wykorzystujemy trzy taśmy ( $I$ , $C$ , $S$ ) oraz maszynę $ℳ$ konstruującą pamięciowo funkcję $g (n) = 3 n$ . Docelowa maszyna $𝒩$ działa według schematu.

Jeśli słowo początkowe jest puste, wypisz $1$ i zatrzymaj się. W przeciwnym wypadku, wykonaj następny krok.
Jeśli słowo wejściowe jest inne niż $1^{n}$ , to odrzuć.
Na taśmie $I$ wypisz słowo wejściowe, na taśmach $C$ i $S$ wypisz słowo $1$ .
Wykonaj symulację maszyny $ℳ$ na taśmie $S$ oraz dopisz symbol $1$ do taśmy $C$ (po jednym przebiegu ilość symboli na taśmie $S$ wzrasta trzykrotnie)
Jeśli słowo na taśmie $C$ jest krótsze niż słowo na taśmie $I$ , wykonaj ponownie krok 4.
W tym momencie na taśmie $S$ zostało zaznaczone $3^{n}$ komórek.

Zamieniamy wypisane symbole na $1$ (zapominamy o symulacji taśm), wracamy nad pierwszy symbol (przed lewym markerem) i przechodzimy do konfiguracji końcowej $s_{1} \in S_{F}$ .

Po zakończeniu cyklu doszliśmy do konfiguracji $♯ s_{1} 1^{3^{n}} ♯$ , co było wymagane w definicji konstruowalności pamięciowej.

Ćwiczenie 4

Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga $ℳ 𝒯$ akceptującej język:

L_{1} = {w w w : : : w \in {\circ, ∙, ⋆}^{*}}

Zmodyfikuj, ewentualnie, tę konstrukcję $ℳ 𝒯$ , aby udowodnić $L_{1} \in$ P .

Ćwiczenie 5

Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga $𝒩 ℳ 𝒯$ akceptującej język:

L_{2} = {w_{1} w_{1} w_{2} w_{2} \dots w_{n} w_{n} : : : w_{i} \in {\circ, ∙}^{+}, n > 0}

Zmodyfikuj, ewentualnie, tę konstrukcję $𝒩 ℳ 𝒯$ aby udowodnić, że $L_{2} \in$ NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego $w$ przeprowadź weryfikację w trzech etapach: konstrukcja słów $w_{1}, \dots, w_{n}$ , gdzie $n < | w |$ (wyrocznia), sklejanie, weryfikacja, czy $w = w_{1} w_{1} w_{2} w_{2} \dots w_{n} w_{n}$ .

ZADANIA DOMOWE

Ćwiczenie 6

Uzasadnij, że jeśli funkcja $s (n)$ jest konstruowalna pamięciowo, to obliczenie $d_{1} \mapsto^{*} d_{2}$ z definicji konstruowalności pamięciowej (tzn. $d_{1} = ♯ s_{0} 1^{n} ♯$ , $d_{2} = ♯ s_{1} 1^{s (n)} w ♯$ ) następuje w co najwyżej $c 2^{s (n)}$ krokach, gdzie $c$ jest pewną stałą niezależną od $n$ .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 7

Uzasadnij, że funkcja $n^{3}$ jest konstruowalna pamięciowo.

@@ Linia 3: / Linia 3: @@
 {{cwiczenie|1||
-Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga
+W trakcie wykładu rozważaliśmy język
-<math>\displaystyle \mathcal{MT}</math> akceptującej język:
+<center><math>
-<center><math>\displaystyle
+L=\{3^k\ : : \ : k=i\cdot j\text{ dla pewnych } i,j> 1\}</math>,</center>
-L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}.
-</math></center>
+wykazując, że <math>L\in</math> '''NP''' .
+Uzasadnij, że także <center><math>L\in</math> '''P''' <math></math>.</center>
-Zmodyfikuj, ewentualnie, tę konstrukcję <math>\displaystyle \mathcal{MT}</math>, aby udowodnić <math>\displaystyle L_1 \in  </math> '''P''' .
 }}
-{{cwiczenie|2||
+<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">
-Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
+Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie <math>i,j>1</math>, dla których
-<math>\displaystyle \mathcal{NMT}</math> akceptującej język:
+<math>k=i\cdot j</math>.
-<center><math>\displaystyle
+</div></div>
-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>
+<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>k^2</math> (wielomianową ilość) mnożeń. Sama weryfikacja
+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
+(maszyna czterotaśmowa):
+# 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>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>4</math> według kolejności taśm <math>2,3,1</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>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>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>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>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>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.
-Zmodyfikuj, ewentualnie, tę konstrukcję <math>\displaystyle \mathcal{NMT}</math> aby udowodnić, że
+W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych <math>n</math>).
-<math>\displaystyle L_2 \in  </math> '''NP''' .<br>
+Dla małych <math>n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania.
+Zatem <math>L\in</math> '''P''' .
+</div></div>
-''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>\displaystyle w</math>
+{{cwiczenie|2||
-przeprowadź weryfikację w trzech
+Uzasadnij, że funkcja <math>s(n)=3n</math> jest konstruowalna pamięciowo.
-etapach: konstrukcja słów <math>\displaystyle w_1, \dots ,w_n</math>, gdzie <math>\displaystyle n< |w|</math> (wyrocznia), sklejanie, weryfikacja, czy <math>\displaystyle w=w_1w_1 w_2 w_2 \dots w_n w_n</math>.
 }}
+<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>2n</math> z wykładu.
+</div></div>
-<center>ZADANIA DOMOWE</center>
+<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>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
+pamięciowej wymagane jest istnienie jednotaśmowej deterministycznej maszyny Turinga.
+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 inne niż <math>1^n</math>, to odrzuć.
+# 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>S</math>.
+# Symulujemy maszynę <math>MT_4</math> na taśmie <math>S</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>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>\sharp s_1 1^{3n} \sharp</math>, co było wymagane w definicji.
+</div></div>
 {{cwiczenie|3||
-Uzasadnij, że jeśli funkcja <math>\displaystyle s(n)</math> jest konstruowalna pamięciowo, to obliczenie <math>\displaystyle d_1 \mapsto^* d_2</math> z definicji
+Uzasadnij, że funkcja <math>s(n)=3^n</math> jest konstruowalna pamięciowo.
-konstruowalności pamięciowej (tzn. <math>\displaystyle d_1=\sharp s_0 1^n \sharp</math>,
-<math>\displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp</math>) następuje w co najwyżej <math>\displaystyle c 2^{s(n)}</math> krokach, gdzie <math>\displaystyle c</math> jest pewną
-stałą niezależną od <math>\displaystyle n</math>.<br>
-''Podpowiedź:'' przeanalizuj ilość możliwych konfiguracji.
 }}
+<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>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>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>\mathcal{N}</math> działa według schematu.
+# 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>1^n</math>, to odrzuć.
+# 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>\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>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>S</math> zostało zaznaczone <math>3^n</math>  komórek.
+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>s_1\in S_F</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.
+</div></div>
 {{cwiczenie|4||
-Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo.
+Zadanie domowe - cwiczenie 6 -  do wykładu 12 polegało na konstrukcji maszyny Turinga
+<math>\mathcal{MT}</math> akceptującej język:
+<center><math>
+L_1=\left\{www\ : : \ : w\in \left\{\circ,\bullet,\star\right\}^*\right\}</math></center>
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{MT}</math>, aby udowodnić <math>L_1 \in</math> '''P''' .
 }}
-{{cwiczenie|10||
+{{cwiczenie|5||
-Skonstruuj maszynę Turinga akceptującą słowo <math>\displaystyle u=1^n</math> w dokładnie <math>\displaystyle n^2</math> krokach. Jak zmodyfikować konstrukcję maszyny, aby akceptowała słowo <math>\displaystyle u</math> dokładnie w <math>\displaystyle 2^n</math> krokach?
+Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
-}}
+<math>\mathcal{NMT}</math> akceptującej język:
+<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\}</math></center>
-{{cwiczenie|11||
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{NMT}</math> aby udowodnić, że
-Wypisz dokładnie wszystkie elementy składowe maszyn Turinga
+<math>L_2 \in</math> '''NP''' .<br>
-rozpoznających języki zadane gramatykami:
-# <math>\displaystyle S\rightarrow AbC</math>  ,  <math>\displaystyle A\rightarrow
-aAb|1</math>, <math>\displaystyle C\rightarrow bCc|1</math>
-# <math>\displaystyle S\rightarrow ABACA\quad , \quad A\rightarrow Aa|a \quad,\quad B\rightarrow bb|b\quad ,\quad C\rightarrow c|1.</math>
+''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>w</math>
+przeprowadź weryfikację w trzech
+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>.
 }}
-{{cwiczenie|12||
-Wykaż (podając ideę kontrukcji), że dla maszyn Turinga <math>\displaystyle TM_1</math>, <math>\displaystyle TM_2</math>
-istnieje maszyna Turinga <math>\displaystyle \mathcal{M}</math> rozpoznająca język:
-<center><math>\displaystyle  L(
-\mathcal{M})=\left\{uv\; : \; u\in L(TM_1), v\in L(TM_2)\right\}.
-</math></center>
-}}
+<center>ZADANIA DOMOWE</center>
-{{cwiczenie|13||
-Czy któraś z poniższych list słów ma własność Posta?
-# <center><math>\displaystyle
-(u_1,v_1)=\left [ \begin{array} {c} a\\a^2 b\end{array} \right]\; ,\;
-(u_2,v_2)=\left [ \begin{array} {c} ba^2\\a^2 \end{array} \right]
-</math></center>
-# <center><math>\displaystyle
-(u_1,v_1)=\left [ \begin{array} {c} a^b\\a \end{array} \right]\; ,\;
-(u_2,v_2)=\left [ \begin{array} {c} a\\b a^2 \end{array} \right]
-</math></center>
-# <center><math>\displaystyle
-(u_1,v_1)=\left [ \begin{array} {c} aaa\\a \end{array} \right], (u_2,v_2)=\left [ \begin{array} {c} b\\b a \end{array} \right], (u_3,v_3)=\left [ \begin{array} {c} bb\\b \end{array} \right], (u_4,v_4)=\left [ \begin{array} {c} ba\\ab \end{array} \right]
-</math></center>
+{{cwiczenie|6||
+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>d_1=\sharp s_0 1^n \sharp</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>n</math>.<br>
+''Podpowiedź:'' przeanalizuj ilość możliwych konfiguracji.
 }}
-{{cwiczenie|14||
+{{cwiczenie|7||
-Udowodnij Twierdzenie&nbsp;2.1 z wykładu:
+Uzasadnij, że funkcja <math>n^3</math> jest konstruowalna pamięciowo.
-'''Twierdzenie.''' Dla każdej gramatyki istnieje
-równoważna gramatyka tego samego typu taka, że każda produkcja, w
-której występuje symbol terminalny  <math>\displaystyle a  </math> , jest postaci  <math>\displaystyle v\longrightarrow a  </math> .
 }}

Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:46, 11 wrz 2023

Ćwiczenia 13

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia