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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 19: Linia 19:
  
  
 +
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.
 +
 +
}}
  
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.
+
{{cwiczenie|2 [Oszacowanie]|Ćwiczenie 2|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania
 +
jak we  [[Teoria informacji/TI Wykad 13#wniosek_identycznosc|Wniosku]]. Dowieść, że
  
 +
<center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
 +
</math></center>
 +
dla pewnej stałej <math>c_U </math>.
 
}}
 
}}
  
{{cwiczenie|2 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math> x, y </math>, jest  
+
{{cwiczenie|3 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math> x, y </math>, jest  
 
<center><math> \langle x,y \rangle = x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
 
<center><math> \langle x,y \rangle = x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
 
</math></center>
 
</math></center>

Wersja z 20:37, 16 gru 2009

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 2 [Oszacowanie]

Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania

jak we Wniosku. Dowieść, że

dla pewnej stałej .

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów , jest

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga , tzn. , jest zbiorem par, przy czym

(i) ,

(ii) (tzn. jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu , zachodziło

gdzie jest funkcją taką, że