Detail předmětu
Kódování v informatice
FEKT-MPC-KODAk. rok: 2024/2025
Studenti se seznámí se základními pojmy teorie kódování a rozšíří si matematické znalosti algebry a teorie čísel.
Jazyk výuky
čeština
Počet kreditů
5
Garant předmětu
Zajišťuje ústav
Vstupní znalosti
Studenti by měli mít znalosti lineární algebry a kombinatoriky na úrovni bakalářského studia, zejména by měli být schopni sčítat a násobit vektory a matice, řešit soustavy lineárních rovnic a spočítat, kolika způsoby lze vybrat k prvků z n-prvkové množiny.
Pravidla hodnocení a ukončení předmětu
Maximálně 25 bodů za kontrolní písemky a aktivity během semestru (aspoň 10 bodů pro zápočet); maximálně 75 bodů za písemnou zkoušku.
Učební cíle
Cílem předmětu je vysvětlit základní pojmy a početní postupy teorie kódování, zejména
- sestrojení nejkratšího binárního kód pomocí Huffmanova algoritmu;
- nalezení minimální vzdálenost blokového kódu;
- rozhodnutí o linearitě blokového kódu;
- odvození generující a kontrolní matice lineárního kódu;
- dekódování metodou nejbližšího souseda a pomocí syndromů.
- sestrojení nejkratšího binárního kód pomocí Huffmanova algoritmu;
- nalezení minimální vzdálenost blokového kódu;
- rozhodnutí o linearitě blokového kódu;
- odvození generující a kontrolní matice lineárního kódu;
- dekódování metodou nejbližšího souseda a pomocí syndromů.
Základní literatura
ADÁMEK, Jiří: Kódování. Praha, SNTL, 1989. (CS)
Doporučená literatura
ZNÁM, Štefan: Teória čísel. Bratislava, Alfa, 1977. (SK)
Elearning
eLearning: aktuální otevřený kurz
Zařazení předmětu ve studijních plánech
- Program MPC-BTB magisterský navazující 1 ročník, letní semestr, povinně volitelný
Typ (způsob) výuky
Přednáška
26 hod., nepovinná
Vyučující / Lektor
Osnova
1. Základní pojmy teorie kódování. Huffmanova konstrukce nejkratšího kódu.
2. Blokové kódy. Hammingova vzdálenost.
3. Detekce a opravování chyb.
4. Základní úloha v teorii kódování. Perfektní kódy.
5. Základní algebraické pojmy - grupa, těleso, vektorový prostor.
6. Lineární kódy.
7. Generující a kontrolní matice.
8. Dekódování lineárních kódů. Syndromy.
9. Hammingovy kódy.
10. Golayovy kódy.
11. Reed-Mullerovy kódy.
2. Blokové kódy. Hammingova vzdálenost.
3. Detekce a opravování chyb.
4. Základní úloha v teorii kódování. Perfektní kódy.
5. Základní algebraické pojmy - grupa, těleso, vektorový prostor.
6. Lineární kódy.
7. Generující a kontrolní matice.
8. Dekódování lineárních kódů. Syndromy.
9. Hammingovy kódy.
10. Golayovy kódy.
11. Reed-Mullerovy kódy.
Elearning
eLearning: aktuální otevřený kurz