Serwisy internetowe Uniwersytetu Warszawskiego Nie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Uniwersalne algorytmy w teorii informacji

Informacje ogólne

Kod przedmiotu: 1000-1S20UAI Kod Erasmus / ISCED: 11.1 / (0541) Matematyka
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)
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.


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.