INFO - Informacie o MFF UK

Matematicke metody informatiky (IS: 642322)

Blok :  Matematicke metody informatiky 

Gestor: Doc. RNDr. Daniel Olejar, CSc.

Predmet: Matematicke metody informatiky

1 Teoria kodovania a kryptologia

Zakladne pojmy teorie kodovania. Rovnomerne a blokove kody. Rozdelitelne
a silne rozdelitelne kody. Kraftova-McMillanova nerovnost. Cena kodu.
Entropia. Kvazioptimalne kody. Konstrukcia optimalneho kodu. Rozsirenia
kodu. Kodovanie Markovovskych zdrojov. Kodovanie s predpovedou.

Model prenosoveho kanala. Typy chyb. Biely sum. Kody odhalujuce a
opravujuce chyby - geometricke principy. Obdlznikove kody, Hammingov
(7,4)-kod. Linearne kody. Konstrukcia, vlastnosti, kodovanie a dekodovanie.
Dokonale a kvazidokonale kody. Cyklicke kody. BCH kody, konstrukcia, metody
kodovania a dekodovania.

Zakladne pojmy: otvoreny, sifrovany text, kluc, sifrovanie, desifrovanie,
kryptoanalyza. Typy kryptoanalytickych utokov. Klasicke kryptosystemy a ich
kryptoanalyza. Generatory presudonahodnych postupnosti. Stream ciphers.
Blokove sifry. DES. Sifrovanie s verejnymi klucmi. RSA. Aplikacie.

------------------------

2 Vypoctova zlozitost

Turingove stroje, zakladne zlozitostne triedy a vztahy medzi nimi
(Savitchova veta, Translacna lema, simulacie a hierarchie; existencia
tazkych problemov). Gap Theorem a Veta o zrychlovani. NP-uplnost, Cookova
veta a niektore dalsie (aj pre prax dolezite) NP-uplne problemy. Vztah
NP-uplnych a NP-optimalizacnych problemov. Aproximacne algoritmy pre
NP-optimalizacne problemy; neaproximovatelnost. Vypocty s orakulom a vztah
tried P a NP. Jednosmerne funkcie a sifrovanie. Pravdepodobnostne algoritmy
a RSA sifrovaci system. PSPACE-uplne problemy.

------------------------

3 Teoria vycislitelnosti

Klony funkcii a ciastocnych funkcii; projekcie, skladanie funkcii, trojice
cislovacich funkcii. Univerzalne funkcie a ciastocne funkcie. Primitivne
rekurzivne, rekurzivne funkcie a ciastocne rekurzivne funkcie (na mnozine N).
Primitivne rekurzivne, rekurzivne a rekurzivne spocitatelne mnoziny.
Postova veta. Registrove (Minskeho) stroje. Turingove stroje.
Ekvivalentnost rekurzivnosti a vypocitatelnosti na registrovych strojoch.
Churchova teza. Problem zastavenia. Rozsirenie pojmov z ciselnych mnozin na
jazyky.

------------------------

4 Kombinatoricka analyza II.

Generujuce funkcie. Zakladne pojmy, operacie s g.f. Konvolucia g.f.
Pouzitie generujucich funkcii na riesenie rekurentnych vztahov. Priklady:
pocet kostier vo vejari, Fibonacciho cisla, dobre uzatvorkovane vyrazy.
Exponencialne generujuce funkcie, operacie s nimi. Bernoulliho cisla.

Asymptoticka analyza. Nekonecne male a nekonecne velke veliciny. Hardyho
trieda logaritmicko-exponencialnych funkcii. Notacia o, O, Omega, Theta,
radova rovnost a asymptoticka rovnost. Narabanie s O. Asymptoticke odhady
odvodene pomocou radov. Metody bootstrapping (asymptoticka iteracia),
traiding tails (odhady podstatnych casti), Eulerova sumacna formula a jej
pouzitie. Priklady.

------------------------

5 Vybrane partie z logiky

1. Vyrokova logika: Jazyk logiky, formalne systemy logiky, vyrokova logika,
   veta o kompaktnosti, dosledok vety o kompaktnosti, formalny system
   vyrokovej logiky, veta o dedukcii, zakladne teoremy vyrokovej logiky,
   Postova veta, bezospornost formalneho systemu, veta o nahradeni
   podformul ekvivalentnymi formulami, de Morganove pravidla, veta o dokaze
   rozborom pripadov, ekvivalentne vyjadrenie formul d.n.f. a k.n.f., veta
   o substitucii prvotnych formul, ekvivalentnost pravidla modus ponens a
   pravidla rezu.

2. Predikatova logika: Jazyk a jeho semantika, semantika predikatovej
   logiky, substitucia termov za premenne. Axiomy a pravidla odvodenia
   predikatovej logiky, pravidlo zavedenia velkeho kvantifikatora, veta o
   uzavere, lema o distribucii kvantifikatorov, veta o ekvivalencii, veta o
   variantoch, veta o dedukcii, veta o konstantach, zovseobecnenie vety o
   dedukcii. Prenexny tvar formuly a Skolemov tvar formuly. Axiomy
   rovnosti, logika s rovnostou, veta o korektnosti, bezospornost
   predikatovej logiky, Godelova veta, Henkinova veta, Lindenbaumova veta.
   Veta o kompaktnosti.

3. Metoda rezolvent: Skolemovske standardne formy. Herbrandovske univerzum.
   Semanticky strom. Herbrandova veta I. a II. variant. Rezolvencna metoda,
   substitucia a unifikacia, unifikacna veta, uplnost rezolvencnej metody,
   strategia vymazavania, algoritmus pohltenia a jeho korektnost.

Datum poslednej aktualizacie tohto dokumentu: 30.4.99.
Posledna aktualizacia udajov v systeme: 091006-V393.