Teoria informacji/TI Ćwiczenia 13: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Niwinski (dyskusja | edycje)
214 edycji
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
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  [[Teoria informacji/TI Wykład 13#random|definicję losowości]] wiemy, że przy pewnym wyborze maszyny uniwersalnej, istnieje nieskończenie wiele liczb losowych. (Dlaczego ?)
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 30: Linia 30:
tylko zamienia 0 i 1.
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.
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>
</div>
</div>
Linia 49: Linia 49:
</div>
</div>
</div>
</div>
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe -- np. przez podanie dalszych warunków, które wykluczają losowość.
'''Problem'''. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.


}}
}}
Linia 63: Linia 63:
(tzn. <math> R_M </math> jest grafem funkcji częściowej).
(tzn. <math> R_M </math> jest grafem funkcji częściowej).


Dowieść, że nie jest możliwe, by dla nieskończenie wielu <math>  \langle x,y \rangle \in R_M </math>,
Dowiedź, że nie jest możliwe, by dla nieskończenie wielu <math>  \langle x,y \rangle \in R_M </math>,
zachodziło  
zachodziło  
<center><math>  
<center><math>  

Wersja z 12:06, 20 wrz 2006

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}


Ćwiczenie 2 [Liczby losowe]

{{{3}}}

Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów x,y, jest
⟨x,y⟩=x10x20…xm−10xm1y

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga M, tzn. RM={M(w):w∈{0,1}*}, jest zbiorem par, przy czym

(i) ⟨x,y⟩∈RM⟹|x|=|y|,

(ii) ⟨x,y⟩,⟨x,y′⟩∈RM⟹y=y′ (tzn. RM jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu ⟨x,y⟩∈RM, zachodziło

(K(y)≥|y|)∧(K(x)≤f(|x|))

gdzie jest funkcją taką, że (n−f(n))→∞.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_13&oldid=54407”