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.

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

@@ Linia 1: / Linia 1: @@
 ==Ćwiczenia 13==
-{{cwiczenie|1.1||
+{{cwiczenie|1||
 W trakcie wykładu rozważaliśmy język
-<center><math>\displaystyle
+<center><math>
-L=\left\{3^k\: : \: k=i\cdot j  </math>  dla pewnych  <math>\displaystyle   i,j> 1\right\}
+L=\{3^k\ : : \ : k=i\cdot j\text{ dla pewnych } i,j> 1\}</math>,</center>
-</math></center>
-wykazując, że <math>\displaystyle L\in  </math> '''NP''' .
+wykazując, że <math>L\in</math> '''NP''' .
-Uzasadnij, że także <center><math>\displaystyle L\in  </math> '''P''' <math>\displaystyle  .</math></center>
+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">
-Zastanów się, ile maksymalnie trzeba wykonać mnożeń aby zweryfikować istnienie <math>\displaystyle i,j>1</math> dla których
+Zastanów się, ile maksymalnie trzeba wykonać mnożeń, aby zweryfikować istnienie <math>i,j>1</math>, dla których
-<math>\displaystyle k=i\cdot j</math>
+<math>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
+Sprawdzamy wszystkie możliwości. Musimy wykonać maksymalnie <math>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.
+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 cztero-taśmowa):
+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]].
-# Taśma nr <math>\displaystyle 1</math> jest tylko do odczytu. Mamy na niej słowo <math>\displaystyle 3^k</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.
-# 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>
+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>)
-# {{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>.
+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.
-# 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.
+W oczywisty sposób otrzymujemy, że ilość wymaganych kroków czasowych maszyny jest ograniczona przez wielomian (dla dużych <math>n</math>).
-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>)
+Dla małych <math>n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania.
-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.
+Zatem <math>L\in</math> '''P''' .
-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|1.2||
+{{cwiczenie|2||
-Uzasadnij że funkcja <math>\displaystyle s(n)=3n</math> jest konstruowalna pamięciowo.
+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">
-Przypomnij sobie uzasadnienie dla funkcji <math>\displaystyle 2n</math> z wykładu.
+Przypomnij sobie uzasadnienie dla funkcji <math>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 jedna dodatkową taśmę (oznaczmy taśmy przez <math>\displaystyle I</math> oraz <math>\displaystyle S</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 pamięciowej wymagane jest istnienie jedno-taśmowej deterministycznej maszyny Turinga. Konstruujemy maszynę <math>\displaystyle \mathcal{M}</math> według schematu
+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>.
-# Jeśli słowo wejściowe jest puste to stop.
+Po zakończeniu cyklu doszliśmy do konfiguracji <math>\sharp s_1 1^{3n} \sharp</math>, co było wymagane w definicji.
-# 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|1.3||
+{{cwiczenie|3||
-Uzasadnij że funkcja <math>\displaystyle s(n)=3^n</math> jest konstruowalna pamięciowo.
+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">
-Wykorzystaj konstruowalność pamięciową funkcji <math>\displaystyle g(n)=3n</math>.
+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>\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.
+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>\displaystyle 1</math> i zatrzymaj się. Inaczej wykonaj następny krok.
+# 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>\displaystyle 1^n</math> to odrzuć.
+# Jeśli słowo wejściowe jest inne niż <math>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>.
+# 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>\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> potraja się)
+# {{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>\displaystyle C</math> jest krótsze niż słowo na taśmie <math>\displaystyle I</math> wykonaj ponownie krok [[#prz.4|4]].
+# 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>\displaystyle S</math> zostało zaznaczone <math>\displaystyle 3^n</math>  komórek.
+# W tym momencie na taśmie <math>S</math> zostało zaznaczone <math>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>.
+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>\displaystyle \sharp s_1 1^{3^n} \sharp</math> co było wymagane w definicji konstruowalności pamięciowej.
-</div></div>
-{{cwiczenie|1.4||
+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
-Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:
+pamięciowej.
-<center><math>\displaystyle
-S\rightarrow aTb|b \quad, \quad T\rightarrow Ta|1
-</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">
-Zacznij od wypisania języka opisanego przez daną gramatykę.
 </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">
-Analizując postać gramatyki, dochodzimy do wniosku, że zadana
-maszyna ma rozpoznawać język postaci:
-<center><math>\displaystyle
-L=\left\{a^n b\: :\; n\geqslant 0\right\}
-</math></center>
-Jest to język regularny, więc rozpoznawany przez automat skończenie stanowy. Zatem do akceptacji tego języka wystarczy, aby maszyna przeszła taśmę z lewej strony do prawej według zasad:
-# Jeśli czytasz symbol <math>\displaystyle a</math> wypisz <math>\displaystyle a</math> i przejdź w prawo powtarzając ten krok. Jeśli czytasz <math>\displaystyle b</math> przejdź w prawo i wykonaj krok następny.
+{{cwiczenie|4||
-# Jeśli jesteś na ograniczniku to akceptuj, inaczej odrzuć.
+Zadanie domowe - cwiczenie 6 -  do wykładu 12 polegało na konstrukcji maszyny Turinga
+<math>\mathcal{MT}</math> akceptującej język:
-</div></div>
+<center><math>
+L_1=\left\{www\ : : \ : w\in \left\{\circ,\bullet,\star\right\}^*\right\}</math></center>
-{{cwiczenie|1.5||
-Przedstaw ideę działania maszyny Turinga rozpoznającej język
-<center><math>\displaystyle
-L=\left\{a^n b^{2n} c^{3n} \;:\; n>1\right\}
-</math></center>
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{MT}</math>, aby udowodnić <math>L_1 \in</math> '''P''' .
 }}
-<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">
+{{cwiczenie|5||
-Wykorzystaj kilka taśm oraz konstruowalność pamięciową.
+Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
-</div></div>
+<math>\mathcal{NMT}</math> akceptującej język:
+<center><math>
-<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">
+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>
-Idea działania poszukiwanej maszyny (cztero taśmowej) jest następująca:
-# Sprawdź czy słowo wjeściowe <math>\displaystyle w</math> zawiera jako pierwszy symbol <math>\displaystyle a</math>. Jeśli nie odrzuć.
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{NMT}</math> aby udowodnić, że
-# Skopiuj najdłuższy prefiks słowa wejściowego <math>\displaystyle w</math> postaci <math>\displaystyle a^k</math> na taśmę nr dwa.
+<math>L_2 \in</math> '''NP''' .<br>
-# Korzystając z konstruowalności pamięciowej funkcji <math>\displaystyle 2k</math> oraz <math>\displaystyle 3k</math> wypisz słowo <math>\displaystyle b^{2k}</math> na taśmie nr <math>\displaystyle 3</math> oraz słowo <math>\displaystyle c^{3k}</math> na taśmie nr <math>\displaystyle 4</math>.
-# Dopisz słowo z taśmy nr <math>\displaystyle 3</math> i <math>\displaystyle 4</math> do słowa na taśmie nr <math>\displaystyle 2</math>. W tym momencie na taśmie nr <math>\displaystyle 2</math> znajduje się słowo <math>\displaystyle a^k b^{2k} c^{3k}</math>.
-# Porównaj słowo z taśmy nr <math>\displaystyle 2</math> ze słowem <math>\displaystyle w</math>. Jeśli są identyczne to akceptuj.
-</div></div>
-{{cwiczenie|1.6||
-W trakcie wykładu rozważaliśmy zamkniętość klas języków w klasyfikacji Chomsky'ego ze względu na różne działania. Podaj uzasadnienie (ideę konstrukcji) następującego faktu:
-Dla dowolnych maszyn Turinga <math>\displaystyle TM_1</math>, <math>\displaystyle TM_2</math> istnieje maszyna <math>\displaystyle \mathcal{M}</math> o własności:
-# <math>\displaystyle  L( \mathcal{M})=L(TM_1)\cup L(TM_2) </math>
-# <math>\displaystyle  L( \mathcal{M})=L(TM_1)\cap L(TM_2) </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>.
 }}
-<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">
-Wykonaj odpowiednią symulację maszyn <math>\displaystyle TM_1</math> oraz <math>\displaystyle TM_2</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">
-'''(Ad. 1)''' Konstruujemy maszynę dwu-taśmową która działa według zasady:
-# Kopiuj słowo wejściowe na taśmę nr 2. Symuluj kolejno jeden krok czasowy <math>\displaystyle TM_1</math> na taśmie <math>\displaystyle 1</math> i jeden krok <math>\displaystyle TM_2</math> na taśmie <math>\displaystyle 2</math>.
-# Jeśli któraś z maszyn zaakceptowała to akceptuj.
-'''(Ad. 2)''' Konstrukcja jest niemalże identyczne. Jedynie w kroku (2) akceptujemy gdy obie maszyny zaakceptowały. Ponieważ może to się stać w różnych krokach czasowych, w momencie gdy jedna z maszyn zaakceptuje, kończymy jej symulację i symulujemy tylko drugą aż do momentu gdy zaakceptuje (o ile to nastąpi).
-</div></div>
-{{cwiczenie|1.7||
-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^2 \\ a^2 b\end{array} \right]\;
-,\; (u_2,v_2)=\left [
-\begin{array} {c} b^2 \\ ba
-\end{array} \right]\; ,\; (u_3,v_3)=\left [ \begin{array} {c} ab^2 \\ b\end{array} \right]
-</math></center>
-# <center><math>\displaystyle
-(u_1,v_1)=\left [ \begin{array} {c} a \\ b^2\end{array} \right]\; ,\;
-(u_2,v_2)=\left [
-\begin{array} {c}
-a^2
-\\b
-\end{array} \right]
-</math></center>
-# <center><math>\displaystyle
-(u_1,v_1)=\left [ \begin{array} {c} ba \\ abab\end{array} \right]\;
-,\; (u_2,v_2)=\left [
-\begin{array} {c}
-b
-\\a
-\end{array} \right]\;,\;
-(u_3,v_3)=\left [
-\begin{array} {c}
-aba
-\\b
-\end{array} \right]\;,\;
-(u_4,v_4)=\left [
-\begin{array} {c}
-aa
-\\a
-\end{array} \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">
-'''(Ad. 1)''' Rozważmy ciąg indeksów <math>\displaystyle (1,2,1,3)</math>. Otrzymujemy:
-<center><math>\displaystyle
-\left [ \begin{array} {c} a^2 \\ a^2 b\end{array} \right] \left
-[\begin{array} {c} b^2 \\ ba\end{array} \right] \left [
-\begin{array} {c} a^2 \\ a^2 b\end{array} \right] \left [
-\begin{array} {c} ab^2 \\ b\end{array} \right]
-=\left [ \begin{array} {c} a^2 b^2 a^2 ab^2\\ a^2 b ba a^2 b b
-\end{array} \right]=\left [ \begin{array} {c} a^2 b^2 a^3 b^2\\ a^2 b^2 a^3 b^2
-\end{array} \right]
-</math></center>
-Zatem własność Posta zachodzi dla tej listy.
-'''(Ad. 2)''' Dany ciąg nie ma własności Posta. bez względu na kolejność indeksów pierwsze ze słów zawsze jest postaci <math>\displaystyle a^k</math> a drugi <math>\displaystyle b^j</math> dla pewnych <math>\displaystyle k,j>0</math>. Ale zawsze <math>\displaystyle a^k \neq b^j</math> czyli własność Posta nie może zachodzić.
-'''(Ad. 3)''' Rozważmy ciąg indeksów <math>\displaystyle (4,2,3,2,3,1,1)</math>.
-Zestawiając zadane pary słów w tej kolejności otrzymujemy:
-<center><math>\displaystyle
-\left [\begin{array} {c} aa\\a\end{array} \right] \left [
-\begin{array} {c} ba \\ abab\end{array} \right]
-\left [ \begin{array} {c} ba \\ abab\end{array} \right] \left [
-\begin{array} {c} b\\a \end{array} \right] \left [
-\begin{array} {c} aba \\b \end{array} \right] \left [
-\begin{array} {c} b\\a \end{array} \right]
-\left [\begin{array} {c} aa\\a\end{array} \right]
-</math></center>
-<center><math>\displaystyle
-= \left [\begin{array} {c}
-aabababababaa\\aabababababaa\end{array} \right]
-</math></center>
-W ten sposób wykazaliśmy, że własność Posta zachodzi.
-</div></div>
-{{cwiczenie|1.8||
-W definicji problemu Posta zakłada się, że alfabet <math>\displaystyle \mathcal{A}</math>
-zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. <math>\displaystyle \mathcal{A}=\left\{1\right\}</math>) problem Posta jest problemem rozstrzygalnym.
-}}
-<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">
-Rozważ dwa przypadki, zależnie od tego czy lista zawiera tylko pary słów postaci <math>\displaystyle (a^k,a^j)</math>, gdzie <math>\displaystyle k>j</math> (lub tylko <math>\displaystyle k<j</math>) czy też jeszcze jakieś inne pary słów.
-</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">
-Rozważmy listę par słów <math>\displaystyle (u_1,v_1),\dots, (u_n,v_n)</math> nad alfabetem
-<math>\displaystyle \mathcal{A}</math>. Przedstawimy algorytm sprawdzający czy lista ma
-własność Posta.
-# Jeśli lista zawiera parę <math>\displaystyle (1^k,1^k)</math> to mamy własność Posta.
-# Jeśli jedyne pary to takie w których <math>\displaystyle (u_i,v_i)=(1^{k_i},1^{l_i})</math> oraz <math>\displaystyle k_i>l_i</math> (lub <math>\displaystyle k_i<l_i</math>) dla
-<math>\displaystyle i=1,\dots,n</math> to własność posta nie jest spełniona (słowo dane przez
-katenację dowolnych <math>\displaystyle u_i</math> zawsze zawiera więcej (odp. mniej) symboli
-niż odpowiadająca mu katenacja słow <math>\displaystyle v_i</math> )
-# W ostatnim przypadku istnieją indeksy <math>\displaystyle i,j</math> takie, że
-<center><math>\displaystyle (u_i,v_i)=(1^k,1^l)\quad , \quad (u_j,v_j)=(1^p,1^q) </math></center>
-przy czym <math>\displaystyle k<l</math> i <math>\displaystyle p>q</math>. W tej sytuacji zachodzi własność Posta. Uzasadnienie jest następujące. Biorąc ciąg:
-<center><math>\displaystyle \begin{array} {c c c} (\underbrace{i\;,\; \dots\;,\;i}&,&\underbrace{j\;,\;\dots\;,\;j})\\ {\displaystyle p-q \mbox{ razy}\displaystyle && {\displaystyle l-k \mbox{ razy}\displaystyle \end{array}</math></center>
-Otrzymujemy słowa:
-<center><math>\displaystyle
-\left [ \begin{array} {c} u_1\\ v_1 \end{array} \right ]^{p-q} \left [
-\begin{array} {c} u_2\\ v_2 \end{array} \right ]^{l-k}=
-\left [ \begin{array} {c} 1^k\\ 1^l \end{array} \right ]^{p-q}\left [
-\begin{array} {c} 1^p\\ 1^1 \end{array} \right ]^{l-k}=
-\left [ \begin{array} {c} 1^{k(p-q)}\\1^{l(p-q)}\end{array} \right ]
-\left [
-\begin{array} {c}1^{p (l-k)}\\
-^{q(l-k)} \end{array} \right ]
-</math></center>
-<center><math>\displaystyle
-=\left [ \begin{array} {c} 1^{kp-kq+pl-pk}\\1^{lp-lq+ql-qk}
-\end{array} \right ]=\left [ \begin{array} {c} 1^{lp-kq}\\1^{lp-kq}
-\end{array} \right ]
-</math></center>
-Dla danej listy, można rostrzygnąć w czasie wielomianowym który z przypadków (1), (2), (3) zachodzi. Otrzymaliśmy rostrzygalność problemu Posta dla tej sytuacji.
-</div></div>
 <center>ZADANIA DOMOWE</center>
-{{cwiczenie|2.1||
-Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga
-<math>\displaystyle \mathcal{MT}</math> akceptującej język:
-<center><math>\displaystyle
-L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}
-</math></center>
-Zmodyfikuj, ewentualnie, tę konstrukcję <math>\displaystyle \mathcal{MT}</math> aby udowodnić <math>\displaystyle L_1 \in  </math> '''P''' .
-}}
-{{cwiczenie|2.2||
-Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
-<math>\displaystyle \mathcal{NMT}</math> akceptującej język:
-<center><math>\displaystyle
-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>
-Zmodyfikuj, ewentualnie, tę konstrukcję <math>\displaystyle \mathcal{NMT}</math> aby udowodnić, że
-<math>\displaystyle L_2 \in  </math> '''NP''' .<br>
-''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>\displaystyle w</math>
-przeprowadź weryfikację w trzech
-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>.
-}}
-{{cwiczenie|2.3||
+{{cwiczenie|6||
-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 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>\displaystyle d_1=\sharp s_0 1^n \sharp</math>,
+konstruowalności pamięciowej (tzn. <math>d_1=\sharp s_0 1^n \sharp</math>,
-<math>\displaystyle d_2=\sharp s_1 1^{s(n)} w \sharp</math>) następuję w conajwyżej <math>\displaystyle c 2^{s(n)}</math> krokach gdzie <math>\displaystyle c</math> jest pewną
+<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>\displaystyle n</math>.<br>
+stałą niezależną od <math>n</math>.<br>
 ''Podpowiedź:'' przeanalizuj ilość możliwych konfiguracji.
 }}
-{{cwiczenie|2.4||
+{{cwiczenie|7||
-Uzasadnij że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo.
+Uzasadnij, że funkcja <math>n^3</math> jest konstruowalna pamięciowo.
-}}
-{{cwiczenie|2.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?
-}}
-{{cwiczenie|2.6||
-Wypisz dokładnie wszystkie elementy składowe maszyn Turinga
-rozpoznających języki zadane gramatykami:
-# <math>\displaystyle S\rightarrow AbC</math>  ,  <math>\displaystyle A\rightarrow
-aAb|\varepsilon</math>, <math>\displaystyle C\rightarrow bCc|\varepsilon</math>
-# <math>\displaystyle S\rightarrow ABACA\quad , \quad A\rightarrow Aa|a \quad,\quad B\rightarrow bb|b\quad ,\quad C\rightarrow c|\varepsilon</math>
-}}
-{{cwiczenie|2.7||
-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>
-}}
-{{cwiczenie|2.8||
-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|2.9||
-Udowodnij Twierdzenie&nbsp;2.1 z wykładu:
-'''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> .
 }}