Uniwersytet Warszawski - Centralny System UwierzytelnianiaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Teoria informacji II

Informacje ogólne

Kod przedmiotu: 1000-2M10TI Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Teoria informacji II
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
Język prowadzenia: angielski
Kierunek podstawowy MISMaP:

informatyka
matematyka

Rodzaj przedmiotu:

monograficzne

Założenia (opisowo):

Studenci powinni mieć podstawową wiedzę z rachunku prawdopodobieństwa i teorii informacji. Mile widziana, acz niekonieczna jest uprzednia znajomość niektórych algorytmów uniwersalnej kompresji danych na przykład z wykładu “Kompresja danych – wprowadzenie” 1000-2N09KDW

Skrócony opis:

Uzupełnienie wykładów „Teoria informacji” 1000-2N03TI i “Kompresja danych – wprowadzenie” 1000-2N09KDW o zagadnienia dotyczące teorii uniwersalnej kompresji danych. Celem wykładu jest pokazanie, dlaczego popularne algorytmy kompresji tekstu takie jak PPM oraz LZ kompresują optymalnie dane generowane przez dowolny stacjonarny proces stochastyczny. W ramach wykładu przedstawione zostaną ciekawe pomocnicze wyniki teoretyczne, dotyczące także statystycznego modelowania języka naturalnego.

Pełny opis:

Uzupełnienie wykładów „Teoria informacji” 1000-2N03TI i “Kompresja danych – wprowadzenie” 1000-2N09KDW o zagadnienia dotyczące teorii uniwersalnej kompresji danych. Celem wykładu jest pokazanie, dlaczego popularne algorytmy kompresji tekstu takie jak PPM oraz LZ kompresują optymalnie dane generowane przez dowolny stacjonarny proces stochastyczny. W ramach wykładu przedstawione zostaną ciekawe pomocnicze wyniki teoretyczne, dotyczące także statystycznego modelowania języka naturalnego.

1. Procesy Markowa, twierdzenie Kołmogorowa o procesie, procesy stacjonarne.

2. Entropia bloku, intensywność entropii i entropia nadwyżkowa.

3. Procesy ergodyczne (cztery intuicyjne definicje).

4. Twierdzenie ergodyczne Birkhoffa.

5. Twierdzenie o rozkładzie ergodycznym.

6. Rozkład ergodyczny intensywności entropii i entropii nadwyżkowej.

7. Nierówności: Krafta, kodowania źródła i Barrona.

8. Twierdzenie Shannona-McMillana-Breimana (SMB).

9. Kody uniwersalne a twierdzenie SMB.

10. Uniwersalność kodu Lempela-Ziva (LZ).

11. Uniwersalność kodu Prediction by Partial Matching (PPM).

12. Rząd PPM i słownik PPM.

13. Twierdzenie o faktach i słowach PPM.

Literatura:

1. Thomas M. Cover and Joy A. Thomas (1991) Elements of Information Theory.

Wiley Series in Telecommunications, 1991.

2. Łukasz Dębowski (2013). Information Theory and Statistics. Institute of Computer Science, Polish Academy of Sciences.

3. Łukasz Dębowski (2018). Is Natural Language a Perigraphic Process? The Theorem about Facts and Words Revisited. Entropy, vol. 20(2), pp. 85

4. Łukasz Dębowski (2018). Information Theory Meets Power Laws: Stochastic Processes and Language Models. W przygotowaniu.

Efekty uczenia się:

Wiedza:

student

– rozróżnia pojęcia procesu stacjonarnego i ergodycznego,

– zna ważne wyniki teoretyczne dotyczące procesów stacjonarnych i ergodycznych,

– zna podstawowe algorytmy uniwersalnej kompresji danych,

– zna podstawowe wyniki teoretyczne dotyczące uniwersalnej kompresji danych.

Umiejętności:

student

– umie sprawdzić w prostych przypadkach, czy dany proces stochastyczny jest ergodyczny,

– umie policzyć w prostych przypadkach intensywność entropii i entropię nadwyżkową danego procesu stacjonarnego,

– umie udowodnić uniwersalność prostych algorytmów kompresji danych.

Kompetencje:

student rozumie matematyczny model uniwersalnej kompresji danych i umie go odnieść do praktycznych aplikacji lub zastosować go w pracy badawczej.

Metody i kryteria oceniania:

Ocena końcowa na podstawie punktów z egzaminu pisemnego i jednego kolokwium. Wagi poszczególnych składników: egzamin - 50%, kolokwium - 50%.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.