Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 1: | Linia 1: | ||
== Ćwiczenia == | == Ćwiczenia == | ||
{{cwiczenie|1 [Liczby pierwsze]|Ćwiczenie 1|W tym ćwiczeniu utożsamiamy | {{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>. | ||
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>. | |||
: Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością). | : 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>. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
| Linia 14: | Linia 15: | ||
: 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ą). | |||
}} | |||
{{cwiczenie|2 [Liczby losowe]|Ćwiczenie 2|Wyjaśnij następujący pozorny paradoks. | |||
Z poprzedniego ćwiczenia wiemy, że prawie wszystkie liczby postaci <math> n = p^k </math> (gdzie <math> p </math> jest pierwsze) nie są losowe. Stąd łatwo dalej wydedukować, że spełniają <math> K_U (n) < \log_2 n</math>. (Dlaczego ?) | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Z nielosowości wynika <math> K_U (n) \leq \log_2 n</math>. Równość mogłaby ewentualnie zachodzić dla <math>n</math> będących potęgami dwójki, ale łatwo widzieć, że | |||
<center><math> K_U (2^k) \leq K_U (k) + C \leq \lfloor \log_2 k \rfloor + 1 + C < k, | |||
</math></center> | |||
dla prawie wszystkich <math> k</math>. | |||
</div> | |||
</div> | |||
Z kolei każdą liczbę złożoną można przedstawić <math> n = a_1 \cdot \ldots \cdot a_m, </math> gdzie każde <math> a_i </math> jest postaci <math> {p_i}^{k_i} </math>. | |||
}} | }} | ||
Wersja z 16:39, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Liczby pierwsze]
{{{3}}}
Ćwiczenie 2 [Liczby losowe]
{{{3}}}
