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

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

LS 2017/2018

NTIN100 - 2/1 Zk

Čas konání: Út 10:40-12:10.
Místo konání: S5, Malá Strana.

Cvičení: Po 14:00-15:40, jednou za čtrnáct dní v S10.

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. 2018.
2. Do 10.4. 2018.
3. Do 7. 5. 2018.
4. Do 29.5. 2018.