================= 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.