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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Forys (dyskusja | edycje)
Forys (dyskusja | edycje)
Linia 2: Linia 2:




{{cwiczenie|3||
{{cwiczenie|1||
W trakcie wykładu rozważaliśmy język
W trakcie wykładu rozważaliśmy język
<center><math>\displaystyle  
<center><math>\displaystyle  
Linia 40: Linia 40:
</div></div>
</div></div>


{{cwiczenie|4||
{{cwiczenie|2||
Uzasadnij, że funkcja <math>\displaystyle s(n)=3n</math> jest konstruowalna pamięciowo.
Uzasadnij, że funkcja <math>\displaystyle s(n)=3n</math> jest konstruowalna pamięciowo.
}}
}}
Linia 64: Linia 64:
</div></div>
</div></div>


{{cwiczenie|5||
{{cwiczenie|3||
Uzasadnij, że funkcja <math>\displaystyle s(n)=3^n</math> jest konstruowalna pamięciowo.
Uzasadnij, że funkcja <math>\displaystyle s(n)=3^n</math> jest konstruowalna pamięciowo.
}}
}}
Linia 90: Linia 90:




{{cwiczenie|1||
{{cwiczenie|4||
Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga
Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga
<math>\displaystyle \mathcal{MT}</math> akceptującej język:
<math>\displaystyle \mathcal{MT}</math> akceptującej język:
Linia 100: Linia 100:
}}
}}


{{cwiczenie|2||
{{cwiczenie|5||
Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga
<math>\displaystyle \mathcal{NMT}</math> akceptującej język:
<math>\displaystyle \mathcal{NMT}</math> akceptującej język:
Linia 119: Linia 119:




{{cwiczenie|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>\displaystyle s(n)</math> jest konstruowalna pamięciowo, to obliczenie <math>\displaystyle 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>\displaystyle d_1=\sharp s_0 1^n \sharp</math>,
Linia 127: Linia 127:
}}
}}


{{cwiczenie|4||
{{cwiczenie|7||
Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo.
Uzasadnij, że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo.
}}
}}

Wersja z 16:43, 3 wrz 2006

Ćwiczenia 13

Ćwiczenie 1

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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L=\left\{3^k\: : \: k=i\cdot j } dla pewnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle i,j> 1\right\}, }

wykazując, że L NP .

Uzasadnij, że także
L P .
Wskazówka
Rozwiązanie

Ćwiczenie 2

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

Wskazówka
Rozwiązanie

Ćwiczenie 3

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

Wskazówka
Rozwiązanie


Ćwiczenie 4

Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga 𝒯 akceptującej język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle L_1=\left\{www\: : \: w\in \left\{\circ,\bullet,\star\right\}^*\right\}. }

Zmodyfikuj, ewentualnie, tę konstrukcję 𝒯, aby udowodnić L1 P .

Ćwiczenie 5

Zadanie domowe 2.2 do wykładu 12 polegało na konstrukcji niedeterministycznej maszyny Turinga 𝒩𝒯 akceptującej język:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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\}. }

Zmodyfikuj, ewentualnie, tę konstrukcję 𝒩𝒯 aby udowodnić, że L2 NP .

Podpowiedź: wykorzystaj konstrukcję z wyrocznią. Dla słowa wejściowego w przeprowadź weryfikację w trzech etapach: konstrukcja słów w1,,wn, gdzie n<|w| (wyrocznia), sklejanie, weryfikacja, czy w=w1w1w2w2wnwn.


ZADANIA DOMOWE


Ćwiczenie 6

Uzasadnij, że jeśli funkcja s(n) jest konstruowalna pamięciowo, to obliczenie d1*d2 z definicji konstruowalności pamięciowej (tzn. d1=s01n, d2=s11s(n)w) następuje w co najwyżej c2s(n) krokach, gdzie c jest pewną stałą niezależną od n.
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.

Ćwiczenie 7

Uzasadnij, że funkcja n3 jest konstruowalna pamięciowo.