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

Aktualna wersja na dzień 22:14, 11 wrz 2023

Ćwiczenia

Ć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]

Niech

bin (n)

oznacza zapis binarny liczby naturalnej

n

. Powiemy, że liczba

n

jest losowa, jeśli ciąg

bin (n)

jest losowy.

Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością).

Wykorzystaj twierdzenie, że gęstość liczb pierwszych jest $\approx \frac{\log n}{n}$ . Dla naszych celów istotne jest, że ta gęstość szacuje się przez funkcję $f$ , taką że $\frac{f (n)}{n} \to 0$

Dowiedź, że liczby postaci

p^{k}

, gdzie

p

jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).

Dowiedź, że liczby postaci

n^{k}

, gdzie

k \geq 2

, nie są losowe (poza co najwyżej skończoną ilością).

Oszacuj z góry bezprefiksową złożoność liczb pierwszych tzn. $K_{U} (bin (p))$ .

Problem. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.

Ć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 [Liczby pierwsze]|Ćwiczenie 1|W tym ćwiczeniu <math> K_U (n) </math> oznacza [[Teoria informacji/TI Wykład 13#Kołmogorow|złożoność Kołmogorowa]] binarnego zapisu liczby <math> n </math>.
+{{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
-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>.
+<center><math>K_U (x) \leq 2 \log |x| + |x| + c_U
+</math></center>
+dla pewnej stałej <math>c_U</math>.
+}}
+{{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]].
+: Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością). }}
 <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
+ta gęstość szacuje się przez funkcję <math>f</math>, taką że
-<math> \frac{f(n)}{n} \to 0.</math>
+<math>\frac{f(n)}{n} \to 0</math>
 </div>
 </div>
-: Dowiedź, że liczby postaci <math> p^k </math>, gdzie <math> p </math> jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).
+: Dowiedź, że liczby postaci <math>p^k</math>, gdzie <math>p</math> jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).
-: Dowiedź, że liczby złożone posiadające czynnik postaci <math> p^k </math>, gdzie <math> p </math> jest pierwsze a <math> k \geq 1 </math>, nie są losowe (poza co najwyżej skończoną ilością).
+:Dowiedź, że liczby postaci <math>n^k</math>, gdzie <math>k \geq 2</math>, nie są losowe (poza co najwyżej skończoną ilością).
-}}
+Oszacuj z góry bezprefiksową złożoność liczb pierwszych tzn. <math>K_U (\mbox{bin } (p))</math>.
+'''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 [Liczby losowe]|Ćwiczenie 2|Wyjaśnij następujący pozorny paradoks.
-Z uwagi poprzedzającej  [[Teoria informacji/TI Wykład 13#random|definicję losowości]] wiemy, że przy pewnym wyborze maszyny uniwersalnej, istnieje nieskończenie wiele liczb losowych. (Dlaczego ?)
+{{cwiczenie|3 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math>x, y</math>, jest
-<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+<center><math>\langle x,y \rangle = x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
-<div class="mw-collapsible-content" style="display:none">
+</math></center>
-Wiemy, że dla każdej maszyny uniwersalnej <math> U,</math> istnieje nieskończenie wiele słów losowych. Gdyby prawie wszystkie te słowa zaczynały się od 0, możemy wziąć maszynę <math> U',</math> która działa tak jak <math> U,</math>
+Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga <math>M</math>, tzn. <math>R_M = \{ M(w) : w \in \{ 0,1\}^* \}</math>, jest zbiorem par, przy czym
-tylko zamienia 0 i 1.
-Zastrzeżenie o wyborze maszyny jest jednak istotne, bo z drugiej strony moglibyśmy wziąć modyfikację <math> U,</math> która ,,przez ''default''" poprzedza wynik jedynką (o ile nie otrzymuje informacji, że ma tego nie robić), co automatycznie zmniejsza złożoność liczb o 1.
+(i) <math>\langle x,y \rangle \in R_M \, \Longrightarrow \, |x| = |y|</math>,
-</div>
-</div>
-Z poprzedniego ćwiczenia wiemy, że jedynymi liczbami losowymi mogą być liczby postaci <math> n = p_1 \cdot \ldots \cdot p_k,</math> gdzie <math> p_1, \ldots , p_k,</math>  są różnymi liczbami pierwszymi. Wiemy także, że <math> K_U (p_i ) \leq \log_2 p_i - \alpha (p_i), </math> gdzie <math>\alpha </math> jest funkcją rozbieżną do <math>\infty </math>. Z drugiej strony <math> \log n = \log p_1 + \ldots + \log p_k </math>. Wydaje się, że program generujący liczbę <math> n </math> (tzn. takie <math> x ,</math> że <math> U(x) = n </math>) można otrzymać jako konkatenację programów generujących liczby <math> p_1, \ldots , p_k,</math> plus informacja (o stałym rozmiarze), że wyniki należy wymnożyć.
+(ii)  <math>\langle x,y \rangle , \langle x,y' \rangle\in R_M \, \Longrightarrow \,  y = y'</math>
+(tzn. <math>R_M</math> jest grafem funkcji częściowej).
-Czy to znaczy, że jednak nie ma liczb losowych?
+Dowiedź, że nie jest możliwe, by dla nieskończenie wielu <math> \langle x,y \rangle \in R_M</math>,
-<div class="mw-collapsible mw-made=collapsible mw-collapsed">
+zachodziło
-<div class="mw-collapsible-content" style="display:none">
+<center><math>
-Oczywiście jest problem z konkatenacją. Jeśli po prostu napiszemy <math> x y </math>, to zgubimy informację o tym, gdzie kończy się <math> x  </math>, a zaczyna <math>  y </math>. Przypuśćmy, że <math> x = x_1 \ldots x_m. </math> <math>y = y_1 \ldots y_n </math>. Odwracalną konkatenacją może być np.
+( K(y) \geq |y|) \; \wedge \; ( K(x) \leq f (|x|) )
-<center><math> x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y
-</math></center>
-co jednak wydłuża wynik o <math> |x|  </math>. Bardziej ekonomiczną realizacją jest
-<center><math> a_1 0 a_2 0 \ldots a_{\ell -1} 0 a_{\ell } 1 x y
 </math></center>
-gdzie <math> a_1 \ldots a_{\ell } </math> jest binarnym przedstawieniem liczby <math> |x|  </math>,
+gdzie jest funkcją taką, że <math>(n - f(n)) \to \infty </math>
-co jednak wydłuża wynik o <math> 2 \cdot \log |x|  </math>.
-</div>
-</div>
 }}

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

Aktualna wersja na dzień 22:14, 11 wrz 2023

Ćwiczenia

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia