Teoria informacji/TI Ćwiczenia 14: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Niwinski (dyskusja | edycje)
214 edycji
Niwinski (dyskusja | edycje)
214 edycji
Linia 33: Linia 33:
</div>
</div>
}}
}}


{{definicja|[Test]|test|Funkcję <math>\delta : \{ 0,1 \}^* \to N </math> nazwiemy '''testem''', jesli dla każdych <math>m,n, </math>  
{{definicja|[Test]|test|Funkcję <math>\delta : \{ 0,1 \}^* \to N </math> nazwiemy '''testem''', jesli dla każdych <math>m,n, </math>  
<center><math>
<center><math>
\frac{|\{ w \in \{ 0,1 \}^n : \delta (w) \geq m \} |}{2^n} \leq \frac{1}{2^m}
\frac{|\{ w \in \{ 0,1 \}^n : \delta (w) \geq m \} |}{2^n} \leq \frac{1}{2^m}
Linia 42: Linia 43:
Zauważmy, że dla każdego <math>w,</math> istnieje co najwyżej skończenie wiele <math>m, </math> takich że <math> \delta (w) \geq m </math>.  Intuicyjnie, funkcja <math> \delta (w)</math> wskazuje, jak bardzo słowo <math>w</math> ,,odbiega od normy". Warunek stwierdza, że takich ciągów nie może być zbyt wiele (w przeciwnym razie stanowiłyby normę).  
Zauważmy, że dla każdego <math>w,</math> istnieje co najwyżej skończenie wiele <math>m, </math> takich że <math> \delta (w) \geq m </math>.  Intuicyjnie, funkcja <math> \delta (w)</math> wskazuje, jak bardzo słowo <math>w</math> ,,odbiega od normy". Warunek stwierdza, że takich ciągów nie może być zbyt wiele (w przeciwnym razie stanowiłyby normę).  


{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2|  
{{cwiczenie|2 [Uniwersalny test Martina-Lofa]|Ćwiczenie 2|
: Niech <math>Z = \{ \delta_0 , \delta_1 , \ldots  \} </math> będzie przeliczalną rodziną testów. Dowiedź, że funkcja  określona wzorem  
 
Niech <math>Z = \{ \delta_0 , \delta_1 , \ldots  \} </math> będzie przeliczalną rodziną testów.  
 
:Dowiedź, że funkcja  określona wzorem  
<center><math>
<center><math>
\delta^Z (w) = \max \{ \delta_n (w) - n : n \geq 0 \}
\delta^Z (w) = \max \{ \delta_n (w) - n : n \geq 0 \}
Linia 49: Linia 53:
jest testem.
jest testem.


Interesujący jest zwłaszcza przypadek, kiedy funkcja <math>\delta^Z </math> sama należy do rodziny <math>Z </math>.


Interesujący jest przypadek, kiedy funkcja <math>\delta^Z </math> sama należy do rodziny <math>Z </math>.
Test <math> \delta</math> nazwiemy '''efektywnym''', jeśli istnieje maszyna Turinga <math>M_{\delta }</math>, która przyjmując na wejściu  parę <math>\langle w,m \rangle, </math>  
 
: Test <math> \delta</math> nazwiemy '''efektywnym''', jeśli istnieje maszyna Turinga <math>M_{\delta }</math>, która przyjmując na wejściu  parę <math>\langle w,m \rangle, </math>  
  jeśli <math> \delta (w) \geq m, </math> zatrzymuje się i daje odpowiedź '''TAK''';
  jeśli <math> \delta (w) \geq m, </math> zatrzymuje się i daje odpowiedź '''TAK''';
  jesli <math> \delta (w) < m, </math> daje odpowiedź '''NIE''', lub się zapętla.  
  jesli <math> \delta (w) < m, </math> daje odpowiedź '''NIE''', lub się zapętla.  

Wersja z 22:20, 25 sie 2006

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność Ω]

{{{3}}}


Definicja [Test]

Funkcję δ:{0,1}*→N nazwiemy testem, jesli dla każdych m,n,
|{w∈{0,1}n:δ(w)≥m}|2n≤12m

Zauważmy, że dla każdego w, istnieje co najwyżej skończenie wiele m, takich że δ(w)≥m. Intuicyjnie, funkcja δ(w) wskazuje, jak bardzo słowo w ,,odbiega od normy". Warunek stwierdza, że takich ciągów nie może być zbyt wiele (w przeciwnym razie stanowiłyby normę).

Ćwiczenie 2 [Uniwersalny test Martina-Lofa]

Niech Z={δ0,δ1,…} będzie przeliczalną rodziną testów.

Dowiedź, że funkcja określona wzorem
δZ(w)=max⁡{δn(w)−n:n≥0}

jest testem.

Interesujący jest zwłaszcza przypadek, kiedy funkcja δZ sama należy do rodziny Z.

Test δ nazwiemy efektywnym, jeśli istnieje maszyna Turinga Mδ, która przyjmując na wejściu parę ⟨w,m⟩, 

jeśli δ(w)≥m, zatrzymuje się i daje odpowiedź TAK;
jesli δ(w)<m, daje odpowiedź NIE, lub się zapętla.

Innymi słowy, zbiór {⟨w,m⟩:δ(w)≥m} jest rekurencyjnie przeliczalny, chociaż funkcja δ nie musi być rekurencyjna.

Zauważmy, że rodzina E wszystkich testów efektywnych jest przeliczalnie wiele. (Dlaczego ?)


Dowiedź, że δE jest testem efektywnym.
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_14&oldid=28231”