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

===================================  12.10.2011  ===================================

odhad výpočetní náročnosti řešení úloh na počítači
čas, prostor
měření v závislosti na velikosti vstupu
maximum přes vstupy dané velikosti
  lineární programování, simplexová metoda
  SAT, zChaff
složitost konkrétního algoritmu versus složitost úlohy
věta o zrychlení - existence jazyka, pro který dokazatelně neexistuje nejefektivnější algoritmus
třídy složitosti definované jako třídy úloh řešitelných při daném asymptotickém omezení složitosti
tato definice je vhodná pro teoretické zkoumání, ale pro praktické aplikace je podstatná
  složitost pro konkrétní velikosti vstupů a ne asymptotická složitost
příklady algoritmů pro násobení matic, asymptoticky nejrychlejší nejsou vhodné pro vstupy běžné velikosti
značení O(n), Omega(n), Theta(n).
typy úloh
  rozhodovací úloha
  výpočet funkce
  vyhledávací úloha
varianty problému kliky
  zda existuje klika alespoň dané velikosti (rozhodovací úloha)
  zjistit velikost maximální kliky (výpočet funkce)
  nalézt některou maximální kliku (vyhledávací úloha)
optimalizační úloha
  - množina přípustných řešení
  - kriteriální funkce
  - najít přípustné řešení s maximální nebo minimální hodnotou kriteriální funkce
příklady klika, MAX-SAT

příklady algoritmicky nerozhodnutelných úloh
složitost Presburgerovy aritmetiky a teorie reálných čísel
problém zastavení v daném čase

Odkazy ke zmínce o sporadických grupách
  http://en.wikipedia.org/wiki/Sporadic_group
  http://en.wikipedia.org/wiki/Monster_group

===================================  19.10.2011  ===================================

Příklady úloh třídy NP: tautologie, SAT, klika, vrcholové pokrytí, nezávislá množina,
Hamiltonovská kružnice, problém obchodního cestujícího (TSP).
Vzájemný převod mezi problémem SAT a kliky.
Násobení přirozených čísel ve složitosti n^{log_2 3}.
Kódování vstupu, efektivní kódování.

===================================  26.10.2011  ===================================

Efektivní kódování.
Příklady převodu vyhledávání na rozhodovací úlohu pro SAT, problém kliky a
  metoda půlení pro optimalizační úlohy.
Vzájemný převod rozhodovacích úloh a výpočtu funkce úloh.
Turingův stroj, varianty pro výpočet funkce a pro rozhodovací úlohy,
  měření prostoru při vstupní pásce jen pro čtení.
RAM, jednotková a logaritmická míra složitosti.
Booleovské obvody.
Simulace TS pomocí posloupnosti obvodů.

===================================  2.11.2011  ===================================

Třída NP, polynomiální převoditelnost, zavedení NP-úplnosti.
Problém SAT je NP-úplný.
NP-úplnost 3-SAT a problémů přesného 3-pokrytí, batohu a půlení.

===================================  9.11.2011  ===================================

NP-úplnost problému
 - Hamiltonovské kružnice, 
 - obchodního cestujícího,
 - MAX-2-SAT.
Algoritmus pro problém batohu polynomiální ve velikosti vstupních čísel.
Úplnost rezolučního odvozování.

===================================  16.11.2011  ===================================

Polynomiální algoritmus pro 2-SAT.
Aproximační algoritmy pro problém
  - vrcholového pokrytí (faktor 2)
  - obchodního cestujícího (faktor 1.5)
  - množinového pokrytí (faktor zhruba ln |X|, kde X je sjednocení vstupních množin)

===================================  23.11.2011  ===================================

Přednášky od 23.11. do 21.12. se nekonaly.

===================================  4.1.2012  ===================================

Využití náhodnosti pro demonstraci neizomorfnosti dvou grafů.
Zmínka o pravděpodobnostním testu neekvivalnce dvou read-once BDD.
Definice generátoru náhodných bitů, který je polynomiálně neodlišitelný
od skutečně náhodných bitů. Existence takového generátoru implikuje
P různé od NP.
Dokončení aproximačního algoritmu pro MAX-SAT s faktorem 3/4.
Analýza aproximačního algoritmu pro množinové pokrytí s faktorem H(max |S_i|).