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

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

ZS 2007/2008

TIN085 - 2/1 Z, Zk

Čas konání: umluveno na čtvrtek 17:50. První přednáška 4.10.2007.
Místo konání: S6 - 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 Spielmana.
• 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 1.11. 2007.
2. Do 15.11. 2007 - rešení.
3. Do 6.12. 2007 - rešení.
4. Do 10.1. 2008.