24
Teoretická informatika
Opakování z minulé přednášky
• Co říká Churchova teze?• Jak lze kódovat Turingův stroj?• Co je to Univerzální Turingův stroj?• Formulujte problém příslušnosti pro Turingovy
stroje. Je tento problém rozhodnutelný? Proč?• Jakým způsobem lze dokázat, že existují problémy,
které nejsou ani částečně rozhodnutelné?• Formulujte problém zastavení pro TS.• Jak dokázat, že problém zastavení je
nerozhodnutelný?• Vysvětlete metodu redukce.
2
Teoretická informatika 3
Rozhodnutelné problémy
• Je-li problém rozhodnutelný, ještě to neznamená, že je rozhodnutelný „v rozumném čase“.
• Za rozumný čas považujeme takový čas, kdy je pro nás výsledek výpočtu ještě využitelný.
• Rozhodnutelností se zabývá teorie vyčíslitelnosti
• Časovou náročností se zabývá teorie složitosti– O tom bude dnešní přednáška
Teoretická informatika 4
Složitost
• Složitost algoritmu vyjadřuje náročnost algoritmu na výpočetní prostředky počítače v závislosti na délce vstupních dat.
• Časová složitost – náročnost algoritmu na čas procesoru – V jakých jednotkách časovou složitost měřit?– Značení: T(x)
• Prostorová složitost – náročnost algoritmu na operační paměť– V jakých jednotkách prostorovou složitost měřit?– Značení: S(x)
Teoretická informatika 5
Výpočetní model pro složitost
• Turingův stroj není vhodný kvůli sekvenčnímu přístupu na pásku
• RAM stroj– Neomezený počet registrů pro uložení
libovolně velkých čísel– Instrukce READ, STORE, LOAD, ADD,
SUB, JUMP, JPOS, JNEG, JZERO, HALT– V základních rysech odpovídá reálnému
počítači
Teoretická informatika 6
Délka výpočtu výrazů
• T(a) = 1, je-li a konstanta či proměnná
• T(ab) = 1 + T(a) + T(b), kde {+,-,*,/,div,mod}
• T(a AND b) = 1 + T(a) [ + T(b)]
• T(a OR b) = 1 + T(a) [ + T(b)]
• T(NOT a) = 1 + T(a)
Teoretická informatika 7
Čas na vykonání příkazu
• Elementární příkazy (délka výpočtu 1):– načtení/výpis jedné proměnné– přiřazení (nutno přičíst čas potřebný na
vyhodnocení přiřazované hodnoty)
• T(IF a THEN b ELSE c) = 1 + T(a) + T(b)|T(c)
• T(FOR i:=1 TO n DO p) = n*(T(p)+2)
Teoretická informatika 8
Druhy složitosti
• Složitost v nejhorším případě: ze všech možných vstupních dat uvažujeme ta, nad nimiž je výpočet (časově) nejnáročnější
• Složitost v nejlepším případě: ze všech možných vstupních dat uvažujeme ta, nad nimiž je výpočet (časově) nejméně náročný
• Složitost v průměrném případě: z (časových) náročností všech možných vstupních dat vypočteme průměrnou hodnotu
• Kterou složitost v praxi nejvíce oceníme?• Kterou složitost dokážeme nejsnáze určit?
Teoretická informatika 9
Definice časové složitosti
• Časová složitost algoritmu je funkce, která je pro každou velikost vstupních dat rovna délce nejdelšího výpočtu na všech možných datech této délky– Je tedy třeba provést analýzu nejhoršího
případu
• Časová složitost problému je minimum časových složitostí všech algoritmů řešících daný problém
Teoretická informatika 10
Definice prostorové složitosti
• Prostorová složitost algoritmu je funkce, která je pro každou délku vstupních dat rovna největšímu počtu registrů RAM stroje / políček pásky Turingova stroje obsazených během výpočtu
• Prostorová složitost problému je minimum prostorových složitostí všech algoritmů řešících daný problém
• Extrasekvenční prostorová složitost je prostorová složitost, do níž nezapočítáváme vstupní údaje
Teoretická informatika 11
Vztah času a prostoru
• Základní rozdíl: prostor lze využít opakovaně, čas ne
• Za jednu jednotku času můžeme obsadit maximálně jednu jednotku prostoru– Anebo využít prostor obsazený dříve
• K obsazení nové jednotky prostoru vždy potřebujeme nejméně jednu jednotku času
• Důsledek: Časová složitost je vždy větší nebo rovna prostorové složitosti
Teoretická informatika 12
Asymptotická časová složitost
• Zanedbáváme aditivní konstanty– Pro analýzu složitosti nemají praktický význam
• Zanedbáváme multiplikativní konstanty– Lze nahradit rychlejším počítačem, větším počtem
počítačů, atd.
• Zajímá nás jen „hrubá“ charakteristika funkce – její chování v nekonečnu– Tedy jen její asymptoty
• Zavedení tříd funkcí
Teoretická informatika 13
Třídy funkcí podle asymptotického růstu• O(g) = {f | c>0, n0: n>n0: |f(n)| ≤ |c∙g(n)|}
– Třída funkcí, které rostou asymptoticky nejvýše tak rychle, jako funkce g
– Např. f(x) = ax2+b O(x2) pro libovolné a, b– Např. f(x) = ax2+b O(x3) pro libovolné a, b
(g) = {f | c>0, n0: n>n0: |c∙g(n)| ≤ |f(n)|}– Třída funkcí, které rostou asymptoticky alespoň tak rychle, jako
funkce g– Např. f(x) = ax2+b (x2) pro libovolné a, b– Např. f(x) = ax3+bx2+c (x2) pro libovolné a, b
(g) = {f | c1,c2>0, n0: n>n0: |c1∙g(n)| ≤ |f(n)| ≤ |c2∙g(n)|}– Třída funkcí ohraničených funkcí g z obou stran– Např. f(x) = ax2+b (x2) pro libovolné a, b– Např. f(x) = ax3+bx2+c (x3) pro libovolné a, b
• Platí: (g) = O(g) (g)
Teoretická informatika 14
Složitostní třídy I.
• Konstantní: O(c)– př.: „Hello world!“, výběr konstanty
• Logaritmická: O(logc n) pro libovolné c– př.: Vyhledávání půlením intervalu, vyhledávání v binárním stromu
• Lineární: O(n)– př.: Sekvenční vyhledávání, překladač
• Kvadratická: O(n2)– př.: Bubble sort, součet matic řádu n
• Kubická: O(n3)– př.: Násobení matic řádu n
• Polynomiální: O(nc) pro libovolné cN• Exponenciální: O(cn) pro libovolné cN
– př.: Problém obchodního cestujícího
Teoretická informatika 15
Řešitelnost v rozumném čase
• Otázka: Kde leží hranice mezi problémy, které považujeme za řešitelné v rozumném čase a těmi, které jsou v rozumném čase neřešitelné?
Teoretická informatika 16
Nedeterminismus
• V teorii složitosti uvažujeme i nedeterministické výpočetní modely– Nedeterministický Turingův stroj– Nedeterministický RAM stroj
• Každý nedeterministický model lze převést na deterministický
• Za cenu nárůstu časové složitosti– Je třeba vyzkoušet všechny možnosti
Teoretická informatika 17
Složitostní třídy II.
• DTIME(f(n)) = množina všech problémů řešitelných deterministickým algoritmem s časovou složitostí patřící do O(f(n))
• DSPACE(f(n)) = množina všech problémů řešitelných deterministickým algoritmem s prostorovou složitostí patřící do O(f(n))
• NTIME(f(n)) = množina všech problémů řešitelných nedeterministickým algoritmem s časovou složitostí patřící do O(f(n))
• NSPACE(f(n)) = množina všech problémů řešitelných nedeterministickým algoritmem s prostorovou složitostí patřící do O(f(n))
Teoretická informatika 18
Vztahy složitostních tříd I.
• DSPACE(f(n)) NSPACE(f(n))– Každý problém řešitelný v prostoru f(n) deterministicky,
lze v témže prostoru řešit nedeterministicky• DTIME(f(n)) NTIME(f(n))
– Každý problém řešitelný v čase f(n) deterministicky, lze v témže čase řešit nedeterministicky
• DTIME(f(n)) DSPACE(f(n))– Prostor lze použít opakovaně, čas nikoliv. Tedy co lze
řešit v čase f(n), lze řešit i v prostoru f(n)• NTIME(f(n)) NSPACE(f(n))
– Taktéž nedeterministicky
Teoretická informatika 19
Vztahy složitostních tříd II.
• NTIME(f(n)) c>0 DTIME(cf(n))– Při převodu nedeterminismu na determinismus je třeba
vyzkoušet všechny možnosti (tj. prohledat c-ární výpočtový strom)
• NSPACE(f(n)) c>0 DTIME(cf(n))– Počet všech konfigurací NTS pracujícího v prostoru f(n) je
|Q|∙||f(n). Sestrojíme-li graf, jehož uzly odpovídají konfiguracím a hrany přechodové fci, jedná se o prohledávání tohoto grafu se složitostí v O(|U|2), tedy v O(cf(n)).
• NTIME(f(n)) DSPACE(f(n))– Nedeterministický stroj je náročnější na čas, nikoliv na
paměť. Co lze řešit (byť nedeterministicky) v čase f(n), lze řešit i v prostoru f(n)
Teoretická informatika 20
Složitostní třídy III.
• P = k>0 DTIME(nk)• NP = k>0 NTIME(nk)• PSPACE = k>0 DSPACE(nk)• NPSPACE = k>0 NSPACE(nk)• DEXPTIME = k>0 DTIME(2^nk)• NEXPTIME = k>0 NTIME(2^nk)• DLOG = DSPACE(log n)• NLOG = NSPACE(log n)
Teoretická informatika 21
Vztahy složitostních tříd
• DLOG NLOG P NP PSPACE DEXPTIME NEXPTIME
• O všech inkluzích se předpokládá, že jsou ostré. O žádné se to však zatím nepodařilo dokázat
• Jistě pouze víme, že– DLOG PSPACE– P DEXPTIME– NP NEXPTIME
• Nejvýznamnější inkluze je mezi P a NP
Teoretická informatika 22
Úplné problémy
• Nechť C je složitostní třída. Problém P nazveme C-úplný, jestliže PC a jestliže pro každý problém patřící do C platí, že jej lze redukovat na P.– Tedy QC: Q ≤ P
• Úplné problémy jsou tedy nejtěžší problémy v dané třídě
• Je-li rozdíl mezi danou třídou a nižší třídou neprázdný, pak obsahuje právě tyto problémy
Teoretická informatika 23
Příklady NP-úplných problémů
• Problém obchodního cestujícího– Problém nalezení nejkratší hamiltonovské kružnice
v grafu o n vrcholech• Problém splnitelnosti booleovské formule
– Je dána výroková formule (v KNF). Existuje ohodnocení proměnných takové, že formule je pravdivá?
• Problém batohu– Je dána konečná množina objektů. Každý objekt má svoji
hmotnost a cenu. Problém spočívá v nalezení takové podmnožiny objektů, jejichž celková hmotnost je nižší než daná mez a jejichž cena je nejvyšší možná
• …
Teoretická informatika 24
P =? NP
• Nejvýznamnější problém teoretické informatiky• Všechny NP-úplné problémy jsou navzájem
redukovatelné jeden na druhý• Nalezení polynomiálního algoritmu pro jediný
z nich znamená nalezení polynomiálního algoritmu pro všechny– a tedy dokázání, že P = NP.
• Důsledek: konec jednosměrných funkcí (hashování, šifrování)
