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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
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 postaci <math> n^k </math>, gdzie <math> k \geq 2 </math>, nie są losowe (poza co najwyżej skończoną ilością).
  
  

Wersja z 20:45, 16 gru 2009

Ćwiczenia

Ćwiczenie 1 [Liczby pierwsze]

{{{3}}}

Ćwiczenie 2 [Oszacowanie]

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

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

dla pewnej stałej .

Ć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