Vybrané kapitoly z výpočetní složitosti I

Michal Koucký
<koucky@math.cas.cz>

ZS 2010/2011

TIN085 - 2/1 Z, Zk

Čas konání: pátek 12:20-13:50.
Místo konání: S4 - Malá Strana

Obsahem této přednášky jsou pokročilé partie z výpočetní složitosti. Tento semestr bude věnován samoopravným kódům. Samoopravné kódy jsou kombinatorický objekt s fascinujícími vlastnostmi. Na přednášce se budeme zabývat základními vlastnostmi samoopravných kódů, jejich konstrukcí a užitím ve složitosti. Ukážeme jak některé algebraické konstrukce tak konstrukce kombinatorické. I když toto téma může vypadat jako čistě teoretické, bez této teorie by nefungovaly CD-přehrávače, mobily, moderní procesory, paměti, pevné disky, zkrátka žádné zařízení skladující nebo přenášející data. Význam samoopravných kódů pro praktické aplikace neustále roste a tudíž lze tuto přednášku doporučit nejen zájemcům o teorii.

Přednáška je určena především studentům vyšších ročníků studia a doktorandům. Přednáška předpokládá základní znalosti z diskrétní matematiky, algebry, pravděpodobnosti a výpočetní složitosti.

Plán přednášky

• Shannonův a Hammingův přístup.
• Náhodné kódy, Hadamardovy, Hammingovy, Reed-Solomonovy kódy.
• Dekódování RS kódů (algoritmus Berlekampa a Welshe).
• Dekódování s více možnostmi.
• Skládání kódů.
• Reed-Mullerovy kódy. 
• Kód Sipsera a Spielmena.
• Lokálně dekódovatelné kódy.
• Užití.
• Kombinatorická omezení kódů.

Literatura:

F.J. MacWilliams and N.J.A. Sloane: The Theory of Error Correcting Codes. North-Holland, Amsterdam, 1981.
Madhu Sudan – lecture notes.

Shrnutí pravděpodobnosti.

Domácí úkoly

1. Do 29.10. 2010.
2. Do 19.11. 2010.
3. Do 17.12. 2010.
4. Do do zkoušky.