Teoria informacji: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Niwinski (dyskusja | edycje)
214 edycji
Niwinski (dyskusja | edycje)
214 edycji
 
(Nie pokazano 9 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
=== Opis ===
== Forma zajęć ==
Wprowadzenie w teorię przydatną  w wielu zastosowaniach informatyki,  
Wykład (30 godzin) + ćwiczenia (30 godzin)
jak m.in. w kryptografii, w modelowaniu języka  naturalnego, czy w  
 
bio-informatyce. Teoria ta okresla ilościowo informację  zawartą w  
== Opis ==
zmiennej losowej lub w ciągu bitów, a także kryteria optymalnego
 
przesyłania zakodowanej wiadomości przez zaszumiony kanał.  
Wprowadzenie w teorię przydatną  w wielu zastosowaniach informatyki, jak m.in. w kryptografii, w modelowaniu języka  naturalnego, czy w bio-informatyce. Teoria ta okresla ilościowo informację  zawartą w zmiennej losowej lub w ciągu bitów, a także kryteria optymalnego przesyłania zakodowanej wiadomości przez zaszumiony kanał.  
 
== Sylabus ==


=== Autorzy ===
=== Autorzy ===
Linia 17: Linia 19:


=== Zawartość ===
=== Zawartość ===
* Od gry w 20 pytań do pojęcia entropii. Nierówność Krafta. Kody Huffmana i Shannona-Fano.
* Od gry w 20 pytań do pojęcia entropii. Nierówność Krafta.  
* Entropia warunkowa, informacja.
* Kody Huffmana i Shannona-Fano.  
* Entropia warunkowa, pojęcie informacji.
* Pierwsze twierdzenie Shannona o optymalnym kodowaniu.
* Pierwsze twierdzenie Shannona o optymalnym kodowaniu.
* Kanały, utrata informacji, poprawa wydajności, przepustowość.
* Przesyłanie wiadomości przez zaszumiony kanał, przepustowość kanału.
* Poprawa wydajności kanału, stopa kodu.
* Główne twierdzenie Shannona o optymalnym przesyłaniu informacji.
* Główne twierdzenie Shannona o optymalnym przesyłaniu informacji.
* Złożoność informacyjna Kołmogorowa. Liczba Chaitina.
* Kody korygujące błędy.
* Złożoność informacyjna Kołmogorowa i jej własności. Liczba Chaitina.
* Złożoność informacyjna Kołmogorowa a entropia Shannona - uniwersalny test Martina Loffa.
* Złożoność informacyjna Kołmogorowa a entropia Shannona - uniwersalny test Martina Loffa.


=== Literatura ===
=== Literatura ===
# "Information and Coding Theory" by Gareth A. Jones and J. Mary Jones, Springer, 2000.
# ''Information and Coding Theory'', Gareth A. Jones and J. Mary Jones, Springer, 2000.
# "Elements of Information Theory" by Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
# ''Elements of Information Theory'', Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
# ''An Introduction to Kolmogorov Complexity and Its Applications'', Ming Li and Paul Vitanyi, Springer, 1997.
# ''Information Theory, Inference, and Learning Algorithms'', David J.C. MacKay, Cambridge University Press, 2003.
 
== Moduły ==
# [[Teoria_informacji/TI Wykład 1|Notacja i kody]] ([[Teoria_informacji/TI Ćwiczenia 1|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 2|Pojęcie entropii]] ([[Teoria_informacji/TI Ćwiczenia 2|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 3|Optymalne kodowanie - kod Huffmana]] ([[Teoria_informacji/TI Ćwiczenia 3|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 4|Optymalne kodowanie - kod Shannona-Fano]] ([[Teoria_informacji/TI Ćwiczenia 4|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 5|Entropia zmiennej losowej i wzajemna informacja]] ([[Teoria_informacji/TI Ćwiczenia 5|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 6|Doskonale bezpieczne szyfrowanie]] ([[Teoria_informacji/TI Ćwiczenia 6|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 7|Kanały transmisji i ich przepustowość]] ([[Teoria_informacji/TI Ćwiczenia 7|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 8|Odczytywanie przesłanej wiadomości]] ([[Teoria_informacji/TI Ćwiczenia 8|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 9|Poprawa wydajności kanału]] ([[Teoria_informacji/TI Ćwiczenia 9|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 10|Efektywne kodowanie wiadomości]] ([[Teoria_informacji/TI Ćwiczenia 10|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 11|Twierdzenie Shannona o kodach]] ([[Teoria_informacji/TI Ćwiczenia 11|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 12|Dowód Twierdzenia Shannona]] ([[Teoria_informacji/TI Ćwiczenia 12|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 13|Złożoność informacyjna Kołmogorowa]] ([[Teoria_informacji/TI Ćwiczenia 13|Ćwiczenia]])
# [[Teoria_informacji/TI Wykład 14|Stała Chaitina]] ([[Teoria_informacji/TI Ćwiczenia 14|Ćwiczenia]])

Aktualna wersja na dzień 08:18, 24 sie 2006

Forma zajęć

Wykład (30 godzin) + ćwiczenia (30 godzin)

Opis

Wprowadzenie w teorię przydatną w wielu zastosowaniach informatyki, jak m.in. w kryptografii, w modelowaniu języka naturalnego, czy w bio-informatyce. Teoria ta okresla ilościowo informację zawartą w zmiennej losowej lub w ciągu bitów, a także kryteria optymalnego przesyłania zakodowanej wiadomości przez zaszumiony kanał.

Sylabus

Autorzy

  • Damian Niwiński
  • Michał Strojnowski
  • Marcin Wojnarski

Wymagania wstępne

  • Matematyka dyskretna
  • Rachunek prawdopodobieństwa i statystyka
  • Języki, automaty i obliczenia

Zawartość

  • Od gry w 20 pytań do pojęcia entropii. Nierówność Krafta.
  • Kody Huffmana i Shannona-Fano.
  • Entropia warunkowa, pojęcie informacji.
  • Pierwsze twierdzenie Shannona o optymalnym kodowaniu.
  • Przesyłanie wiadomości przez zaszumiony kanał, przepustowość kanału.
  • Poprawa wydajności kanału, stopa kodu.
  • Główne twierdzenie Shannona o optymalnym przesyłaniu informacji.
  • Kody korygujące błędy.
  • Złożoność informacyjna Kołmogorowa i jej własności. Liczba Chaitina.
  • Złożoność informacyjna Kołmogorowa a entropia Shannona - uniwersalny test Martina Loffa.

Literatura

  1. Information and Coding Theory, Gareth A. Jones and J. Mary Jones, Springer, 2000.
  2. Elements of Information Theory, Thomas M. Cover and Joy A. Thomas, Wiley Series in Telecommunications, 1991.
  3. An Introduction to Kolmogorov Complexity and Its Applications, Ming Li and Paul Vitanyi, Springer, 1997.
  4. Information Theory, Inference, and Learning Algorithms, David J.C. MacKay, Cambridge University Press, 2003.

Moduły

  1. Notacja i kody (Ćwiczenia)
  2. Pojęcie entropii (Ćwiczenia)
  3. Optymalne kodowanie - kod Huffmana (Ćwiczenia)
  4. Optymalne kodowanie - kod Shannona-Fano (Ćwiczenia)
  5. Entropia zmiennej losowej i wzajemna informacja (Ćwiczenia)
  6. Doskonale bezpieczne szyfrowanie (Ćwiczenia)
  7. Kanały transmisji i ich przepustowość (Ćwiczenia)
  8. Odczytywanie przesłanej wiadomości (Ćwiczenia)
  9. Poprawa wydajności kanału (Ćwiczenia)
  10. Efektywne kodowanie wiadomości (Ćwiczenia)
  11. Twierdzenie Shannona o kodach (Ćwiczenia)
  12. Dowód Twierdzenia Shannona (Ćwiczenia)
  13. Złożoność informacyjna Kołmogorowa (Ćwiczenia)
  14. Stała Chaitina (Ćwiczenia)
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji&oldid=26081”