Algoritmy a výpočetní složitost

Algoritmy a výpočetní složitost Zdeněk Sawa Katedra informatiky, FEI Vysoká škola báňská – Technická universita Ostrava 17. listopadu 15, Ostrava-Poruba 708 33 Česká republika

12. prosince 2005

Zdeněk Sawa (VŠB-TU Ostrava)

Algoritmy a výpočetní složitost

12. prosince 2005

1 / 42

Co je to algoritmus? Algoritmus Algoritmus je mechanický postup skládající se z nějakých jednoduchých elementárních kroků, který pro nějaký zadaný vstup vyprodukuje nějaký výstup. Algoritmus může být zadán: slovním popisem v přirozeném jazyce jako počítačový program v nějakém programovacím jazyce (C, C++, Java, Pascal, . . . ) jako hardwarový obvod ... Algoritmy slouží k řešení různých problémů. Zdeněk Sawa (VŠB-TU Ostrava)


12. prosince 2005

2 / 42

Problémy Problém V zadání problému musí být určeno: co je množinou možných vstupů co je množinou možných výstupů jaký je vztah mezi vstupy a výstupy vstupy


výstupy


12. prosince 2005

3 / 42

Příklad problému Problém Vstup: Seznam měst a silnic spojujících tato města. U každé silnice je uvedeno, z kterého města do kterého vede, a jaká je její délka (v km). Dále pak dvě města ze seznamu měst – označme je město A a město B. Výstup: Nejkratší cesta z města A do města B.

23

28

18

15 14 20

A

21

17

30 31

17

18

B

22 41 25 37

34 Zdeněk Sawa (VŠB-TU Ostrava)

29 Algoritmy a výpočetní složitost

12. prosince 2005

4 / 42

Další příklady problémů Vyhledávání výskytů slova v textu Vstup: Text T a slovo S. Výstup: Seznam všech pozic, na kterých se v textu T vyskytuje slovo S.

Prvočíselnost Vstup: Přirozené číslo n. Výstup: „Anoÿ pokud je n prvočíslo, „Neÿ v opačném případě. Pozn.: Přirozená čísla N = {0, 1, 2, 3, 4, 5, . . .}



12. prosince 2005

5 / 42

Rozhodovací a optimalizační problémy

Situace, kdy množina výstupů je {„Anoÿ, „Neÿ} je poměrně častá. Takovým problémům se říká rozhodovací problémy.

Prvočíselnost Vstup: Přirozené číslo n. Otázka: Je n prvočíslo?

Problémům, kde je úkolem najít mezi mnoha potenciálními řešeními takové, které je podle nějakého zadaného kritéria nejlepší, se nazývají optimalizační problémy.



12. prosince 2005

6 / 42

Instance problému

Instance problému Konkrétní vstup z množiny možných vstupů problému se nazývá instance problému. Příklad 1: Text „010001001010100101100101ÿ a slovo „1011001ÿ je instancí problému Vyhledávání slova v textu. Příklad 2: Číslo 1729 je instancí problému Prvočíselnost.



12. prosince 2005

7 / 42

Řešení problémů

Řešení problému Algoritmus řeší daný problém, když: 1

2

Se pro libovolný vstup daného problému (libovolnou instanci) po konečném počtu kroků zastaví. Vyprodukuje výstup z množiny možných výstupů, který vyhovuje podmínkám uvedeným v zadání problému.

Algoritmus, který řeší daný problém, je korektní. Jeden problém může mít více různých korektních řešení.



12. prosince 2005

8 / 42

Doba výpočtu Počítače pracují rychle (řádově miliardy operací za sekundu), ovšem ne nekonečně rychle – provedení jedné operace trvá nějakou nenulovou dobu. Výpočet pro tentýž vstup může u různých algoritmů (nebo u různých implementací téhož algoritmu) trvat různou dobu. Tato doba závisí mimo jiné na: konkrétní implementaci algoritmu konkrétním použitém programovacím jazyce konkrétním použitém překladači nebo interpretru konkrétním použitém hardwaru (zejména na taktovací frekvenci procesoru) ...



12. prosince 2005

9 / 42

Posuzování efektivnosti algoritmů

Přirozené otázky: Jak závisí doba běhu programu na použitém algoritmu? Který z algoritmů, které řeší daný problém, je „lepšíÿ?



12. prosince 2005

10 / 42

Velikost vstupu

Pokud známe všechny potřebné detaily můžeme dobu běhu programu pro daný konkrétní vstup vypočítat, případně změřit. Doba běhu programu je obecně pro různé vstupy různá. Zavádíme pojem velikost vstupu – např. počet měst a silnic, počet znaků v textu a ve slově, počet bitů v binární reprezentaci čísla apod. Nejčastěji je velikost vstupu definována jako počet bitů (resp. bytů) vstupu.



12. prosince 2005

11 / 42

Efektivnost algoritmů U daného algoritmu zkoumáme, jak závisí doba běhu programu na velikosti vstupu, tj. jak dlouho běží program pro vstup velikosti n.

Časová složitost Funkce, která vyjadřuje závislost doby běhu programu na velikosti vstupu se nazývá časová složitost algoritmu. Zkoumáme buď: dobu běhu v nejhorším případě, nebo dobu běhu v průměrném případě.



12. prosince 2005

12 / 42

Příklad: třídění

Problém: Třídění Vstup: Posloupnost n prvků a1 , a2 , . . . , an . Výstup: Prvky a1 , a2 , . . . , an seřazené od nejmenšího po největší. Příklad: Vstup: 31, 41, 59, 26, 41, 58 Výstup: 26, 31, 41, 41, 58, 59



12. prosince 2005

13 / 42

Algoritmus 1 – třídění přímým vkládáním

31 41 59 26 41 58 – nesetříděné prvky – setříděné prvky – právě zpracovávaný prvek



12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42





12. prosince 2005

14 / 42



Celkový počet operací v nejhorším případě: 1 + 2 + 3 + · · · + (n − 2) + (n − 1) =


n · (n − 1) 1 1 = n2 − n 2 2 2


12. prosince 2005

14 / 42

Algoritmus 2 – Merge Sort

Hlavní myšlenka: Dvě setříděné posloupnosti snadno spojíme do jediné setříděné posloupnosti. Pokud mají obě posloupnosti dohromady n prvků, vyžaduje tato operace n kroků.

34 42 58 61 =⇒

10 11 53 67



12. prosince 2005

15 / 42



34 42 58 61 =⇒

11 53 67


10


12. prosince 2005

15 / 42



34 42 58 61 =⇒

53 67


10 11


12. prosince 2005

15 / 42



42 58 61 =⇒

53 67


10 11 34


12. prosince 2005

15 / 42



58 61 =⇒

53 67


10 11 34 42


12. prosince 2005

15 / 42



58 61 =⇒

67


10 11 34 42 53


12. prosince 2005

15 / 42



61 =⇒

67


10 11 34 42 53 58


12. prosince 2005

15 / 42



=⇒

67


10 11 34 42 53 58 61


12. prosince 2005

15 / 42



=⇒


10 11 34 42 53 58 61 67


12. prosince 2005

15 / 42

Algoritmus 2 – Merge Sort (pokračování) Vstup: 58, 42, 34, 61, 67, 10, 53, 11 n

58

42

42 58

34

61

67

34 61

10

53

10 67

11

11 53

log2 n

34 42 58 61

10 11 53 67

10 11 34 42 53 58 61 67 Celkový počet operací: n log2 n Zdeněk Sawa (VŠB-TU Ostrava)


12. prosince 2005

16 / 42

Porovnání dvou implementací

Je třeba setřídit 106 prvků. Implementace A: Použito třídění přímým vkládáním Rychlý počítač: 109 operací za sekundu Efektivní implementace: 2n2 operací Implementace B: Použit merge sort Pomalý počítač: 107 operací za sekundu Neefektivní implementace: 50n log n operací



12. prosince 2005

17 / 42

Porovnání dvou implementací (pokračování)

Setřídění 106 prvků vyžaduje: Implementace A:

Implementace B:


2 · (106 )2 instr. = 2000 s 109 instr./s 50 · (106 ) log(106 ) instr. ≈ 100 s 107 instr./s


12. prosince 2005

18 / 42

Příklad Program zpracovává vstup velikosti n. Předpokládejme, že pro vstup velikosti n provede f (n) operací, a že provedení jedné operace trvá 1 µs (10−6 s). n f (n)

20

40

60

80

100

200

500

1000

n

20 µs

40 µs

60 µs

80 µs

0.1 ms

0.2 ms

0.5 ms

1 ms

n log n

86 µs

0.213 ms

0.354 ms

0.506 ms

0.664 ms

1.528 ms

4.48 ms

9.96 ms

n2

0.4 ms

1.6 ms

3.6 ms

6.4 ms

10 ms

40 ms

0.25 s

1s

n3

8 ms

64 ms

0.216 s

0.512 s

1s

8s

125 s

16.7 min.

n4

0.16 s

2.56 s

12.96 s

42 s

100 s

36560 let

38.3·109 let

40.1·1015 let

–

–

–

–

–

–

–

–

–

2n n!

1.05 s

12.75 dní

1.85·106 let 6.2·1035 let



26.6 min. 17.36 hod. 11.57 dní

12. prosince 2005

19 / 42

Asymptotická notace

Při analýze algoritmů většinou není potřeba spočítat počet provedených operací (resp. čas jejich provedení) přesně. Používá se asymptotická notace, která vyjadřuje odhad rychlosti růstu funkce, přičemž jsou zanedbány konkrétní konstanty a méně významné členy: Např. místo 35n2 + 732n + 2378 pracujeme s výrazem O(n2 ). Výhoda asymptotické notace: Výrazně zjednodušuje analýzu, výsledek nezávisí na detailech konkrétní implementace.



12. prosince 2005

20 / 42

Datové struktury

Důležitou součástí studia algoritmů je zkoumání různých datových struktur a analýza složitosti jednotlivých operací prováděných na těchto datových strukturách (vkládání, odstraňování, vyhledávání prvků). Pole: 0

1

2

3

4

5

6

7

8

9 10 11 12 13

Seznam:



12. prosince 2005

21 / 42

Datové struktury (pokračování)

Hashovací tabulka: Strom:



12. prosince 2005

22 / 42

Efektivní algoritmy

Obecně jsou ze efektivní algoritmy považovány ty, jejichž časová složitost je omezena polynomem, tj. O(nk ), kde k je konstanta. O(n), O(n2 ), O(n3 ), O(n4 ), . . . Takovým algoritmům se říká polynomiální algoritmy. n

2n

Pokud je složitost např. 2n , 22 , 22 , . . ., pak algoritmus není polynomiální. Algoritmům, které mají složitost 2O(n


k)

se říká exponenciální algoritmy.


12. prosince 2005

23 / 42

Obtížné problémy

Otázka: Existuje pro každý problém efektivní (polynomiální) algoritmus, který ho řeší?



12. prosince 2005

24 / 42

Obtížné problémy

Otázka: Existuje pro každý problém efektivní (polynomiální) algoritmus, který ho řeší?

Odpověď: Ne, existují problémy, pro které se dá dokázat, že neexistuje žádný efektivní algoritmus, který by daný problém řešil. Dokonce existují problémy, pro které se dá dokázat, že neexistuje žádný (ani neefektivní) algoritmus, který by daný problém řešil.



12. prosince 2005

24 / 42

Neexistence algoritmů

Námitka: Jak dokázat, že něco neexistuje?



12. prosince 2005

25 / 42

Neexistence algoritmů

Námitka: Jak dokázat, že něco neexistuje?

Odpověď: Sporem. Předpokládáme, že to existuje a ukážeme, že z toho vyplývá nějaký závěr, který je ve zjevném rozporu se skutečností (typicky ukážeme, že něco musí být současně pravda i nepravda).



12. prosince 2005

25 / 42

Příklad obtížného problému Problém Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant. Otázka: Je tato formule pravdivá v oboru přirozených čísel? Příklad vstupu: ∀x∃y ∀z((x + y = z) ∧ (y + 5 = x)) 2O(n)

. Současně bylo Pro tento problém je znám algoritmus se složitostí 22 dokázáno, že jakýkoliv algoritmus řešící tento problém má složitost cn minimálně 22 . Zdeněk Sawa (VŠB-TU Ostrava)


12. prosince 2005

26 / 42

Příklad algoritmicky neřešitelného problému Problém Vstup: Uzavřená aritmetická formule vytvořená ze symbolů +, ×, =, ∧, ∨, ¬, ∀, ∃, (, ), proměnných a celočíselných konstant. Otázka: Je tato formule pravdivá v oboru přirozených čísel? Příklad vstupu: ∀x∃y ∀z((x × y = z) ∧ (y + 5 = x)) Tento problém je algoritmicky neřešitelný (u rozhodovacích problémů se používá též pojem algoritmicky nerozhodnutelný). Úzce souvisí s Gödelovou větou o neúplnosti.



12. prosince 2005

27 / 42

Další příklad nerozhodnutelného problému

Problém Vstup: Počítačový program a nějaká jeho vstupní data. Otázka: Zastaví se někdy tento program, když dostane na vstup tato data? Idea důkazu nerozhodnutelnosti: Předpokládejme existenci programu H, který řeší tento problém. Můžeme ho snadno upravit na podprogram H ′ (p, v ), který vrací „Anoÿ nebo „Neÿ jako návratovou hodnotu. ...



12. prosince 2005

28 / 42

Další příklad nerozhodnutelného problému (pokračování)

... Vytvoříme nový program D: Vezme svůj vstup x a zavolá H ′ jako H ′ (x, x). Pokud H ′ vrátí „Anoÿ, D skočí do nekonečné smyčky. Pokud H ′ vrátí „Neÿ, D se zastaví. Zastaví se program D nebo ne, když mu předložíme jako vstup jeho vlastní kód?



12. prosince 2005

29 / 42

Třídy problémů

Některé problémy jsou těžší než jiné. Při posuzování obtížnosti problémů se ukázalo jako užitečné rozdělit problémy do tříd složitosti, např.: PTIME problémy řešitelné v polynomiálním čase PSPACE problémy řešitelné s polynomiálním množstvím paměti EXPTIME problémy řešitelné v exponenciálním čase EXPSPACE problémy řešitelné s exponenciálním množstvím paměti ...



12. prosince 2005

30 / 42

Třída NPTIME

Jednou z nejdůležitějších tříd je třída NPTIME .

Třída NPTIME: Do třídy NPTIME patří rozhodovací problémy, pro které existuje polynomiální algoritmus, který ověří správnost nalezeného řešení. Přesněji řečeno, pokud je odpověď „Anoÿ, existuje svědek, který dosvědčuje, že odpověď je „Anoÿ, kterého je možné v polynomiálním čase otestovat, že tomu tak skutečně je. Pokud je odpověď „Neÿ, žádný takový svědek neexistuje.



12. prosince 2005

31 / 42

Příklad problému z NPTIME Problém Vstup: Popis mapy (seznam států a informace který stát sousedí s kterým) a číslo k. Otázka: Je možné státy obarvit k barvami tak, aby žádné dva sousední státy neměly stejnou barvu?



12. prosince 2005

32 / 42

Příklad problému z NPTIME Problém Vstup: Popis mapy (seznam států a informace který stát sousedí s kterým) a číslo k. Otázka: Je možné státy obarvit k barvami tak, aby žádné dva sousední státy neměly stejnou barvu?



12. prosince 2005

32 / 42

P vs. NP

Jeden z největších otevřených problémů teoretické informatiky:

Otevřený problém: Je P = NP?

Pozn.: Třídy PTIME a NPTIME bývají také označovány stručněji P a NP.



12. prosince 2005

33 / 42

NP-úplné problémy

Důležitou podtřídou třídy NPTIME jsou tzv. NP-úplné problémy.

Definice Problém P je NP-těžký, jestliže platí, že libovolný problém ze třídy NPTIME je možné v polynomiálním čase redukovat na problém P.

Definice Problém P je NP-úplný, jestliže je NP-těžký a současně sám patří do třídy NPTIME.



12. prosince 2005

34 / 42

NP-úplné problémy (pokračování) NP-úplné problémy jsou důležité, protože: Kdyby alespoň jeden z nich byl řešitelný v polynomiálním čase, všechny problémy z NPTIME by byly řešitelné v polynomiálním čase. Pokud v NPTIME existuje alespoň jeden problém, který není řešitelný v polynomiálním čase, pak žádný z NP-úplných problémů není řešitelný v polynomiálním čase. Velké množství problémů, které se objevují v praxi v různých oblastech informatiky, je NP-úplných nebo NP-těžkých. To, že NP-úplné problémy nelze řešit v polynomiálním čase je podmínkou nutnou (nikoli však postačující) pro to, aby existovaly šifrovací algoritmy, které by nebyly snadno prolomitelné.



12. prosince 2005

35 / 42

NP-úplné problémy (pokračování) Někdy dva problémy mohou vypadat podobně, a přitom jeden z nich je řešitelný v polynomiálním čase, zatímco druhý je NP-úplný.

Problém 1 Vstup: Popis měst a silnic. Výstup: Existuje okružní cesta, na které projedeme každou silnici právě jednou?



12. prosince 2005

36 / 42

NP-úplné problémy (pokračování)

Problém 2 Vstup: Popis měst a silnic. Výstup: Existuje okružní cesta, na které projedeme každé město právě jednou? Problém 1 je v PTIME. Problém 2 je NP-úplný.



12. prosince 2005

37 / 42

Jak řešit těžké problémy? Pokud pro daný problém neexistuje efektivní algoritmus, máme následující možnosti: 1 2

3

4

5

Exponenciální algoritmy – použitelné jen na malé instance. Aproximační řešení – použitelné jen pro optimalizační problémy. Najde řešení, které je o něco horší než optimum. Pravděpodobnostní (randomizované) algoritmy – najde rychle řešení, ale řešení je s určitou pravděpodobností špatně. Speciální případy – soutředit se jen na některé speciální případy instancí, neřešit problém v plné obecnosti. Heuristiky – postup, který najde řešení rychle ve většině „rozumnýchÿ případů, není však zaručeno že vždy.



12. prosince 2005

38 / 42

Randomizovaný algoritmus Prvočíselnost Vstup: Přirozené číslo p. Otázka: Je p prvočíslo? Teprve od roku 2003 je znám polynomiální algoritmus (O(n12+ε ), později o něco zlepšen). V praxi je používán randomizovaný algoritmus se složitostí O(n3 ): Pokud p je prvočíslo, vrátí vždy odpověď „Anoÿ. Pokud p není prvočíslo, je pravděpodobnost odpovědi „Neÿ minimálně 50%, ale existuje až 50% šance, že program vrátí chybnou odpověď „Anoÿ.



12. prosince 2005

39 / 42

Randomizovaný algoritmus (pokračování) Program můžeme volat opakovaně (k krát): Pokud program vrátí alespoň jednou odpověď „Neÿ, víme na 100%, že p není prvočíslo. Pokud program vrátí pokaždé „Anoÿ, je pravděpodobnost toho, že p není prvočíslo, menší než 2−k . Když k = 100, je pravděpodobnost chyby zanedbatelně malá. Poznámka: Lze například odvodit, že pravděpodobnost toho, že počítač bude zasažen během dané mikrosekundy meteoritem, je nejméně 2−100 za předpokladu, že každých 1000 let je meteoritem zničeno alespoň 100 m2 zemského povrchu.



12. prosince 2005

40 / 42

Testování prvočíselnosti Pro číslo p hledáme svědka složenosti. Svědka vybíráme náhodně z množiny potenciálních svědků, což je množina {1, 2, 3, 4, . . . , p − 1} Využívá se:

Malá Fermatova věta: Pokud p je prvočíslo, pak pro každé a takové, že 1 ≤ a < p, platí (ap−1 mod p) = 1 Poznámka: Hodnotu (ap−1 mod p) je možné spočítat v polynomiálním čase.



12. prosince 2005

41 / 42

Testování prvočíselnosti (pokračování) Pokud zjistíme, že pro nějaké a je (ap−1 mod p) 6= 1, je číslo a svědkem složenosti p. Pro velkou většinu složených čísel alespoň jedna polovina všech čísel a v intervalu 1, . . . , p − 1 splňuje nerovnost (ap−1 mod p) 6= 1. Poznámka: Existují i však i složená čísla, pro která je takových a málo (jen ta a, kde největší společný dělitel s p je větší než jedna). Proto se v algoritmu využívá ještě následující tvrzení:

Věta: Jestliže p je liché prvočíslo, pak rovnice (x 2

mod p) = 1

má v intervalu {1, 2, . . . , p − 1} právě dvě řešení: x = 1, x = p − 1. Zdeněk Sawa (VŠB-TU Ostrava)


12. prosince 2005

42 / 42

Algoritmy a výpočetní složitost

Recommend Documents