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

Wersja z 21:09, 16 gru 2009

Ćwiczenie 1 [Oszacowanie]

Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania jak we Wniosku. Dowieść, że zachodzi słabsze oszacowanie

K_{U} (x) \leq 2 \log | x | + | x | + c_{U}

dla pewnej stałej $c_{U}$ .

Ćwiczenie 2 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów

x, y

, jest

⟨ x, y ⟩ = x_{1} 0 x_{2} 0 \dots x_{m - 1} 0 x_{m} 1 y

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga $M$ , tzn. $R_{M} = {M (w) : w \in {0, 1}^{*}}$ , jest zbiorem par, przy czym

(i) $⟨ x, y ⟩ \in R_{M} ⟹ | x | = | y |$ ,

(ii) $⟨ x, y ⟩, ⟨ x, y^{'} ⟩ \in R_{M} ⟹ y = y^{'}$ (tzn. $R_{M}$ jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu $⟨ x, y ⟩ \in R_{M}$ , zachodziło

(K (y) \geq | y |) \land (K (x) \leq f (| x |))

gdzie jest funkcją taką, że $(n - f (n)) \to \infty .$

@@ Linia 1: / Linia 1: @@
 == Ćwiczenia ==
-{{cwiczenie|1 [Oszacowanie]|Ćwiczenie 1|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania
+{{cwiczenie|1 [Oszacowanie]|Ćwiczenie 1|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania jak we  [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|Wniosku]]. Dowieść, że zachodzi słabsze oszacowanie
-jak we  [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|Wniosku]]. Dowieść, że zachodzi słabsze oszacowanie
 <center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
@@ Linia 10: / Linia 9: @@
-{{cwiczenie|2 [Liczby pierwsze]|Ćwiczenie 2|Niech <math>  \mbox{bin } (n) </math> oznacza zapis binarny liczby
+{{cwiczenie|2 [Liczby pierwsze]|Ćwiczenie 2|Niech <math>  \mbox{bin } (n) </math> oznacza zapis binarny liczby naturalnej <math> n</math>. Powiemy, że liczba <math> n</math> jest losowa, jeśli ciąg <math>  \mbox{bin } (n) </math> jest [[Teoria informacji/TI Wykład 13#random|losowy]].
-naturalnej <math> n</math>. Powiemy, że liczba <math> n</math> jest losowa, jeśli ciąg <math>  \mbox{bin } (n) </math>
-jest [[Teoria informacji/TI Wykład 13#random|losowy]].
 : Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością).