Složitost. Teoretická informatika Tomáš Foltýnek

Teoretická informatika Tomáš Foltýnek [email protected]

Složitost

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


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

3


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)

4


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

5


Délka výpočtu výrazů •  T(a) = 1, je-li a konstanta či proměnná •  T(a⊕b) = 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)

6


Č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*(p+2)

7


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?

8


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

9


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

10


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

11


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í

12


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)

13


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é c∈N •  Exponenciální: O(cn) pro libovolné c∈N –  př.: Problém obchodního cestujícího

14


Ř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é?

15


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

16


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))

17


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

18


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)

19


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)

20


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

21


Úplné problémy •  Nechť C je složitostní třída. Problém P nazveme C-úplný, jestliže P∈C a jestliže pro každý problém patřící do C platí, že jej lze redukovat na P. –  Tedy ∀Q∈C: 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

22


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á •  …

23


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í)

24

Složitost. Teoretická informatika Tomáš Foltýnek

Recommend Documents