Teoria informacji/TI Ćwiczenia 13
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaĆ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 losowy.
oznacza zapis binarny liczby naturalnej . Powiemy, że liczba jest losowa, jeśli ciąg jest - 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łogdzie jest funkcją taką, że