Teoria informacji/TI Ćwiczenia 13

From Studia Informatyczne

Ć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 \mbox{bin } (n) oznacza zapis binarny liczby naturalnej n. Powiemy, że liczba n jest losowa, jeśli ciąg \mbox{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 (\mbox{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
\langle x,y \rangle = x_1 0 x_2 0 \ldots 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) \langle x,y \rangle \in R_M \, \Longrightarrow \, |x| = |y|,

(ii) \langle x,y \rangle , \langle x,y' \rangle\in R_M \, \Longrightarrow \,  y = y' (tzn. R_M jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu \langle x,y \rangle \in R_M, zachodziło

( K(y) \geq |y|) \; \wedge \; ( K(x) \leq f (|x|) )

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