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
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
Linia 7: Linia 7:
<math>r  </math>.
<math>r  </math>.


Liczbę <math>r  </math> nazwiemy ''rekurencyjnie aproksymowalną'' jesli jest granicą obliczalnego
Liczbę <math>r  </math> nazwiemy ''rekurencyjnie aproksymowalną'', jeśli jest granicą obliczalnego
ciągu liczb wymiernych, tzn. istnieje funkcja obliczalna <math> f : N \to N \times N </math>, taka że
ciągu liczb wymiernych, tzn. istnieje funkcja obliczalna <math> f : N \to N \times N </math>, taka że
<center><math>
<center><math>
Linia 36: Linia 36:




{{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''', jeśli 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}
</math></center>}}
</math></center>}}


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|

Wersja z 12:34, 20 wrz 2006

Ćwiczenia

Ćwiczenie 1 [Nieobliczalność Ω]

{{{3}}}


Definicja [Test]

Funkcję δ:{0,1}*→N nazwiemy testem, jeśli 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]

{{{3}}}
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_14&oldid=54434”