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

===================================  1.10.2013  ===================================

zavedení pojmů časová a prostorová složitost
rozdíl mezi složitostí konkrétního algoritmu a složitostí úlohy
asymptotická složitost, třídy P, NP, PSPACE
značení O(f), \Omega(f)
rozhodovací úlohy, výpočet funkce, vyhledávací úlohy, příklady
kódování vstupu pomocí slov z konečné abecedy, požadavek rozumného kódování
dokazatelně obtížné úlohy, problém zastavení v daném čase, Presburgerova
  aritmetika, aritmetika reálných čísel
zavedení některých konkrétních úloh, problém splnitelnosti (SAT), problém kliky,
  vrcholového pokrytí, Hamiltonovské kružnice, TSP
převedení problému Hamiltonovské kružnice na TSP
převedení problémů SAT a kliky oběma směry
 
===================================  10.10.2013  ===================================

\Theta(g)
Algoritmy pro třídění podle kritéria "na místě" (in situ) a stability.
Algoritmus pro násobení přirozených čísel v čase O(n^log_2 3), zmínka
  o algoritmu složitosti O(n log n log log n).
Věta o zrychlení a o mezerách.
Třídy DTIME(t), DSPACE(s).
Poznámka o obtížně vyčíslitelných racionálních číslech.
Převod vyhledávací úlohy a výpočtu funkce na rozhodovací úlohy.
Zavedení RAM, jednotková a logaritmická míra složitosti.

===================================  17.10.2013  ===================================

Příklad programu pro RAM, který nesplňuje polynomiální omezení čísel.
Citován výsledek, že výpočet RAM bez omezení čísel s polynomiální jednotkovou složitostí
  je ekvivalentní polynomiálnímu prostoru na TS.
Simulace TS v čase t na RAM s jednotkovou složitostí O(t) a bitovou složitostí O(t log t).
Bez důkazu simulace RAM s jednotkovou mírou k a bitovou mírou b na TS v čase O(k^2 log k)
  nebo O(b^2).
Booleovský obvod a jeho převod na formuli.
Simulace TS pomocí posloupnosti obvodů.
Definice třídy NP pomocí kvantifikace polynomiálně omezené relace.
Polynomiální převoditelnost.
Příště: Uvést odhady pro simulaci vícepáskového TS na jednopáskovém.
Zadáno cvičení: Jak zajistit, aby C_m(x)=0, pokud x není tvaru k_m(w).

===================================  24.10.2013  ===================================
Přednáška se nekonala.

===================================  31.10.2013  ===================================
Přednáška se nekonala.

===================================  7.11.2013  ===================================
Přednáška se nekonala.

===================================  15.11.2013  ===================================

Simulace k-TS pomocí 1-TS v čase O(t log t) bez důkazu.
Úprava obvodu pro rozpoznání vstupů, které nemají tvar k_n(w) pro dané n.
Zadáno cvičení: nalézt obvod složitosti 2.5n + O(1) pro současný výpočet konjunkce,
  disjunkce a parity daných n proměnných.
Připomínka definice NP-úplnosti.
NP-úplnost úloh SAT-obvody, SAT-CNF, 3-SAT.
Převod 3-SAT na úlohu přesného-3-pokrytí a dále na problém batohu a problém půlení
  (problém dvou loupežníků).

===================================  21.11.2013  ===================================

Problém vrcholového pokrytí, Hamiltonovské kružnice, MAX-2-SAT.
Rezoluční metoda důkazu nesplnitelnosti CNF.
Polynomiální algoritmus pro 2-SAT.

===================================  28.11.2013  ===================================

Obvod pro výpočet AND, OR, XOR velikosti 2.5 n + C.
Polynomiální algoritmus pro problém batohu.
Aproximační algoritmy
  faktor 2 pro problém vrcholového pokrytí,
  faktor 3/2 pro problém TSP,
  faktor log m pro problém množinového pokrytí.
Zadáno cvičení: Dokažte, že souvislý graf se sudými stupni vrcholů je Eulerovský.

===================================  5.12.2013  ===================================

Aproximační faktor algoritmu pro množinové pokrytí pomocí harmonické řady.
Převod SAT na problém množinového pokrytí.
Frekventistický přístup k pravděpodobnosti.
Střední hodnota součtu a součinu náhodných veličin.
Zmínka o aproximačním algoritmu pro problém MAX-CUT autorů Goemans a Williamson, aproximační
  faktor je vyjádřen jako minimum z výrazu 2/pi phi/(1 - cos phi).
Příklad využití náhodnosti pro interaktivní důkaz neizomorfnosti dvou grafů.
Binární rozhodovací diagram pro paritu a důkaz, že DNF pro paritu je exponenciálně velká.

===================================  12.12.2013  ===================================

DNF odvozená z konečných geometrií definuje funkci, která má pouze exponenciálně
  velké 1-bdd.
Porovnání vyjadřovací síly DNF, CNF, formulí, bdd, 1-bdd.
Existence polynomiálního převodu 1-bdd na formule implikuje polynomiální převod
  obecných bdd na formule.
Test splnitelnosti a výpočet počtu splňujících ohodnocení pro 1-bdd.
Polynomy definované pomocí součtu přes cesty v acyklickém orientovaném grafu.
Je-li f(x_1, ..., x_n) polynom přiřazený 1-bdd, pak f(1/2, ..., 1/2) je pravděpodobnost,
  že náhodné ohodnocení je splňující.
Příště: test neekvivalence 1-bdd pomocí dosazování hodnot z obecného tělesa.

===================================  19.12.2013  ===================================

Pravděpodobnostní test neekvivalence 1-dd.
Popis pravděpodobnostního polynomiálního aproximačního algoritmu pro MAX-SAT s faktorem 3/4
  a část jeho analýzy.

===================================  2.1.2014  ===================================

Dokončení pravděpodobnostního aproximačního algoritmu pro MAX-SAT s faktorem 3/4.
Deterministická verze předchozího algoritmu pomocí metody postupného upřesňování.
Třída PSPACE a polynomiální hierarchie (PH).
NP \subseteq PSPACE.
Třídy \Sigma_k, \Pi_k jsou také v PSPACE (bez důkazu).
Pokud je PH nekonečná, pak PSPACE není její sjednocení.

===================================  9.1.2014  ===================================

QBF lze interpretovat jako formule predikátového počtu v jazyce s jedním predikátem a
  žádným funkčním symbolem.
QBF je PSPACE-úplná úloha.
Každá konečná hra má vítěznou strategii pro jednoho z hráčů nebo remízní pro oba hráče.
Zavedení hry na grafech.