IB002 Algoritmy a datové struktury I Ivana Černá Fakulta informatiky, Masarykova univerzita Jaro 2016 IB002 Algoritmy a datové struktury I () Jaro 2016 1/88 Informace o předmětu ■ vyučující předmětu • Ivana Černá (přednášky) • Vojtěch Řehák (cvičení) • Nikola Beneš, Jan Obdržálek, Jaromír Plhák, Kristina Zákopčanová, František Blahoudek, Henrich Lauko, Peter Bezděk, Filip Opálený, Tomáš Zábojník, Jan Ježek, Kristýna Pavlíčková, Tomáš Novotný, Jan Koniarik, Peter Benčík ■ interaktivní osnova předmětu - kompletní informace is.muni.cz/auth/el/1433/jaro2016/IB002/index.qwarp • organizace výuky (přednášky, cvičení, domácí úkoly, konzultace) • hodnocení předmětu (odpovědníky, praktický test, zkouška) • studijní materiály (slajdy, skripta, zadání úkolů, rozcestníky) ■ diskusní fórum předmětu v IS MU IB002 Algoritmy a datové struktury I () Jaro 2016 2 / 88 Literatura ■ T. Cormen, Ch. Leiserson, R. Rivest, C. Stein:Introduction to Algorithms. Third Edition. MIT Press, 2009 ■ J. Kleinberg, and E. Tardos:/4/g"or/t/?A77 Design. Addison-Wesley, 2006 ■ S. Dasgupta, Ch. Papadimitriou, U. \/az\rari\\Algorithms. McGraw Hill, 2007. ■ T. Cormen .Algorithms Unlocked. MIT Press, 2013 ■ J. Bentley: Programming Pearls (2nd Edition). Addison-Wesley, 1999. ■ Wikipedie (eng) ■ online materiály a video přednášky (^doporučuji MIT 6.006 Intro to Algorithms ) obrázky použité v prezentacích jsou částečné převzaty z uvedených monografií IB002 Algoritmy a datové struktury I () Jaro 2016 3 / 88 Obsah algoritmus způsob řešení problému datová struktura způsob uložení informací techniky návrhu a analýzy algoritmů důkaz korektnosti algoritmu, analýza složitosti algoritmu, asymptotická notace, technika rozděl & panuj a rekurze datové struktury halda, prioritní fronta, vyhledávací stromy, červeno-černé stromy, B-stromy, hašovací tabulky algoritmy řazení rozdělováním, slučováním, haldou, v lineárním čase grafové algoritmy prohledávání grafu, souvislost, cesty IB002 Algoritmy a datové struktury I () Jaro 2016 4 / 88 Motivace IB002 Algoritmy a datové struktury I () Chicago road networks, http://csun.uic.edu/dataviz.html Jaro 2016 5 /8 Motivace naučit se něco nového... An algorithm must be seen to be believed, and the best way to learn about what an algorithm is all about is to try it. — Donald Knuth, The Art of Computer Programming Algorithms: a common language for nature, human, and computer. — Avi Wigderson 1 á IB002 Algoritmy a datové struktury I () Jaro 2016 6/88 Motivace stát se dobrým programátorem. I will, in fact, claim that the difference between a bad programmer and a good one is whether he considers his code or his data structures more important. Bad programmers worry about the code. Good programmers worry about data structures and their relationships. — Linus Torvalds (creator of Linux) Progress is possible only if we train ourselves to think about programs without thinking of them as pieces of executable code. — Edsger W. Dijkstra Algorithms + Data Structures = Programs. Nikla us Wirt h Data Structures= Programs IB002 Algoritmy a datové struktury I () Jaro 2016 7 / 88 Motivace široké uplatnění... ■ návrh počítačů logické obvody, systém souborů, překladače ■ Internet vyhledávání, distribuované sdílení, cloud computing, packet routing ■ počítačová grafika virtuální realita, video, hry ■ multimédia mp3, jpg, rozpoznávání obrazu ■ bezpečnost šifrování, hlasování, e-obchod ■ sociální sítě doporučenia predikce, reklama ■ fyzika simulace ■ biologie projekt lidského genomu, simulace IB002 Algoritmy a datové struktury I () Jaro 2016 8 / 88 Motivace pro zábavu a zisk. Google facebook amazon.com Adobe 1 ČESI X 1 * SECURITY8 Honeywell redhat o i ORACLE NETSUITE central european institute of technology BRNO I CZECH REPUBLIC IB002 Algoritmy a datové struktury I () Jaro 2016 9 / 88 Složitost a korektnost algoritmů Návrh a analýza algoritmů □ Složitost a korektnost algoritmů ■ Motivace ■ Analýza složitosti ■ Korektnost algoritmů ■ Asymptotická notace ■ Maximální a minimální prvek ■ Složitost rekurzivních algoritmů ■ Jak nepoužívat rekurzi ■ Problém maximální podposloupnosti ■ Lokální maximum IB002 Algoritmy a datové struktury I () Jaro 2016 10 / 88 Složitost a korektnost algoritmů Motivace Motivace najdi nej kratší cestu pro rozvoz čerstvé pizzy ALGORITMUS??? IB002 Algoritmy a datové struktury I () Jaro 2016 11 / 88 Složitost a korektnost algoritmů Motivace Řešení 1 vyber počáteční vrchol iíq, i ^— 0 while existuje nenavštívený vrchol do i <- i + 1 nechť p i je nenavštívený vrchol nej blíž k^_i navštiv pi od return vrať cestu z po do pi IB002 Algoritmy a datové struktury I () Jaro 2016 12 / 8: Složitost a korektnost algoritmů Motivace Řešení 1 vyber počáteční vrchol iíq, i ^— 0 while existuje nenavštívený vrchol do i <- i + 1 nechť p i je nenavštívený vrchol nej blíž k^_i navštiv pi od return vrať cestu z po do pi -21 -5 -1 0 1 11 IB002 Algoritmy a datové struktury I () Jaro 2016 12 / 88 Složitost a korektnost algoritmů Motivace •v Řešení 2 nechť n je počet vrcholů for i = 1 to n — 1 do d oo for každou dvojici (x, koncových bodů částečných cest do if dist(x, y) < d then xi x, y, d dist(x, y) fi od spoj vrcholy a^,^ hranou od spoj hranou koncové vrcholy cesty IB002 Algoritmy a datové struktury I () Jaro 2016 13 / 88 Složitost a korektnost algoritmů Motivace •v Řešení 2 nechť n je počet vrcholů for i = 1 to n — 1 do d oo for každou dvojici (x, koncových bodů částečných cest do if dist(x, y) < d then xi x, y, d dist(x, y) fi od spoj vrcholy a^,^ hranou od spoj hranou koncové vrcholy cesty IB002 Algoritmy a datové struktury I () Jaro 2016 13 / 88 Složitost a korektnost algoritmů Motivace Korektní algoritmus d i— oo for každou z n\ permutací 11^ vrcholů do if costilii) < d cost(Ili)je cena cesty určené permutací Hi then d «— costilii) A Pmin ^~ H fi od return Pmin korektnost algoritmus prověří všech n\ možných způsobů projití grafu IB002 Algoritmy a datové struktury I () Jaro 2016 14 / 88 Složitost a korektnost algoritmů Motivace Korektní algoritmus d oo for každou z n\ permutací 11^ vrcholů do if cost{Iii) < d cost{Iii)je cena cesty určené permutací lii then d costilii) A Pmin Hi fi od return P™. korektnost algoritmus prověří všech n\ možných způsobů projití grafu složitost algoritmus je nepoužitelný již pro velmi malé grafy 111 existuje efektivnější algoritmus ??? www joly on .co.uk IB002 Algoritmy a datové struktury I () Jaro 2016 14 / Složitost a korektnost algoritmů Analýza složitosti Vyhledávání prvku v posloupnosti Vstup posloupnost prvků All n a prvek x Výstup index i takový, že A[i] — x, resp. hodnota No jestliže prvek x se v posloupnosti nevyskytuje Procedure Linear Search 1 answer No 2 for i — 1 to n do s if A[i] = x then answer ^— i fi 4 od 5 return answer IB002 Algoritmy a datové struktury I () Jaro 2016 15 / 88 Složitost a korektnost algoritmů Analýza složitosti Vyhledávání prvku v posloupnosti - optimalizace I Procedure Better Linear Search 1 for i — 1 to n do 2 if A[i] — x then return i fi 3 od 4 return No první výskyt x ukončí prohledávání každý průchod cyklem znamená 2 testy: v řádku 1 testujeme rovnost i < n, v řádku 2 testujeme rovnost A[i] = x stačí 1 test? IB002 Algoritmy a datové struktury I () Jaro 2016 16 / 88 Složitost a korektnost algoritmů Analýza složitosti Vyhledávání prvku v posloupnosti - optimalizace II Procedure Sentinel Linear Search 1 last n. V obou případech z platnosti tvrzení po ukončení iterace cyklu plyne korektnost vypočítaného výsledku. IB002 Algoritmy a datové struktury I () Jaro 2016 25/ Složitost a korektnost algoritmů Řazení vkládáním Problém řazení Vstup posloupnost n čísel (ai, 0,2,..., an) Výstup permutace (přeuspořádání) (a[, a'2l..., a'n) vstupní posloupnosti taková, že a[ < af2 < ... < o!n IB002 Algoritmy a datové struktury I () Jaro 2016 26 / 88 Složitost a korektnost algoritmů Řazení vkládáním Princip řazení vkládáním (a) (b) (c) 7 2 4 9 1 3 2 7 4 9 1 3 u 2 4 7 9 1 3 (d) (e) (/) 2 4 7 9 1 3 1 2 4 7 9 3 1 2 3 4 7 9 IB002 Algoritmy a datové struktury I () Jaro 2016 27 / 88 Složitost a korektnost algoritmů Řazení vkládáním Algoritmus Insert Sort(A) 1 for j — 2 to A.length do 2 key A [j] j j Vlož A [j] do seřazené postupnosti A[l. Í 0 A A[z] > fcey do A[z + 1] <- A[z] z «— z — 1 od A[z + 1] «— fcey od IB002 Algoritmy a datové struktury I () Jaro 2016 28 / 88 Složitost a korektnost algoritmů Řazení vkládáním Korektnost řazení vkládáním Invariant cyklu Na začátku každé iterace for cyklu obsahuje pole A[l... j — 1] stejné prvky jako na začátku výpočtu, ale seřazené od nej menšího po nej větší. Inicializace Před první iterací je j = 2 a tvrzení platí. Iterace Předpokládejme že tvrzení platí před iterací j, tj. prvky v A[l... j — 1 jsou seřazeny. Jestliže A[j] < A[j — 1], tak v těle cyklu se prvky A[j — 1], A[j — 2], A[j — 3], ... posouvají o jednu pozici doprava tak dlouho, až se najde vhodná pozice pro prvek A[j] (ř. 5 - 7). Pole A[l... j] proto na konci iterace cyklu obsahuje stejné prvky jako na začátku, ale seřazené. Po navýšení hodnoty j zůstává tvrzení v platnosti. Ukončení Cyklus skončí když j > A.length = n. Protože v každé iteraci se hodnota j navyšuje o 1, musí platit j — n + 1. Z platnosti invariantu cyklu plyne, že A[l.. .n] obsahuje stejné prvky jako na začátku výpočtu, ale seřazené. IB002 Algoritmy a datové struktury I () Jaro 2016 29 / 88 Složitost a korektnost algoritmů Řazení vkládáním Složitost řazení vkládáním Insertion Sort(A) cena počet i for j = 2 to A.length do Cl n 2 key A[j] C2 n — 1 3 Z ^— J — 1 C3 n — 1 4 while i > 0 A A[z] > /cey do C4 5 A[i + 1] <- A[z] C5 -i) 6 z z — 1 od C6 -i) 7 A[z + 1] 0 A A[z] > /cey do A[z + 1] <- A[z] z «— z — 1 od A[z + 1] «— /cey od T(n) = cín + c2(n - 1) + c3(n - 1) + c4 ^t,- + c5 ^(ij - 1) n j=2 j=2 + C6$^fo-l) + c7(n-l) = cín + C2(n — 1) + c4(n — 1) + 04(71 - ■ 1) + cj{n — 1) = an + b lineární složitost IB002 Algoritmy a datové struktury I () Jaro 2016 31 / Složitost a korektnost algoritmů Řazení vkládáním Složitost řazení vkládáním -nejhorší případ Insertion Sort(A) cena počet i for j = 2 to A.length do Cl n 2 key A[j] C2 n — 1 3 Z ^— J — 1 C3 n — 1 4 while i > 0 A A[z] > key do C4 5 A[z + 1] <- A[i] C5 -i) 6 I uq platí f(n) < cg{n) ■ zápis f(n) £ 0(g(n)) vs zápis f(n) — 0(g(n)) (historické důvody) ■ funkce g(n) roste asymptoticky rychleji než funkce f(n) ■ alternativní definice f(n) = 0(g(n)) právě když lim sup ^4 < oo IB002 Algoritmy a datové struktury I () Jaro 2016 35 / 88 Složitost a korektnost algoritmů Asymptotická notace O notace - příklady ■ 8n2-88n + 888 = 0(n2) protože 8n2 — 88n + 888 < 8n2 pro všechna n > 11 ■ 8n2 - 88n + 888 = 0(n3) protože 8n2 — 88n + 8 < ln3 pro všechna n > 10 ■ 8n2 - 88n + 888 ^ 0(n) protože cn < 8n2 — 88n + 888 pro n > c IB002 Algoritmy a datové struktury I () Jaro 2016 36 / 88 Složitost a korektnost algoritmů Asymptotická notace Q notace Definice f(n) — í}(g(n)) právě když existují kladné konstanty no a c takové, že pro všechna n > uq platí f{n) > cg{n) funkce g(n) roste asymptoticky pomaleji než funkce f(n) IB002 Algoritmy a datové struktury I () Jaro 2016 37 / 88 Složitost a korektnost algoritmů Asymptotická notace Q notace - příklady ■ 8n2 - 88n + 8 = 0(n2) protože 8n2 ■ 8n2 - 88n + 8 ^ 0(n3) protože 8n2 ■ 8n2 - 88n + 8 = Q(n) protože 8n2 - - 88n + 8 > n2 pro n > 13 - 88n + 8 < cn3 pro n > | 88n + 8 > n pro n > 11 IB002 Algoritmy a datové struktury I () Jaro 2016 38 / 88 Složitost a korektnost algoritmů Asymptotická notace 6 notace Definice f(ri) = @(g(n)) právě když existují kladné konstanty no,ci a c\ takové, že pro všechna n > no platí c\g{n) < f(n) < c^gin) funkce f(ri) a g(n) rostou stejně rychle Donald E. Knuth: Big Omicron and big Omega and big Theta. ACM SIGACT, Volume 8 Issue 2, April-June 1976, pp. 18 - 24. IB002 Algoritmy a datové struktury I () Jaro 2016 39 / 88 Složitost a korektnost algoritmů Asymptotická notace 0 notace - příklady ■ 8n2 - 88n + 8 = 6(n2) protože 8n2 - 88n + 8 = 0(n2) a současně 8n2 - 88n + 8 = 0(n2) ■ 8n2 - 88n + 8 ^ 6(n3) protože 8n2 - 88n + 8 ^ 0(n3) ■ 8n2 - 88n + 8 ^ 6(n) protože 8n2 - 88n + 8 ^ 0(n) IB002 Algoritmy a datové struktury I () Jaro 2016 40 / 88 Složitost a korektnost algoritmů Asymptotická notace 0 notace - příklad -n2 — 3n = Q(n2) 2 v ; musíme najít kladné konstanty ci,C2 a no takové, že o 1 o o cin < -n — 3/7 < 2 platí pro všechna n > uq po úpravě dostáváme 1 3 ci <---< c2 2 n pravá nerovnost platí pro každé n > 1 jestliže zvolíme c2 > 1/2 levá nerovnost platí pro každé n > 7 jestliže zvolíme c\ < 1/14 volba ci = 1/14, C2 = 1/2 a no = 7 dokazuje platnost vztahu 1^2 o__éOií^2\ -Sn = 6(n2) IB002 Algoritmy a datové struktury I () Jaro 2016 41 / 88 Složitost a korektnost algoritmů Asymptotická notace Asymptotická notace - vlastnosti tranzitivita f(n) = ®(g(n)) a g(n) — Q(h(n)) implikuje f(n) — Q(h(n)) f(n) = 0{g{n)) a g(n) = 0{h{n)) implikuje f(n) = 0[h[n)) f(n) = Q(g(n)) a g(n) = Q(h(ri)) implikuje f(n) = Q(h(n)) reflexivita f(n) = 0(/(n)) podobně pro O a O symetrie f(n) = Q(g(n)) právě když g(n) = 0(/(n)) transpozice f(n) = 0(g{n)) právě když g(n) = íí(/(n)) poznámka: ne každá dvojice funkcí je asymptoticky srovnatelná IB002 Algoritmy a datové struktury I () Jaro 2016 42 / 88 Rozděl a panuj Návrh a analýza algoritmů ■ Motivace ■ Analýza složitosti ■ Korektnost algoritmů ■ Asymptotická notace Q Rozděl a panuj ■ Maximální a minimální prvek ■ Složitost rekurzivních algoritmů ■ Jak nepoužívat rekurzi ■ Problém maximální podposloupnosti ■ Lokální maximum IB002 Algoritmy a datové struktury I () Jaro 2016 43 / 88 Rozděl a panuj Návrh algoritmů ideální svět návod (algoritmus) „jak konstruovat algoritmy" realita osvědčené postupy • iterativní přístup • rekurzivní přístup (rozděl a panuj, divide et i m pera, divide and conquer) • dynamické programování • hladové techniky • heuristiky • náhodnostní techniky • aproximativní techniky • parametrizované techniky IB002 Algoritmy a datové struktury I () Jaro 2016 44 / 88 Rozděl a panuj Rozděl a panuj - principy Nothing is particularly hard if you divide it into small jobs Henry Ford Rozděl [divide] problém na podproblémy, které mají menší velikost než původní problém. Vyřeš [conquer] podproblémy stejným postuperr\(rekurzívně). Jestliže velikost podproblému je malá, použij přímé řešení. Kombinuj [combine] řešení podproblému a vyřeš původní problém. IB002 Algoritmy a datové struktury I () Jaro 2016 45 / 88 Rozděl a panuj Maximální a minimální prvek Maximální a minimální prvek problém nalezení maximálního a minimálního prvku posloupnosti S[l.. .n složitostní kritérium - počet porovnání prvků MaxMin Iterative(S') 1 max S[l] 2 min S[l 3 for i — 2 to n do 4 if S [i] > max then max 5 if S [i] < min then min 6 od S [i] f i STil f i celkem 2{n 1) porovnání IB002 Algoritmy a datové struktury I () Jaro 2016 46 / 88 Rozděl a panuj Maximální a minimální prvek Přístup Rozděl a panuj □ posloupnost rozděl na dvě (stejně velké) podposloupnosti Q najdi minimální a maximální prvek v obou podposloupnostech Q kombinuj řešení podproblémů: maximálním prvek posloupnosti je větší z maximálních prvků podposloupnosti minimálním prvek posloupnosti je menší z minimálních prvků podposloupnosti 1 if r = l then return (£[/], S[r]) fi 2 if r = l + 1 then return (max(Sř[Z], ^[r]), min(Sř[Z], ^[r])) fi 3 if r > l + 1 then (A, B) <- MaxMin(S', + r)/2J) 4 (C, £>) <- MaxMin(5, [(/ + r)/2j + 1, r) 5 return (max(A, C), min(£>, D)) fi iniciální volání MaxMin(S', 1, n) IB002 Algoritmy a datové struktury I () Jaro 2016 47 / 88 Rozděl a panuj Maximální a minimální prvek Korektnost konečnost výpočtu plyne z faktu, že každé rekurzivní volání se provede pro postupnost menší délky správnost vypočítaného výsledku dokážeme indukcí vzhledem k délce vstupní posloupnosti n = 1, n = 2 provedou se příkazy v řádku 1, resp. v řádku 2 indukční předpoklad algoritmus vypočítá korektní hodnoty pro všechny posloupnosti délky nejvýše n — 1 (n > 1) platnost tvrzení pro n dle indukčního předpokladu jsou čísla A b B maximálním a minimálním prvkem posloupnosti S[l,..., [(1 + n)/2j], stejně tak čísla C a i? jsou maximálním a minimálním prvkem posloupnosti 5[L(l + n)/2j větší z čísel A, C je pak maximálním prvkem posloupnost ..., n menší z čísel £>, D jejím minimem IB002 Algoritmy a datové struktury I () Jaro 2016 48 / 88 Rozděl a panuj Maximální a minimální prvek Složitost rozděl problém na podproblémy menší velikosti vyřeš podproblémy kombinuj řešení podproblémů a vyřeš původní problém n je délka vstupu, podproblémy mají velikosti 774, n2,..., T(-) je časová složitost výpočtu na vstupu délky n T(n) — složitost rozdělení+ T(n1)+T(n2) + ...T{nk) + + složitost kombinace konkrétně pro algoritmus MAxMin, složitost je počet porovnání prvků posloupnosti '0 + T(Ln/2j) +T(\n/2]) + 2 pro n > 2 T(n) = { 1 pro n = 2 0 pro n = 1 IB002 Algoritmy a datové struktury I () Jaro 2016 49 / 88 Rozděl a panuj Maximální a minimální prvek Složitost fT([n/2\) + T(\n/2\) + 2 pro n > 2 T (n) = { 1 pro n = 2 0 pro n — 1 indukcí vzhledem k n ověříme, že pro n > 1 platí 5 T(n) < -n - 2 V ; ~ 3 indukční základ n = 2 T(2) = 1 < | - 2 — 2 indukční předpoklad nerovnost platí pro všechny hodnoty i, 2 < i < n platnost pro n T (n) T( [n/2j) + T( [n/2]) + 2 využijeme indukční předpoklad < |LV2J -2+|rn/2l -2 + 2 = |n-2 IB002 Algoritmy a datové struktury I () Jaro 2016 50 / 88 Rozděl a panuj Maximální a minimální prvek Kdo je nej rychlejší??? Minl(S,Z,r) minimum S[l] for i = l + 1 to r do if minimum > S i then minimum 5 z fi od return minimum Min2(5,Z,r) if r = Z then return 5[r] fi if r > / then A <- Min2(S, I, [(l + r)/2J) B <- Min2(5, [(l + r)/2j + 1, r) return min(^4, S) fi Min3(S,Z,r) if r = Z then return 5[r] fi if r > I then A <- Min3(S', Z, r return min(A, 5 » r -i) IB002 Algoritmy a datové struktury I () Jaro 2016 51 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Složitost rekurzivních algoritmů ■ složitost obvykle zapíšeme pomocí rekurentní rovnice, která vyjadřuje složitost výpočtu na vstupu velikosti n pomocí složitosti výpočtů na menších vstupech ■ označme T(n) časovou složitost výpočtu na vstupu délky n ■ pro dostatečně malý vstup (n < c) si přímé řešení vyžaduje konstantní čas ■ velký vstup rozdělíme na a podproblému z nichž každý má velikost 1/b velikosti původního vstupu ■ řešení každého podproblému si vyžádá čas T(n/b) ■ označme D{n) čas potřebný na konstrukci podproblému a C{n) čas potřebný na kombinaci řešení podproblému a nalezení řešení původního problému T(n) = 0(1) pro n < c aT(n/b) + D (n) + C (n) jinak jak najít řešení1 rekurentní rovnice??? 1nerekurzivní popis funkce, která splňuje podmínky rovnice IB002 Algoritmy a datové struktury I () Jaro 2016 52 / Rozděl a panuj Řešení rekurentních rovnic Složitost rekurzivních algoritmů substituční metoda „uhodneme" řešení a dokážeme jeho správnost matematickou indukcí metoda rekurzivního stromu konstruujeme strom, jehož vrcholy vyjadřují složitost jednotlivých rekurzivních volání; výslednou složitost vypočítáme jako sumu ohodnocení vrcholů stromu kuchařková věta (master method) vzorec pro řešení rekurentní rovnice tvaru T(n) = aT(n/b)+ f(n) IB002 Algoritmy a datové struktury I () Jaro 2016 Rozděl a panuj Složitost rekurzivních algoritmů Substituční metoda „uhodni" řešení matematickou indukcí dokaž jeho korektnost Příklad T(n) = 1 pro n — 1 2T([n/2j) +n jinak T(n) — 0{n\ogn) indukcí dokážeme, že T(n) < cnlogn pro dostatečně velké n a vhodně zvolenou konstantu c IB002 Algoritmy a datové struktury I () Jaro 2016 54 / 88 Rozděl a panuj Složitost rekurzivních algoritmů dokazujeme T(n) = O(nlogn) pro rovnici T(n) = 1 pro n — 1 2T([n/2j) +n jinak Indukční krok ■ předpokládejme, že tvrzení platí pro všechna m < n, tj. speciálně pro m= [n/2\ platí T([n/2\) < c[n/2\ log([n/2j) ■ využitím indukčního předpokladu dokážeme platnost tvrzení pro n T (n) < 2(c[n/2j log([n/2j)) + n < cnlog(n/2) + n = cn log n — cn log 2 + n — cn log n — cn + n < cnlogn IB002 Algoritmy a datové struktury I () Jaro 2016 Rozděl a panuj Složitost rekurzivních algoritmů dokazujeme T(n) = O(nlogn) pro rovnici T(n) = 1 pro n — 1 2T([n/2j) +n jinak ■ jako indukční základ nemůžeme použít případ n = l, protože neplatí T(l) < cn log n — cl log 1 = 0 ■ využijeme, že dokazujeme asymptotický vztah a proto stačí, aby nerovnost platila pro všechna dostatečně velká n ■ tvrzení dokážeme pro n > 2 ■ základem indukce bude platnost vztahu pro n — 2 a n — 3 ■ pro n > 3 závisí hodnota T(n) jenom od T(2) a T(3) Indukční základ n = 2 a n = 3 ■ dosazením do rovnice zjistíme, že T(2) = 4 a T(3) = 5 ■ zvolíme konstantu c > 1 tak, aby pro n = 2 a n = 3 platilo T(n) < cnlogn ■ dobrá volba je c > 2, protože platí T(2) < c • 2 log 2 i T(3) < c • 3 log 3 IB002 Algoritmy a datové struktury I () Jaro 2016 56 / Rozděl a panuj Složitost rekurzivních algoritmů Metoda rekurzivního stromu ■ „rozbalování rekurze" ■ přehledný zápis pomocí stromu, jehož vrcholy vyjadřují složitost jednotlivých rekurzivních volání ■ vrchol stromu je ohodnocen složitostí dekompozice a kompozice ■ synové vrcholu odpovídají jednotlivým rekurzivním voláním ■ výslednou složitost vypočítáme jako sumu ohodnocení vrcholů, obvykle sečítáme po jednotlivých úrovních stromu metodu můžeme použít pro ■ nalezení přesného řešení (je nutné přesné počítání) ■ pro získání odhadu na řešení rekurentní rovnice; pro důkaz řešení se pak použije substituční metoda IB002 Algoritmy a datové struktury I () Jaro 2016 57 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Metoda rekurzivního stromu - příklad 3T([n/4j) + cn2 jinak metodu použijeme pro získání odhadu řešení, můžeme proto předpokládat, že n je mocninou 4 IB002 Algoritmy a datové struktury I () Jaro 2016 58 / 88 Rozděl a panuj Složitost rekurzivních algoritmů IB002 Algoritmy a datové struktury I () Jaro 2016 59 / 88 Rozděl a panuj Složitost rekurzivních algoritmů log4 3 - (d) Total: 0(n2) IB002 Algoritmy a datové struktury I () Jaro 2016 60 / 88 Rozděl a panuj Složitost rekurzivních algoritmů ■ kořen má hloubku 0 ■ (vnitřní) vrchol v hloubce i je označen složitostí c(n/42)2 ■ počet vrcholů s hloubkou i je 3l ■ součet složitostí vrcholů v hloubce z je ?>lc(n/A1)2 — (3/16)2cn2 ■ list je označen složitostí 1 (základ rekurentní rovnice) a má hloubku i — log4n (protože n/4log4n = 1) ■ počet listů je 3log4n = nl°^3 ■ sumací přes všechny úrovně dostáváme T(n) = cn2 + -cn2 + ■■■+ (-Y°gi n_1cn2 + n1^ 3 IB002 Algoritmy a datové struktury I () Jaro 2016 61 / 88 Rozděl a panuj Složitost rekurzivních algoritmů T>í \ 2,3 2 , , / ^ \log4n-l 2 , r\í log, 3) l{n)—cn H--cn +•••+(— cn + (Sin &4 7 v ; 16 v16; v log4n-l (Ji)icn2 + 0(nlog43) i=0 <^(±)lcn2 + @(nlog43) i=0 1 cn2 + e(nlog^3) 1 - (3/16) 13 = 0{n2) hodnotu T(n) = 0(n2) použijeme jako odhad pro substituční metodu Jaro 2016 62 / IB002 Algoritmy a datové struktury I () Rozděl a panuj Složitost rekurzivních algoritmů Kuchařková věta (Master method) Nechť a > 1 a b > 1 jsou konstanty, f(n) je polynomiální funkce, a nechť T(n) je definována na nezáporných číslech rekurentní rovnicí Potom platí 'ecf(n)) T[n) = { O(nlo^a) T {n) = aT(n/b) + f{n) když af(n/b) — «/(n) pro nějakou konstantu « < 1 když af(n/b) — Kf{n) pro nějakou konstantu K > 1 l ©(/(«) log6 když af(n/b) = /(n) IB002 Algoritmy a datové struktury I () Jaro 2016 63 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Kuchařková věta - alternativní varianta Nechť a>l,6>lad>0 jsou konstanty a nechť T(n) je definována na nezáporných číslech rekurentní rovnicí T(n) = aT(n/b) + 6(nc) Potom platí f 6(nc) když a < bc T{n) — < 0(nclogn) když a — U U případ 1 případ 2 případ 3 věta platí i ve variantě pro O a Ví IB002 Algoritmy a datové struktury I () Jaro 2016 64 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Příklady použití kuchařkové věty I ■ T{n) = 4T(n/2) + 1 => T(n) = 6(n2) případ 3, a = 4, b = 2, c = 0, 4 > 2° ■ T (n) 4T(n/2) + n T (n) 6(n2) případ 3, a = 4, b = 2, c = 1, 4 > 21 ■ T(n) = 4T(n/2) + n2 T (n) = 6(n2 log n) případ 2, a = 4, 6 = 2, c = 2, 4 = 22 ■ T(n) 4T(n/2) + n3 =>► T(n) 6(n3) případ 1, a = 4, 6 = 2, c = 3, 4 < 23 IB002 Algoritmy a datové struktury I () Jaro 2016 65 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Příklady použití kuchařkové věty II ■ T(n) = 2T(n/2) + 1 T(n) = 6(n) případ 3, a = 2, b = 2, c = 0, 2 > 2° ■ T (n) = 2T(n/2) + n T (n) = G(nlogn) případ 2, a = 2, 6 = 2, c = 1, 2 = 21 ■ T(n) = 2T(n/2) + n2 =^ T(n) = 6(n2) případ 1, a = 2, 6 = 2, c = 2, 2 < 22 ■ T (n) 2T(n/2) + n3 =>► T (n) 6(n3) případ 1, a = 2, 6 = 2, c = 3, 2 < 23 IB002 Algoritmy a datové struktury I () Jaro 2016 66 / 88 Rozděl a panuj Složitost rekurzivních algoritmů Příklady Hanojské věže T(n) = 2T(n - 1) + 1, základní případ T(0) = 0 T(n) = 2n - 1 MergeSort T(n) < 2T(n/2) + O(n) T(n) = O(nlogn) násobení celých čísel T(n) = 4T(n/2) + O(n) T(n) = C(n2) Strassenův algoritmus pro násobení celých čísel T(n) = 7T(n/2) + 0(n2) T(n) = O(nios"a) = 0(nlog27) = 0(n2-81) IB002 Algoritmy a datové struktury I () Jaro 2016 67 / 88 Jak nepoužívat rekurzi Rozděl a panuj Jak nepoužívat rekurzi - nedefinovaný výpočet BacLFactorial(n) return n • BAD_FACTORiAL(n - 1) chybí základ rekurze IB002 Algoritmy a datové struktury I () Jaro 2016 68 / 88 Rozděl a panuj Jak nepoužívat rekurzi Jak nepoužívat rekurzi - nekonečný výpočet AwfuLFactorial(n) if n — 0 then return 1 else return -^7AwFUL_FACTORiAL(n + 1) fi n+l v / Beta(n) if n = 1 then return 1 else return n(n — l)BETA(n — 2) fi IB002 Algoritmy a datové struktury I () Jaro 2016 69 / 88 Rozděl a panuj Jak nepoužívat rekurzi Jak nepoužívat rekurzi - složitost Fibonacciho posloupnost = 0, Fi — 1, Fn — Fn_i + Fn_: RecFibo(n) if n < 2 then return n else return REcFiBo(n 1) + RECFiBO(n - 2) fi časová složitost algoritmu T(0) = 1, T(l) = l, T(ra)=T(ra-l)+T(ra-2) + l T(n) = 6(n), 0= (a/5 + 1)/2 IB002 Algoritmy a datové struktury I () Jaro 2016 70 / 88 Rozděl a panuj Jak nepoužívat rekurzi Jak nepoužívat rekurzi - složitost Fibonacciho posloupnost F0 = 0, i*i = 1, Fn = Fn-i + Fn_: IterFibo(n) F[0] i- 0 F[l] <- 1 for i = 1 to n do <- F [i - 1] + F return F\n i - 21 od časová složitost algoritmu T(n) = 6(n) IB002 Algoritmy a datové struktury I () Jaro 2016 71 / 88 Rozděl a panuj Problém maximální podposloupnosti Jak používat rekurzi - význam definice podproblémů problém maximální podposloupnosti ■ dané je pole celých čísel A[l..n] ■ cílem je najít takové indexy 1 < i < j < n, pro které je suma A[i] + • • • + A[j] maximální ■ 13, -3, -25, 20 -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 ■ řešením je 18, 20, -7, 12 ■ řešení hrubou sílou - prozkoumat všechny dvojice indexů z, j ■ kvadratická složitost ■ existuje lepší řešení ■ rozděl a panuji IB002 Algoritmy a datové struktury I () Jaro 2016 72 / 88 Rozděl a panuj Problém maximální podposloupnosti Rozděl a panuj daná je posloupnost A[low ... high] a hodnota mid hledané řešení A[i... j (A) je podposloupnosti A[low ... mid] (low < i < j < mid) (B) je podposloupnosti A[mid + 1... high] (mid + 1 < i < j < high) (C) zasahuje do obou podposloupnosti (low < i < mid < j < high) (A) a (B) jsou problémy stejného typu jako původní problém (C) 1111 IB002 Algoritmy a datové struktury I () Jaro 2016 73 / 88 Rozděl a panuj Problém maximální podposloupnosti Rozděl a panuj daná je posloupnost A[low ... high] a hodnota mid hledané řešení A (A) je podposloupnosti A[low ... mid] (low < i < j < mid) (B) je podposloupnosti A[mid + 1... high] (mid + 1 < i < j < high) (C) zasahuje do obou podposloupnosti (low < i < mid < j < high) (A) a (B) jsou problémy stejného typu jako původní problém (C) 1111 pro řešení (C) stačí poznat podposloupnosti tvaru A A[mid + 1... j] s maximální sumou i... mid] a IB002 Algoritmy a datové struktury I () Jaro 2016 73 / Rozděl a panuj Problém maximální podposloupnosti Případ C Find_Max_Crossing_Subarray F_M_C_S( A low, mid, high) 1 leftsum i--oo 2 sum 0 3 for i — mid downto low do 4 sum sum + A[i 5 if sum > leftsum then leftsum sum 6 maxleft i fi od 7 rightsum i--oo 8 sum 0 9 for j — mid + 1 to high do io sum sum + A [7] i i if sum > rightsum then rightsum si/m i 2 maxright j f i od i5 return (maxleft, maxright, leftsum -\- rightsum) IB002 Algoritmy a datové struktury I () Jaro 2016 74 / 88 Rozděl a panuj Problém maximální podposloupnosti Algoritmus Find_Maximum_Subarray F_M_S(A, low, high) 1 if high — low 2 then return (low, high, A[low]) 3 else mid — \(low + high)/2] 4 (leftlow, lefthigh, leftsum) F_M_S(A, low, mid) 5 (rightlow, righthigh, righttsum) F_M_S(A, mid + 1, high) 6 (crosslow, crosshigh, crosssum) F_M_C_S(A, low, mid, high) fi 7 if leftsum > rightsum A leftsum > crosssum 8 then return (leftlow, lefthigh, leftsum) fi 9 if leftsum < rightsum A rightsum > crosssum 10 then return (rightlow,righthigh, rightsum) 11 else return (crosslow,crosshigh, crosssum) fi IB002 Algoritmy a datové struktury I () Jaro 2016 75 / 88 Rozděl a panuj Problém maximální podposloupnosti Složitost procedura Find_Max_Crossing_Subarray(A, low, mid, high) ■ označme n — high — low + 1 ■ jedna iterace obou cyklů má konstantní složitost ■ počet iterací cyklu pro levou část posloupnosti je mid — low + 1 ■ počet iterací cyklu pro pravou část posloupnosti je high — mid ■ celková složitost je 0(n) algoritmus Find_Maximum_Subarray dekompozice a kompozice v konstantním čase, řešení problému (C) v čase 0(n) 2T(n/2) + 0(n) jinak pro n — 1 T (n) — 0(nlogn) IB002 Algoritmy a datové struktury I () Jaro 2016 76 / 88 Rozděl a panuj Lokální maximum Lokální maximum ■ dané pole A[l... n] celých čísel ■ úkolem je najít lokální maximum v A, tj. takový index i, pro který platí A[i] > A[i + 1] a současně A[i] > A[i — 1] ■ krajní prvek je lokálním maximem právě když A[l] > A[2] resp. A[n] > A[n - 1 ■ 12654738 Algoritmus 1 ■ hrubá síla ■ otestuj, zda A[2],..., A[n] jsou lokálním maximem ■ každý test složitosti 0(1) =^ složitost 0{n) Algoritmus 2 ■ najdi maximální prvek v A ■ složitost 0(n) IB002 Algoritmy a datové struktury I () Jaro 2016 77 / 88 Rozděl a panuj Lokální maximum Lokální maximum Algoritmus 3 - rozděl a panuj ■ zkontroluj prvek na pozici i ■ jestliže A[i] je lokálním maximem, hotovo ■ v opačném případě má A[i] většího souseda ■ jestliže A[i — 1] > A[i], tak lokální maximum je vlevo ■ jestliže A[i + 1] > A[i], tak lokální maximum je vpravo ■ pokračuj s posloupností A[: i — 1] resp. A[i + 1 v nejhorším případě rekurze s max{z — l,n — i} prvky balance: i — 1 = n — i, tj. i — [n — l)/2 T{n) =T(n/2) + G(l) T(n) — Q{logn) IB002 Algoritmy a datové struktury I () Jaro 2016 78 / 88 Rozděl a panuj Lokální maximum Lokální maximum - dvourozměrné daná n x n matice vzájemně různých celých čísel lokálním maximem je prvek M[i,j], který je větší než všichni jeho sousedé, tj prvky M[i + lJ], M[i-l,j], M[iJ + l] a M[iJ-l] prvek na hranici matice je lokálním maximem právě když je větší než jeho sousedé v matici Algoritmus 1 ■ hrubá síla ■ otestuj všech n2 prvků matice ■ složitost 0(n2) Algoritmus 2 ■ redukce na problém lokálního maxima v poli ■ najdi maximální prvek v každém sloupci ■ v posloupnosti maximálních prvků najdi lokální maximum ■ složitost 0(n2) (složitost hledání maximálních prvků v sloupcích!!!) Jaro 2016 79 /8 IB002 Algoritmy a datové struktury I () Rozděl a panuj Lokální maximum Lokální maximum - dvourozměrné ■ daná n x n matice vzájemně různých celých čísel ■ lokálním maximem je prvek M[i,j], který je větší než všichni jeho sousedé, tj prvky M[i + l,j], M[i-lJ], M[iJ + l] a M[iJ -1} ■ prvek na hranici matice je lokálním maximem právě když je větší než jeho sousedé v matici Algoritmus 3 ■ redukce na problém lokálního maxima v poli ■ v posloupnosti maximálních prvků najdi lokálním maximum ■ maximální prvek v sloupci hledej až když ho potřebuješ ■ složitost O(nlogn) existuje efektivnější řešení??? je možné najít lokálním maximum y n x n matici v čase O(n) ??? IB002 Algoritmy a datové struktury I () Jaro 2016 80 / 88 Lokální maximum - rozděl a panuj ■ okno - n x n matice ■ rám okna - první, prostřední a poslední řádek okna, první, prostřední a poslední sloupec okna ■ najdi maximální prvek g mezi 6n — 6 prvkami rámu ■ jestliže g je větší než jeho sousedé, hotovo ■ v opačném případě má g většího souseda, který určitě nepatří do rámu ■ pokračuj s podoknem, do kterého patří větší soused prvku g IB002 Algoritmy a datové struktury I () Jaro 2016 Korektnost 1. zvolené podokno obsahuje lokální maximum ■ nechť max je maximální prvek podokna ■ max > soused prvku g > g, , tj. všichni sousedé prvku max jsou menší a max je lokálním maximem 2. konečnost ■ v případě, že lokální maximum není prvkem rámu podokna, algoritmus rekurzívně hledá maximum v jeho podokně ■ rekurze se zastaví když rám okna pokrývá celé okno (tj. počet řádků / sloupců je nejvýše 3), v takovém případě algoritmus prověří každý prvek okna a podle tvrzení 1 musí toto okno obsahovat lokální maximum 3. prvek, který najde algoritmus ve zvoleném podokně, je lokálním maximem ■ nechť m je maximální prvek rámu zvoleného podokna, platím > g ■ když algoritmus vrátí m, tak m je určitě větší než všichni jeho sousedé v podokně a současně je i větší než jeho sousedé obklopující podokno (všichni jsou menší než g) ■ v opačném případě algoritmus vrátí prvek, který nepatří do rámu podokna, je větší než všichni jeho sousedé v podokně a tedy je lokálním maximem IB002 Algoritmy a datové struktury I () Jaro 2016 82 / Rozděl a panuj Lokální maximum Složitost vstupem problému je matice rozměrů n x n, jako velikost problému uvažujeme hodnotu n T(n) = T(n/2) + 0(n) T(n) = 0(n) IB002 Algoritmy a datové struktury I () Jaro 2016 83 / 88 Rozděl a panuj Rekurzivní vs iterativní přístup Rekurzivní vs iterativní přístup pro ■ intuitivní, jednoduchý návrh ■ důkaz korektnosti využitím matematické indukce ■ analýza složitosti využitím rekurentní rovnice ■ efektivní řešení proti ■ neefektivní implementace ■ ne vždy podpora ze strany programovacího jazyka ■ neefektivní řešení každý rekurzivní algoritmus lze převést na iterativní simulace zásobníku volání (resp. dynamické programování) jednoduchý přepis v případě tail rekurze IB002 Algoritmy a datové struktury I () Jaro 2016 84 / Rozděl a panuj Rekurzivní vs iterativní přístup Rekurzivní vs iterativní přístup tail rekurze -speciální případ rekurze, kde se po rekurzivním volání nedělá žádný výpočet ANO F(x,y) if y — 0 then return x else F(x • y + x, y — 1) fi NE G(x) if y — 0 then return x else y «— G (x return x • ?/ - 1) fi IB002 Algoritmy a datové struktury I () Jaro 2016 85 / 88 Rozděl a panuj Rekurzivní vs iterativní přístup Rekurzivní vs iterativní přístup F(x,y) if y — 0 then return x else F (x • y + x, y — 1) fi F(z,y)_ ZafreZ : if y 0 then return x else x ^ x • y -\- x y <- ž/ - 1 goto ZafreZ fi F(z,y) ret x for y = 1 to y do ret ret • y + ret od return ret IB002 Algoritmy a datové struktury I () Jaro 2016 86 / 88 Rozděl a panuj Rekurzivní vs iterativní přístup Rekurzivní vs iterativní přístup Bin Search(x, A, left, right) if right = left then return A[left] == x fi if right < left then mid = [(left + right)/2j if A[mid] — x then return true fi if A[mid] < x then leftmid + 1 else rig/ži mid fi Bin Search(x, A, left, right) fi Bin Search(x, A, left, right) while right < left do mid = [(left + right)/2j if A[mid] = x then return trae fi if A[mid] < x then left mid + 1 else rig/it mid fi od IB002 Algoritmy a datové struktury I () Jaro 2016 87 /8 Rozděl a panuj Rekurzivní vs iterativní přístup Domácí úkol Vstup: pole A[l... n] celých čísel CoToDELA(n) if n — 1 then write A else for i = 1 to n do CoToDELA(n - 1) if n je liché then swap A[l] a A else swap A[i] a A od fi n n fi ■ co je výstupem algoritmu? ■ jaká je složitost výpočtu? IB002 Algoritmy a datové struktury I () Jaro 2016 88 / 88