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

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

LS 2016/2017

NTIN100 - 2/1 Zk

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

Cvičení: Čt 15:40-17:10, jednou za čtrnáct dní v S8 (První bude 16.3.2016.)

První přednáška se koná až dne 2.3.2016 a první cvičení 16.3.2016

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.
• Poznámky ke cvičení.
• 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 23.3. 2017.
2. Do 13.4. 2017.
3. Do 4. 5. 2017.
4. Do 18.5. 2017.
5. Do dvou dnů před zkouškou.