Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami
Matiunreal (dyskusja | edycje) |
Matiunreal (dyskusja | edycje) |
||
Linia 317: | Linia 317: | ||
</div></div> | </div></div> | ||
==Zadania domowe== | ==2. Zadania domowe== | ||
{{cwiczenie||| | {{cwiczenie|2.1|| | ||
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 329: | Linia 329: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.2|| | ||
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 345: | Linia 345: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.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 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 353: | Linia 353: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.4|| | ||
Uzasadnij że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo. | Uzasadnij że funkcja <math>\displaystyle n^3</math> jest konstruowalna pamięciowo. | ||
}} | }} | ||
{{cwiczenie||| | {{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 | 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? | akceptowała słowo <math>\displaystyle u</math> dokładnie w <math>\displaystyle 2^n</math> krokach? | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.6|| | ||
Wypisz dokładnie wszystkie elementy składowe maszyn Turinga | Wypisz dokładnie wszystkie elementy składowe maszyn Turinga | ||
rozpoznających języki zadane gramatykami: | rozpoznających języki zadane gramatykami: | ||
Linia 371: | Linia 371: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.7|| | ||
Wykaż (podając ideę kontrukcji) że dla maszyn Turinga <math>\displaystyle TM_1</math>, <math>\displaystyle TM_2</math> | 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: | istnieje maszyna Turinga <math>\displaystyle \mathcal{M}</math> rozpoznająca język: | ||
Linia 379: | Linia 379: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.8|| | ||
Czy któraś z poniższych list słów ma własność Posta? | Czy któraś z poniższych list słów ma własność Posta? | ||
# <center><math>\displaystyle | # <center><math>\displaystyle | ||
Linia 398: | Linia 398: | ||
}} | }} | ||
{{cwiczenie||| | {{cwiczenie|2.9|| | ||
Udowodnij Twierdzenie 2.1 z wykładu: | Udowodnij Twierdzenie 2.1 z wykładu: | ||
Wersja z 08:39, 24 sie 2006
ĆWICZENIA 13
Ćwiczenie 1.1
W trakcie wykładu rozważaliśmy język
wykazując, że NP .
Uzasadnij, że takżeĆwiczenie 1.2
Uzasadnij że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 1.3
Uzasadnij że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 1.4
Skonstruuj maszynę Turinga rozpoznającą język zadany gramatyką:
Ćwiczenie 1.5
Przedstaw ideę działania maszyny Turinga rozpoznającej język
Ćwiczenie 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 , istnieje maszyna o własności:
Ćwiczenie 1.7
Czy któraś z poniższych list słów ma własność Posta?
Ćwiczenie 1.8
W definicji problemu Posta zakłada się, że alfabet zawiera co najmniej dwa elementy. Wykaż, że gdy to założenie nie jest spełnione (tzn. ) problem Posta jest problemem rozstrzygalnym.
2. Zadania domowe
Ćwiczenie 2.1
Zadanie domowe 2.1 do wykładu 12 polegało na konstrukcji maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję aby udowodnić P .
Ćwiczenie 2.2
Zadanie domowe 2.2 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 2.3
Uzasadnij, że jeśli funkcja jest konstruowalna pamięciowo to obliczenie z definicji
konstruowalności pamięciowej (tzn. ,
) następuję w conajwyżej krokach gdzie jest pewną
stałą niezależną od .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.
Ćwiczenie 2.4
Uzasadnij że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 2.5
Skonstruuj maszynę Turinga akceptującą słowo w dokładnie krokach. Jak zmodyfikować konstrukcję maszyny aby akceptowała słowo dokładnie w krokach?
Ćwiczenie 2.6
Wypisz dokładnie wszystkie elementy składowe maszyn Turinga rozpoznających języki zadane gramatykami:
- , ,
Ćwiczenie 2.7
Wykaż (podając ideę kontrukcji) że dla maszyn Turinga , istnieje maszyna Turinga rozpoznająca język:
Ćwiczenie 2.8
Czy któraś z poniższych list słów ma własność Posta?
Ćwiczenie 2.9
Udowodnij Twierdzenie 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 , jest postaci .