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

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

LS 2015/2016

NTIN100 - 2/1 Zk

Čas konání: Út 14:00-15:30.
Místo konání: S5, Malá Strana.

Cvičení: Po 9:15-10:40, jednou za čtrnáct dní v S5 (První bude 14.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. (Přednáška P. Gregora z 5.4.2016.)
• 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.
• 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.
• E. Kushilevitz, N. Nisan, Communication complexity. Cambridge University Press, 1997.
• Stručný přehled pravděpodobnosti.

Domácí úkoly

1. Do 22.3. 2016.
2. Do 12.4. 2016.
3. Do 26.4. 2016. (Ve třetí úloze by 1,...,m mělo být 1,...,k.)
4. Do 10.5. 2016.
5. Do Do zkoušky.