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

Wersja z 20:47, 19 sty 2007

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 2 [Liczby losowe]

{{{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 4: / Linia 4: @@
 Przyjmujemy więc <math> |n| = \lfloor \log_2 n \rfloor + 1 </math>. Mamy więc zawsze [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|szacowanie]] <math> K_U (n) \leq  \log_2 n + C, </math> dla pewnej stałej <math> C</math>.
-: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością). Dokładniej, <math> K_U (p) \leq \log_2 p - \alpha (p), </math> gdzie <math>\alpha </math> jest pewną funkcją, taką że <math>\alpha (n) \to \infty </math>.
+: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością). Dokładniej, <math> K_U (p) \leq \alpha (p), </math> gdzie <math>\alpha </math> jest pewną funkcją, taką że <math>\alpha (n) / \log_2 n \to \infty </math>.
 <div class="mw-collapsible mw-made=collapsible mw-collapsed">
 <div class="mw-collapsible-content" style="display:none">
 Wykorzystaj twierdzenie, że gęstość liczb pierwszych jest
-<math> \approx \frac{n}{\log n} </math>. Dla naszych celów istotne jest, że
+<math> \approx \frac{\log n}{n} </math>. Dla naszych celów istotne jest, że
 ta gęstość szacuje się przez funkcję <math> f</math>, taką że
 <math> \frac{f(n)}{n} \to 0.</math>