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
Niwinski (dyskusja | edycje)
214 edycji
Linia 1: Linia 1:
== Ćwiczenia ==
== Ćwiczenia ==


{{cwiczenie|1 [Liczby pierwsze]|Ćwiczenie 1|W tym ćwiczeniu <math> K_U (n) </math> oznacza [[Teoria informacji/TI Wykład 13#Kołmogorow|złożoność Kołmogorowa]] binarnego zapisu liczby <math> n </math>.
{{cwiczenie|1 [Oszacowanie]|Ćwiczenie 1|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania
Przyjmujemy więc <math> |n| = \lfloor \log_2 n \rfloor + 1 </math>. Mamy więc zawsze [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|szacowanie]] <math> K_U (n) \leq  \log_2 n + C, </math> dla pewnej stałej <math> C</math>.
jak we  [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|Wniosku]]. Dowieść, że zachodzi przynajmniej
 
<center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
</math></center>
dla pewnej stałej <math>c_U </math>.
}}
 
 
{{cwiczenie|2 [Liczby pierwsze]|Ćwiczenie 2|Niech <math> \mbox{bin } (n) </math> oznacza zapis binarny liczby
naturalnej <math> n</math>. Powiemy, że liczba <math> n</math> jest losowa, jeśli ciąg <math> \mbox{bin } (n) </math>  
jest [[Teoria informacji/TI Wykład 13#random|losowy]].  


: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością).  
: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością).  
Linia 18: Linia 28:
:Dowiedź, że liczby postaci <math> n^k </math>, gdzie <math> k \geq 2 </math>, nie są losowe (poza co najwyżej skończoną ilością).
:Dowiedź, że liczby postaci <math> n^k </math>, gdzie <math> k \geq 2 </math>, nie są losowe (poza co najwyżej skończoną ilością).


Oszacuj z góry bezprefiksową złożoność liczb pierwszych tzn. <math>K_U (\mbox{bin } (p)) </math>.


'''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 23: Linia 34:
}}
}}


{{cwiczenie|2 [Oszacowanie]|Ćwiczenie 2|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania
jak we  [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|Wniosku]]. Dowieść, że zachodzi przynajmniej
<center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
</math></center>
dla pewnej stałej <math>c_U </math>.
}}


{{cwiczenie|3 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math> x, y </math>, jest  
{{cwiczenie|3 [Generowanie funkcji]|Ćwiczenie 3|Przyjmujemy, że ''parą'' słów <math> x, y </math>, jest  

Wersja z 21:03, 16 gru 2009

Ćwiczenia

Ćwiczenie 1 [Oszacowanie]

Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania

jak we Wniosku. Dowieść, że zachodzi przynajmniej

KU(x)≤2log⁡|x|+|x|+cU

dla pewnej stałej cU.


Ćwiczenie 2 [Liczby pierwsze]

{{{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=75906”