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

Michal Koucký
<koucky@iuuk.mff.cuni.cz>

LS 2018/2019

NTIN100 - 2/1 Zk

Čas konání: St 10:40-12:10.
Místo konání: S4, Malá Strana.

Cvičení: Čt 15:40 - 17:10, jednou za čtrnáct dní v S1 (první cvičení 14.3.2019).

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.

Plán přednášky

• 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

Literatura

• Aktualizované poznámky k přednášce.
• T.M. Cover, J.A. Thomas, Elements of Information Theory. John Wiley & Sons, 2nd edition, 2006.
• Stručný úvod do Kolmogorovské složitosti.
• V. Guruswami, A. Rudra and M. Sudan, Essential Coding Theory. 2012-2017.
• E. Kushilevitz, N. Nisan, Communication complexity. Cambridge University Press, 1997.
• Stručný přehled pravděpodobnosti.

Rozšiřující čtení

• F.J. MacWilliams and N.J.A. Sloane, The Theory of Error Correcting Codes. North-Holland, Amsterdam, 1981.
• J.H. van Lint, Introduction to coding theory. Springer, 3rd edition, 1998.

Domácí úkoly

1. Do 20.3.2019.
2. Do 10.4.2019.
3. Do 24.4.2019.
4. Do 15.5.2019.
5. Do dvou dnů před zkouškou.

Zkouška