Teoria informacji/TI Wykład 1: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m
Linia 43: Linia 43:
  
  
'''Wniosek: ''' Jeśli <math>\alpha: N-> \Sigma*</math> jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n: <math>\alpha(n)> \lfloor log_r n \rfloor </math>
+
'''Wniosek: ''' Jeśli <math>\alpha: N\to \Sigma^*</math> jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n: <math>\alpha(n)> \lfloor log_r n \rfloor </math>
  
 
'''Dowód: ''' Wybierzmy m takie że <math>\lfloor log_r m \rfloor > |\alpha(0)| </math>. Z powyższego Faktu, dla pewnego <math>i_0 \in \{0, 1, \ldots, m-1\}</math> mamy <math>|\alpha(i_0)|\ge \lfloor log_r m \rfloor>\lfloor log_r i_0 \rfloor </math>. Z tego wynika również że <math>i_0>0</math>.
 
'''Dowód: ''' Wybierzmy m takie że <math>\lfloor log_r m \rfloor > |\alpha(0)| </math>. Z powyższego Faktu, dla pewnego <math>i_0 \in \{0, 1, \ldots, m-1\}</math> mamy <math>|\alpha(i_0)|\ge \lfloor log_r m \rfloor>\lfloor log_r i_0 \rfloor </math>. Z tego wynika również że <math>i_0>0</math>.

Wersja z 10:55, 10 cze 2006

Je n’ai fait celle-ci plus longue que parce que je n’ai pas eu le loisir de la faire plus courte.

(Napisałem ten list trochę dłuższy, gdyż nie miałem czasu napisać go krócej).

Blaise Pascal, Lettres provinciales, 1657

Notacja, co to takiego?

Zaczynamy od prostego eksperymentu: Odgadnij słowo o którym ktoś myśli – na przykład zgadując literę po literze. Czy będzie to równie łatwe w przypadku odgadywania liczby? Zauważmy że w przeciwieństwie do słów w języku naturalnym, liczby całkowite w systemie dziesiętnym są „ciasno upakowane”. Dowolny ciąg znaków ze zbioru {0, 1, …, 9} jest jakąś liczbą (o ile nie zaczyna się od zera), ale bardzo niewiele ciągów z liter {a, b, …, z} jest sensownymi słowami. Możliwym wyjaśnieniem tego jest fakt że nasze „algorytmy” do komunikacji za pomocą słów wymagają znacznie więcej redundancji niż te do operowania liczbami.

Przykład zastosowania: Wypełniając czek wpisujemy kwotę zarówno przy pomocy liczb, jak i słownie. Dzięki temu małe przekłamanie nie zmienia wpisanej kwoty.


Teoria informacji usiłuje pogodzić dwa przeciwstawne cele:

  • zapisywania wiadomości jak najzwięźlej
  • chronienia wiadomości przed przekłamaniami podczas transmisji


Czy istnieją wiadomości których nie da się skrócić? Zanim odpowiemy na to pytanie rozważmy paradoks Berrego:

Niech n będzie najmniejszą liczbą naturalną której nie da się zdefiniować za pomocą mniej niż 1000 słów.

(To zdanie definiuje konkretną liczbę, stąd paradoks).

Istotne jest zatem prawidłowe definiowanie notacji. Notacja nie jest częścią badanego obiektu. Jest czymś zewnętrznym, nadanym w celu rozróżniania pomiędzy obiektami.

Definicja: Notacją dla S nazywamy dowolną różnowartościową funkcję gdzie jest skończonym alfabetem.


Fakt: Jeśli i to dla pewnego .

Dowód: Ciągów długości mniejszej niż jest:

Podstawiając stwierdzamy że nie ma wystarczająco wiele słów krótszych niż k do oznaczenia wszystkich elementów S. QED.


Wniosek: Jeśli jest dowolną notacją dla liczb naturalnych, to dla nieskończenie wielu n:

Dowód: Wybierzmy m takie że . Z powyższego Faktu, dla pewnego mamy . Z tego wynika również że .

Wybierzmy teraz m’ takie że . Znów musi istnieć takie że . Analogicznie . I tak dalej. QED.


Jako zastosowanie, możemy podać teorioinformacyjny dowód znanego faktu:

Fakt (Euklides): Istnieje nieskończenie wiele liczb pierwszych.

Dowód: Załóżmy przeciwnie, że istnieje tylko M liczb pierwszych: . Wprowadzamy notację w następujący sposób: Dla niech

gdzie jest zwykłym zapisem binarnym liczby ().

Ponieważ , mamy , dla wszystkich i. A zatem

dla wszystkich n, co oczywiście przeczy twierdzeniu że dla nieskończenie wielu n . QED