Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 1: | Linia 1: | ||
== Ćwiczenia == | == Ćwiczenia == | ||
{{cwiczenie|1 [Liczby pierwsze]|Ćwiczenie 1|W tym ćwiczeniu <math> K_U (n) </math> oznacza złożoność Kołmogorowa binarnego zapisu liczby utożsamiamy liczby <math> n </math>. | {{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 utożsamiamy liczby <math> n </math>. | ||
Przyjmujemy więc <math> |n| = \lfloor \log_2 n \rfloor + 1 </math>. Mamy więc zawsze szacowanie <math> K_U (n) \leq \log_2 n + C, </math> dla pewnej stałej <math> C</math>. | 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ą 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ą 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>. | ||
Wersja z 16:45, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Liczby pierwsze]
{{{3}}}
Ćwiczenie 2 [Liczby losowe]
{{{3}}}
