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

LS 2021/2022
NTIN100 - 2/1 Zk

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

Přednáška 25.4. a cvičení 26.4. odpadají.

Čas konání: Po 10:40-12:10.
Místo konání: S4, Malá Strana.
Jazyk: česky nebo anglicky dle požadavku studentů (taught in Czech or English depending on students)

Cvičení: Út 14:00 (liché týdny, první cvičení 1.3.) - zápočet za domácí úkoly.

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

Transcript of Lectures 2019/2020

• 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)

Recordings

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 21.3.2022.
2. Do 4.4.2022.
3. Do 25.4.2022.
4. Do 24.5.2022.

Zkouška