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 uwagi poprzedzającej | Z uwagi poprzedzającej [[Teoria informacji/TI Wykład 13#random|definicję 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 mw-made=collapsible mw-collapsed"> | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
| Linia 39: | Linia 39: | ||
<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 | Oczywiście jest problem z konkatenacją. Jeśli po prostu napiszemy <math> x y </math>, to zgubimy informację o tym, gdzie kończy się <math> x </math>, a zaczyna <math> y </math>. Przypuśćmy, że <math> x = x_1 \ldots x_m. </math> <math>y = y_1 \ldots y_n </math>. Odwracalną konkatenacją może być np. | ||
<center><math> x_1 0 x_2 0 \ldots x_{m-1} 0 x_m 1 y | |||
</math></center> | |||
co jednak wydłuża wynik o <math> |x| </math>. Bardziej ekonomiczną realizacją jest | |||
<center><math> a_1 0 a_2 0 \ldots a_{\ell -1} 0 a_{\ell } 1 x y | |||
</math></center> | |||
gdzie <math> a_1 \ldots a_{\ell } </math> jest binarnym przedstawieniem liczby <math> |x| </math>, | |||
co jednak wydłuża wynik o <math> 2 \cdot \log |x| </math>. | |||
</div> | </div> | ||
</div> | </div> | ||
}} | }} | ||
Wersja z 17:56, 25 sie 2006
Ćwiczenia
Ćwiczenie 1 [Liczby pierwsze]
{{{3}}}
Ćwiczenie 2 [Liczby losowe]
{{{3}}}
