Teorie informace a kódování [ KMI/TIK ]
Předmět je úvodem do teorie informace, jejích aplikací a teorie kódování.
Zkouška
- požadované znalosti dány seznamem přednášek, přesněji odpřednášenou látkou a obsahem prvních a druhých slajdů k přednáškám a (přehledově) prvního nebo druhého materiálu k Reed-Mullerovým kódům
- průběh ústním zodpovězením vylosovaných otázek s písemnou přípravou
Zápočet
- požadováno vypracování zápočtové práce
- zápočtová práce: zadání na posledních dvou slajdech druhých slajdů k přednáškám
Materiály
- Bělohlávek R.: Introduction to Information Theory and Its Applications (slajdy)
- Belohlavek R.: Information Theory and Coding (slajdy)
- Reed-Muller Codes: Weak Codes with Easy Decoding (kopie z knihy)
- Reed Mullerovy kódy (materiál od dr. Večerky)
- Havrlant L.: Teorie informace a kódování (slajdy)
Přednášky
- Úvod:
Klasická teorie informace, potřebné pojmy z pravděpodobnosti: pravděpodobnostní prostor, pravděpodobnost, náhodná proměnná.
slajdy - Úvod od teorie informace:
Entropie, sdružená entropie, podmíněná entropie, vzájemná informace.
slajdy - Vybrané aplikace teorie informace 1:
Rozhodovací stromy a jejich konstrukce (algoritmus ID3), použití entropie.
slajdy - Vybrané aplikace teorie informace 2:
Rozšíření algoritnu ID3, další metody klasifikace.
slajdy - Úvod do kódování:
Kódování, kódy, jednoznačná dekódovatelnost.
slajdy - Optimální kódy 1:
Existence kódů: Kraftova a McMillanova věta.
slajdy - Optimální kódy 2:
Shannonova věta.
slajdy - Optimální kódy 3:
Huffmanova konstrukce optimálních kódů.
slajdy - Detekční a opravné kódy:
Úvod, příklady kódů, Hammingova a minimální vzdálenost, detekce a oprava chyb.
slajdy, slajdy - Binární lineární kódy:
Definice, Hammingova a minimální váha, kontrolní matice, příklady, Hammingovy kódy.
slajdy, slajdy - Lineární kódy:
Potřebné pojmy z algebry: grupa, těleso, vektorový prostor, definice, generující a kontrolní matice, kódování a dekódování, příklady.
slajdy, slajdy - Reed-Mullerovy kódy:
Booleovské funkce a polynomy, definice, generující matice, kódování, geometrická interpretace, dekódování.
kopie z knihy, slajdy
Cvičení
- Pravděpodobnostní prostor: Důkazy vlastností.
- Entropie: Demonstrace interpretace entropie.
- Informace: Výpočet informace jako snížení entropie.
- Rozhodovací stromy 1: Naivní konstrukce.
- Rozhodovací stromy 2: Konstrukce algoritmem ID3.
- Dekódovatelnost kódu: Rozhodování dekódovatelnosti, určení nejdnoznačně dekódovatelných kódů.
- Binární prefixové kódy: Konstrukce, optimalita.
- Huffmanův kód: Konstrukce, efektivita.
- Detekční a opravné kódy: Minimální vzdálenost, kódové slovo.
Literatura
- Yeung R. W.: A First Course in Information Theory. Springer, New York, USA, 2002.
- Cover T. M.: Elements of Information Theory. J. Wiley, 2006.
- Adámek J.: Foundations of Coding. J. Wiley, 1991.
- Adámek J.: Kódování. SNTL, Praha, 1989.
- Ash R. B.: Information Theory. Dover, New York, 1990.