Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 24: | Linia 24: | ||
{{cwiczenie|2 [Liczby losowe]|Ćwiczenie 2|Wyjaśnij następujący pozorny paradoks. | {{cwiczenie|2 [Liczby losowe]|Ćwiczenie 2|Wyjaśnij następujący pozorny paradoks. | ||
Z poprzedniego ćwiczenia wiemy, że jedynymi liczbami losowymi mogą być liczby postaci 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 ?) | Z uwagi poprzedzającej definicję [[Teoria informacji/TI Wykład 13#random|losowości]] wiemy, że przy pewnym wyborze maszyny uniwersalnej, istnieje nieskończenie wiele liczb losowych. (Dlaczego ?) | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | |||
<div class="mw-collapsible-content" style="display:none"> | |||
Wiemy, że dla każdej maszyny uniwersalnej <math> U,</math> istnieje nieskończenie wiele słów losowych. Gdyby prawie wszystkie te słowa zaczynały się od 0, możemy wziąć maszynę <math> U',</math> która działa tak jak <math> U,</math> | |||
tylko zamienia 0 i 1. | |||
Zastrzeżenie o wyborze maszyny jest jednak istotne, bo z drugiej strony moglibyśmy wziąć modyfikację <math> U,</math> która ,,przez ''default''" poprzedza wynik jedynką (o ile nie otrzymuje informacji, że ma tego nie robić), co automatycznie zmniejsza złożoność liczb o 1. | |||
</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. 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 mw-made=collapsible mw-collapsed"> | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Wersja z 17:25, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Liczby pierwsze]
{{{3}}}
Ćwiczenie 2 [Liczby losowe]
{{{3}}}
