Języki, automaty i obliczenia/Ćwiczenia 13: Złożoność obliczeniowa.: Różnice pomiędzy wersjami
Linia 91: | Linia 91: | ||
{{cwiczenie|4|| | {{cwiczenie|4|| | ||
Zadanie domowe | Zadanie domowe - cwiczenie 6 - 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: | ||
<center><math>\displaystyle | <center><math>\displaystyle | ||
Linia 101: | Linia 101: | ||
{{cwiczenie|5|| | {{cwiczenie|5|| | ||
Zadanie domowe | 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>\displaystyle \mathcal{NMT}</math> akceptującej język: | ||
<center><math>\displaystyle | <center><math>\displaystyle |
Wersja z 16:44, 3 wrz 2006
Ćwiczenia 13
Ćwiczenie 1
W trakcie wykładu rozważaliśmy język
wykazując, że NP .
Uzasadnij, że takżeĆwiczenie 2
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 3
Uzasadnij, że funkcja jest konstruowalna pamięciowo.
Ćwiczenie 4
Zadanie domowe - cwiczenie 6 - do wykładu 12 polegało na konstrukcji maszyny Turinga akceptującej język:
Zmodyfikuj, ewentualnie, tę konstrukcję , aby udowodnić P .
Ćwiczenie 5
Zadanie domowe - cwiczenie 7 - 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 6
Uzasadnij, że jeśli funkcja jest konstruowalna pamięciowo, to obliczenie z definicji
konstruowalności pamięciowej (tzn. ,
) następuje w co najwyżej krokach, gdzie jest pewną
stałą niezależną od .
Podpowiedź: przeanalizuj ilość możliwych konfiguracji.
Ćwiczenie 7
Uzasadnij, że funkcja jest konstruowalna pamięciowo.