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

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

LS 2019/2020

NTIN100 - 2/1 Zk

Čas konání: Ut 14:00-15:30.
Místo konání: Via Zoom https://matfyz.zoom.us/j/4042155019, Malá Strana.

Cvičení: Ut 15:40 - 17:10, jednou za čtrnáct dní v S10 (první cvičení 10.3.2020).

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

Lectures

• 17.3.2020 - Prefix-free codes, Shannon Code,...
• 24.3.2020 - Kolmogorov complexity
• 31.3.2020 - Transmission over noisy channel
• 7.4.2020 - Shannon Theorems
• 14.4.2020 - Error-correcting codes, Hamming code (Tutorial class)
• 21.4.2020 - Reed-Solomon code (Tutorial class)
• 28.4.2020 - Berlekamp-Welch (2 part), Varshamov code
• 5.5.2020 - List decoding, Local decoding, Communication complexity (Tutorial class)
• 12.5.2020 - Protocols and combinatorial rectangles
• 19.5.2020 - Nondeterministic communication complexity (Tutorial class)

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 17.3.2020.
2. Do 7.4.2020.
3. Do 5.5.2020.
4. Do 29.5.2019.

Zkouška