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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
 
== Ćwiczenia ==
 
== Ćwiczenia ==
  
{{cwiczenie|1 [Oszacowanie]|Ćwiczenie 1|Jak zauważyliśmy, dla złożoności bezprefiksowej nie ma tak dobrego oszacowania
+
{{cwiczenie|1 [Oszacowanie]|Ćwiczenie 1|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 słabsze oszacowanie
jak we  [[Teoria informacji/TI Wykład 13#wniosek_identycznosc|Wniosku]]. Dowieść, że zachodzi słabsze oszacowanie
 
  
 
<center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
 
<center><math> K_U (x) \leq 2 \log |x| + |x| + c_U
Linia 10: Linia 9:
  
  
{{cwiczenie|2 [Liczby pierwsze]|Ćwiczenie 2|Niech <math>  \mbox{bin } (n) </math> oznacza zapis binarny liczby  
+
{{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]].  
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ą losowe (poza co najwyżej skończoną ilością).  
 
: Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością).  

Wersja z 21:09, 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 słabsze oszacowanie

dla pewnej stałej .


Ćwiczenie 2 [Liczby pierwsze]

{{{3}}}


Ćwiczenie 3 [Generowanie funkcji]

Przyjmujemy, że parą słów , jest

Przypuśćmy, że zbiór wartości obliczanych przez maszynę Turinga , tzn. , jest zbiorem par, przy czym

(i) ,

(ii) (tzn. jest grafem funkcji częściowej).

Dowiedź, że nie jest możliwe, by dla nieskończenie wielu , zachodziło

gdzie jest funkcją taką, że