Katedra informatiky | |
Fakulta matematiky, fyziky a informatiky | |
Univerzity Komenského, Bratislava |
Základné pojmy teórie kódovania. Rovnomerné a blokové kódy. Rozdeliteľné a silne rozdeliteľné kódy. Kraftova-McMillanova nerovnosť. Cena kódu. Entropia. Kvázioptimálne kódy. Konštrukcia optimálneho kódu. Rozšírenia kódu. Kódovanie Markovovských zdrojov. Kódovanie s predpoveďou.
Model prenosového kanála. Typy chýb. Biely šum. Kódy odhaľujúce a opravujúce chyby --- geometrické princípy. Obdĺžnikové kódy, Hammingov (7,4)-kód. Lineárne kódy. Konštrukcia, vlastnosti, kódovanie a dekódovanie. Dokonalé a kvázidokonalé kódy. Cyklické kódy. BCH kódy, konštrukcia, metódy kódovania a dekódovania.
Základné pojmy: otvorený, šifrovaný text, kľúč, šifrovanie, dešifrovanie, kryptoanalýza. Typy kryptoanalytických útokov. Klasické kryptosystémy a ich kryptoanalýza. Generátory presudonáhodných postupností. Stream ciphers. Blokové šifry. DES. Šifrovanie s verejnými kľúčmi. RSA. Aplikácie.
Turingove stroje, základné zložitostné triedy a vzťahy medzi nimi (Savitchova veta, Translačná lema, simulácie a hierarchie; existencia ťažkých problémov). Gap Theorem a Veta o zrýchľovaní. NP-úplnosť, Cookova veta a niektoré ďalšie (aj pre prax dôležité) NP-úplné problémy. Vzťah NP-úplných a NP-optimalizačných problémov. Aproximačné algoritmy pre NP-optimalizačné problémy; neaproximovateľnosť. Výpočty s orákulom a vzťah tried P a NP. Jednosmerné funkcie a šifrovanie. Pravdepodobnostné algoritmy a RSA šifrovací systém. PSPACE-úplné problémy.
Funkcie a čiastočné funkcie; projekcie, skladanie funkcií, trojice číslovacích (párovacích) funkcií. Univerzálne funkcie a čiastočné funkcie. Primitívne rekurzívne, rekurzívne funkcie a čiastočne rekurzívne (vypočítateľné) funkcie (na množine N). Primitívne rekurzívne, rekurzívne a rekurzívne spočítateľné množiny a predikáty a ich vlastnosti. Modely vypočítateľnosti (Turingove stroje a iné modely). Ekvivalentnosť modelov vypočítateľnosti. Churchova téza. Problém zastavenia a iné nerozhodnuteľné problémy. Kódovanie nečíselných oborov (oborov slov) do prirodzených čísel.
Generujúce funkcie. Základné pojmy, operácie s g.f. Konvolúcia g.f. Použitie generujúcich funkcií na riešenie rekurentných vzťahov. Príklady: počet kostier vo vejári, Fibonacciho čísla, dobre uzátvorkované výrazy. Exponenciálne generujúce funkcie, operácie s nimi. Bernoulliho čísla.
Asymptotická analýza. Nekonečne malé a nekonečne veľké veličiny. Hardyho trieda logaritmicko-exponenciálnych funkcií. Notácia o, O, Omega, Theta, rádová rovnosť a asymptotická rovnosť. Narábanie s O. Asymptotické odhady odvodené pomocou radov. Metódy bootstrapping (asymptotická iterácia), traiding tails (odhady podstatných častí), Eulerova sumačná formula a jej použitie. Príklady.