PRŮBĚH PŘEDNÁŠKY VÝPOČTOVÁ SLOŽITOST (LETNÍ SEMESTR 2008/2009)

==========================  25.2.2009  ==============================

Algoritmus pro problém batohu pomocí dynamického programování v čase polynomiálním
  od velikosti vstupních čísel.
Programovací jazyk s proměnnými pro TS. Použití na simulaci vícepáskového TS
  pomocí jednopáskového TS.

==========================  4.3.2009  ==============================

Simulace 1-TS pomocí RAM.
Simulace RAM pomocí TS. Složitost TS vyjádřena pomocí jednotkové i bitové složitosti RAM.
Zavedení aproximačního faktoru pro optimalizační úlohy.

==========================  11.3.2009  ==============================

Aproximační algoritmus pro vrcholové pokrytí s faktorem 2. Poznámka
o neaproximovatelnosti s faktorem 2 - eps.
Aproximační algoritmy pro TSP s faktorem 2 a 3/2.
Zaveden problém množinového pokrytí a ukázána jeho souvislost s minimalizací KNF a DNF.

==========================  18.3.2009  ==============================

Aproximační algoritmus pro množinové pokrytí.
Zavedení PSPACE, PSPACE-úplnost, problém KBF.

==========================  25.3.2009  ==============================

NP \subset PSPACE .
Poznámka o #P (sharp P), #SAT (number SAT) a permanentu.
KBF \in PSPACE.
Zavedení některých pomocných formulí pro simulaci TS pomocí formulí tvaru KBF.
  Mimo jiné byla použita formule pro Booleovskou funkci
  "právě jedna jednička na vstupu".

==========================  1.4.2009  ==============================

Přednáška se nekonala.

==========================  8.4.2009  ==============================

Dokončení PSPACE-úplnosti KBF.
Hra na grafech, existence vítězné nebo remízní strategie pro libovolnou konečnou hru.
Rozhodnutí, kdo má vítěznou strategii v hře na grafech je PSPACE-úplná úloha.

==========================  15.4.2009  ==============================

Úvod do kryptografických systémů s veřejným klíčem.
Rozšířený Eukleidův algoritmus, inverzní prvek v okruhu Z_m.
Čínská věta o zbytcích, bijekce mezi Z_{n_1 ... n_k} a kartézským součinem Z_{n_1} x ... x Z_{n_k}.
Eulerova funkce, výpočet z rozkladu na prvočinitele.
Formulace Eulerovy věty.

==========================  22.4.2009  ==============================

Eulerova věta.
Kryptografické systémy RSA a Diffie-Hellman.
Úvod do složitosti Booleovských funkcí.
Efektivní reprezentace funkce, velikost reprezentace.
Booleovské formule, obvody, rozhodovací diagramy, read-once rozhodovací diagramy,
DNF, KNF, rozhodovací stromy.

==========================  29.4.2009  ==============================

Převody ze slabších modelů do silnějších v diagramu Booleovských modelů.
Zavedení značení size_M(f), dt(f), dnf(f), cnf(f).
Poznámka o postupu vyvážení obecné Booleovské formule.
Pojem duální funkce f^* a důkaz dnf(f) = cnf(f^*), size_formule(f) = size_formule(f^*).

==========================  6.5.2009  ==============================

Duální funkce, dnf(f^*) = cnf(f), cnf(f^*) = dnf(f), dt(f^*) = dt(f).
dnf(f) + cnf(f) \le dt(f) pomocí dt_0(f), dt_1(f).
Posloupnosti Booleovských funkcí, Poly(M) pro model M.
Složitost funkce parity v různých modelech. Dolní odhad pro dnf, cnf.
Důsledky pro ostré inkluze v diagramu.
Cvičení: Najít funkci, pro kterou dt_0(f) + dt_1(f) < dt(f).

==========================  13.5.2009  ==============================

Monom, implikát, primární implikát.
Funkce je disjunkcí primárních implikátů.
Minimální DNF nemusí obsahovat všechny primární implikáty.
Částečný vstup, podkrychle, jsou to množiny splňujících ohodnocení monomu.
Primární implikáty monotonní funkce jsou monotonní.
Pro monotonní f je dnf(f) rovno počtu primárních implikátů.
Funkce free-dnf, free-cnf.
dnf(free-cnf_n) \ge 2^n, cnf(free-dnf_n) \ge 2^n.
Důsledek pro separaci tříd Poly(dnf), Poly(cnf) a Poly(dt).