Uniwersytet Warszawski - Centralny System Uwierzytelniania
Strona główna

Uniwersalne algorytmy w teorii informacji

Informacje ogólne

Kod przedmiotu: 1000-1S20UAI
Kod Erasmus / ISCED: 11.1 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0541) Matematyka Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu: Uniwersalne algorytmy w teorii informacji
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Seminaria monograficzne dla matematyki 2 stopnia
Punkty ECTS i inne: (brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS:
  • roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
  • tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
  • 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
  • tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
  • nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

seminaria monograficzne

Założenia (opisowo):




Skrócony opis:

A reading seminar on universal algorithms in information theory from a theoretical point of view as well as related subjects in the theory of dynamical systems.

Pełny opis:

Information theory is a branch of (applied) mathematics which has many applications in science and especially in computer science and electrical engineering. The field studies communication of information between a source and destination taking into account inter alia quantification, coding, noise reduction, decoding and storage.

The seminar will focus on universal algorithms in information theory from a theoretical point of view as well as related subjects in the theory of dynamical systems.

In order to illustrate the concept of universality and its relation to the theory of dynamical systems, consider the famous 1977 Lempel-Ziv universal lossless data compression algorithm which in finite versions is the basis for many popular data compression packages. This algorithm allows to almost surely code a message of length n (in the asymptotic regime n-->infinity) generated from an unknown arbitrary ergodic process by at most nh + o(n) binary digits. Moreover no other algorithm can perform better asymptotically.

Several proofs of this remarkable fact have been given. One proof by Ziv uses tools from topological dynamics. Another proof by Ornstein and Weiss uses tools from ergodic theory.

Literatura:

Paul C. Shields, The ergodic theory of discrete sample paths. Vol. 13. American Mathematical Soc., 1996.

Robert M. Gray, Entropy and information theory. Springer Science & Business Media, 2011.

Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compression. IEEE Transactions on information theory 23(3): 337-343, 1977.

Jacob Ziv. Coding theorems for individual sequences. IEEE Transactions on Information Theory 24(4): 405-412, 1978.

Donald S. Ornstein and Benjamin Weiss. Entropy and data compression schemes. IEEE Transactions on Information Theory, 39(1):78–83, 1993.

Donald S. Ornstein and Paul C. Shields. Universal almost sure data compression. The Annals of Probability 18(2): 441-452, 1990.

Amos Lapidoth and Jacob Ziv. On the universality of the LZ-based decoding algorithm, IEEE Transactions on Information Theory 44(5):1746–1755, 1998.Yonatan Gutman and Masaki Tsukamoto. Embedding minimal dynamical systems into Hilbert cubes. Inventiones Mathematicae, 2020.

Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, and Marcelo J. Weinberger. Universal discrete denoising: Known channel. IEEE Transactions on Information Theory, 51(1):5–28, 2005.

Meir Feder, Neri Merhav, and Michael Gutman. Universal prediction of individual sequences. IEEE transactions on Information Theory, 38(4):1258–1270, 1992.

Boris Ryabko. Compression-based methods for nonparametric prediction and estimation of some characteristics of time series. IEEE Transactions on Information Theory 55(9): 4309-4315, 2009.

Shirin Jalali and H. Vincent Poor. Universal compressed sensing for almost lossless recovery. IEEE Transactions on Information Theory, 63(5):2933–2953, 2017.

Efekty uczenia się:

Acquire a deep understanding of at least one article related to the theme of the seminar as well as the ability to teach its essentials to an audience.

Metody i kryteria oceniania:

Presentation of at least one paper on a given topic during the semester. The presentation may take several meetings.

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.
ul. Banacha 2
02-097 Warszawa
tel: +48 22 55 44 214 https://www.mimuw.edu.pl/
kontakt deklaracja dostępności USOSweb 7.0.3.0-2b06adb1e (2024-03-27)