Teorie informace

Garant předmětu:

Pavel Hrabák

Přednášející:

Pavel Hrabák

Cvičící:

Pavel Hrabák

Předmět zajišťuje:

katedra aplikované matematiky

Anotace:

Předmět cílí na matematický popis náhodného zdroje zpráv, jeho kódování a přenosu zdroje šumovým kanálem. Úloha kódování je nahlížena pravděpodobnostně, je akcentována souvislost střední délky optimálního kódu s entropií a rychlostí entropie náhodného zdroje, v případě šumového kanálu se zaměřujeme na množinu typických zpráv a její vhodné kódování samoopravnými kódy. Součástí předmětu je i připomenutí potřebných pojmů jako podmíněné rozdělení, testy dobré shody a testy nezávislosti, úvod do náhodných řetězců.

Požadavky:

Je nutné mít absolvované základy teorie pravděpodobnosti a statistiky v rozsahu odpovídajícím předmětu BI-PST na FIT ČVUT.

Osnova přednášek:

1.Opakování pravděpodobnosti, náhodné veličiny a jejich rozdělení.

2. Náhodné vektory, vícerozměrné rozdělení, podmíněné rozdělení.

3. Charakteristiky náhodných vektorů.

4. Vzdálenosti mezi rozděleními, souvislost s testy dobré shody, testy nezávislosti.

5. Testování hypotéz, testy nezávislosti.

6. Zdroj zpráv, entropie, podmíněná entropie, relativní entropie, vzájemná informace.

7. Diferenciální entropie, princip maximální entropie.

8. Komprese dat, instantní a jednoznačně dekódovatelné kódy, Huffmanovo kódování, souvislost s entropií zdroje.

9. Úvod do teorie markovských řetězců.

10. Entropie a kódování markovského zdroje.

11. Informační kanály, kapacita kanálu.

12. Přenesitelnost zdrojů informačním kanálem, typické zprávy.

13. Simulace náhodného zdroje zpráv.

Osnova cvičení:

1. Opakování pravděpodobnosti, náhodné veličiny a jejich rozdělení.

2. Náhodné vektory, vícerozměrné rozdělení.

3. Charakteristiky náhodných vektorů, podmíněné rozdělení.

4. Vzdálenosti mezi rozděleními, testy dobré shody.

5. Testy nezávislosti.

6. Entropie, podmíněná entropie, relativní entropie, vzájemná informace.

7. Princip maximální entropie.

8. Huffmanovo kódování, souvislost s entropií zdroje.

9. Markovské řetězce, markovská podmínka.

10. Entropie a kódování markovského zdroje.

11. Informační kanály, kapacita kanálu.

12. Množina a kódování typických zpráv, Hammingovy kódy.

13. Simulace náhodného zdroje zpráv.

Cíle studia:

Předmět cílí na matematický popis náhodného zdroje zpráv, jeho kódování a přenosu zdroje šumovým kanálem. Úloha kódování je nahlížena pravděpodobnostně, je akcentována souvislost střední délky optimálního kódu s entropií a rychlostí entropie náhodného zdroje, v případě šumového kanálu se zaměřujeme na množinu typických zpráv a její vhodné kódování samoopravnými kódy. Součástí předmětu je i připomenutí potřebných pojmů jako podmíněné rozdělení, testy dobré shody a testy nezávislosti, úvod do náhodných řetězců.

Studijní materiály:

1. Cover, T. M., Thomas, J. A.: Elements of Information Theory, 2nd Edition

Wiley-Interscience 2006

ISBN 9780471241959

2. Johnson, J. L.: Probability and Statistics for Computer Science

Wiley-Interscience 2008

ISBN 9780471326724

3. Wilde, M. M.: Quantum Information Theory

Cambridge University Pres 2013

ISBN 9781316809976

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/QNI-TIN.

Výuka probíhá paralelně s předmětem NI-TIN v českém jazyce.

Další informace:

https://courses.fit.cvut.cz/QNI-TIN

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Kvantová informatika (povinný předmět programu)