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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 4: Linia 4:
 
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>.
 
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>.
  
: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością). Dokładniej, <math> K_U (p) \leq \alpha (p), </math> gdzie <math>\alpha </math> jest pewną funkcją, taką że <math>\frac{\alpha(n)}{\log_2 n} \to 0 </math>.
+
: Dowiedź, że liczby pierwsze nie są [[Teoria informacji/TI Wykład 13#random|losowe]] (poza co najwyżej skończoną ilością).  
 
<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 16: Linia 16:
 
: Dowiedź, że liczby postaci <math> p^k </math>, gdzie <math> p </math> jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).
 
: Dowiedź, że liczby postaci <math> p^k </math>, gdzie <math> p </math> jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).
  
: Dowiedź, że liczby złożone posiadające czynnik postaci <math> p^k </math>, gdzie <math> p </math> jest pierwsze a <math> k \geq 1 </math>, nie są losowe (poza co najwyżej skończoną ilością).
+
:
  
 
}}
 
}}

Wersja z 20:06, 16 gru 2009

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}


Ćwiczenie 2 [Liczby losowe]

{{{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