Teoria informacji/TI Ćwiczenia 13

Ć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}0x_{2}0\ldots x_{m-1}0x_{m}1y$

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 .$