Základy přenosu a zpracování informace - NTIN100

• Anglický název: Introduction to Information Transmission and Processing
• Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Garant: prof. Mgr. Michal Koucký, Ph.D.
• Vyučující: doc. Mgr. Petr Gregor, Ph.D.; Mgr. Tung Anh Vu
• Je neslučitelnost pro: NTIX100
• Je záměnnost pro: NTIX100

Anotace

čeština

Přednáška pokrývá základy teorie informace, samoopravných kódů a komunikační složitosti. Předpokládají se znalosti na úrovni předmětu Pravděpodobnostní techniky.

Poslední úprava: IUUK (27.01.2015)

angličtina

The course covers the fundamental concepts of information theory, error-correcting codes and communication complexity.

Poslední úprava: IUUK (27.04.2015)

Podmínky zakončení předmětu

čeština

Zápočet se uděluje po získání dostatečného počtu bodů z domácích úkolů. Je nutné získat alespoň 70% všech možných bodů za příklady z domácích úkolů.

Zápočet nelze opakovat.

Zkouška je ústní.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

angličtina

The credit from tutorials is given based on the number of points obtained from the homework assignments. To get the credit one has to get at least 70% of the total number of points

from the assignments.

There are no make-up homeworks.

The exam is oral.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

Literatura

čeština

· T.M. Cover, J.A. Thomas, Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.

· F.J. MacWilliams, N.J.A. Sloane, The theory of error correcting codes. North-Holland, Amsterdam, 1981.

· E. Kushilevitz, N. Nisan, Communication Complexity. Cambridge University Press, 1997.

· J.H. van Lint, Introduction to coding theory. Springer, 3rd edition, 1998.

Poslední úprava: IUUK (27.01.2015)

Požadavky ke zkoušce

čeština

Zkouška je ústní. Zkouší se z probrané látky. Po zadání otázek dostane student čas na přípravu.

Studijní materiály (skripta, učebnice a zápisky z přednášek) ani notebooky, kalkulačky, PDA, atd., nejsou u zkoušky dovoleny.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

angličtina

The exam is oral from the material covered by the lectures. Each student gets reasonable time (at most three hours) for preparation upon receiving the questions.

Study materials (lecture notes, text books, etc.), computers and other electronic devices are not allowed during the exam.

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (10.06.2019)

Sylabus

čeština

Teorie Informace

· Informace, entropie, vzájemná informace

· Relativní informace a její vlastnosti

· Komprese dat - Shannon-Fanův kód, Huffmanův kód

· Kolmogorovská složitost, Kolmogorovská informace, symetrie Kolmogorovské informace

Samoopravné kódy

· Přenos dat po nespolehlivém kanálu, kapacita kanálu, Shannonovy věty

· Neexplicitní kódy

· Hammingovy kódy

· Reed-Solomonovy kódy, Berlekamp-Welchův algoritmus

Komunikační složitost

· Model komunikační složitosti

· Deterministická složitost, kombinatorické obdélníky, příklady

· Pravděpodobnostní protokoly, veřejné versus soukromé náhodné bity

· Nedeterministické protokoly

· Užití: analýza datových struktur

Poslední úprava: IUUK (27.01.2015)

angličtina

Information Theory

· Information, entropy, mutual information

· Relative information and its properties

· Data compression - Shannon-Fano code, Huffman code

· Kolmogorov complexity, Kolmogorov information, symmetry of Kolmogorov information

Error-Correcting Codes

· Data transmission over a noisy channel, channel capacity, Shannon's theorems

· Non-explicit codes

· Hamming codes

· Reed-Solomon codes, Berlekamp-Welch algorithm

Communication Complexity

· Model of communication complexity

· Deterministic complexity, combinatorial rectangles, examples

· Probabilistic protocols, public and private random bits

· Non-deterministic protocols

· Application: analysis of data structures

Poslední úprava: IUUK (27.04.2015)