Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 34: | Linia 34: | ||
</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ć. | |||
Czy to znaczy, że jednak nie ma liczb losowych? | |||
<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"> | ||
Oczywiście jest problem z konkatenacja. | |||
</div> | </div> | ||
</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>. | 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 17:41, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Liczby pierwsze]
{{{3}}}
Ćwiczenie 2 [Liczby losowe]
{{{3}}}
