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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 11: Linia 11:
 
{{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]].  
 
{{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ą losowe (poza co najwyżej skończoną ilością).  
+
: Dowiedź, że liczby pierwsze nie są 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 29: Linia 29:
 
'''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ść.
  
}}
+
 
  
  

Aktualna wersja na dzień 21:02, 27 wrz 2020

Ć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]

Niech oznacza zapis binarny liczby naturalnej . Powiemy, że liczba jest losowa, jeśli ciąg jest losowy.
Dowiedź, że liczby pierwsze nie są losowe (poza co najwyżej skończoną ilością).
Dowiedź, że liczby postaci , gdzie jest liczbą pierwszą, nie są losowe (poza co najwyżej skończoną ilością).
Dowiedź, że liczby postaci , gdzie , nie są losowe (poza co najwyżej skończoną ilością).

Oszacuj z góry bezprefiksową złożoność liczb pierwszych tzn. .

Problem. Spróbuj określić, jakie własności muszą mieć liczby losowe - np. przez podanie dalszych warunków, które wykluczają losowość.



Ć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