=================  30.9.2003  ====================

spotřeba zdrojů - čas, paměť
příklady:
 - SAT (nejhorší případ 2^n, často lze lépe, zchaff)
 - třídění (bublinkové, stromem, heap-sort - n log n, často se používá shellsort - n^1.5)
 - násobení n^2, n log n log log n (zcela jiné speciální algoritmy pro hardware)
 - násobení matic (n^3, Strassen, další zlepšení, 2+eps hypotéza)
 - testování prvočíselnosti
 - problém zastavení v daném čase
 - Presburgerova aritmetika, reálná aritmetika
 - obtižnost inverze MD5

výpočetní modely 
 - TS + varianty
 - RAM + varianty

formalizace pojmu úloha
 - obecná úloha (sigma1 -> sigma2)
 - rozhodovací úloha
 - optimalizační úloha

meření složitosti
 - nejhorší versus průměrný případ
   (nejhorší je často příliš pesimistický, průměrný závisí na volbě
    rozdělení, které je často neznamé)
 - odhad složitosti pomocí funkce závisející na délce vstupu versus
   odhad složitosti pro vstupy fixované délku vstupu
   (Existují příklady, kdy asymptotická složitost je vzdálená složitosti
    v praktických situacích. Asymptotika je ale důležitá, pokud chceme
    získat alespoň nějaký obecný nadhled nad situací.)

=================  7.10.2003  ====================

Předmět zkoumání: asymptotická složitost rozhodovacích úloh na TS
(především polynomiální čas, nedeterministický polynomiální čas,
polynomiální prostor)

kódování vstupu pomocí slov v konečné abecedě, problém efektivního kódování.

Vztah obecných úloh a rozhodovacích úloh: hledání splňujícího
ohodnocení, Hamiltonovské kružnice, obecná věta o ekvivalenci
z hlediska polynomiálních úloh.
V důkazu této věty jsme trochu předběhli některé pojmy:
- předpokládáme předběžnou znalost toho, co je to jazyk rozpoznávaný TS
- jako složitost používáme představu o počtu operací na běžném počítači
  bez přesné definice.  Později tuto složitost nahradíme RAM s jednotkovou
  mírou složitosti.

Turingův stroj
jednostranné pásky, 
 vstupní (někdy jen ke čtení)
 pracovní
 výstupní (jen zápis)
instrukce s k-ticemi q,a,a,s,q

koncové stavy q-plus, q-minus
přijímání koncovým stavem q-plus
zamítnutí nedefinovaným přechodem (není def. instrukce nebo přechod mimo pásku)

měření časové složitosti
 vstupní páska může být použita k zápisu
 měří se počet kroků

měření prostorové složitosti
 vstupní páska jen pro čtení (umožňuje definovat prostor menší než n)
 meří se maximum počtu navštívených polí na jednotlivých pracovních páskách

RAM
registry r_i \in Z
vstupní posloupnost v_i \in Z
řídící jednotka
program pi_1, pi_2,...
čítač instrukcí kappa

příklad úlohy, kde je vícepáskový stroj efektivnější, je kopírování
 delšího úseku pásky.

=================  14.10.2003  ===================

parametry a instrukce RAM
měření složitosti (jednotková, logaritmická)
Booleovské obvody, posloupnosti obvodů, rozdíl proti formulím
-- vynecháno kódování obecných slov --

=================  21.10.2003  ===================

zopakování měr složitosti na RAM, souhrnný diagram plánovaných simulací
simulace vícepáskového stroje na jednopáskovém - program v pseudokódu

=================  4.11.2003  ====================

připomenut diagram transformací 1-TS, m-TS, RAM j.m.s.p.o., RAM l.m.
  k <= b <= kO(log k) (při splnění p.o.)
simulace RAM na 6-TS
  pásky: vstupní, paměť, adresovací, 3 aritmetické
  program pro RAM vyjádříme jako vývojový diagram
  blok každé instrukce přepíšeme na TS (u skoků budou mít dva možné výstupy)
  tím získáme vývojový diagram pro simulující TS
  z něj získáme TS
  časová složitost simulace jedné instrukce
    bitové složitosti jednotlivých instrukcí: b_i, b = \sum b_i
    čtení z paměti a zápis do paměti O(s), s = \sum b_i
    aritmetická operace O(b_i^2)
    součet přes všechny instrukce \sum b_i^2 + k \sum b_i \le 2 (\sum b_i)^2
           pokud b_i \le O(log k), pak také omezeno O(k^2 log k)

=================  11.11.2003  ===================

Simulace polynomiálně omezeného TS polynomiálně velkými obvody.
TS s pomocnou funkcí, ekvivalence P/poly a polynomiálně velkých obvodů bez důkazu.
Příklady úloh se snadno verifikovatelnými důkazy kladné odpovědi: SAT, klika.
Polynomiálně omezené relace, definice třídy NP, polynomiální převoditelnost.
Problém SAT je převoditelný na problém kliky.

=================  18.11.2003  ===================

Dokončení důkazu p-převoditelnosti SAT na problém kliky.
Vsuvka: Pokud formule v KNF má m klausulí, které mají délky k_1, k_2, ..., k_m,
  pak platí implikace
       \sum_i  1/2^{k_i}  <  1  =>  formule je splnitelná
  Např. při délkách 3,3,3 je
           \sum_i  1/2^{k_i} = 3/8 <  1
  a formule je tedy splnitelná.
p-převoditelnost je tranzitivní.
L_1 p-převoditelný na L_2, L_2 \in P => L_1 \in P
Definice NP-úplné úlohy.
Pokud je L NP-úplná, pak L \in P <=> P = NP
Pokud jsou L_1 a L_2 NP-úplné, pak L_1 \in P <=> L_2 \in P
Cookova věta: SAT je NP-úplný 
  Pro libovolnou danou NP-úlohu L jsme zkonstruovali funkci g_L(w), jejíž hodnotou
  je Booleovský obvod a která dává p-převoditelnost L na problém splnitelnosti obvodů.
  Dotažení převodu až na splnitelnost formulí (SAT) příště.

=================  25.11.2003  ===================

Splnitelnost obvodů je p-převoditelná na SAT.
Důsledek: SAT je NP-úplný.
SAT je p-převoditelný na 3-SAT.
Důsledek: 3-SAT je NP-úplný. 
Pro porovnání: 2-SAT je v P.
(k,s)-SAT, formulace věty o skoku v parametru s.
Důkaz splnitelnosti každé (k,k)-SAT instance z Hallovy věty.

==================   2.12.2003  ==================

Přednáška odpadla.