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 4: / Linia 4: @@
 {{cwiczenie|1||
 W trakcie wykładu rozważaliśmy język
-<center><math>\displaystyle
+<center><math>
-L=\{3^k\ : : \ : k=i\cdot j\text{ dla pewnych } i,j> 1\},
+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 czterotaśmowa):
-# Taśma nr <math>\displaystyle 1</math> jest tylko do odczytu. Mamy na niej słowo <math>\displaystyle 3^k</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>\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>.
+# 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>\displaystyle 4</math> według kolejności taśm <math>\displaystyle 2,3,1</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>\displaystyle 4</math> czy <math>\displaystyle k=i\cdot j</math>. Jeśli tak, to akceptuj. Inaczej krok następny.
+# 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>\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>.
+# 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>\displaystyle 3</math> jest dłuższe niż <math>\displaystyle k</math>, to odrzuć. W przeciwnym przypadku przejdź do kroku [[#prz.3|3]].
+# 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>\displaystyle 2</math> (licznik 1) i <math>\displaystyle 3</math> (licznik 2) jako liczniki, a na taśmie <math>\displaystyle 4</math> wykonuj symulacje.
+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>\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>)
+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>\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.
+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>\displaystyle n</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>\displaystyle n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania.
+Dla małych <math>n</math> możemy zawsze rozbudować maszynę tak, aby akceptowała słowa bez żadnego testowania.
-Zatem <math>\displaystyle L\in   </math> '''P''' .
+Zatem <math>L\in</math> '''P''' .
 </div></div>
 {{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 jedną 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 jednotaśmowej deterministycznej maszyny Turinga.
-Konstruujemy maszynę <math>\displaystyle \mathcal{M}</math> według schematu:
+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>\displaystyle 1^n</math>, to odrzuć.
+# 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>\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).
+# 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>\displaystyle S</math>.
+# Kopiujemy słowo wejściowe na taśmę <math>S</math>.
-# Symulujemy maszynę <math>\displaystyle MT_4</math> na taśmie <math>\displaystyle S</math>.
+# Symulujemy maszynę <math>MT_4</math> na taśmie <math>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.
+# 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>\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>.
+# 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>\displaystyle \sharp s_1 1^{3n} \sharp</math>, co było wymagane w definicji.
+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 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>.
+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>\displaystyle \mathcal{N}</math> działa według schematu.
+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ę. W przeciwnym wypadku, 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> wzrasta trzykrotnie)
+# {{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)
+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>\displaystyle s_1\in S_F</math>.
+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
+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>
@@ Linia 92: / Linia 91: @@
 {{cwiczenie|4||
 Zadanie domowe - cwiczenie 6 -  do wykładu 12 polegało na konstrukcji maszyny Turinga
-<math>\displaystyle \mathcal{MT}</math> akceptującej język:
+<math>\mathcal{MT}</math> akceptującej język:
-<center><math>\displaystyle
+<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>\displaystyle \mathcal{MT}</math>, aby udowodnić <math>\displaystyle L_1 \in  </math> '''P''' .
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{MT}</math>, aby udowodnić <math>L_1 \in</math> '''P''' .
 }}
 {{cwiczenie|5||
 Zadanie domowe - cwiczenie 7 - do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
-<math>\displaystyle \mathcal{NMT}</math> akceptującej język:
+<math>\mathcal{NMT}</math> akceptującej język:
-<center><math>\displaystyle
+<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>\displaystyle \mathcal{NMT}</math> aby udowodnić, że
+Zmodyfikuj, ewentualnie, tę konstrukcję <math>\mathcal{NMT}</math> aby udowodnić, że
-<math>\displaystyle L_2 \in  </math> '''NP''' .<br>
+<math>L_2 \in</math> '''NP''' .<br>
-''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>\displaystyle w</math>
+''Podpowiedź:'' wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego <math>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>.
+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||
-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ępuje w co najwyż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|7||
-Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo.
+Uzasadnij, że funkcja <math>n^3</math> 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