Expanderové kódy

• Název práce v češtině: Expanderové kódy
• Název v anglickém jazyce: Expander codes
• Klíčová slova: expander, samoopravný kód, efektivní dekódování
• Klíčová slova anglicky: expander, error-correcting code, linear-time decoding
• Akademický rok vypsání: 2017/2018
• Typ práce: bakalářská práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: Mgr. Martin Mareš, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 15.12.2017
• Datum zadání: 15.12.2017
• Datum potvrzení stud. oddělením: 19.12.2017
• Datum a čas obhajoby: 18.06.2018 10:00
• Datum odevzdání elektronické podoby: 17.05.2018
• Datum odevzdání tištěné podoby: 17.05.2018
• Datum proběhlé obhajoby: 18.06.2018
• Oponenti: RNDr. Radek Hušek, Ph.D.

Zásady pro vypracování

Student se seznámí s technikou konstrukce efektivních samoopravných kódů z grafů s expanzními vlastnostmi a různými třídami těchto grafů. Cílem práce je popsat základní výsledky s přihlédnutím k jejich algoritmickým aplikacím.

Seznam odborné literatury

Reingold, Vadhan, Wigderson: Entropy waves, the zig-zag graph product, and new constant-degree expanders. Annals of mathematics, 2002.

Guruswami: Guest column: error-correcting codes and expander graphs. ACM SIGACT News, 35(3), 2004.

Sipser, Spielman: Expander codes. IEEE Transactions on Information Theory, 42(6), 1996.