IB002 Algoritmy a datové struktury I Ivana Černá Fakulta informatiky, Masarykova univerzita Jaro 2018 IB002 Algoritmy a datové struktury I Jaro 2018 1/39 Informace o předmětu vyučující předmětu • Ivana Černá (přednášky) • Vojtěch Řehák (cvičení) • Nikola Beneš, Tomáš Brázdil, Vlastimil Dohnal, Tomáš Masopust, Jan Obdržálek, František Blahoudek, Henrich Lauko, Dominik Velan, Radka Cieslarová, Jan Koniarik, Jan Horáček, Oliver Roch Kateřina Sloupová, Miloslav Staněk, Viktoria Vozárová, Tatiana Zbončáková, Miriama Zemaníková (vedenícvičení) • Lucia Dupkaničová, Adam Matoušek,Mikoláš Stuchlík, Alena Zahradníčkova, (příprava cvičení) interaktivní osnova předmětu - kompletní informace is.muni.cz/auth/el/1433/jaro2018/IB002/index.qwarp • organizace výuky: přednášky, cvičení, domácí úkoly, konzultace • studijní materiály: učebnice, slajdy z přednášky, skripta příkladů, zadání úkolů, rozcestníky • hodnocení předmětu: seminární odpovědníky, domácí úkoly a speciální domácí úkol, implementační a znalostní část zkoušky diskusní fórum předmětu v IS MU IB002 Algoritmy a datové struktury I Jaro 2018 2 / 39C 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. ■ online materiály (odkazy viz Interaktivní osnova) ■ 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 2018 3 / 39 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 2018 4 / 390 Motivace řešit jinak neřešitelné problémy... IB002 Algoritmy a datové struktury I Chicago road networks, http://csun.uic.edu/dataviz.html Jaro 2018 5 / 390 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 IB002 Algoritmy a datové struktury I Jaro 2018 6 / 390 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 m Algorithms+ Data Structures= Programs IB002 Algoritmy a datové struktury I Jaro 2018 7 / 390 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 2018 8 / 390 Motivace pro zábavu a zisk. Google -im facebook amazon.com Adobe SECURITY' Honeywell redhat o "A 37 ORACLE NETSUITE central european institute of technology BRNO I CZECH PEPUBLIC IB002 Algoritmy a datové struktury I Jaro 2018 9 / 390 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 lvi ■ Maximální a minimální prvek ■ Složitost rekurzivních algoritmů ■ Jak nepoužívat rekurzi ■ Problém maximální podposloupnosti IB002 Algoritmy a datové struktury I Jaro 2018 10 / 39 Složitost a korektnost algoritmů Motivace Motivace najdi nej kratší cestu pro rozvoz čerstvé pizzy ALGORITMUS??? IB002 Algoritmy a datové struktury I Jaro 2018 11 / 390 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 pí od return vrať cestu z po do p i IB002 Algoritmy a datové struktury I Jaro 2018 12 / 390 Složitost a korektnost algoritmů Motivace Řešení 1 vyber počáteční vrchol vq, 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 pí od return vrať cestu z po do p i -21 -1 0 1 11 IB002 Algoritmy a datové struktury I Jaro 2018 12 / 390 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 2018 13 / 390 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 2018 13 / 390 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 2018 14 / 390 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 2018 14 / 39C Složitost a korektnost algoritmů Analýza složitosti Složitost Charles Babage, 1864 As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any resul is sought by its aid, the question will arise - By what course of calculation can these results be arrived at by the machine in the shortest time? _m nu 4>ih \rw intf ani nm mb* il-,__ THE ANALYTICAL ENGINE (1833) kolikrát musíme zatočit klikou? IB002 Algoritmy a datové struktury I Jaro 2018 15 / 390 Složitost a korektnost algoritmů Analýza složitosti Časová složitost časová složitost výpočtu = součet cen všech vykonaných operací časová složitost algoritmu je funkce délky vstupu • složitost v nejhorším případě maximální délka výpočtu na vstupu délky n • složitost v nej lepším případě minimální délka výpočtu na vstupu délky n • průměrná složitost průměr složitostí výpočtů na všech vstupech délky n složitost = časová složitost v nej horším případě IB002 Algoritmy a datové struktury I Jaro 2018 16 / 390 Složitost a korektnost algoritmů Analýza složitosti Vyhledávání prvku v posloupnosti Vstup posloupnost prvků A[l... 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 2018 17 / 390 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 2018 18 / 390 Složitost a korektnost algoritmů Analýza složitosti Vyhledávání prvku v posloupnosti - optimalizace II Procedure Sentinel Linear Search i last A n 2 A 3 1 < n x 1 4 while A[i] / a; do z ^ i + 1 od 5 A[n] ^— last 6 if i < n V A[n] = x 7 then return i 8 else return No fi ■ první výskyt x ukončí prohledávání ■ sentinel (zarážka) pro případ, že pole neobsahuje prvek x m každý průchod cyklem znamená 1 test ■ 2 testy na závěr (řádek 6) IB002 Algoritmy a datové struktury I Jaro 2018 19 / 390 Složitost a korektnost algoritmů Analýza složitosti Časová složitost Linear Search 1 answer <— No 2 for i — 1 to n do if A — x 3 4 then answer <- 5 return answer i fi od ■ označme ti cenu operace na řádku i ■ operace z řádků 1 a 5 se vykonají jednou ■ řádek 2 se vykoná n + 1 krát ■ řádek 3 se vykoná n krát ■ přiřazení v řádku 4 se vykoná úměrně počtu výskytů x v poli časová složitost v nejlepším případě íi + *2 • + 1) + *3 • + r4 • 0 + t5 časová složitost v nej horším případě ti + t2 • (n + 1) + Í3 • n + ŕ4 • n + ŕ5 složitost je tvaru c • n + d, kde c a d jsou konstanty nezávislé na n složitost je lineární vzhledem k délce vstupu n IB002 Algoritmy a datové struktury I Jaro 2018 20 / 39 Složitost a korektnost algoritmů Analýza složitosti Časová složitost optimalizovaných algoritmů Better Linear Search 1 for i — 1 to n do if A 2 return No i — x then return i fi od časová složitost v nejhorším případě je lineární časová složitost v nejlepším případě je konstantní Sentinel Linear Search 1 last <(— A[n], A[n] ^— x, i <(— 1 2 while A[i] / a; do z ^ i + 1 od s A[n] ^— last 4 if i < n V — x then return z else return No fi ■ časová složitost v nejhorším případě je lineární ■ časová složitost v nejlepším případě je konstantní ■ rozdíl je v konstantních faktorech IB002 Algoritmy a datové struktury I Jaro 2018 21 / 390 Složitost a korektnost algoritmů Korektnost algoritmů Korektnost algoritmu vstupní podmínka ze všech možných vstupů pro daný algoritmus vymezuje ty, pro které je algoritmus definován výstupní podmínka pro každý vstup daného algoritmu splňující vstupní podmínku určuje, jak má vypadat výsledek odpovídající danému vstupu algoritmus je (totálně) korektní jestliže pro každý vstup splňující vstupní podmínku výpočet skončí a výsledek splňuje výstupní podmínku úplnost (konvergence) pro každý vstup splňující vstupní podmínku výpočet skončí částečná (parciální) korektnost pro každý vstup, který splňuje vstupní podmínku a výpočet na něm skončí, výstup splňuje výstupní podmínku IB002 Algoritmy a datové struktury I Jaro 2018 22 / 390 Složitost a korektnost algoritmů Korektnost algoritmů Korektnost iterativního algoritmu analyzujeme efekt jednotlivých operací analýza efektu cyklu ■ u vnořených cyklů začínáme od cyklu nejhlubší úrovně ■ pro každý cyklus určíme jeho invariant ■ invariantem cyklu je takové tvrzení, které platí před vykonáním a po vykonání každé iterace cyklu ■ dokážeme, že invariant cyklu je pravdivý ■ využitím invariantu • dokážeme konečnost výpočtu cyklu • dokážeme efekt cyklu IB002 Algoritmy a datové struktury I Jaro 2018 23 / 390 Složitost a korektnost algoritmů Korektnost algoritmů Invariant cyklu Inicializace invariant je platný před začátkem vykonávání cyklu Iterace jestliže invariant platí před iterací cyklu, zůstává v platnosti i vykonání iterace Ukončení cyklus skončia po jeho ukončení platný invariant garantuje požadovaný efekt cyklu IB002 Algoritmy a datové struktury I Jaro 2018 Složitost a korektnost algoritmů Korektnost algoritmů Korektnost Better Linear Search 1 for i — 1 to n do if A[i] — x then return i fi od 2 return No Invariant cyklu Na začátku každé iterace cyklu platí, že jestliže prvek x se nalézá v A, tak se nalézá v části mezi pozicemi i a n. Inicializace Na začátku je i — 1 a proto tvrzení platí. Iterace Předpokládejme platnost tvrzení na začátku iterace. Jestliže iterace nevrátí výslední hodnotu, tak A[i] ^ x. Proto x musí být na některé z pozic i + 1 až n a invariant zůstává v platnosti i po ukončení iterace (tj. před následující iterací). Jestliže iterace vrátí hodnotu i, platnost tvrzení po ukončení iterace je zřejmá. Ukončení Cyklus skončí buď proto, že je nalezena hodnota x anebo proto, že i > 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 2018 25 / 39C 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 2018 26 / 390 Složitost a korektnost algoritmů Princip řazení vkládáním (a) (c) 7 2 4 9 1 3 2 7 4 9 1 3 a 2 4 7 9 1 3 (d) (/) 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 2018 27 / 390 Složitost a korektnost algoritmů Algoritmus Insert Sort(A) 1 //Vstup: A[l... n] 2 for j = 2 to A.length do 3 key A [j] j j Vlož A [j] do seřazené postupnosti A[l. Í 0 A A[i] > key do A[z + 1] <- A[i] i «— z — 1 od A[z + 1] «— fcey od IB002 Algoritmy a datové struktury I Jaro 2018 28 / 390 Složitost a korektnost algoritmů 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 prvky A[j — 1], A[j — 2], A[j — 3], ... posouvají o jednu pozici doprava v těle cyklu se 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 2018 29 / 390 Složitost a korektnost algoritmů 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] <- C5 -i) 6 z z — 1 od C6 -i) 7 A[i + 1] key od C7 n — 1 t j označuje počet opakovaní while cyklu pro danou hodnotu j počet testů v hlavičce cyklu je o 1 vyšší než počet iterací cyklu IB002 Algoritmy a datové struktury I Jaro 2018 30 / 390 Složitost a korektnost algoritmů Složitost řazení vkládáním -nejlepší případ Insertion Sort(A) 1 for j — 2 to A.length do 2 key A [j] i 0 A A[z] > /cey do A[z + 1] <- A[i] i «— z — 1 od A[z + 1] «— /cey od T(n) = c\n + c2(n - 1) + c3(n - 1) + c4 ^t,- + c5 ^(ŕj - 1) n j=2 3=2 + c6^(tJ--l) + c7(n-l) = cín + C2(n — 1) + c4(n — 1) + c4(n - ■ 1) + c^{n — 1) = an + b lineární složitost IB002 Algoritmy a datové struktury I Jaro 2018 31 / 39C 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 + (ci + c2 + c3 + ----- + c7)n - (c2 + c3 + c4 + c7) = an + on + c = 9(n2) IB002 Algoritmy a datové struktury I Jaro 2018 33 / 390 Složitost a korektnost algoritmů Asymptotická notace Typy notací f(n) = 0(g(n)) znamená, že C x g (n) je horní hranicí pro f (n) f (n) = Q (g (n)) znamená, že C x g (n) je dolní hranicí pro f (n) f (n) — Q (g (n)) znamená, že C\ x g (n) je horní hranicí pro f (n) a C2 x g (n) je dolní hranicí pro f (n) /, g jsou funkce, /, g : N —>► N C, Ci, C2 jsou konstanty nezávislé na n IB002 Algoritmy a datové struktury I Jaro 2018 34 / 390 Složitost a korektnost algoritmů Asymptotická notace O notace Definice f(ri) — 0(g(n)) právě když existují kladné konstanty no a c takové, že pro všechna n > uq platí f(n) < cg{n) ■ zápis f(n) G 0(g(n)) vs zápis f(n) — 0(g(n)) (historické důvody) ■ funkce f(n) neroste asymptoticky rychleji než funkce g{n) ■ alternativní definice f(n) = 0(g(n)) právě když lim sup ^4 < oo IB002 Algoritmy a datové struktury I Jaro 2018 35 / 390 Složitost a korektnost algoritmů Asymptotická notace O notace - příklady 8n2 - 88n + 888 = C(n2) protože 8n2 — 88n + 888 < 8n2 pro všechna n > 11 8n2 - 88n + 888 = C(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 2018 36 / 390 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 f(ri) neroste asymptoticky pomaleji než funkce g(n) IB002 Algoritmy a datové struktury I Jaro 2018 37 / 390 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 > - C- 88n + 8 > n pro n > 11 IB002 Algoritmy a datové struktury I Složitost a korektnost algoritmů 6 notace Definice f(n) = ®(g(n)) právě když existují kladné konstanty no,ci a c\ takové, že pro všechna n > uq platí c\g(n) < f(n) < c^gip) funkce f(n) a g(ri) 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 laro 2018 39 / 390 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{ri) IB002 Algoritmy a datové struktury I Jaro 2018 40 / 390 Složitost a korektnost algoritmů Asymptotická notace B notace - příklad —n2 — 3n = 0(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 > no 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 ln2 - 3n = 6(n2) IB002 Algoritmy a datové struktury I Jaro 2018 41 / 390 Složitost a korektnost algoritmů Asymptotická notace Asymptotická notace - vlastnosti tranzitivita f(n) — Q(g(n)) a g(n) — @{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(n)) implikuje f(n) = Q(h(n)) reflexivita f(n) = 0(/(n)) podobně pro O a fž symetrie f(n) — Q(g(n)) právě když g(n) — Q(f(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 2018 Rozděl a panuj Návrh a analýza algoritmů ■ Motivace ■ Analýza složitosti ■ Korektnost algoritmů ■ Asymptotická notace B Rozděl a panuj ■ Maximální a minimální prvek ■ Složitost rekurzivních algoritmů ■ Jak nepoužívat rekurzi ■ Problém maximální podposloupnosti IB002 Algoritmy a datové struktury I Jaro 2018 43 / 390 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 2018 44 / 390 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. Jaro 2018 45 / 390 Rozděl a panuj 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] fi STil f i celkem 2{n 1) porovnání IB002 Algoritmy a datové struktury I Jaro 2018 46 / 390 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 5 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 2018 47 / 390 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 posloupnost 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 A[l. menší z čísel £>, D jejím minimem n IB002 Algoritmy a datové struktury I Jaro 2018 48 / 390 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 ni, ri2,..., 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([n/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 2018 49 / 390 Rozděl a panuj 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 Tin) < -n - 2 V 7 - 3 indukční základ n = 2 T(2) = 1 < | - 2 — 2 indukční předpoklad nerovnost platí pro všechny hodnoty z, 2 < z < n platnost pro n T(n) = T([n/2\) + T(\n/2~\) + 2 využijeme indukční predpoklad < lln/2] -2+|fn/2l -2 + 2 = ^n-2 IB002 Algoritmy a datové struktury I Jaro 2018 50 / 390 Rozděl a panuj Maximální a minimální prvek Kdo je nejrychlejší??? Minl(S,Z,r) minimum <— S[l] for i — l + 1 to r do if minimum > S [i] then minimum return minimum S\i] f i od Min2(S,í,r) if r = I then return S[r] f i if r > l then 4 <- Min2(S*, l, [(l + r)/2J) S <- Min2(5, L(Z + r)/2j + l,r) return min(.A, B) fi Min3(S,č,r) if r = I then return S[r] f i if r > l then 4 <- Min3(5, l,r-l) return min(.A, S[r]) fi IB002 Algoritmy a datové struktury I Jaro 2018 51 / 39C Rozděl a panuj 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 pro n < c T(n) = í0(1) PVOr \aT{n/b) + D{n) + C{n) jinak jak najít řešení1 rekurentní rovnice??? nerekurzivní popis funkce, která splňuje podmínky rovnice IB002 Algoritmy a datové struktury I Jaro 2018 52 / 39C Rozděl a panuj Řešení rekurentních rovnic 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 2018 53 / 390 Rozděl a panuj 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 2018 54 / 390 Rozděl a panuj 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 2018 55 / 390 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 2018 56 / 39C Rozděl a panuj 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 2018 57 / 390 Rozděl a panuj 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 2018 58 / 390 Rozděl a panuj IB002 Algoritmy a datové struktury I Jaro 2018 59 / 390 Rozděl a panuj Total: 0(n2) IB002 Algoritmy a datové struktury I Jaro 2018 60 / 390 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 32c(n/4z)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 rní \ 2,3 2 | , / ^ \log4n-l 2 , log, 3 1 in) — cn H--cn +■■•+( —) cn + n fe4 IB002 Algoritmy a datové struktury I Jaro 2018 61 / 390 Rozděl a panuj rrí \ 2,3 2 i i / ^ \^og4n-l 2 i loe;, 3) l{n)—cn H--cn +•••+ — cn + B(n fe4 J v ; 16 v16; v log4n-l = y (Ji)lcn2 + 0(nlog43) z—' v 16 ?;=o 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) + /(n) když af(n/b) — K,f(n) pro nějakou konstantu k < 1 když af(n/b) — Kf(n) pro nějakou konstantu ií > 1 l ©(/(n) logb n) když af(n/b) = f(n) IB002 Algoritmy a datové struktury I Jaro 2018 63 / 390 Rozděl a panuj Kuchařková věta - alternativní varianta Nechť a>l,6>lac>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(ri) — < 0(nclogn) když a — U U případ 1 případ 2 případ 3 věta platí i ve variantě pro O a O IB002 Algoritmy a datové struktury I Jaro 2018 64 / 390 Rozděl a panuj 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 2018 65 / 390 Rozděl a panuj 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, b = 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, b = 2, c = 3, 2 < 23 IB002 Algoritmy a datové struktury I Jaro 2018 66 / 390 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) r(n) = O(nlogn) násobení celých čísel T(n) = 4T(n/2) + C(n) T(n) = G(n2) Strassenův algoritmus pro násobení celých čísel T(n) = 7T(n/2) + C(n2) T(n) = (D(nlos»a) = 0(nl0^7) = C(n2-81) IB002 Algoritmy a datové struktury I Jaro 2018 67 / 390 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 2018 68 / 390 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 2018 69 / 390 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(n)=T(n-í)+T(n-2) + l T(n) = 6(n), 0= (a/5 + 1)/2 IB002 Algoritmy a datové struktury I Jaro 2018 70 / 390 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] «- 0 F[l] <- 1 for z = 2 to n do F [i] <- F [i - 1] + F return F\n 21 od časová složitost algoritmu T(n) = G(n) IB002 Algoritmy a datové struktury I Jaro 2018 71 / 390 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 silou - 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 2018 72 / 39 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 IB002 Algoritmy a datové struktury I Jaro 2018 73 / 390 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 mid] a IB002 Algoritmy a datové struktury I Jaro 2018 73 / 390 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 2018 74 / 390 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 2018 75 / 390 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 2018 76 / 390 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 2018 77 / 39C 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 2018 78 / 390 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 2018 79 / 390 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/zi 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 2018 80 / 390 Rozděl a panuj Rekurzivní vs iterativní přístu 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) n if n je liché then swap A[l] a A else swap A[i] a A[n] f i od fi ■ co je výstupem algoritmu? ■ jaká je složitost výpočtu? Přehled algoritmů Razení B Přehled algoritmů m Merge sort ■ Problém inverzí ■ Razení haldou ■ Prioritní fronty ■ Counting Sort ■ Radix Sort ■ Bucket Sort IB002 Algoritmy a datové struktury I Jaro 2018 82 / 390 Problém řazení Přehled algoritmů ■ je daná množina K, nad kterou je definované úplné uspořádání ■ vstupem problému řazení je posloupnost A — (fci,..., kn) prvků z K ■ výstupem je posloupnost A! — (k[,..., kfn), která je takovou permutací posloupnosti A, že Vi, j, 1 < i < j < n, platí k\ < k'- IB002 Algoritmy a datové struktury I Jaro 2018 83 / 390 Přehled algoritmů Stabilní algoritmy a algoritmy in situ ■ prvky množiny K mohou být strukturované ■ řazení podle klíče ■ řazení se nazývá stabilní právě když zachovává vzájemné pořadí položek se stejným klíčem ■ prostorová složitost algoritmů řazení je protože samotná vstupní posloupnost má délku n ■ pro přesnější charakterizaci prostorové složitosti jednotlivých algoritmů uvažujeme tzv. extrasekvenční prostorovou složitost, do které nezapočítáváme paměť obsazenou vstupní posloupností ■ algoritmy, jejichž extrasekvenční složitost je konstantní, se nazývají in situ (in pláce) IB002 Algoritmy a datové struktury I Jaro 2018 84 / 390 Přehled algoritmů Přehled časová složitost časová složitost algoritmus v nej horším v průměrném případě případě řazení vkládáním 6(n2) 6(n2) řazení výběrem 6(n2) 6(n2) řazení sléváním 0(nlog n) 0(nlog n) řazení haldou 0(nlog n) 0(nlog n) řazení rozdělováním 6(n2) 0(nlog n) řazení počítáním Q(k + n) @(k + n) číslicové řazení Q(d(n + k)) Q(d(n + k)) přihrádkové řazení 6(n2) 6(n) IB002 Algoritmy a datové struktury I Jaro 2018 85 / 390 Přehled algoritmy založené na porovnávání prvků vkládáním, Insertion sort in situ, stabilní výběrem, Selection sort in situ, není stabilní sléváním, Merge sort asymptoticky časově optimální, není in situ, stabilní haldou, Heapsort asymptoticky časově optimální, in situ, není stabilní rozdělováním, Quicksort není časově optimální, extrasekvenční složitost a stabilita závisí od implementace (optimálně in situ, existují stabilní implementace), velmi dobrý v praxi (průměrná složitost je O(nlogn)) algoritmy, které získávají informace jinak než porovnáváním prvků počítáním, Counting sort vstupní prvky jsou z množiny {0,..., k} číslicové řazení, Radix sort zobecnění řazení počítáním přihrádkové řazení, Bucket sort vyžaduje znalost o pravděpodobnostním rozdělení čísel na vstupu IB002 Algoritmy a datové struktury I Jaro 2018 86 / 39 Řazení sléváním Razení r íclllcU dIc^Ui ILI11U □ Řazení sléváním ■ Merge sort ■ Problém inverzí ■ Razení haldou ■ Prioritní fronty ■ Counting Sort ■ Radix Sort ■ Bucket Sort IB002 Algoritmy a datové struktury I Jaro 2018 87 / 390 Řazení sléváním Merge sort Řazení sléváním (Merge sort) Rozděl posloupnost na dvě stejně velké podposloupnosti Vyřeš obě podposloupnosti (rekurzivně) Kombinuj dvě seřazené podposloupnosti do jedné IB002 Algoritmy a datové struktury I Jaro 2018 88 / 390 Řazení sléváním Merge sort Spojení dvou seřazených posloupností - Merge otázkou je, jak spojit dvě seřazené posloupnosti do jedné, která bude seřazená při slévání porovnáváme vedoucí prvky obou posloupností menší z porovnávaných prvků přesuneme do výslední posloupnosti procedura Merge má 4 parametry pole A indexy p, r takové, že p < q < r předpokládáme, že posloupnosti A[p... q] a A[q + 1... r] jsou seřazené pro provedení výpočtu je posloupnost A[p... r] seřazená pro zjednodušení kódu používáme sentinel IB002 Algoritmy a datové struktury I Jaro 2018 89 / 390 8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17 • • • 2 4 5 7 i 2 3 6 • • • A • • • 1 4 5 7 i 2 3 6 • • • 1 2 /c 3 4 5 i 2 3 4 5 1 2 3 k 4 5 i 2 3 4 5 L 2 4 5 7 oo i? 1 2 3 6 OO L 2 4 5 7 OO R 1 2 3 6 OO i (a) J i (P) j 8 9 10 11 12 13 14 15 16 17 8 9 10 11 12 13 14 15 16 17 • • • 1 2 5 7 1 2 3 6 • • • A • • • 1 2 2 7 1 2 3 6 • • • i 2 3 4 k 5 i 2 3 4 5 i 2 3 4 5 /c i 2 3 4 5 L 2 4 5 7 OO R 1 2 3 6 OO L 2 4 5 7 OO Ä 1 2 3 6 OO i (c) J i (d) j IB002 Algoritmy a datové struktury I Jaro 2018 Řazení sléváním Merge sort L L L 8 9 10 íi 12 13 14 15 16 17 A 1 2 2 3 1 2 3 6 1 2 3 4 5 k i 2 3 4 5 2 4 5 7 oo R 1 2 3 6 OO i (e) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 3 6 i 2 3 4 5 i k 2 3 4 5 2 4 5 7 OO R 1 2 3 6 OO i (a) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 6 7 ... i 2 3 4 5 i 2 3 /c 4 5 2 4 5 7 OO Ä 1 2 3 6 OO (0 J L L 8 9 10 íi 12 13 14 15 16 17 A 1 2 2 3 4 2 3 6 1 2 3 4 5 /c i 2 3 4 5 2 4 5 7 OO R 1 2 3 6 OO i (/) 3 8 9 10 11 12 13 14 15 16 17 A 1 2 2 3 4 5 6 6 i 2 3 4 5 i 2 k 3 4 5 2 4 5 7 OO R 1 2 3 6 OO (h) 3 IB002 Algoritmy a datové struktury I Jaro 2018 91 / 390 Řazení sléváním Merge sort Merge Procedure Merge(A,p, q, r) 1 Tli < 2 n2 q - p + 1 r — q s j/nechť L[l... n\ + 1] a R[l... ri2 + 1] jsou nová pole A[p + i — 1] od - A[q + j] od 4 for z = 1 to n\ do L 5 for j; = 1 to ri2 do i? [7 6 L[n\ + 1] oo 7 Íž[n2 + 1] bj, tak 6j je v inverzi se všemi prvky a^,..., a^, a proto k počtu inverzí připočteme fc — i + 1 IB002 Algoritmy a datové struktury I Jaro 2018 101 / 390 Řazení sléváním Problém inverzí zařazené prvky A B 3 ■ inverze mezi prvky zařazenými do výsledné posloupnosti jsou již započítané ■ jestliže ai < bj, tak do výsledné posloupnosti přesuneme ai clí < bj < bj+i < bj+2 < • • • ai není v inverzi se žádným z bj, &7+1, • • • ■ jestliže ai > bj, tak do výsledné posloupnosti přesuneme bj bj < a{ < ai+i < < • • • bj je v inverzi s každým z a^, a^+i, a^+2 • • • IB002 Algoritmy a datové struktury I Jaro 2018 102 / 390 Řazení sléváním Problém inverzí Algoritmus Merge_and_Count(A, B) 1 l A[i Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Inicializace iniciální přiřazení je pivot ^— A invariant (triviálně) platí r IB002 Algoritmy a datové struktury I Jaro 2018 110 / 390 Quicksort Korektnost Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Iterace A[j] > pivot - efektem iterace cyklu je zvýšení hodnoty j o 1; invariant platí A[j] < pivot - efektem iterace cyklu je zvýšení hodnoty i a výměna A[i] s A\j], to garantuje zachování platnosti podmínky 1 zachování platnosti podmínky 2 garantuje fakt, že jsme do A[j — 1] přesunuli prvek větší než pivot IB002 Algoritmy a datové struktury I Jaro 2018 111 / 390 Quicksort Korektnost Invariant cyklu na začátku každé iterace for cyklu v řádcích 3-6 platí pro každý index k □ jestliže p < k < i, tak A[k] < pivot jestliže i + l pivot Ukončení výpočet končí když j = r + 1, což spolu s faktem, že po posledním provedení iterace platí invariant, garantuje, že pro p < k < i platí A[k] < A[i] a pro i < k A[i] v poslední iteraci je j — p, A[j] = pivot < pivot, provede se výměna A[i] s A[j což garantuje, že po ukončení výpočtu cyklu platí A[i] — pivot IB002 Algoritmy a datové struktury I Jaro 2018 112 / 390 Quicksort Složitost složitost v nejhorším případě např. pro vstupní posloupnost, která je již seřazená, nebo která obsahuje stejné prvky T{n) = T{n - 1) + T(0) + 6(n) = T{n - 1) + 6(n) T(n) = G(n2) složitost v nejlepším případě nastává, když při každém rekurzivním volání rozdělí pivot posloupnost na dvě stejně velké podposloupnosti T{n) = 2T(n/2) + G(n) T{n) — O(nlogn) průměrná složitost T{n) — O(nlogn) IB002 Algoritmy a datové struktury I Jaro 2018 113 / 390 Quicksort Alternativní postup rozdělování I ■ postupujeme od obou konců posloupnosti až do chvíle, než jsou detekovány dva prvky, které jsou vůči sobě v opačném pořadí; prvky si vymění svou pozici ■ při tomto postupu se udělá průměrně 3 krát méně výměn ■ algoritmus není stabilní Hoare Partition(A,p, r) 1 X x od 7 if i < j then swapA[z] a A[j] else return j fi od Quicksort(A,p, r) 1 \f p p then stack.push((p, q — i))fi 8 \f q -\- 1 < r then stack.push((q + 1, r)) f i p od IB002 Algoritmy a datové struktury I Jaro 2018 116 / 39C Složitost problému řazení složitost řadících algoritmů založených na vzájemném porovnávání prvků posloupnosti je O(nlogn) □ búno vstupní posloupnost ai,..., an obsahuje vzájemně různé prvky B každé porovnání určí větší ze dvou prvků B výpočet algoritmu můžeme popsat rozhodovacím stromem, jehož vnitřní vrcholy jsou označeny y porovnávaných prvků a mají dva syny odpovídající vztahu < a > □ výpočet na konkrétním vstupu představuje cestu v rozhodovacím stromě z kořene do listu; jeho složitost je úměrná délce cesty B každý list jednoznačně určuje seřazení a7r(i) < a7r(2) < • • • < air(n) vstupních prvků □ algoritmus musí mít možnost vypočítat každou možnou permutaci vstupních prvků Q počet různých permutací je n\ B strom musí mít alespoň n\ listů ^> má hloubku alespoň log(n!) = O(nlogn) IB002 Algoritmy a datové struktury I Jaro 2018 117 / Řazení haldou Razení ll(5U dlliUi ILIIIUJ ■ Merge sort ■ Problém inverzí •v □ Razení haldou ■ Razení haldou ■ Prioritní fronty ■ Counting Sort ■ Radix Sort ■ Bucket Sort IB002 Algoritmy a datové struktury I Jaro 2018 118 / 390 Řazení haldou Řazení haldou Razení haldou - Heapsort idea ■ cílem je seřadit posloupnost prvků ■ najdeme největší prvek x posloupnosti P ■ prvek x přidáme na začátek posloupnosti již seřazených prvků ■ odstraníme prvek x z P ■ postup opakujeme dokud posloupnost P není prázdná co potřebujeme ■ datovou strukturu nad kterou dokážeme Q efektivně najít největší prvek a Q efektivně z ní odstranit největší prvek ■ halda co je halda ■ halda je stromová datová struktura splňující vlastnost haldy IB002 Algoritmy a datové struktury I Jaro 2018 119 / 390 Řazení haldou Řazení haldou Kořenový strom ■ strom s vyznačeným vrcholem r nazýváme kořenovým stromem s kořenem r ■ u kořenových stromů používáme pojmy rodič, děti/synové, sourozenci, potomek ■ kořen nemá žádného rodiče, ostatní vrcholy jsou potomky kořene ■ listem je každý vrchol, který nemá potomky ■ místo slova vrchol často používáme termín uzel ■ podstrom určený vrcholem x je podgraf indukovaný všemi následníky vrcholu x; tento podstrom je opět kořenovým stromem s kořenem x 2definice viz učebný text Matematické Základy Informatiky (FhIBOOO) prof. Hliněného 2 ES Q Jaro 2018 120 / 390 IB002 Algoritmy a datové struktury I Řazení haldou Řazení haldou Kořenový strom stupeň vrcholu v kořenovém stromě T je počet jeho synů hloubka vrcholu x v T je délka cesty (íy. počet hran) z kořene do x\ kořen je tedy v hloubce nula výška vrcholu x v T je délka nejdelší cesty z x do listu; list má tedy výšku nula hloubka stromu T = výška stromu T je délka nejdelší cesty od kořene k listu k-tá hladina stromu T je množina všech vrcholů stromu T ležících v hloubce k\ hladiny začínáme počítat od nulté binární strom je strom, ve kterém má každý vrchol nejvýše dva syny; tyto často označujeme jako levého a pravého syna fc-ární strom je strom, ve kterém má každý vrchol nejvýše k synů IB002 Algoritmy a datové struktury I Jaro 2018 121 / 390 Řazení haldou Řazení haldou Stromová datová struktura ■ stromová datová struktura je reprezentace stromu v počítači ■ při reprezentaci stromu v počítači je důležité, abychom se z každého vrcholu uměli dostat k jeho synům a z každého vrcholu, kromě kořene, k jeho rodiči ■ strom můžeme reprezentovat dynamicky pomocí ukazatelů (pointru) a nebo staticky v poli ■ v každém vrcholu v stromu si pamatujeme hodnotu v.key, které se říká klíč; v případě potřeby si můžeme pamatovat i další hodnoty IB002 Algoritmy a datové struktury I Jaro 2018 122 / 390 Řazení haldou Řazení haldou Halda a binární halda halda ■ je stromová datová struktura splňující vlastnost haldy ■ kořenový strom má vlastnost haldy právě tehdy, když pro každý uzel v a pro každého jeho syna w platí v.key > w.key ■ díky této vlastnosti obsahuje kořen stromu největší klíč z celé haldy binární halda ■ je úplný binární strom s vlastností haldy ■ binární strom je úplný, pokud jsou všechny jeho hladiny kromě poslední úplně zaplněny a v poslední hladině leží listy co nejvíce vlevo maximová vs. minimová halda d-regulární halda, binomiální halda, Fibonacciho halda IB002 Algoritmy a datové struktury I Jaro 2018 123 / 390 Řazení haldou Řazení haldou Binární halda a její reprezentace v poli ■ prvky pole A odpovídají uzlům binárního stromu ■ uzly očíslujeme po hladinách počínaje od jedničky; klíč z uzlu i uložíme do A[í\ ■ levý syn uzlu k bude uložen na pozici 2k a pravý syn uzlu k na pozici 2k + 1 ■ otec uzlu k se bude nacházet na pozici [k/2\ 17 15 8 12 7 IB002 Algoritmy a datové struktury I Jaro 2018 124 / 39 Řazení haldou Řazení haldou Binární halda a její reprezentace v poli pole reprezentující haldu má atributy ■ A.length je počet prvků v poli ■ A.heapsize je počet prvků haldy uložených v poli ■ prvky haldy jsou v poli uloženy na pozicích A[l...A.heapsize pro daný index i vypočteme indexy synů a otce uzlu A[i] předpisem Parent(z) return [i/2\ Left(z) return 2i Right(z) return 2% + 1 IB002 Algoritmy a datové struktury I Jaro 2018 125 / 390 Řazení haldou Řazení haldou Operace nad haldou jak vybudovat haldu? jak využít haldu k seřazení posloupnosti? vybudování haldy vstupem je posloupnost klíčů uložená v poli A[l... n] klíče v poli přeuspořádáme tak, aby na konci výpočtu tvořili haldu varianta A v odpovídajícím binárním stromu postupujeme od listů směrem ke kořeni operace Max_Heapify časová složitost 0{n) varianta B v odpovídajícím binárním stromu postupujeme od kořene směrem k listům operace Insert časová složitost O(nlogn) IB002 Algoritmy a datové struktury I Jaro 2018 126 / 390 Řazení haldou Řazení haldou Vybudování haldy varianta A invariant • v každém kroku algoritmu splňují všechny uzly j, pro i < j < n, vlastnost haldy • v následujícím kroku necháme klíč z uzlu i — 1 přebublat dolů takže také uzel i — 1 bude splňovat vlastnost haldy procedura Max_Heapify(A, i) ■ předpokládá, že binární stromy s kořeny Left(z) a Right(z) mají vlastnost haldy a že klíč A[i] může být menší než jeho následníci, tj. nemusí splňovat vlastnost haldy ■ procedura modifikuje A tak, že po její provedení strom s kořenem A[i] má vlastnost haldy ■ úprava je založena na přesunu prvku A[i] směrem dolů IB002 Algoritmy a datové struktury I Jaro 2018 127 / 390 IB002 Algoritmy a datové struktury I Jaro 2018 128 / 390 Řazení haldou Řazení haldou Max.Heapify Max_Heapify(A, i) i l <— Left(z) 2 r <- Right(z) 3 if I < A.heapsize A A[l] > A 1 4 then largest A[largest] 7 then largest x ■ alternativně můžeme definovat prioritní frontu vůči minimálnímu prvku ■ prioritní frontu implementujeme jako maximovou haldu IB002 Algoritmy a datové struktury I Jaro 2018 138 / 390 Maximum a Extract.Max ■ prvky množiny S tvoří haldu A ■ maximální prvek haldy je v jejím kořeni; jeho nalezení má konstantní složitost Heap_Maximum(A) i return A[l] ■ odstranění maximálního prvku se implementuje stejně jako v algoritmu řazení ■ složitost operace je O(logn) Heap_Extract_Max(A) 1 if A.heapsize < 1 then return prázdná fronta fi 2 max <(— A[l] s A[l] <(— A[A.heapsize] 4 A.heapsize <(— A.heapsize — 1 5 Max_Heapify(A, 1) 6 return max IB002 Algoritmy a datové struktury I Jaro 2018 139 / 390 Increase.Key ■ procedura Heap_Increase_Key implementuje operaci IncreaseJKey ■ index i identifikuje prvek, který má být operací nahrazen (navýšen) ■ nejdříve změníme hodnotu A[i] na novou hodnotu key a potom obnovíme vlastnost haldy Heap_lncrease_Key(A, z, key) 1 if key < A[i] then return nová hodnota je menší než původní fi 2 A[i] key 3 while i > 1 A A[Parent(z)] < A[i] do 4 vyměň A[i] a A[Parent(z)] 5 i <— Parent(z) od složitost: O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 140 / 390 Řazení haldou Prioritní fronty Insert ■ procedura Max_Heap_Insert implementuje operaci Insert ■ na konec pole vložíme nový prvek, který je menší než všechny ostatní prvky, symbolicky ho označujeme —oo ■ zvýšíme hodnotu vloženého prvku na hodnotu prvku, který chceme vložit do fronty Max_Heap_lnsert(A, key) 1 A.heapsize A.heapsize + 1 2 A[A.heapsize] i--oo s Heap_Increase_Key(A, A.heapsize, key) složitost: O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 141 / 390 Řazení v lineárním čase Razení ■ Merge sort ■ Problém inverzí ■ Razení haldou ■ Prioritní fronty □ Řazení v lineárním čase ■ Counting Sort ■ Radix Sort ■ Bucket Sort IB002 Algoritmy a datové struktury I Jaro 2018 142 / 390 Řazení v lineárním čase Counting Sort Řazení počítáním - Counting Sort předpokládá, že vstupní posloupnost obsahuje celá čísla z intervalu 0... k, kde k je nějaké pevně dané přirozené číslo jestliže k — 0(ri), tak složitost řazení počítáním je Q(n) IB002 Algoritmy a datové struktury I Jaro 2018 143 / 39C Řazení v lineárním čase Counting sort ■ vstupní posloupnost A[l... n ■ pole B[l.. .n] obsahuje seřazenou posloupnost ■ pole C[0... A:] se využívá v průběhu výpočtu ■ pro každou hodnotu i — 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel i, výsledný počet uložíme do C [i] ■ pro každou hodnotu i — 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel menších nebo rovných i, využijeme k tomu hodnoty napočítané v předcházejícím kroku a výsledný počet uložíme opět do C [i] ■ procházíme vstupní posloupnost od konce a každé číslo uložíme do B přímo na jeho pozici, která je určená počtem menších nebo rovných čísel; hodnoty v C průběžně aktualizujeme IB002 Algoritmy a datové struktury I Jaro 2018 144 / 390 Counting sort Řazení v lineárním čase A C 1 2 3 4 5 6 2 5 3 0 2 3 0 i 2 3 4 5 2 0 2 3 0 1 0 c 2 2 4 7 7 8 B C 1 2 3 4 5 6 0 1 2 3 4 5 2 2 4 6 7 8 i 2 3 4 5 6 7 8 i 2 3 4 5 6 7 8 B 0 3 0 3 3 0 1 2 3 4 5 0 1 2 3 4 5 C 1 2 4 6 7 8 C 1 2 4 5 7 8 0 0 2 2 3 3 3 5 IB002 Algoritmy a datové struktury I Jaro 2018 145 / 39 Řazení v lineárním čase Counting_Sort(A, £>, k) 1 j/inicializace C [O ... k] 2 for i = 0 to k do s C [i] <- 0 od 4 for j = 1 to A.length do 5 C[A[j]] <- C[A[j]] + 1 od 6 //C[i] obsahuje počet čísel rovných i 7 for i = 1 to k do 5 C [i] <- C [i] + C [i - 1] od 9 //C[i] obsahuje počet čísel menších nebo rovných i ío for j — A.length downto 1 do u B[c[A\j}}} ^ m 12 C[A[j}} <- C[A[j}} - 1 od IB002 Algoritmy a datové struktury I Jaro 2018 146 / 39C Řazení v lineárním čase Časová složitost ■ cyklus na řádcích 2-3 (inicializace C) - složitost Q(k) ■ cyklus na řádcích 4-5 (počet čísel — i) - složitost O(n) ■ cyklus na řádcích 7-8 (počet čísel < i) - složitost 0(fc) ■ cyklus na řádcích 10 - 12 (přesun z A do B) - složitost O(n) ■ celková složitost @(k + n) ■ v praxi používaný pro k — O (n) ■ stabilní algoritmus: prvky se stejnou hodnotou se ve výstupní posloupnosti vyskytují ve stejném pořadí jako ve vstupní posloupnosti (důležité např. pro radix sort) IB002 Algoritmy a datové struktury I Jaro 2018 147 / 390 Řazení v lineárním čase Varianty a optimalizace ■ v případě, že vstupní posloupnost obsahuje pouze čísla (a ne složitější datové objekty s klíčem), tak druhý cyklus algoritmu je možné vynechat a zapisovat do pole B přímo čísla ■ algoritmus se dá využít k odstraňování duplicitních klíčů (pole C nahradíme bitovým polem) ■ umožňuje efektivní paralelizaci (vstupní posloupnost rozdělíme na stejně velké podposloupnosti a pro každou z nich počítáme frekvence výskytu paralelně) ■ extrasekvenční složitost algoritmu je 0{n + k) IB002 Algoritmy a datové struktury I Jaro 2018 148 / 390 Řazení v lineárním čase Radix Sort Číslicové řazení - Radix Sort ■ řazení čísel podle číslic na jednotlivých bitech ■ postup zleva doprava (most significant digit, MSD) - používá se např. pro lexikografické uspořádání ■ postup zprava doleva (least significant digit, LSD), stabilní řazení ■ dá se použít i pro řazení položek, které nemají číselný charakter ■ používá se např. když potřebujeme seřadit položky vzhledem k různým klíčům Radix_Sort(A, d) 1 for i = 1 to d do 2 použij stabilní řazení a seřaď položky podle zte číslice 3 od IB002 Algoritmy a datové struktury I Jaro 2018 149 / 390 Řazení v lineárním čase Radix Sort Radix Sort Lema 1 Danou posloupnost n čísel s d číslicemi, přičemž číslice můžou nabývat k různých hodnot, seřadí Radix_Sort korektně v čase @(d(n + k)) za předpokladu, že stabilní řazení, které využívá, má složitost 0(n + k). ■ složitost je garantovaná např. při použití algoritmu Counting sort ■ jestliže d je konstanta a fc = 0(n), pak časová složitost číslicového řazení je lineární IB002 Algoritmy a datové struktury I Jaro 2018 150 / 39 Řazení v lineárním čase Radix Sort Varianty ■ řazení binárních čísel (lze zobecnit pro libovolnou číselnou soustavu) ■ nechť každé číslo má b bitů, zvolíme r < b ■ číslo rozdělíme na \b/r\ skupin po r bitech ■ každou skupinu chápeme jako číslo z intervalu 0 až 2r — 1 ■ při řazení postupujeme po skupinách, použijeme Counting sort pro k — 2r — 1 Lema 2 Danou posloupnost n binárních b bitových čísel Radix_Sort korektně seřadí v čase Q((b/r)(n + 2r)) za předpokladu, že stabilní řazení, které využívá, má složitost Q(n + k) pro čísla z intervalu 0 až k. otázka vhodné volby parametru r pro dané n a b závisí od poměru veličin n a b [b < lognj pro r < b platí (n + 2r) — Q(n), optimální je proto volba r — b pro kterou je celková složitost číslicového řazení (b/b)(n + 2b) = @(n) [b > lognj ■ pro r = [log nj je složitost je 0(6n/logn) ■ pro r > [logn\ je složitost je 0(6n/logn) ■ pro r < [logn\ hodnota výrazu (b/r) klesá a hodnota výrazu n + 2r zůstává @(n) IB002 Algoritmy a datové struktury I Jaro 2018 151 / 39 Řazení v lineárním čase Bucket Sort Přihrádkové řazení - Bucket Sort předpokládá, že ■ vstupní posloupnost obsahuje čísla z intervalu [0... 1) ■ čísla rovnoměrně pokrývají celý interval ■ interval [0... 1) rozdělíme na stejně velké podintervaly - koše ■ vstupní čísla rozdělíme dle jejich hodnoty do košů ■ seřadíme prvky v každém koši IB002 Algoritmy a datové struktury I Jaro 2018 152 / 390 IB002 Algoritmy a datové struktury I Jaro 2018 153 / 390 Řazení v lineárním čase Bucket Sort Bucket sort Bucket_Sort(A) 1 //B[0 ... n — 1] je nové pole 2 n A.length 3 for i — 0 to n — 1 do 4 B [i] ^— prázdny seznam od 5 for i = 1 to n do £ přidej A[i] do seznamu £>[[n • A[i]\] od 7 for z = 0 to n — 1 do 8 seřaď prvky seznamu B [i] použitím řazení vkládáním od 9 spoj seznamy £>[0], £>[1],..., B[n — 1] do jednoho seznamu nechť rii označuje počet prvků v koši B složitost je T(n) = Q(n) + Y%=o O {rif) očekávaná složitost je pro vstup s uniformně rozdělenými čísly 0(n) IB002 Algoritmy a datové struktury I Jaro 2018 154 / 390 Datové typy ■ jaká data jsou potřebné pro řešení problému? ■ jak se budou data reprezentovat? ■ jaké operace se budou nad daty provádět? Datový typ ■ rozsah hodnot, které může nabývat proměnná daného datového typu ■ množina operací, které jsou pro daný datový typ povolené / definované ■ nezávisí na konkrétní implementaci IB002 Algoritmy a datové struktury I Jaro 2018 155 / 39 Datové typy a struktury jednoduchý (skalární) datový typ data zabírají vždy konstantní (typicky malé) množství paměti, zpřístupnění hodnoty skalárního typu trvá konstantní čas číselné a znakové typy, typ pravdivostních hodnot, výčtový typ složený datový typ implementace složeného datového typu se nazývá datová struktura ■ statický - pevná velikost; časová složitost zpřístupnění prvku je konstantní k-tice, pole konstantní délky ■ dynamický - neomezená velikost; časová složitost zpřístupnění prvku je funkcí závislou na velikosti seznam, zásobník, fronta, slovník, strom, graf IB002 Algoritmy a datové struktury I Jaro 2018 156 / 39 Dynamické datové typy ■ množina objektů; v průběhu výpočtu můžeme do množiny prvky přidávat a odebírat resp. množinu jinak modifikovat (tzv. dynamická množina) ■ každý prvek dynamické množiny je reprezentovaný jako objekt, jehož atributy můžeme zkoumat a modifikovat za předpokladu, že máme ukazatel / referenci na tento objekt ■ jeden z atributů objektu je jeho identifikátor - klíč key ■ jestliže všechny prvky mají různé klíče, často mluvíme o množině obsahující klíče IB002 Algoritmy a datové struktury I Jaro 2018 157 / 390 Dynamické datové typy - základní operace Search(S', k) pro množinu S a klíč k vrátí ukazatel x takový, že x.key — k resp. Nil, když objekt s klíčem k není obsažen v množině S Insert^, x) do množiny S vloží objekt s ukazatelem x Delete(S', x) z množiny S odstraní objekt s ukazatelem x Maximum(S') pro množinu S s úplně uspořádanými objekty vrátí ukazatel x na objekt, jehož klíč je maximálni Minimum(S') pro množinu S s úplně uspořádanými objekty vrátí ukazatel x na objekt, jehož klíč je minimálni Successor(S', x) pro množinu S s úplně uspořádanými objekty vrátí ukazatel na objekt, jehož klíč následuje bezprostředně za klíčem x.key, resp. hodnotu Nil když x je maximální Predecessor(S', x) symetricky k Successor IB002 Algoritmy a datové struktury I Jaro 2018 158 / 390 Vyhledávací stromy Datové struktury □ Vyhledávací stromy ■ Binární vyhledávací stromy ■ Intervalové stromy □ Červeno cerne stromy ■ Červeno černé stromy ■ Rank prvku ■ Zřetězené hašování ■ Otevřená adresace IB002 Algoritmy a datové struktury I Jaro 2018 159 / 390 Vyhledávací stromy Motivace Problém rezervací online rezervační systém (např rezervace lékařského vyšetření, přistávací ranveje, ...) ■ množina rezervací R ■ požadavek t na rezervaci ■ rezervace může být potvrzena právě když v intervalu (t — k,t + k) není žádná jiná rezervace (fc je délka trvání události) a současně t je aktuální ■ mazání realizovaných aktualizací příklad: R = {21, 26, 29, 36}, k = 3, aktuální čas 20 rezervace 24 není validní (možná), protože 26 g R 33 je OK 15 není validní, protože aktuální čas je 20 IB002 Algoritmy a datové struktury I Jaro 2018 160 / 390 Vyhledávací stromy Motivace Problém rezervací - řešení jaký datový typ je vhodný pro reprezentaci R a realizaci požadovaných operací??? uspořádaný seznam ověření rezervace v čase 0(n), záznam rezervace v čase 0(1) uspořádané pole ověření rezervace v čase 0(logn), záznam rezervace v čase 0(n) neuspořádaný seznam / pole ověření rezervace v čase 0(n), záznam rezervace v čase 0(1) minimová halda ověření rezervace v čase 0(n), záznam rezervace v čase 0(logn), aktuálnost rezervace v čase 0(1) binární pole rezervace t je uložena v položce s indexem t - problém velikosti pole existuje lepší řešení?? současně efektivní vyhledávání i vkládání! IB002 Algoritmy a datové struktury I Jaro 2018 161 / 39 Vyhledávací stromy Binární vyhledávací stromy Vyhledávací stromy ■ umožňují efektivní implementaci operací Search, Minimum, Maximum, Predecessor, Successor, Insert, Delete ■ operace nad vyhledávacím stromem mají složitost úměrnou hloubce stromu, tj. v nejhorším případě až lineární ■ binární vyhledávací stromy - každý vrchol stromu má nejvýše 2 následníky, tj. strom může mít až hloubku n ■ vyvážené binární vyhledávací stromy mají logaritmickou hloubku, tj. operace mají složitost O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 162 / 390 Vyhledávací stromy Binární vyhledávací stromy Binární vyhledávací stromy (BVS) ■ datová struktura, která využívá ukazatele ■ každý vrchol (uzel) stromu představuje jeden objekt ■ každý vrchol obsahuje • klíč • ukazatele leh, right a p na levého syna, pravého syna a na otce; ukazatel má hodnotu Nil právě když vrchol nemá příslušného syna, resp. otce • případné další data v binárním vyhledávacím stromu jsou klíče vždy uloženy tak, že platí BVS vlastnost jestliže x je vrchol BVS a y je vrchol v levém podstromu vrcholu x, tak platí y.key < x.key y }e vrchol v pravém podstromu vrcholu x, tak platí y.key > x.key IB002 Algoritmy a datové struktury I Jaro 2018 163 / 390 Vyhledávací stromy Binární vyhledávací stromy BVS - procházení stromu ■ cílem je projít strom tak, aby každý vrchol byl navštíven právě jednou ■ využití: provedení operace nad každým vrcholem, výpis klíčů, kontrola vlastností stromu, ... ■ strom procházíme rekurzivně ■ začínáme v kořeni stromu ■ (rekurzivně) navštívíme všechny vrcholy levého podstromu kořene ■ (rekurzivně) navštívíme všechny vrcholy pravého podstromu kořene IB002 Algoritmy a datové struktury I Jaro 2018 164 / 390 Vyhledávací stromy Binární vyhledávací stromy BVS - výpis klíčů klíče uložené v BVS můžeme vypsat v pořadí inorder hodnotu klíče uloženého v kořeni vypíšeme mezi vypsáním klíčů uložených v jeho levém a pravém podstromě (2 3 5 5 7 8) preorder hodnotu klíče uloženého v kořeni vypíšeme před vypsáním klíčů uložených v jeho levém a pravém podstromě (5 3 2 5 7 8) postorder hodnotu klíče uloženého v kořeni vypíšeme po vypsání klíčů uložených v jeho levém a pravém podstromě (2 5 3 8 7 5) IB002 Algoritmy a datové struktury I Jaro 2018 165 / 39 Vyhledávací stromy Binární vyhledávací stromy Inorder lnorder_Tree_Walk(x) 1 if x ^ Nil 2 then lNORDER_TREE_WALK(x./e/í) 3 print x.key 4 lNORDER_TREE_WALK(x.rz^/lí) 5 fi ■ Inorder_Tree_Walk(T.rooí) vypíše klíče uložené v BVS T od nejmenšího po největší ■ časová složitost je 0(n), kde n je počet vrcholů stromu T ■ BVS Sort - časová složitost ??? IB002 Algoritmy a datové struktury I Jaro 2018 166 / 390 Vyhledávací stromy Binární vyhledávací stromy BVS - vyhledávání ve stromu ■ začínáme v kořeni stromu, postupujeme rekurzivně ■ porovnáme hledaný klíč k s klíčem uloženým v navštíveném uzlu, jestliže se rovnají, tak vyhledávání končí úspěchem ■ jestliže hledaný klíč k je menší než klíč x.key uložený v navštíveném uzlu x, tak pokračujeme v levém podstromu uzlu x ■ v opačném případě pokračujeme v pravém podstromu uzlu x ■ vyhledávání končí neúspěchem právě když hledaný klíč není uložen ani v navštíveném listu Tree_Search(x, k) 1 if x — Nil V k = x.key 2 then return x fi s if k < x.key 4 then return TREE_SEARCH(x./e/í, k) 5 else return TREE_SEARCH(x.rz^/ií, k) fi IB002 Algoritmy a datové struktury I Jaro 2018 167 / 39 Vyhledávací stromy Binární vyhledávací stromy BVS - minimální a maximální klíč ■ jestliže hledáme minimální klíč, tak v stromu postupujeme vždy doleva ■ jestliže hledáme maximální klíč, tak v stromu postupujeme vždy doprava Tree_Minimum(x) 1 while x.left ^ Nil doxf- x.left od 2 return x Tree_Maximum(x) 1 while x.right ^ Nil doxf- x.right od 2 return x IB002 Algoritmy a datové struktury I Jaro 2018 168 / 39 Vyhledávací stromy Binární vyhledávací stromy BVS - předchůdce a následník předpokládáme, že všechny klíče uložené v stromě jsou vzájemně různé3 následníkem uzlu x je uzel, který obsahuje nejmenší klíč větší než x.key (successor) předchůdcem uzlu x je uzel, který obsahuje největší klíč menší než x.key (predecessor) 3analogicky se operace definují i pro strom, který může obsahovat uzly se stejnými klíči Jaro 2018 169 / 390 IB002 Algoritmy a datové struktury I Binární vyhledávací stromy následníkem uzlu x je uzel, který obsahuje nejmenší klíč větší než x.key ■ jestliže uzel x má neprázdný pravý podstrom, tak jeho následníkem je nejmenší klíč uložený v jeho pravém podstromu ■ jestliže pravý podstrom je prázdný, tak • následníkem x je uzel y takový, že x.key je největším klíčem v levém podstromu uzlu y • uzel y je prvním uzlem na cestě z x do kořene stromu takový, že y.key > x.key (Jinými slovy x patří do levého podstromu uzlu y) Tree_Successor(x) 1 if x.right ^ Nil 2 then return TREE_MiNiMUM(x.rz^/it) fi 3 y x.p 4 while y ^ Nil Ax — y.right 5 do x i.low 4 then x i.low 4 then x i.low 4 then x bh(x) — 0 a současně počet vnitřních uzlů podstromu s kořenem x je 0 h > 0 • nechť x má výšku h a černou výšku bh(x) — b • každý syn uzlu x má výšku h — 1 a černou výšku b anebo b — 1 • z indukčního předpokladu má podstrom každého syna alespoň 2bh(x)-i _ i vnitřních uzlů • podstrom s kořenem x má alespoň 2{2bh^~1 — 1) + 1 = 2bh^ — 1 vnitřních uzlů ^vnitřním uzlem rozumíme uzel, který nese hodnotu, tj. list není vnitřním uzlem IB002 Algoritmy a datové struktury I Jaro 2018 193 / 39 Červeno černé stromy Červeno černé stromy Výška červeno černého stromu Věta 5 Červeno černý strom s n vnitřními uzly má výšku nejvýše 21og2(n + 1). ■ nechť strom má výšku h a černou výšku b m z předchozích lemmat plyne n > 2b - 1 > 2h/2 - 1 ■ po úpravě log2(n + 1) > h/2, a tedy h < 2 log2(n + 1) IB002 Algoritmy a datové struktury I Jaro 2018 194 / 390 Červeno černé stromy Červeno černé stromy Červeno černé stromy - operace ■ Search, Min, Max, Successor, Predecessor se implementují stejně jako pro binární vyhledávací stromy ■ vyjmenované operace mají složitost O(logn) ■ Insert a Delete modifikují strom ■ modifikace může porušit vlastnosti červeno černého stromu ■ jsou potřebné další kroky, které vlastnosti obnoví ■ základní operací, která vede k obnovení požadovaných vlastností, je rotace IB002 Algoritmy a datové struktury I Jaro 2018 195 / 390 Červeno černé stromy Červeno černé stromy Rotace ■ rotace zachovává vlastnost binárního vyhledávacího stromu a G a,b G /3,c G 7 a < x < b < y < c ■ časová složitost 0(1) IB002 Algoritmy a datové struktury I Jaro 2018 196 / 390 Rotace Left_Rotate(T, x) 1 y <— x.right 2 x.right «— y.left 3 if y.left ^ Nil 4 then y.left.p <— x fi 5 y.p <— x.p 6 if x.p — Nil 7 then T.root <— y s else if x — x.p.left 9 then x.p.left <— y 10 else x.p.right«— y fi fi 11 y.left <— x 12 x.p «— y IB002 Algoritmy a datové struktury I Jaro 2018 197 / 390 Červeno černé stromy Červeno černé stromy Přidání nového uzlu ■ uzel x do stromu přidáme stejným postupem jako do binárního vyhledávací stromu ■ jakou barvou máme obarvit nový uzel? ■ obě možnosti mají za důsledek porušení některých vlastností červeno černého stromu ■ řešení: obarvi uzel x červenou barvou ■ vlastnosti 1 (černý kořen) jestliže x je kořenem, tak vlastnost neplatí 3 (otec červeného uzlu je černý) nemusí platit 4 (stejná černá výška) zůstává v platnosti IB002 Algoritmy a datové struktury I Jaro 2018 198 / 390 Červeno černé stromy Červeno černé stromy Přidání nového uzlu - schéma RB_lnsert(T, a) 1 Tree_Insert(T, a) 2 a.color <— red 3 while a ^ T.root A a.p.color = red 4 do if a.p — a.p.p.left 5 then d <(— a.p.p.right 6 if d.color — red 7 then případ 1 8 else if a — a.p.right 9 then případ 2 10 else případ 3 n fi 12 fi 13 else stejně jako THEN se záměnou left a right 14 fi 15 od 16 T.root.color <(— black IB002 Algoritmy a datové struktury I Jaro 2018 199 / 390 Červeno černé stromy Červeno černé stromy Přidání nového případ 1 a.p.color black d.color black a.p.p.color red a a.p.p uzlu - schéma případ 2 a <— a.p Left_Rotate(T, a) případ 3 a.p.color <— black a.p.p.color <— red Right_Rotate(T, a.p.p) IB002 Algoritmy a datové struktury I Jaro 2018 200 / 390 Červeno černé stromy Červeno černé stromy Přidání nového uzlu - korekce - případ 1 ■ nově přidaný uzel a je červený ■ jeho otec b je červený a je levým synem svého otce5 ■ strýc d uzlu a je červený ■ praotec c uzlu a je černý obarvi otce (b) a strýce (d) uzlu a černou barvou obarvi praotce (c) uzlu a červenou barvou x x stromy x, y,p,q mají černý kořen a všechny mají stejnou černou výšku 5situace když b je pravým synem svého otce se řeší symetricky IB002 Algoritmy a datové struktury I Jaro 2018 201 /390 Červeno černé stromy Červeno černé stromy Přidání nového uzlu - korekce - případ 2 ■ uzel a je červený a je pravým synem svého otce ■ jeho otec b je červený a je levým synem svého otce ■ strýc d uzlu a je černý ■ praotec c uzlu a je černý ■ proveď levou rotaci kolem otce (b) uzlu a ■ pokračuj na případ 3 x y Left_Rotate(Ô) z x IB002 Algoritmy a datové struktury I Jaro 2018 202 / 390 Červeno černé stromy Červeno černé stromy Přidání nového uzlu - korekce - případ 3 ■ uzel a je červený a je levým synem svého otce ■ jeho otec b je červený a je levým synem svého otce ■ strýc d uzlu a je černý ■ praotec c uzlu a je černý ■ proveď pravou rotaci kolem praotce (c) uzlu a ■ vyměň obarvení mezi otcem (6) uzlu a a jeho novým bratrem (c) IB002 Algoritmy a datové struktury I Jaro 2018 203 / 390 Červeno černé stromy Červeno černé stromy Složitost přidání nového uzlu ■ případ 1: změna obarvení 3 uzlů ■ případy 2 a 3: jedna nebo dvě rotace a změna obarvení 2 uzlů ■ v případě 1 může změna barvy praotce (c) uzlu a způsobit nový konflikt a to když otec uzlu c má červenou barvou ■ v popsaném případě musíme pokračovat další iterací a korigovat barvu uzlu c ■ konečnost je garantována faktem, že každou iterací se zmenšuje vzdálenost korigovaného uzlu od kořene stromu ■ celková složitost O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 204 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu ■ uzel x ze stromu odstraníme stejným postupem jako z binárního vyhledávací stromu ■ v případě, že odstraněný uzel měl červenou barvu, vlastnosti stromu zůstávají zachované ■ v případě, že měl černou barvu, může dojít k porušení vlastnosti 4 (stejná černá výška) ■ černou barvu z odstraněného uzlu přesouváme směrem ke kořenu tak, abychom obnovili platnost vlastnosti 4 IB002 Algoritmy a datové struktury I Jaro 2018 205 / 39 Červeno černé stromy Červeno černé stromy Odstranění uzlu a - případy 1 a 2 a nemá levého syna ■ odstraň a a nahraď ho jeho pravým synem (b) ■ jestliže po přesunu uzel b a jeho otec porušují vlastnost 3 (oba jsou červené), tak uzel b obarvíme černou barvou; tím zachováme černou výšku (a musel být černý) a nemá pravého syna - symetricky IB002 Algoritmy a datové struktury I Jaro 2018 206 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu a - případ 3 a má dva syny, následník (successor) uzlu a je jeho pravým synem ■ odstraň a a nahraď ho jeho následníkem (c) ■ levý syn uzlu a se stane levým synem následníka uzlu a ■ po přesunu obarvíme následníka (c) barvou uzlu a ■ jestliže následník měl původně černou barvu, tak černou barvu dostane jeho syn, tj. syn má dvě barvy (červenou a černou anebo černou a černou) ■ problém dvou barev vyřešíme při korekci IB002 Algoritmy a datové struktury I I Jaro 2018 207 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu a - případ 4 a má dva syny, následník (successor) uzlu a není jeho synem ■ následníka (d) nahraď jeho pravým synem (e) ■ odstraň a a nahraď ho jeho následníkem (d), synove uzlu a se stanou syny následníka (d) ■ po přesunu obarvíme následníka (d) barvou uzlu a ■ jestliže následník měl původně černou barvu, tak černou barvu dostane jeho syn, tj. syn má dvě barvy (červenou a černou anebo černou a černou) ■ problém dvou barev vyřešíme při korekci IB002 Algoritmy a datové struktury I Jaro 2018 208 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu - korekce dvou barev - případ 1 uzel a má dvě barvy bratr (c) uzlu a je červený proveď levou rotaci kolem otce (b) uzlu a vyměň barvy mezi otcem (6) a praotcem (c) uzlu a pokračuj některým z následujících případů z w p q Rotate_Left(6) x y z w x y z w ; ^__________________* jiný případ stromy x,y, z,w,p,q mají stejnou černou výšku, nemají žádný uzel s dvěma barvami a neporušují žádnou vlastnost červeno černého stromu IB002 Algoritmy a datové struktury I Jaro 2018 Červeno černé stromy Červeno černé stromy Odstranění uzlu - korekce dvou barev - případ 2 uzel a má dvě barvy bratr (c) uzlu a stejně jako oba jeho synové (d, e) mají černou barvu ■ vezmi jednu černou barvu z uzlu a a přesuň ji do jeho otce (b) ■ bratr (c) uzlu a dostane červenou barvu (aby se zachovala černá výška) ■ uzel se dvěma barvami se přesunul blíž ke kořenu, problém jeho dvou barev řešíme rekurzivně IB002 Algoritmy a datové struktury I Jaro 2018 210 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu - korekce dvou barev - případ 3 uzel a má dvě barvy bratr (c) uzlu a a jeho pravý syn (e) mají černou barvu, levý syn (d) je červený ■ proveď pravou rotaci kolem bratra (c) uzlu a ■ vyměň barvy mezi původním a novým bratrem uzlu a (d, c) ■ pokračuj případem 4 IB002 Algoritmy a datové struktury I Jaro 2018 211 / 390 Červeno černé stromy Červeno černé stromy Odstranění uzlu - korekce dvou barev - případ 4 uzel a má dvě barvy bratr (c) uzlu a má černou barvu, jeho pravý syn (e) má červenou barvu ■ proveď levou rotaci kolem otce (b) uzlu a ■ obarvi nového praotce (c) uzlu a barvou jeho otce (b) ■ přesuň černou barvu z uzlu a na jeho otce (6), otec (b) se stane černým ■ uzel (e) se stane černým IB002 Algoritmy a datové struktury I Jaro 2018 212 / 390 Červeno černé stromy Rank prvku Pořadí (rank) prvku využití červeno černých stromů při určení ranku (pořadí) prvku a vyhledávání prvku s daným rankem ■ množina A obsahující n vzájemně různých čísel ■ číslo x £ A má rank i právě když v A existuje přesně i — l čísel menších než x možné řešení ■ jestliže prvky A jsou uložené v poli, tak v čase 0{n) můžeme • najít číslo s rankem i • určit rank daného čísla existuje efektivnější řešení? při použití červeno černých stromů dokážeme oba problémy vyřešit v čase O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 213 / 390 Červeno černé stromy Rank prvku Rozšírení červeno černých stromů požadujeme ■ efektivní implementaci standardních operací nad červeno černým stromem ■ efektivní implementaci operace RB_Select(x, i), která najde z-ty nejmenší klíč v podstromě s kořenem x ■ efektivní implementaci operace RB_Rank(T.x), která určí rank klíče uloženého v uzlu x jestliže strom obsahuje uzly se stejnými klíči, tak rankem klíče je pořadí uzlu v Inorder uspořádání uzlů stromu IB002 Algoritmy a datové struktury I Jaro 2018 214 / 390 Červeno černé stromy Rank prvku Princip ke každému uzlu x přidáme atribut x.size - počet (vnitřních) uzlů v podstromě s kořenem x, včetně uzlu x x.size = x.left.size + x.right.size + 1 NIL NIL NIL NIL NIL NIL IB002 Algoritmy a datové struktury I Jaro 2018 215 / 390 Červeno černé stromy Rank prvku Vyhledání klíče s daným rankem RB_SelectO,z) 1 r x.left.size + 1 2 if i — r then return x 3 else if i < r then return RB_SELECT(x./e/í, i) 4 else return RB-Select(x.right, i r) fi fi korektnost ■ z definice atributu .size plyne, že počet uzlů v levém podstromu uzlu x navýšený o 1 (r) je přesně rank klíče uloženého v x v podstromě s kořenem x ■ když i — r, tak x je hledaný uzel ■ když i < r, tak z-ty nejmenší klíč se nachází v levém podstromě uzlu x a je z-tým nej menším klíčem v tomto podstromě ■ když i > r, tak z-ty nejmenší klíč se nachází v pravém podstromě uzlu x a jeho poradiv tomto podstromě je i snížené o počet uzlů levého podstromu IB002 Algoritmy a datové struktury I Jaro 2018 216 / 390 Červeno černé stromy Rank prvku Vyhledání klíče s daným rankem RB_Select(>,z) 1 r x.left.size + 1 2 if i — r then return x 3 else if i < r then return RB_SELECT(x./e/t, i) 4 else return RB_SELECT(x.rz^/it, i — r) fi fi složitost ■ každé rekurzivní volání se aplikuje na strom, jehož hloubka je o 1 menší ■ hloubka červeno černého stromu je O(logn) ■ složitost RB_Select je O(logn) IB002 Algoritmy a datové struktury I Jaro 2018 217 / 390 Červeno černé stromy Rank prvku Určení ranku daného prvku NIL NIL NIL NIL NIL NIL rank prvku 11 ■ všechny uzly v levém podstromě uzlu 11 ■ sledujeme cestu od 11 do kořene ■ jestliže uzel na cestě je levým synem, nemění rank prvku 11 ■ jestliže uzel na cestě je pravým synem, tak on sám jakož i jeho levý podstrom obsahují klíče menší než 11 IB002 Algoritmy a datové struktury I Jaro 2018 218 / 39 Určení ranku daného prvku RB_Rank(T, x) 1 r x.left.size + 1 2 y x 3 while y ^ T.root 4 do if y — y.p.right 5 then r <(— r + y.p.left.size + 1 f i 6 y ^— y.p od 7 return r korektnost invariant na začátku každé iterace while cyklu je r rovné ranku klíče x.key v podstromě s kořenem y inicializace na začátku je r rovné ranku x.key v podstromě s kořenem x a x = y IB002 Algoritmy a datové struktury I Jaro 2018 219 / 390 Červeno černé stromy Rank prvku RB_Rank(T, x) 1 r x.left.size + 1 2 y x 3 while y ^ T.root 4 do if y — y.p.right 5 then r r + y.p.left.size + 1 f i 6 y y.p od 7 return r invariant na začátku každé iterace while cyklu je r rovné ranku klíče x.key v podstromě s kořenem y iterace ■ na konci cyklu se vykoná y <(— y.p ■ po provedení cyklu proto musí platit, že r je rank x.key v podstromě s kořenem y.p ■ jestliže y je levý syn, tak všechny klíče v podstromě jeho bratra jsou větší než x.key a r se nemění ■ jestliže y je pravý syn, tak všechny hodnoty v podstromě jeho bratra jsou menší než x.key a hodnota r se zvýší o velikost tohoto stromu plus 1 (klíč v uzlu y.p je taky menší než x.key) IB002 Algoritmy a datové struktury I Jaro 2018 220 / 39 Červeno černé stromy Rank prvku RB_Rank(T, x) 1 r i— x.left.size + 1 2 y <— x 3 while y ^ T.root 4 do if y — y.p.right 5 then r <— r + y.p.left.size + 1 fi 6 y Right_Rotate(T, y) IB002 Algoritmy a datové struktury I Jaro 2018 222 / 39C Červeno černé stromy Rank prvku Odstranění uzlu první fáze odstraní uzel ze stromu • na pozici odstraněného uzlu se přesune uzel y • pro aktualizaci hodnot size procházíme cestu od původní pozice uzlu y do kořene a každému uzlu na této cestě snížíme hodnotu size o 1 • složitost operace se navýší o O(logn) korekce obarvení stromu • ke změně velikosti podstromu může dojít při rotaci, aktualizace hodnot viz přidání nového uzlu • počet rotací je nejvýše 3, složitost se navýší o 0(1) složitost přidávání i odstraňování uzlu zůstává asymptoticky stejná IB002 Algoritmy a datové struktury I Jaro 2018 223 / 390 B-stromy Datové struktury ■ Binární vyhledávací stromy ■ Intervalové stromy V ■ Červeno černé stromy ■ Rank prvku EE B-stromy ■ Zřetězené hašování ■ Otevřená adresace IB002 Algoritmy a datové struktury I Jaro 2018 224 / 390 B-stromy B stromy B stromy jsou zobecněním binárních vyhledávacích stromů ■ B strom je balancovaný, všechny listy mají stejnou hloubku ■ vnitřní uzel stromu obsahuje t — 1 klíčů a má t následníků ■ klíče ve vnitřních uzlech stromu zároveň vymezují t intervalů, do kterých patří klíče každého z jeho t podstromů využití B stromů ■ B stromy se typicky používají v databázových systémech a aplikacích, kde objem zpracovávaných dat není možné uchovávat v operační paměti ■ počet klíčů uložených v uzlu (a tím i počet následníků) se může pohybovat od jednotek po tisíce; cílem je minimalizovat počet přístupů na disk ■ v pseudokódu modelujeme přístupy operacemi DiSK_READa Disk_Write ■ existují různé varianty, podrobněji viz např. PV062 ■ Bayer, McCreight 1972 IB002 Algoritmy a datové struktury I Jaro 2018 225 / 390 B-stromy B stromy vs BVS a červeno černé stromy ■ zachován princip vyhledávání ■ všechny uzly mají stejnou hloubku ■ uzly B stromů můžou mít víc následníků ■ výška B stromu je O(logn), díky většímu počtu následníků může být ale výrazně menší ■ operace minimalizují průchod stromem IB002 Algoritmy a datové struktury I Jaro 2018 226 / 390 B-stromy Stupeň B stromu minimální stupeň stromu číslo t, které definuje dolní a horní hranici na počet klíčů uložených v uzlu ■ každý uzel (s výjimkou kořene) musí obsahovat alespoň t — 1 klíčů ■ jestliže strom je neprázdný, tak kořen musí obsahovat alespoň jeden klíč ■ každý vnitřní uzel (s výjimkou kořene) musí mít alespoň t následníků ■ každý uzel může obsahovat nejvýše 2t — 1 klíčů ■ každý vnitřní uzel může mít nejvýše 2t následníků ■ uzel, který má přesně 2t — 1 klíčů, se nazývá plný ■ nejjednodušší B strom má minimální stupeň 2 ■ každý jeho vnitřní uzel má 2, 3 anebo 4 následníky ■ obvykle se označuje jako 2-3-4 strom IB002 Algoritmy a datové struktury I Jaro 2018 227 / 390 B-stromy Výška B stromu všechny listy mají stejnou hloubku B strom s n > 1 klíči a minimálním stupněm t > 2 má hloubku nejvýše n + 1 h < log t kořen obsahuje alespoň jeden klíč, každý vnitřní uzel alespoň t — 1 klíčů strom má 1 uzel hloubky 0 (kořen), alespoň 2 uzly hloubky 1, alespoň 2t uzlů hloubky 2, alespoň 2í2 uzlů hloubky 3, obecně alespoň 2th~1 uzlů hloubky h h h-1 i=l z=0 ŕh - 1 > 1 + (t - 1) 2ť"1 = 1 + 2(t - 1) 5^ ť = l + 2(í-l)(T-r)=2íÄ-l z toho í*1 < 2±1 a tedy logť í*1 < logť ^ □ Jaro 2018 228 / 390 IB002 Algoritmy a datové struktury I B-stromy Klíče v B stromu ■ každý uzel x má atributy • x.n - počet klíčů uložených v uzlu x • klíče x.keyi,x.kei/2, • • • ,x.keyxm, které jsou uloženy v neklesajícím pořadí • x.leaf - booleovská proměnná nabývající hodnotu je true právě když uzel x je listem stromu ■ každý vnitřní uzel x obsahuje navíc x.n + 1 ukazatelů X.C\, X.C2, • • • 5 X.CX,fi-\-l ■ klíče x.keyi definují intervaly, z kterých jsou klíče uložené v každém z podstromů; jestliže ki je klíč uložený v podstromě s kořenem x.Ci, tak platí k\ < x.keyi < k2 < x.key2 < ... < x.keyx.n < kx.n+i IB002 Algoritmy a datové struktury I Jaro 2018 229 / 390 B-stromy Operace nad B stromem ■ vytvoření stromu; vyhledávání, přidání a odstranění klíče ■ typické aplikace, které využívají B stromy, pracují s daty uloženými na externím disku ■ před každou operací, která přistupuje k objektu x, se nejdříve musí vykonat operace Disk_Read(x), která zkopíruje objekt do operační paměti (za předpokladu, že tam není) ■ symetricky operace Disk_Write(x) se použije pro uložení všech změn vykonaných nad objektem x ■ předpokládáme, že kořen B stromu je vždy uložený v operační paměti a proto nad kořenem vykonáváme pouze operaci Disk_Write ■ asymptotická složitost všech operací je úměrná hloubce stromu, tj. O(logn), kde n je počet klíčů uložených v stromu ■ z důvodu optimalizace počtu přístupů na externí disk jsou všechny operace navrženy tak, aby se uzel stromu navštívil nejvýše jednou, tj. všechny operace postupují směrem od kořene dolů a nikdy se nevracejí do již navštíveného uzlu IB002 Algoritmy a datové struktury I Jaro 2018 230 / 390 B-stromy Vyhledávání ■ analogicky jako v binárním vyhledávacím stromě, vybíráme jednoho z následníků uzlu ■ argumentem operace je ukazatel T.root na kořen stromu a hledaný klíč k ■ jestliže klíč k je v B stromě, operace vrátí dvojici (y, i), kde y je uzel a i index takový, že y.keyi — k ■ v opačném případě vrátí hodnotu Nil vyhledání klíče R T.root B C F G J K L N P R S V w Y Z IB002 Algoritmy a datové struktury I Jaro 2018 231 / 390 B-stromy Vyhledávání B-Tree_Search(x, k) 1 i <-1 2 while i < x.n A x.keyi < k do 3 1 ' <$>' <$>' N. SW y = cc. c* z = cc.ci+i ä S T U V p Q R < > t \ f \ f \ f V T U v T\ T2 T3 T4 T5 Tq Ty T8 TľT2T3T4 T5T6T7T8 argumentem operace B-Tree_Split je ■ vnitřní uzel x, který není plný ■ index i takový, že x.ci je plný následník uzlu x IB002 Algoritmy a datové struktury I Jaro 2018 237 / 390 B-stromy Rozdělení kořene - schéma T.root r T\ T2 T3 T4 T5 T6 T7 Tg T.root A D F H L N P - A D F f \ 1 y 1 y < > > 1 1 \ í V Ti T2 T3 T4 L N P V ) f V n n t7 t8 když potřebujeme rozdělit kořen stromu, tak nejdříve vytvoříme nový, prázdný uzel, který se stane novým kořenem stromu rozdělení kořene způsobí navýšení hloubky stromu o 1 IB002 Algoritmy a datové struktury I Jaro 2018 238 / 390 B-stromy Rozdělení uzlu - implementace B-Tree_Split(x, i) 1 z <— Allocate_Node() 2 y x.Ci 3 z.leaf y.leaf 4 z.n t — 1 5 for j = 1 to t — 1 do z.keyj y.key^+t od (5 if -^y.leaf then for j; = 1 to £ do z.Cj y.Cj+t °d fi 7 y.n 1 A x.keyi > k 4 do x.keyi+i x.keyi 5 z 1 A x.keyi > do z ^ i - lod 10 z z + 1 11 Disk_Read(x.q) is if x.Q.n = 2t — l then B-Tree_Split(x, z) 15 if x.keyi < k then z z + 1 fi fi 14 B-Tree_Insert_Nonfull(x.q, k) 15 fi IB002 Algoritmy a datové struktury I Jaro 2018 244 / 390 B-stromy Přidání klíče - složitost ■ počet operací Disk_Write a Disk_Read je 0{h) {vždy jenom jedna mezi dvěma voláními B-Tree_Insert_NonfullJ ■ celková složitost je 0(th) = 0(tlogtn) ■ procedura B-Tree_Insert_Nonfull je tail - rekurzivní, a proto je počet uzlů, které musí být uloženy v operační paměti, konstantní IB002 Algoritmy a datové struktury I Jaro 2018 245 / 390 B-stromy Odstranění klíče odstranění probíhá analogicky jako u binárního vyhledávacího stromu ■ jestliže se klíč určený k odstranění nachází v listu, odstraníme ho ■ jestliže se klíč určený k odstranění nachází v uzlu, který není listem, nahradíme ho jeho následníkem (resp. předchůdcem) a následníka odstraníme z listu ve kterém se původně nacházel ■ samotné mazání klíče se vždy realizuje v listu ■ operace má stejnou asymptotickou složitost jako u BVS ■ samotná implementace má ale několik speciálních případů, protože klíč může být odstraněn z libovolného uzlu ■ v optimalizované variantě klíč odstraníme při jednom průchodu stromem od kořene dolů, s možnou výjimkou návratu do uzlu, ve kterém byl původně uložen odstraňovaný klíč IB002 Algoritmy a datové struktury I Jaro 2018 246 / 390 B-stromy Odstranění klíče - základní varianta odstranění klíče k z listu x □ list x je současně kořenem stromu • klíč k odstraníme Q list x není kořenem a obsahuje alespoň t klíčů • klíč k odstraníme B list x není kořenem a obsahuje přesně t — 1 klíčů • vezmi toho bratra y listu x, který má více klíčů • vytvoř seznam obsahující klíče z listů x b y b navíc ten klíč z otce p listu x, který tvoří hranici mezi x b y • délka seznamu je t — 2 (= počet klíčů v x) + 1 (= klíč z otce) + počet klíčů ví/>t-2 + l+t-l • rozlišujeme dva případy podle délky seznamu IB002 Algoritmy a datové struktury I Jaro 2018 247 / 390 B-stromy Odstranění klíče - základní varianta - délka seznamu 3 A seznam obsahuje alespoň 2t — 1 klíčů ■ seznam rozdělíme na 3 části: Left, Middle a Right, kde Middle je medián seznamu, Left obsahuje klíče menší než medián a Right klíče větší než medián ■ klíč Middle vrátíme do otce p, ze kterého jsme předtím odebrali hraniční klíč ■ klíče Left a Right vložíme do dvou uzlů x a y ■ uzly x a y mají alespoň t — 1 klíčů, počet klíčů v uzlu p zůstal nezměněný, hotovo 3 B seznam obsahuje právě 2t — 2 klíčů ■ uzly x a y nahradíme jediným uzlem obsahujícím všechny klíče seznamu ■ nový list má povolený počet klíčů ■ otec p má počet klíčů o 1 nižší než původně ■ v případě, že počet klíčů v uzlu p klesl pod minimální hranici t — 1, opakujeme (rekurzivně) postup pro uzel p IB002 Algoritmy a datové struktury I Jaro 2018 248 / 390 B-stromy Odstranění klíče - základní varianta ■ po odstranění klíče z listu může klesnout počet klíčů v jeho uzlu pod minimální hranici ■ musíme realizovat operace, které obnoví platnost podmínky minimálního počtu klíčů v uzlu ■ může nastat situace, když se prochází strom od kořene k listu a potom zpátky od listu ke kořeni (např. když všechny uzly na cestě od kořene do listu obsahujícího klíč mají stupeň přesně ť) ■ podobně jako při vkládaní klíče optimalizujeme proces odstranění klíče tak, abychom minimalizovali počet přístupů na disk IB002 Algoritmy a datové struktury I Jaro 2018 249 / 390 B-stromy Odstranění klíče - optimalizace ■ postupujeme od kořene směrem k listu ■ vždy, když procházíme přes uzel, který má přesně t — 1 klíčů, tak uděláme takovou korekci, která zvýší počet klíčů v uzlu na t ■ když narazíme na uzel, ze kterého potřebujeme odstranit klíč, máme garanci, že jeho otec má alespoň t klíčů ■ když odstranění klíče z uzlu způsobí snížení počtu klíčů v jeho otci, nevznikne žádný problém IB002 Algoritmy a datové struktury I Jaro 2018 250 / 390 B-stromy Optimální odstranění klíče - pravidla odstraňujeme klíč k 1 když klíč A: je v listu x, odstraň k z x 2 když klíč k je ve vnitřním uzlu x, tak a. jestliže syn y, který je před k v x, obsahuje alespoň t klíčů, tak najdi v podstromě s kořenem y předchůdce k' klíče k\ nahraď v x klíč k klíčem k'\ rekurzivně odstraň klíč k' b. jestliže syn y má méně než t klíčů tak, symetricky, prozkoumej syna z, který následuje za k v x\ v případě že z obsahuje alespoň t klíčů, tak najdi v podstromě s kořenem z následníka k' klíče k\ nahraď v x klíč k klíčem k'\ rekurzivně odstraň klíč k' c. v případě, že synové y i z mají jen t — 1 klíčů, tak do vrcholu y přesuň klíč k a všechny klíče z vrcholu z\ z vrcholu x odstraň k a ukazatel na z\ nový uzel y obsahuje 2t — 1 klíčů (mezi nimi i klíč fc); rekurzivně odstraň k z y IB002 Algoritmy a datové struktury I Jaro 2018 251 / 390 B-stromy Odstranění klíče - pravidla, pokračování 3 když klíč k není ve vnitřním uzlu x , tak urči kořen x.ci stromu, který musí obsahovat k (za předpokladu, že A: je v stromě); v případě, že uzel x.Ci obsahuje jen t — 1 klíčů, pokračuj body 3.a. anebo 3.b. které zaručí, že rekurzivní volání se aplikuje na uzel obsahující alespoň t klíčů; rekurzivně odstraň klíč k z vhodného následníka uzlu x a. v případě, že x.Ci obsahuje jen t — 1 klíčů, ale některý z jeho přímých bratrů obsahuje alespoň t klíčů, tak zvyš počet klíčů v x.Ci a to tak, že přesuneš klíč z x do x.Ci, přesuneš klíč z bratra x a přesuneš příslušný ukazatel na následníka z bratra do uzlu x.Ci b. v případě, že x.Ci i jeho jeho přímí bratři obsahují jen t — 1 klíčů, tak přesuň do x.Ci jeden klíč z x a všechny klíče z jednoho z bratrů IB002 Algoritmy a datové struktury I Jaro 2018 252 / 390 B-stromy Odstranění klíče F - případ 1 t = 3 A B D E F J K L \ \ N O \ | Q R S || U V Y Z A B D E J K L \ \ N O \ | Q R S || U V Y Z IB002 Algoritmy a datové struktury I Jaro 2018 253 / 390 B-stromy Odstranění klíče M - případ 2a t = 3 . C, G M-/ \ A B D E J K L N 0 Q R S || U V Y Z A B D E J K N 0 IB002 Algoritmy a datové struktury I Jaro 2018 254 / 390 B-stromy Odstranění klíče G — případ 2c t = 3 A B D E J K N 0 Q R S \\U V Y Z A B D E J K NO Q R S \\U V Y Z IB002 Algoritmy a datové struktury I Jaro 2018 255 / 390 B-stromy Odstranění klíče B — případ 3a t = 3 a b e j k n o q r s u v y z e. L.P.t x a c j k n 0 q r s u v y z IB002 Algoritmy a datové struktury I Jaro 2018 256 / 390 B-stromy Odstranění klíče Z — případ 3b t = 3 A C J K N 0 Q R S U V Y Z E. L.P.T A C J K N 0 Q R S U V X Y IB002 Algoritmy a datové struktury I Jaro 2018 257 / 390 B-stromy Odstranění klíče D — případ 3b t = 3 A B D E J K NO Q R S || U V || Y Z A B E J K N 0 Q R S U V Y Z .CL L,P J JC. " / \^ A B E J K N 0 Q R S U V Y Z IB002 Algoritmy a datové struktury I Jaro 2018 258 / 39C B-stromy Odstranění klíče - složitost ■ v případě, že se odstraňovaný klíč nachází v listu, procedura prochází od kořene k listu bez nutnosti návratu ■ v případě, že se klíč nachází ve vnitřním uzlu, tak procedura postupuje od kořene k listu s možným návratem do vrcholu, ze kterého byl klíč odstraněn a nahrazen svým předchůdcem anebo následníkem (případy 2.a., 2.b.) ■ mezi dvěma rekurzivními voláním se vykoná nanejvýš jedna operace Disk_Write a jedna operace Disk_Read; jejich celkový počet je proto O(h) ■ celková složitost je 0{th) — 0{t\ogtn) IB002 Algoritmy a datové struktury I Jaro 2018 259 / 390 B-stromy B+ stromy ■ klíče jsou uloženy pouze v listech ■ zřetězení listů zachovává pořadí klíčů ■ vnitřní uzly B+ stromů indexují listy výhody a nevýhody ■ klíč v B stromě se najde před dosažením listu ■ vnitřní uzly B stromů jsou větší, do uzlů se proto může uložit méně klíčů a strom je hlubší ■ operace vkládaní a odstraňování klíče z B stromu jsou komplikovanější ■ implementace B stromu je náročnější než implementace B+stromu IB002 Algoritmy a datové struktury I Jaro 2018 260 / 390 Hašovaní Datové struktury ■ Binární vyhledávací stromy ■ Intervalové stromy ■ Červeno černé stromy ■ Rank prvku EE Hašovaní ■ Zřetězené hašovaní ■ Otevřená adresace IB002 Algoritmy a datové struktury I Jaro 2018 261 / 390 Hašovaní Slovník ■ dynamický datový typ pro reprezentaci množiny objektů ■ podporované operace Insert^, x) do množiny S přidá objekt x Search(S', x) zjistí, zda množina S obsahuje objekt x Delete(S', x) z množiny S odstraní objekt x vhodné datové struktury pro implementaci slovníku seznam všechny operace mají složitost 0(n) (n je mohutnost množiny S) vyhledávací strom se dá použít za předpokladu, že objekty mají číselný klíč, při použití vyváženého stromu je složitost operací O(logn) cíl: složitost všech operací v nej horším případě Q(n) v očekávaném případě 0(1) IB002 Algoritmy a datové struktury I Jaro 2018 262 / 390 Hašovaní Přímé adresování Přímé adresování ■ každý prvek reprezentované množiny prvků má přiřazen klíč vybraný z univerza U — {0,1,..., m — 1} ■ žádné dva prvky nemají přiřazený stejný klíč ■ pole T[0.. .m - 1] • každý slot (pozice) v T odpovídá jednomu klíči z U • když reprezentovaná množina obsahuje prvek x s klíčem k, tak T [k] obsahuje ukazatel na x • v opačném případě je T[k] prázdné (Nil) ■ složitost operací je konstantní IB002 Algoritmy a datové struktury I Jaro 2018 263 / 390 Hašovaní Přímé adresování - schéma IB002 Algoritmy a datové struktury I Jaro 2018 264 / 390 Hašovaní Přímé adresování Výhody a nevýhody přímého adresování výhody ■ konstantní složitost všech operací ■ jednoduchá implementace nevýhody ■ v případě, že univerzum ř7 je veliké, tak uchovávání tabulky velikosti univerza je neefektivní resp. nemožné ■ v případě, že množina aktuálně uložených klíčů je malá ve srovnání s velikostí univerza, tak větší část paměti alokované pro tabulku T je nevyužitá ■ problém objektů se stejným klíčem IB002 Algoritmy a datové struktury I Jaro 2018 265 / 390 Hašovaní Přímé adresování Hašovací tabulka v případě, že množina aktuálně uložených klíčů K je výrazně menší než U, využívá hašovací tabulka výrazně méně paměti, než tabulka s přímým přístupem potřebný prostor se dá redukovat až na Q(\K\) složitost operací zůstává konstantní avšak v očekávaném (a ne v nejhorším) případě rozdíly přímé adresování hašování prvek prvek x s klíčem k x s klíčem k uloží v uloží v tabulce na tabulce na pozici pozici T[k] T[h(k)} ■ h je funkce h : U —> {0,1,..., m -n h se nazývá hašovacífunkce IB002 Algoritmy a datové struktury I Jaro 2018 266 / 390 Hašovaní Přímé adresování Hašovací tabulka - problémy k řešení 1. řešení kolizí kolize « dva anebo více klíčů zahašujeme na stejnou pozici pro x 7^ y je h(x) — h(y), x a y mají stejný otisk ■ zřetězené hašovaní (chaining) ■ otevřená adresace (open adressing) 2. výběr hašovací funkce ■ minimalizovat počet kolizí ■ efektivní výpočet funkce IB002 Algoritmy a datové struktury I Jaro 2018 267 / 390 Zřetězené hašování hašování každá položka tabulky obsahuje (ukazatel na) seznam prvků zahašovaných na stejnou pozici seznam je prázdný právě když žádný prvek nebyl zahašovaný na danou pozici vkládání prvku x do hašovací tabulky T se realizuje jako přidání prvku na začátek seznamu T[h(x.key)] prvek x vyhledáváme v seznamu T[h(x.key)] prvek x odstraníme vymazáním ze seznamu T[h(x.key)] IB002 Algoritmy a datové struktury I Jaro 2018 268 / 390 IB002 Algoritmy a datové struktury I Jaro 2018 269 / 390 Hašovaní Zřetězené hašovaní Zřetězené hašovaní - složitost složitost v nejhorším případě Insert konstantní (za předpokladu, že vkládaný prvek není v tabulce) Search úměrná délce seznamu; v nejhorším případě Q(ri), kde n je počet prvků uložených v tabulce Delete (asymptoticky) stejná jako složitost Search (za předpokladu dvousměrného seznamu) složitost v průměrném případě záleží od výběru hašovací funkce IB002 Algoritmy a datové struktury I Jaro 2018 270 / 390 Hašovaní Zřetězené hašovaní Zřetězené hašovaní - průměrná složitost předpokládáme, že hašovací funkce je jednoduchá uniformní (simple uniform), tj. že pro každý prvek univerza je pravděpodobnost jeho zahašování na kterýkoliv index tabulky stejná (a nezávislá od toho, kam jsou zahašovány zbylé prvky univerza) složitost operací se vyjadřuje vzhledem k faktoru naplnění (had factor) pro danou tabulku s m pozicemi, ve které je uložených n prvků, definujeme faktor naplnění a předpisem a — n/m, tj. průměrný počet prvků zahašovaných na stejnou pozici pro j — 0,1,..., m — 1 nechť rij označuje délku seznamu T[j pro jednoduchou uniformní hašovací funkci platí, že očekávaná délka seznamu T 3\ Je E[rij] — a — n/m předpokládáme, že výpočet hodnoty funkce má konstantní časovou složitost IB002 Algoritmy a datové struktury I Jaro 2018 271 / 390 Hašovaní Zřetězené hašovaní Zřetězené hašovaní - průměrná složitost V hašovací tabulce, ve které jsou kolize řešeny zřetězením a ve které se používá jednoduchá uniformní funkce, má operace neúspěšného vyhledávaní prvku průměrnou časovou složitost 0(1 + a). V hašovací tabulce, ve které jsou kolize řešeny zřetězením a ve které se používá jednoduchá uniformní funkce, má operace úspěšného vyhledávaní prvku průměrnou časovou složitost 0(1 + a). v případě, že počet pozic v tabulce je proporcionální počtu prvků v tabulce, n — O (m), platí a — n/m — 0{m)/m — 0(1) vyhledávaní prvku má konstantní průměrnou složitost samotné vložení prvku a odstranění prvku ze seznamu má konstantní složitost všechny operace mají za daných předpokladů konstantní průměrnou složitost IB002 Algoritmy a datové struktury I Jaro 2018 272 / 39 Hašovaní Hašovací funkce Výběr hašovací funkce jak vybrat dobrou hašovací funkci? ■ funkce by měla mít vlastnosti jednoduché uniformní funkce: každý klíč je zahašován na všechny pozice se stejnou pravděpodobností ■ v praxi je těžké ověřit podmínku uniformity protože neznáme rozložení klíčů (a navíc jsou na sobě často závislé) ■ v praxi využíváme při volbě hašovací funkce znalosti rozložení klíčů s cílem, aby se často společně se vyskytující klíče zahašovaly na různé pozice ■ příklad: když klíče jsou vybírány náhodně s uniformním rozdělením z intervalu (0,1), tak hašovací funkce h{k) — \ k • m\ je jednoduchou uniformní funkcí IB002 Algoritmy a datové struktury I Jaro 2018 273 / 390 Hašovaní Hašovací funkce Klíče jako přirozené čísla ■ většina hašovacích funkcí je navržená pro univerzum - množinu přirozených čísel N ■ když klíče nejsou přirozená čísla, můžeme je interpretovat jako přirozená čísla použitím vhodného kódování příklad • znakový řetězec interpretujeme jako číslo (ve vhodně zvolené číselné soustavě) • řetězec CLRS • ASCII hodnoty: C = 67, L = 76, R = 82, S = 83 • máme 128 ASCII hodnot, volíme proto číselnou soustavu se základem 128 • CLRS interpretujeme jako (67 • 1283) + (76 • 1282) + (82 • 1281) + (83 • 128°) IB002 Algoritmy a datové struktury I Jaro 2018 274 / 390 Hašovaní Hašovací funkce Hašovací funkce - metoda dělení h(k) — k mod m příklad m = 20, k = 91 h(k) = 11 výhody rychlost nevýhody špatné chování pro některé m • pro m — 2P je hodnota vždy p nejpravějších bitů z k • když je znakový řetězec interpretovaný při základě 2P, tak hodnota m = 2P — 1 není vhodná, protože po permutaci řetězce se hodnota hašovací funkce nezmění • dobrou volbou pro m je prvočíslo IB002 Algoritmy a datové struktury I Jaro 2018 275 / 390 Hašovaní Hašovací funkce Hašovací funkce - metoda binárního násobení ■ předpoklad: univerzum je U množina binárních čísel délky w ■ předpoklad: velikost m tabulky je mocninou dvojky, m — 2p ■ cílem je zahašovat ^-bitové čísla na p-bitové čísla ■ zvolíme libovolnou konstantu A, 0 < A < 1 hA(k) = [m (k A mod 1)J postup výpočtu □ vynásob klíč k konstantou A b ze součinu vezmi desetinnou část výsledek vynásob číslem m a ze součinu vezmi celou část IB002 Algoritmy a datové struktury I Jaro 2018 276 / 390 Hašovaní Hašovací funkce hA(k) = ■ zvolíme A tvaru s/2w ■ vynásobíme čísla kas ■ výsledkem násobení je 2w bitové číslo, kde r\ je celočíselná část součinu k A a ro je desetinná část součinu (viz obrázek) ■ pro další výpočet potřebujeme pouze ro ■ potřebujeme celou část součinu čísel ro a m ■ vzhledem k tomu, ze m — 2P, násobení znamená posun o p bitů doleva ■ ve skutečnosti nemusíme vůbec násobit a stačí vzít p nejvýznamnějších bitů čísla ro w bitů x I s = A.2W I m (k A mod 1)1 ri vezmi p nejlevějších bitů IB002 Algoritmy a datové struktury I Jaro 2018 277 / 39 Hašovaní Hašovací funkce Metoda binárního násobení - příklad ■ w = 5, m = 8, w = 3, tj. hašujeme 5 bitové čísla, velikost tabulky je 8 = 23 a chceme hašovat na 3 bitové čísla ■ hašujeme klíč k — 21 ■ vybíráme konstantu A tvaru s/2w a takovou, aby 0 < A < 1 - proto musí platit 0 < s < 25, vybereme s = 13 A = 13/32 výpočet IiA(k) podle vzorce — Lm ^- mo(i 1)J fcA = 21 • 13/32 = 8|| kA mod 1 = 17/32 m(kA mod 1) = 8 • 17/32 = \\ [m(kA mod 1)J = 4 = /ia(^) implementace • fcs = 21 • 13 = 273 = 8 • 25 + 17 • T\ — 8,ro = 17; bitový zápis ro je 10001 • vezmeme p = 3 nejvýznamnější bity ro, tj. 100 (4 v desítkové soustavě) • hA{k) = 4 IB002 Algoritmy a datové struktury I Jaro 2018 278 / 39 Hašovaní Univerzální hašování Univerzální hašování scénář ani nejlepší hašovací funkce negarantuje dobré chování hašování v případě, že klíče určené k zahašování jsou vybrány tím nejhorším možným způsobem (můžeme si představit útočníka, který pozná náš hašovací program a hašovací funkci a na základě toho dokáže vybrat takové klíče, které se zahašují na stejnou pozici, viz analogii s výběrem pivota pro Quicksort) řešení při každém použití hašovacího programu vybereme náhodně jinou hašovací funkci (když útočník neví, jaká hašovací funkce bude vybrána, nemůže záměrně vybírat vstupy, které povedou k špatnému chování) výběr funkce samotný fakt náhodného výběru funkce ještě negarantuje efektivitu hašování; je potřebné vybírat z vhodných kandidátů IB002 Algoritmy a datové struktury I Jaro 2018 279 / 390 Hašovaní Univerzální hašování Univerzální hašování Definice 6 Necht H je konečná i na m pozic. % je uni každou dvojici klíčů k h[k) — h(l), nejvýše mn vei U ožina hašovacích funkcí, které mapují univerzum klíčů U rzální množinou hašovacích funkcí právě když pro E U, k 7^ l, je počet hašovacích funkcí h E H, pro které /m. Věta 7 Předpokládejme, že hašovací funkce, náhodně vybraná z univerzální množiny hašovacích funkcí, je použita pro za hašovánín klíčů do tabulky s m pozicemi. Pak pro klíč k platí, že když • k není v tabulce, tak očekávaná délka seznamu, do kterého se zahašuje k, je nejvýše a — n/m • k je v tabulce, tak očekávaná délka seznamu, který obsahuje k, je nejvýše < 1 + a. IB002 Algoritmy a datové struktury I Jaro 2018 280 / 390 Hašovaní Univerzální hašování Univerzální hašování - složitost Důsledek 8 Libovolná posloupnost n operací Insert, Search a Delete, z nichž nejvýše 0(m) operací je typu Insert, má očekávanou časovou složitost @{n) za předpokladu použití zřetězeného hašování, univerzální množiny hašovacích funkcí a tabulky s m pozicemi. Důsledek 9 Použitím univerzálního hašování a řešení kolizí řetězením v tabulce s m pozicemi zabere očekávaný čas @{n) jakákoliv posloupnost n operacíInsert, Search a Delete, která obsahuje O(m) operacíInsert. IB002 Algoritmy a datové struktury I Jaro 2018 281 / 390 Hašovaní Univerzální hašování Konstrukce univerzální množiny hašovacích funkcí příklad univerzálního hašování ■ zvolíme prvočíslo p takové, že žádný klíč není větší než p ■ pro libovolná čísla a E {1,2, ...p—1} a b E {0,1,.. .p — 1} definujeme hašovací funkci předpisem habik) — ((ak + b) mod p) mod m) ■ množina funkcí T-tpm = {hab\a E {1, 2,... p — 1}, b E {0,1,.. .p - 1} je univerzálni množinou hašovacích funkcí ■ výběr prvočísla umožňuje efektivní implementaci operací mod přesné důkazy tvrzení jako i další podrobnosti týkající se univerzálního hašovaní jsou v literatuře, např v monografii T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Third Edition. MIT Press, 2009 IB002 Algoritmy a datové struktury I Jaro 2018 282 / 390 Hašovaní Otevřená adresace Otevřená adresace ■ všechny klíče ukládáme přímo do tabulky počet klíčů nemůže přesáhnout velikost tabulky ■ při vyhledávání se systematicky zkoumají pozice tabulky dokud není nalezen hledaný klíč nebo není jasné, že v tabulce není ■ nepotřebujeme seznamy a ukazatele, místo nich se počítá sekvence pozic v tabulce, které mají být prozkoumány (tzv. sondování) IB002 Algoritmy a datové struktury I Jaro 2018 283 / Hašovaní Otevřená adresace Otevřená adresace - vyhledávání ■ hašovací funkce je typu h : U x {0,1,..., m — 1} —>► {0,1,..., m — 1} ■ pro každý klíč potřebujeme posloupnost (h(k, 0), h(k, 1),... h(k, m — 1)), která je permutací posloupnosti (0,1,..., m — 1) ■ každá pozice tabulky obsahuje buď klíč, anebo hodnotu Níl ■ při hledání klíče k • proměnná zje rovna pořadovému číslu testu, iniciální hodnota i je 0 • vypočítáme hodnotu h(k,i) a testujeme obsah pozice h(k,i) • když pozice h(k,i) obsahuje klíč k, vyhledávání je úspěšné • když pozice h(k,i) obsahuje hodnotu Nil, vyhledávání je neúspěšné (tabulka neobsahuje klíč k) • když pozice h(k,i) obsahuje neprázdnou hodnotu různou od k, tak zvýšíme pořadové číslo testu a vypočítáme novou pozici v tabulce jako funkci k a pořadového čísla testu a klíč hledáme pomocí této nové hašovací funkce IB002 Algoritmy a datové struktury I Jaro 2018 284 / 390 Otevřená adresace Otevřená adresace - vkládání analogicky jako při vyhledávání najdeme volnou pozici v tabulce vkládání skončí úspěchem když je nalezena volná pozice, na kterou se klíč vloží když počet testů dosáhne m, tak vkládání končí neúspěchem IB002 Algoritmy a datové struktury I Jaro 2018 285 / 390 Hašovaní Otevřená adresace Otevřená adresace - odstranění klíče ■ vyhledáme klíč k v tabulce, nechť se nalézá na pozici j ■ může nastat situace, že po odstranění klíče k budeme v tabulce vyhledávat klíč k', který je v tabulce uložen) a v průběhu jeho vyhledávání budeme zkoumat i pozici j ■ když bychom na pozici j vložili hodnotu Nil, tak bychom při následném vyhledávání klíče k' dostali nesprávný výsledek řešení ■ místo hodnoty Nil použijeme speciální hodnotu Deleted ■ operace Insert považuje pozici s hodnotou Deleted za prázdnou ■ operace Search považuje pozici s hodnotou Deleted za obsazenou, ale obsahující jinou hodnotu než hledaný klíč IB002 Algoritmy a datové struktury I Jaro 2018 286 / 390 Otevřená adresace Otevřená adresace - výpočet sekvence sond nejčastěji se používají k výpočtu sekvence sond tři techniky ■ lineární adresace (linear probing) ■ kvadratická adresace (quadratic probing) ■ dvojité hašování (double hashing) IB002 Algoritmy a datové struktury I Jaro 2018 287 / 390 Hašovaní Otevřená adresace Otevřená adresace - lineární využívá pomocnou hašovací funkci h! : U —> {0,1,..., m — 1} h{k, i) = (h!(h) + i) mod m pro daný klíč je nejdříve prozkoumána pozice T[hf(k)], pak pozice T[h'{k) + 1].....T[m - 1] a pak zase od T[0] až k T[h'{k) - 1] problémem je tzv. primární shlukování, které může výrazně zvýšit složitost operací IB002 Algoritmy a datové struktury I Jaro 2018 288 / 390 Hašování Otevřená adresace Otevřená adresace - kvadratická využívá pomocnou hašovací funkci h' : U —> {0,1,..., m — 1} a pomocné konstanty ci, C2 ^ 0 h(k, i) = (h!(k) + c±i + C2Í2) mod m ■ pro daný klíč je nejdříve prozkoumána pozice T[hf(k)], dále pak pozice posunuta o offset závislý kvadratickým způsobem na pořadí sondy ■ kvadratická adresace je obvykle lepší než lineární ■ problémem je vhodný výběr konstant c\ a C2 a velikosti tabulky m ■ když dva klíče jsou primárně zahašovány na stejnou pozici protože h!{k\) — h!{k2), tak mají stejnou celou posloupnost sond - tzv. sekundární shlukování IB002 Algoritmy a datové struktury I Jaro 2018 289 / 390 Hašovaní Otevřená adresace Otevřená adresace - dvojité hašování využívá dvě pomocné hašovací funkce /ii,/i2 h(k,i) — (h\(k) Jrifi2{k)) mod m pro daný klíč je nejdříve prozkoumána pozice T[hi(k)], následující pozice je posunuta o offset Ii2(k) mod m hodnota /i2(fc) musí být nesoudělná s velikostí hašovací tabulky m, aby byla prohledána celá tabulka vhodnou volbou je vzít m jako mocninu 2 a navrhnout tak, že výsledkem bude vždy liché číslo, nebo zvolit m jako prvočíslo a navrhnout tak, že výsledkem bude vždy kladné číslo < m dvojité hašování je lepší než kvadratické, protože generuje 0(m2) posloupností sond místo O(m) jako kvadratická adresace IB002 Algoritmy a datové struktury I Jaro 2018 290 / 39 Hašovaní Otevřená adresace Otevřená adresace - složitost Věta 10 Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a = n j m < 1 je očekávaný počet sond při neúspěšném hledání nejvýše 1/(1 — a) a to za předpokladu uniformního basování. Věta 11 Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a — n j m < 1 je očekávaný počet sond při úspěšném hledání nejvýše ^ ln a to za předpokladu uniformního basování. uniformní hašovaní je takové, že každý klíč má jako posloupnost sond se stejnou pravděpodobností libovolnou z m\ permutací (0,1,..., m — 1 IB002 Algoritmy a datové struktury I Jaro 2018 291 / 390 Hašovaní Kukaččí hašovaní Kukaččí hašovaní (Cuckoo hashing) ■ pro hašovaní se používají dvě tabulky velkosti m a dvě hašovací funkce h\, ti2 : U —> {0,1,... m — 1} ■ každý klíč je zahašovaný buď na pozici h\[k) v první tabulce, anebo na pozici /i2(&) v druhé tabulce ■ hledání klíče má konstantní složitost, protože stačí otestovat dvě pozice ■ odstranění klíče má konstantní složitost, analogicky jako jeho hledání ■ při vkládání nového klíče k se použije hladová strategie, nejdříve se pokusíme vložit klíč k na pozici h\[k) ■ když je pozice /ii(/c)obsazena, tak klíč y uložený na pozici h\[k) přesuneme do druhé tabulky na jeho alternativní pozici /^(y) ■ proces opakujeme a přepínáme se mezi tabulkami dokud nenajdeme volnou pozici, anebo se proces zacyklí R. Pagh, F. Rodler: Cuckoo hashing. Journal ofAlgorithms 51 (2004) 122 - 144 IB002 Algoritmy a datové struktury I Jaro 2018 292 / 390 Hašovaní Dokonalé hašovaní Dokonalé hašovaní (Perfect hashing) ■ hašovaní, které má konstantní složitost i v nej horším případě ■ předpokladem je statická množina klíčů ■ využívá dvě úrovně hašovaní první úroveň v podstatě stejná, jako zřetězené hašovaní druhá úroveň ■ místo seznamů použijeme sekundární hašovací tabulky Sj s asociovanou hašovací funkcí hj, přičemž vhodným výběrem můžeme zajistit, aby na druhé úrovni nebyly žádné kolize ■ velikost rrij tabulky Sj je kvadratická vůči počtu klíčů zahašovaných na pozici j ■ hašovací funkce na první úrovni se vybírá z univerzální množiny hašovacích funkcí Hpm, na druhé úrovni z univerzální množiny T-Lprn- IB002 Algoritmy a datové struktury I Jaro 2018 293 / 390 Průzkum grafů a grafová souvislost Grafové algoritmy EE Průzkum grafů a grafová souvislost ■ Průzkum do šíTky ■ Průzkum do hloubky ■ Topologické uspořádání ■ Silně souvislé komponenty ■ Algoritmus Bellmana a Forda ■ Acyklické grafy ■ Dijkstrův algoritmus ■ Lineární nerovnice IB002 Algoritmy a datové struktury I Jaro 2018 294 / 390 Průzkum grafů a grafová souvislost Graf a jeho reprezentace ■ graf G = (V, E) • orientovaný / neorientovaný • ohodnocené hrany / vrcholy • jednoduché / násobné hrany ■ reprezentace grafů • seznam následníků • matice sousednosti ■ složitost grafových algoritmů je funkcí počtu vrcholů a hran ■ používáme zjednodušenou notaci, např. 0{V + E) IB002 Algoritmy a datové struktury I Jaro 2018 295 / 390 Matice sousednosti 1 2 3 4 1 0 1 1 0 2 1 0 1 0 3 1 1 0 1 4 0 0 1 0 1 2 3 4 1 0 1 1 0 2 0 0 0 0 3 0 1 0 0 4 0 0 1 0 matice A — (a^) rozměrů \V\ x \V\, kde (2 i j — 1 pokud (z, j) G E1 0 jinak prostorová složitost: Q(V2) vhodné pro husté grafy časová složitost výpisu všech sousedů vrcholu u je 0(V) časová složitost ověření zda (u,v) G E je 0(1) IB002 Algoritmy a datové struktury I Jaro 2018 296 / 390 Průzkum grafů a grafová souvislost Seznam následníků Adj 1 2 3 4 > 3 / > 3 / > 3 / / Adj 1 2 3 4 -> 2--> 3 / / -> 2 / -> 3 / pole Adj velikosti \V\ prostorová složitost: @(V + E) vhodné pro řídké grafy časová složitost výpisu všech sousedů vrcholu u je Q(deg[u)) (deg(u) je stupeň vrcholu u) časová složitost ověření zda (u,v) E E je 0(deg(u)) varianta použít místo pole hašovací tabulku, zřetězené hašování nahradit otevřenou adresací HUB EQ HH 91 Jaro 2018 297 / 390 IB002 Algoritmy a datové struktury I Průzkum grafů a grafová souvislost Srovnání matice soused nosti seznam následníků hašovací tabulka test {u, v} E E o(i) 0(V) 0(1) test (u, v) E E 0(i) 0(V) 0(1) seznam sousedů vrcholu v 0(V) 0(1 + deg{v)) 0(l + deg(v)) seznam hran 0(V2) O (V + E) O (V + E) přidání hrany 0(1) 0(1) 0(1)* odstranění hrany 0(1) 0(V) 0(1)* očekávaná složitost IB002 Algoritmy a datové struktury I Jaro 2018 298 / 390 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu Everything on earth can be found, if only you do not let yourself be put off searching. Philemon of Syracuse (ca. 360 BC-264 BC) pro daný graf G a vrchol s grafu je cílem • navštívit všechny vrcholy grafu dosažitelné z vrcholu s, resp. • navštívit všechny vrcholy grafu průzkum realizovat maximálně efektivně, tj. se složitostí 0(V + E) (vyhnout se opakovaným návštěvám ) jaké další informace o grafu zjistíme v průběhu průzkumu??? IB002 Algoritmy a datové struktury I Jaro 2018 299 / 390 Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šírky vs do hloubky Theseus si před bludištěm uváže jeden konec nitě na strom a vsoupí dovnitř. V prvním vrcholu (křižovatce) si vybere jednu možnou cestu / hranu a projde po ní do dalšího vrcholu. Aby Theseus neměl zmatek v tom, které hrany už prošel, tak si všechny hrany, které prochází označuje křídou - a to na obou koncích. V každém vrcholu, do kterého Theseus dorazí, provede následující: ■ Pokud na zemi najde položenou nit, tak ví, že už ve vrcholu byl a že se do něj při namotávání nitě zase vrátí. Odloží tedy další prozkoumávání tohoto vrcholu na později, provede čelem vzad a začne namotávat nit na klubko. To ho dovede zpátky do předchozího vrcholu. ■ Pokud na zemi žádnou nit nenajde, tak se vydá první možnou neprošlou hranou. Pokud by taková hrana neexistovala, tak je vrchol zcela prozkoumán. V tom případě Theseus neztrácí čas a začne namotávat nit na klubko. Tím se dostane zpátky do předchozího vrcholu. Tímto postupem prozkoumá celé bludiště a nakonec se vrátí do výchozího vrcholu.6 Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka HUB EQ HH 91 Jaro 2018 300 / 390 IB002 Algoritmy a datové struktury I Průzkum grafu do šírky vs do hloubky implementace křída proměnná označující jestli jsme hranu prošli klubko položená niť vyznačuje cestu z výchozího do aktuálního vrcholu, cestu si pamatujeme jako posloupnost vrcholů na této cestě. Pro uložení cesty použijeme zásobník. Odmotávání nitě odpovídá přidání vrcholu do zásobníka. Namotávání nitě při návratu zpět odpovídá odebrání vrcholu ze zásobníku. IB002 Algoritmy a datové struktury I Jaro 2018 301 / 39 Průzkum grafu do šírky vs do hloubky Tento průchod (prohledánígrafu) si můžeme představit tak, že se do výchozího vrcholu postaví miliarda trpaslíků a všichni naráz začnou prohledávat graf Když se cesta rozdělí, tak se rozdělí i dav řítící se hranou. Předpokládáme, že všechny hrany jsou stejně dlouhé. Graf prozkoumáváme „po vlnách''. V první vlně se všichni trpaslíci dostanou do vrcholů, dokterých vede z výchozího vrcholu hrana. V druhé vlně se dostanou do vrcholů, které jsou ve vzdálenosti 2 od výchozího vrcholu. Podobně v k-té vlně se všichni trpaslíci dostanou do vrcholů ve vzdálenosti k od výchozího vrcholu. Kvůli těmto vlnám se někdy průchodu do šířky říka algoritmus vlny. 7 implementace V počítači vlny nasimulujeme tak, že při vstupu do nového vrcholu uložíme všechny s ním sousedící vrcholy do fronty. Frontu průběžně zpracováváme. Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka HUB EQ HH 91 Jaro 2018 302 / 390 IB002 Algoritmy a datové struktury I Průzkum grafů a grafová souvislost Průzkum grafu Průzkum grafu do šířky a do hloubky průzkum grafu do šířky vs do hloubky se liší pouze použitím fronty a zásobníku NE IB002 Algoritmy a datové struktury I Jaro 2018 303 / 390 Průzkum do sirky - strategie cílem je prozkoumat všechny vrcholy dosažitelné z daného iniciálního vrcholu s ■ postupujeme od iniciálního vrcholu s po vrstvách ■ nejdříve prozkoumáme všechny vrcholy dosažitelné z s po 1 hraně ■ pak všechny vrcholy dosažitelné po 2 hranách, po 3 hranách atd. ■ pro manipulaci s vrcholy používáme prioritní frontu Q ■ v £ Q právě když byl dosažen (objeven) ale ještě nebyl prozkoumán IB002 Algoritmy a datové struktury I Jaro 2018 304 / 39 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do sirky - příklad Q: S Q: AD Q: DC Q: CBE C D Q: BE C D Q: E C D Q: 0 IB002 Algoritmy a datové struktury I Jaro 2018 305 / 390 Průzkum do sirky - atributy vrcholu v.color ■ v průběhu výpočtu je vrchol postupně objeven (je zařazen do fronty) a prozkoumán (všechny sousedící vrcholy jsou objeveny) ■ vrchol má černou barvu právě když je dosažitelný z iniciálního vrcholu a byl již prozkoumán ■ vrchol má šedivou barvu právě když je dosažitelný z iniciálního vrcholu, byl již objeven, ale nebyl ještě prozkoumán ■ vrchol má bílou barvu právě když není dosažitelný z iniciálního vrcholu anebo ještě nebyl objeven v.7t ■ vrchol, ze kterého byl v objeven v.d ■ délka (počet hran) cesty z s do v, na které byl v objeven (= délka nej kratší cesty z s do v ) IB002 Algoritmy a datové struktury I Jaro 2018 306 / 39 Průzkum grafů a grafová souvislost Průzkum do šířky Průzkum do sirky - implementace BFS(G,s) 1 foreach u £ V \ {s} 2 do u.color white] u.d oo; u.tt 3 s.color gray] s.d 0; s.tt Nil 4 Q^tt 5 Enqueue(Q, s) 6 while Q ŕ 0 do 7 8 9 10 11 12 13 U 15 od Nil od u <— Dequeue(Q) foreach v G Ad; [m] do if v.color — white then v.color gray i?.d u.d + 1 i;.7T u Enqueue(Q, v) fi u.color 6/acA: od IB002 Algoritmy a datové struktury I Jaro 2018 307 / 39C BFS - kompaktní verze BFS(G,s) 1 foreach wGľ \ {s} 2 do u.d 1 vrcholy najdi vrchol v, do kterého nevstupuje žádná hrana (kdyby takový neexistoval, tak bychom mohli z libovolného vrcholu jít donekonečna „pozpátku'' a našli bychom cyklus) ■ G — v je acyklický (odstranění vrcholu nemůže způsobit vznik cyklu) ■ z indukčního předpokladu G — v má topologické uspořádání ■ topologické uspořádání pro G má na prvním místě v následované uspořádáním pro G — v IB002 Algoritmy a datové struktury I Jaro 2018 333 / 390 Průzkum grafů a grafová souvislost Topologické uspořádání Topologické uspořádání - naivní algoritmus Topological_Sort_Visit(G) 1 n <- | V 2 for i = 1 to n do 3 v <(— libovolný vrchol, do kterého nevstupuje žádná hrana S v 5 odstraň z G vrchol v a všechny jeho hrany 6 od 7 return S\l... n ■ algoritmus pro acyklický graf ■ nalezení vrcholu do kterého nevstupuje žádná hrana má složitost ??? ■ celková složitost algoritmu je ??? ■ existuje efektivnější algoritmus (ideálně s lineární složitostí)??? ■ symetricky se dá postupovat podle vrcholů z nichž nevychází žádná hrana 2g wm 22 O jar°2018 334 /390 IB002 Algoritmy a datové struktury I Průzkum grafů a grafová souvislost Topologické uspořádání Acyklický graf - testování Lema 15 Orientovaný graf G je acyklický právě když DFS průzkum grafu neoznačí žádnou hranu jako zpětnou. Důkaz ^> zpětná hrana (u,v) spojuje vrchol u s jeho předchůdcem v v DFS stromu, tj. uzavírá cyklus <= ■ nechť v grafu existuje cyklus c, nechť v je první vrchol cyklu c navštívený při DFS průzkumu grafu a nechť (u,v) je hrana cyklu c ■ v čase v.d vrcholy cesty c tvoří bílou cestu z v do u co implikuje, že u je následníkem v v DFS stromu ■ (u,v) je zpětná hrana IB002 Algoritmy a datové struktury I Jaro 2018 335 / 390 Průzkum grafů a grafová souvislost Topologické uspořádání Topologické uspořádání - algoritmus □ aplikuj DFS na G B když průzkum označí některou hranu jako zpětnou, tak graf nemá topologické uspořádání Q v opačném případě vypiš vrcholy v uspořádání reverse postorder, tj. podle značky ./ (finishing time) v klesajícím pořadí IB002 Algoritmy a datové struktury I Jaro 2018 336 / 390 Průzkum grafů a grafová souvislost Topologické uspořádání Korektnost potřebujeme dokázat, že pro libovolnou dvojici vrcholů u,v platí jestliže G obsahuje hranu (u,v), tak u.f > v. f jaké jsou barvy vrcholů u a v při průzkumu hrany (u,v)l ■ u je šedivý m v je šedivý nemůže nastat, protože (u,v) by v takovém případě byla zpětnou hranou a graf by nebyl acyklický bílý v takovém případě je (u,v) stromová hrana, v je následníkem u v DFS stromu a u.d < v.d < v.f < u.f černý v takovém případě je průzkum vrcholu v ukončený a průzkum vrcholu u ještě není ukončený a proto v.f < u.f IB002 Algoritmy a datové struktury I Jaro 2018 337 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Souvislost v orientovaném grafu orientovaný graf G — (V, E) ■ vrchol v je dosažitelný z vrcholu u, značíme u v, právě když v G existuje orientovaná cesta z u do v ■ Reach(u) je množina všech vrcholů dosažitelných z ■ vrcholy u b v jsou silně dosažitelné (strongly connected) právě když u je dosažitelný zua současně v je dosažitelný z ^ ■ silná dosažitelnost - relace ekvivalence ■ silně souvislá komponenta grafu je třída ekvivalence relace silné dosažitelnosti, tj. maximální množina vrcholů C C V taková, že pro každé u,v G C platí u v a současně v ^ u ■ graf nazýváme silně souvislý právě když má jedinou silně souvislou komponentu problém najít všechny silně souvislé komponenty grafu IB002 Algoritmy a datové struktury I Jaro 2018 338 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Souvislost v neorientovaném grafu v neorientovaném grafu jsou pojmy dosažitelnosti a silné dosažitelnost totožné pro hledání silně souvislé komponenty grafu můžeme použít BFS nebo DFS jednotlivé DFS (BFS) stromy korespondují s komponentami souvislosti složitost O (V + E) IB002 Algoritmy a datové struktury I Jaro 2018 339 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Silně souvislé komponenty v orientovaném grafu výpočet silně souvislé komponenty obsahující daný vrchol u ■ najdi množinu Reach(u) všech vrcholů dosažitelných z u aplikací DFS_Visit(G>) ■ najdi množinu Reach~ľ(u) všech vrcholů, ze kterých je dosažitelný u ■ pro výpočet Reach~ľ(u) využijeme transponovaný graf8 rev(G), na který aplikujeme DFS_Visrr(re?;(G), u) ■ silně souvislá komponenta obsahující u je průnikem Reach(u) H Reach~ľ(u) m časová složitost výpočtu je 0(V + E) 8transponovaný graf rev(G) = (V, rev(E)) je graf G s obrácenou orientací hran, rev(E) = {(x,y) | (y,x) G E} IB002 Algoritmy a datové struktury I Jaro 2018 340 / 39 Průzkum grafů a grafová souvislost Silně souvislé komponenty Silně souvislé komponenty v orientovaném grafu výpočet všech silně souvislých komponent grafu ■ můžeme zabalit popsaný postup (podobně jako je DFS_Visit(G, u) zabalené do DFS) ■ v nejhorším případě má graf \V\ komponent souvislosti a detekce každé z nich má časovou složitost O(E) ■ celková časová složitost výpočtu je O (V • E) ■ existuje efektivnější algoritmus, optimálně s lineární časovou složitostí ??? ■ motivace: v čase 0(V + E) dokážeme rozhodnout, zda všechny silně souvislé komponenty grafu jsou jednoduché (obsahují pouze jeden vrchol) IB002 Algoritmy a datové struktury I Jaro 2018 341 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf ■ komponentový graf (aka graf silně souvislých komponent) je orientovaný graf, který vznikne kontrakcí každé silně souvislé komponenty grafu do jednoho vrcholu a kontrakcí paralelních hran do jedné hrany, značíme scc{G) ■ scc(G) je orientovaný acyklický graf ■ vrcholy scc(G) můžeme topologicky uspořádat ■ listová komponenta == list grafu scc(G) ■ kořenová komponenta == kořen grafu scc{G) ■ platí rev(scc(G)) = scc{rev(G)) IB002 Algoritmy a datové struktury I Jaro 2018 342 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Příklad kořenová komponenta A listové komponenty D, CF, GHIJK IB002 Algoritmy a datové struktury I Jaro 2018 343 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf ■ listová komponenta grafu = list grafu scc(G) ■ z každého vrcholu u listové komponenty C jsou dosažitelné všechny vrcholy C, tj. DFS průzkum z u navštíví všechny vrcholy z C ■ naopak, z vrcholu u není dosažitelný žádný vrchol nepatřící do C (C je listová komponenta!!), tj . DFS průzkum z u navštíví pouze všechny vrcholy z C ■ na tomto pozorování můžeme postavit algoritmus pro detekci komponent Strong_Components(G) 1 count 0 2 while G není prázdný do 3 count count + 1 4 v <(— libovolný vrchol z listové komponenty 5 C <— One_Component(í;, count) 6 odstraň z grafu G vrcholy z C a hrany vstupující do C od potřebujeme (efektivně) najít vrchol patřící listové komponentě IB002 Algoritmy a datové struktury I Jaro 2018 344 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf ■ potřebujeme (efektivně) najít vrchol patřící listové komponentě ■ umíme (efektivně) najít vrchol patřící kořenové komponentě Věta 16 Vrchol s nejvyšší časovou značkou ./ leží v kořenové komponentě. Důkaz tvrzení je důsledkem následujícího obecnějšího tvrzení IB002 Algoritmy a datové struktury I Jaro 2018 345 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Komponentový graf Věta 17 Necht Ci a C2 jsou silně souvislé komponenty takové, že z C\ vede hrana do C2-Potom největší hodnota .f v komponentě C\ je větší než největší hodnota .f v komponentě C2. Důkaz mohou nastat dva případy ■ v prvním případě navštíví DFS komponentu C2 jako první; pak ale DFS zůstane v komponentě C2 dokud ji celou neprozkoumá, teprve pak se dostane do d ■ v druhém případě navštíví DFS komponentu C\ jako první; nechť v je vrchol, který byl v C\ navštíven jako první; DFS opustí vrchol v, až když prozkoumá všechny vrcholy, které jsou z v dosažitelné a které dosud nebyly navštíveny; proto nejprve projde celou komponentu C2 a pad se teprve naposledy vrátí do v IB002 Algoritmy a datové struktury I Jaro 2018 346 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Algoritmus pro detekci silně souvislých komponent v lineárním čase ■ Robert Tarjan, 1972 ■ Harold Gabow, 2000 ■ Rao Kosaraju, 1978; Micha Sharir, 1981 ■ vrcholy grafu uspořádej v obráceném postorder pořadí, tj. podle značky ./ v klesajícím pořadí ■ proveď DFS průzkum z vrcholů v daném pořadí IB002 Algoritmy a datové struktury I Jaro 2018 347 / 390 Průzkum grafů a grafová souvislost Silně souvislé komponenty Kosaraju_Sharir(G) 1 foreach u G V do u.color white od 2 foreach u G do if u.color = white then Push_DFS(G, fi od 5 foreach ^ G V do u.color white od 4 count 0 5 while S ^ 0 do £ u S.popQ 7 if u.color — white then count count + 1 8 Label_One_DFS(Rev(G), u, count) fi od Push_DFS(G» i u.color gray £ foreach i; G Adj[u do s if v.color = white then Push_DFS(G, fi od 4 u.color black; Label_DFS(G, count) i u.color gray £ foreach i; G Adj[u do 3 if v.color = white then Label_DFS(G, i;, count) fi od 4 u.color black; u.label count IB002 Algoritmy a datové struktury I Jaro 2018 348 / 39 N ej kratší cesty Grafové algoritmy EE Průzkum grafu a grafová souvislost ■ Průzkum do šírky ■ Průzkum do hloubky ■ Topologické uspořádání ■ Silně souvislé komponenty El Nejkratší cesty ■ Algoritmus Bellmana a Forda ■ Acyklické grafy ■ Dijkstrův algoritmus ■ Lineární nerovnice IB002 Algoritmy a datové struktury I Jaro 2018 349 / 390 N ej kratší cesty Cesta v grafu cesta v grafu G — (V, E) je posloupnost vrcholů p — (vo, ..., Vk) taková, že (vi-i, Vi) G E pro i = 1,..., k jednoduchá cesta je cesta, která neobsahuje dva stejné vrcholy terminologie cesta jednoduchá cesta path simple path walk path sled cesta p = (vq, vi, ..., je cestou z vrcholu u do vrcholu v právě když vo = u a Vk = v v je dosažitelný z u, u v IB002 Algoritmy a datové struktury I Jaro 2018 350 / 39C Formulace problému nej kratších cest Délka cesty graf G — (V, E), váhová funkce (ohodnocení, délka hran) w : E —)► M délka cesty p — (vq, vi, ..., Vk) je součet délek hran cesty k i=l délka nejkratší cesty z vrcholu u do vrcholu v je definovaná předpisem nejkratší cesta z vrcholu u do vrcholu v je libovolná cesta p z ^ do i; pro kte w(p) — S(u, v) pro neohodnocené grafy se délka cesty definuje jako počet hran cesty Jaro 2018 N ej kratší cesty Varianty problému nejkratší cesty nejkratší cesty z daného vrcholu do všech vrcholů single source shortest path, SSSP tato přednáška nejkratší cesty ze všech vrcholů do daného vrcholu pro neorientované grafy totožné s SSSP pro orientované grafy redukce na SSSP změnou orientace hran nejkratší cesta mezi danou dvojicí vrcholů speciální případ SSSP, nejsou známy asymptoticky rychlejší algoritmy než pro SSSP tato přednáška nejkratší cesty mezi všemi dvojicemi vrcholů řešení opakovanou aplikací algoritmu pro SSSP existují efektivnější algoritmy ADS II nejdelší, nejširší, nejspolehlivější ... cesty viz literatura IB002 Algoritmy a datové struktury I Jaro 2018 352 / 390 N ej kratší cesty Algoritmy pro SSSP orientované grafy neohodnocený graf průzkum do šírky, BFS acyklický graf průzkum do hloubky tato přednáška graf s nezáporným ohodnocením hran Dijkstrův algoritmus a jiné tato přednáška obecný graf algoritmus Bellmana Forda a jiné tato přednáška IB002 Algoritmy a datové struktury I Jaro 2018 353 / 39 N ej kratší cesty Algoritmy pro SSSP neorientované grafy neohodnocený graf ■ průzkum do šírky, BFS graf s nezáporným ohodnocením hran ■ hranu nahradíme dvojici orientovaný hran a převedeme na úlohu v orientovaném grafu obecný graf ■ nahrazením hrany se záporným ohodnocením dvojicí orientovaných hran vznikne cyklus záporné délky ■ pokud původní graf obsahuje hrany záporné délky, ale žádný cyklus záporné délky, lze takovou úlohu převést na hledání nej levnějšího perfektního párování ■ když obsahuje cyklus záporné délky, problém je NP-těžký a umíme ho řešit pouze algoritmy exponenciální složitosti ■ viz literatura IB002 Algoritmy a datové struktury I Jaro 2018 354 / 39C N ej kratší cesty Nejkratší cesta vs nejkratší jednoduchá cesta graf neobsahuje hrany záporné délky jestliže mezi dvojicí vrcholů existuje cesta, tak mezi nima existuje taková nejkratší cesta, která je jednoduchá nechť p je nejkratší cesta, která není jednoduchá, tj. obsahuje cyklus ■ cyklus nemůže mít zápornou délku (spor s předpokladem neexistence hran záporné délky) ■ cyklus nemůže mít kladnou délku (spor s předpokladem, že cesta je nejkratší) ■ cyklus má nulovou délku - cyklus můžeme z cesty vypustit a dostaneme jednoduchou nejkratší cestu IB002 Algoritmy a datové struktury I Jaro 2018 355 / 390 N ej kratší cesty Nejkratší cesta vs nejkratší jednoduchá cesta graf obsahuje hrany záporné délky ■ cyklus {b, c, d, b) má délku -2 ■ jestliže nějaká cesta z x do y obsahuje cyklus záporné délky, tak žádná cesta z x do y nemůže být nejkratší cestou, ô(x,y) — —oo v případě, že graf obsahuje hrany se zápornou délkou, problém nejkratší cesty je formulovaný jako 1. rozhodni, zda graf obsahuje cyklus záporné délky 2. když ne, tak najdi nejkratší (jednoduché) cesty IB002 Algoritmy a datové struktury I Jaro 2018 356 / 39 N ej kratší cesty Formulace problému nej kratších cest Struktura nejkratších cest Lemma 18 Každá podcesta nej kratší cesty je nej kratší cestou. ■ nechť p je nej kratší cesta z u do v W(P) W(PUX) + W(pxy) + W(Pyy) Pux Pxy Pyv předpokládejme, že existuje kratší cesta z x do y, w(p'xy) < w(pxy) zkonstruujeme novou cestu p — u ^ x ^ y v W(p) W{pux) + W(pxy) + W(pyv) < w(Pux) + ^faxy) + w(Pyv) — w(p) což je spor s předpokladem, že p je nejkratší cesta z u do v Pxy Pyv IB002 Algoritmy a datové struktury I Jaro 2018 357 / 390 N ej kratší cesty Generický SSSP algoritmus Reprezentace nejkratších cest strom nejkratších cest pozor na rozdíl mezi stromem nejkratších cest a nej levnější kostrou grafu IB002 Algoritmy a datové struktury I Jaro 2018 358 / 390 N ej kratší cesty Generický SSSP algoritmus Reprezentace stromu nejkratších cest z vrcholu s atribut vzdálenost distance, v.d • iniciální nastavení v.d = oo • hodnota v.d se v průběhu výpočtu snižuje • hodnota v.d je horním odhadem délky nej kratší cesty, v.d > S(s,v) • na konci výpočtu je v.d — ô(s, v) atribut předchůdce parent, v.tt • iniciální nastavení v.tv = Nil • vrchol v.tv je předchůdcem vrcholu v na cestě z s do v délky v.d • na konci výpočtu je v.tt předchůdce vrcholu v na nejkratší cestě z s do v, resp. v.tt — Nil když neexistuje cesta z s do v graf předchůdců Gp = (VpiEp) je definovaný hodnotami .tt Vp = {v G V | v.tt ^ Nil} U {s} Ep = {(v.tt, v) \v © © 3 >© Relax Relax ©-Kz) ©-KD ■ hranu (u,v) nazýváme napjatou právě když u.d + w(u,v) < v.d IB002 Algoritmy a datové struktury I Jaro 2018 360 / 39 N ej kratší cesty Generický SSSP algoritmus Generický SSSP algoritmus lnit_SSSP(G,s) 1 foreach v E V do v.d oo; v.tt Nil od 2 s.d u.d + w(u, v) 7 then Relax(í/, v, w) 8 S * • • • —>* v.7t.7t —>* v.7t —>* v ■ když žádná hrana grafu není napjatá, tak cesta s —)►••• v.tt.tt —>► v.tt —>► v je nejkratší cestou z s do v důkaz indukcí na počet relaxací důsledek: když výpočet generického algoritmu skončí, tak Gp je strom nej kratších cest IB002 Algoritmy a datové struktury I Jaro 2018 362 / 390 N ej kratší cesty Generický SSSP algoritmus Složitost generického SSSP algoritmu závisí od toho ■ jakou datovou strukturu použijeme pro reprezentaci množiny S obsahující vrcholy určené k prozkoumání (tj. vrcholy, u kterých byla změněna hodnota .ď) ■ v jakém pořadí budeme prozkoumávat vrcholy z množiny S IB002 Algoritmy a datové struktury I Jaro 2018 363 / 390 N ej kratší cesty Bellmanův - Ford ú v algoritmus Bellman-Ford(G, w, s) 1 Init_SSSP(G,s) 2 for i = 1 to \V\ — 1 do s foreach (u, v) G E do 4 if v.d > u.d + w{u, v) then Relax(i/, i;, u>) fi 5 od 6 od 7 foreach (u, v) E E do 8 if v.d > u.d + 1^(1/, v) then return False fi 9 od 10 return True optimalizace: výpočet můžeme ukončit, jestliže v iteraci for cyklu v rádcích 2-6 nebyla nalezena žádná napjatá hrana IB002 Algoritmy a datové struktury I Jaro 2018 364 / 390 a q 2 (a) N ej kratší cesty Algoritmus Bellmana a Forda (b) (c) a © 2 graf G p 2 (d) (e) výpočet algoritmu Bellman-Ford, hledáme nejkratší cesty z vrcholu a v každé iteraci cyklu 2-6 relaxujeme hrany v pořadí (c, e), (d, e), (6, d), (c, d), (6, c), (a,c), (a, 6) barevně jsou vyznačeny hrany grafu předchůdců Gp IB002 Algoritmy a datové struktury I Jaro 2018 365 / 390 N ej kratší cesty Korektnost 1 Lema 19 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak po \V\ — 1 iteracích cyklu 3-5 pro všechny vrcholy v platí v.d = ô(s, v). nechť v je dosažitelný z s a nechť p = (vq, .. cesta z s do v (vq = s, vj~ — v) protože cesta p neobsahuje cyklus, má nanejvýš \V v každé iteraci cyklu se relaxují všechny hrany grafu, speciálně • v první iterace se relaxuje hrana (vo,vi) • v druhé iteraci se relaxuje hrana (^1,^2) Vk) je nejkratší jednoduchá 1 hran, tj. k < \V\ - 1 • v k-té iteraci se relaxuje hrana (vk-i,Vk) indukcí ověříme, že po z-té iteraci platí Vi.d — ô(s, vi) IB002 Algoritmy a datové struktury I Jaro 2018 366 / 390 N ej kratší cesty Korektnost 2 Lema 20 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vráti hodnotu True. ■ po ukončení výpočtu platí pro každou hranu (u, v) G E v.d = S(s,v) < ô(s, u) + w{u, v) — u.d + w(u,v) m žádná hrana není napjatá a test na řádku 8 nevrátí hodnotu False IB002 Algoritmy a datové struktury I Jaro 2018 367 / 390 N ej kratší cesty Algoritmus Bellmana a Forda Korektnost 3 Lema 21 Když graf G obsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vráti hodnotu False. ■ nechť c = (vq, ..., Vk), vq = vj~ je cyklus záporné délky dosažitelný z s, E;=i w(vi-UVi) < 0 ■ předpokládejme, že algoritmus vráti hodnotu True, tj. pro každou hranu cyklu platí Vi.d < V{-\.d + w(ví-i, vi) ■ sumací přes všechny vrcholy cyklu k k U Vi) i=l i=l i=l i=l m každý vrchol se vyskytuje právě jednou v součtech Yl k i=i Vi-i.d a J2i=i vi-d k k k i=l i=l ■ spor s předpokladem o délce cyklu c Jaro 2018 368 / 390 N ej kratší cesty Složitost složitost algoritmu Bellmana a Forda ■ inicializace má složitost Q (V) ■ relaxace hrany má konstantní složitost ■ cyklus 3 - 5 má složitost Q (E); počet jeho opakování je V — 1 ■ celková složitost je OiVE) jiný zápis: 0(mn), kde n je počet vrcholů a m je počet hran grafu existuje efektivnější řešení? ne lehce najdeme graf a takové pořadí relaxace jeho hran, pro které je nutných V — 1 iterací 111 otázka vhodného pořadí relaxace hran ano vhodné pořadí hran dokážeme určit pro speciální typy grafů • acyklické grafy • grafy bez záporných hran IB002 Algoritmy a datové struktury I Jaro 2018 369 / 390 N ej kratší cesty Acyklické grafy Nejkratší cesty v orientovaném acyklickém grafu ■ optimálně pořadí relaxace hran v Bellmanově - Fordově algoritmu je takové, že vždy relaxujeme hranu (u,v) pro kterou u.d — ô(s,u) ■ pro obecný graf určit pořadí relaxací tak, aby byla dodržena uvedená podmínka, může být stejně náročné jako vypočíst nejkratší cesty ■ speciálně pro acyklické grafy se toto pořadí dá vypočíst jednoduše: požadovanou vlastnost má topologické uspořádání vrcholů grafu A u.d + w{u, v) then Relax(i/, v, w ) « 6 od 7 od ■ časová složitost Q(V + E) ■ topologické uspořádání garantuje, že hrany každé cesty jsou relaxované v pořadí, v jakém se vyskytují na cestě IB002 Algoritmy a datové struktury I Jaro 2018 371 / 390 Dijkstrův algoritmus ■ pro reprezentaci množiny vrcholů určených k prozkoumání využívá prioritní frontu, kde priorita vrcholu v je určena hodnotou v.d ■ Dijkstrův algoritmus můžeme nahlížet i jako efektivní implementaci prohledávání grafu do šířky, na rozdíl od BFS neukládáme vrcholy, které mají být prozkoumané, do fronty, ale do prioritní fronty ■ řeší problém SSSP pro grafy s nezáporným ohodnocením hran IB002 Algoritmy a datové struktury I Jaro 2018 372 / 390 N ej kratší cesty Dijkstrův algoritmus Dijkstrův algoritmus Dijkstra(G, w, s) 1 Init_SSSP(G,s) 2 S ^0 3 Q 4r- V 4 while Q ^ 0 do 5 u f- Extract_Min((5) 6 S^Su{u} 7 foreach (u, v) g E do 8 if v.d > u.d + w(u, v) then Relax(í/, v, w) fi 9 od i o od ■ algoritmus udržuje dvě množiny S vrcholy, pro které je již vypočtena délka nej kratší cesty Q prioritní fronta, Q = V \ S ■ algoritmus vybírá vrchol u £ Q s nejmenší hodnotou u.d a relaxuje hrany vycházející z u IB002 Algoritmy a datové struktury I Jaro 2018 373 / 390 N ej kratší cesty Dijkstrův algoritmus Dijkstrúv algoritmus - príklad vrcholy se přidávají do množiny S v pořadí s, y, z, x IB002 Algoritmy a datové struktury I Korektnost Lema 22 (Invariant cyklu while) Na začátku iterace while cyklu platí v.d — ô(s, v) pro všechny vrcholy v G S. Inicializace na začátku S — 0 a tvrzení platí triviálně Ukončení na konci Q = 0, tj. S = V a v.d = v) pro všechny i; G V Iterace potřebujeme prokázat, že když ^ přesuneme do S, tak i/.d = S(u.s) ■ když i/ není dosažitelný z 5 tak tvrzení platí protože u.d — ô(s, u) — oo ■ v opačném případě nechť p je nejkratší cesta z s do u\ cestu p můžeme dekomponovat na dvě cesty s x —)► y ^ tak, že bezprostředně před zařazením ^ do 5 všechny vrcholy cesty pi patří do 5 a y ^ 5 ■ x G £ x.d = x) ■ při zařazení x do 5 byla relaxovaná hrana (x, y)) a 5 % x —)► y je nejkratší cesta do y =^> y.d = ô(s, y) ■ hrany mají nezápornou délku =^> ô(s,y) < ô(s,u) ■ v dané iteraci jsme vybrali vrchol u =^> u.d < y.d ■ spojením dostáváme u.d < y.d — ô(s, y) < ô(s, u) =^> u.d < ô(s, u) IB002 Algoritmy a datové struktury I Jaro 2018 375 / 39 N ej kratší cesty Dijkstrův algoritmus Složitost Dijkstrova algoritmu Q (V) operací Insert (do fronty přidá nový objekt) Q(V) operací Extract_Min (z fronty odstraní objekt s minimálním klíčem) Q (E) operací DecreaseJKey (objektu ve frontě sníží hodnotu klíče) složitost algoritmu závisí od způsobu implementace prioritní fronty Q pole složitost Q(V -V + E - í) = Q(V2) Insert má složitost 6(1) Extract_Min má složitost 6(V) DecreaseJKey má složitost 6(1) binární halda složitost 6(V log V + E log V) Insert má složitost Q (log V) Extract_Min má složitost Q (log V) DecreaseJKey má složitost Q (log V) Fibonacciho halda složitost 6(VlogV + E) Insert má složitost 6(1) Extract JVIin má složitost Q (log V) Decrease_Key má složitost 6(1) IB002 Algoritmy a datové struktury I Jaro 2018 376 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy s a t optimalizace 1 ■ výpočet ukončíme když vrchol t odebereme z prioritní fronty IB002 Algoritmy a datové struktury I Jaro 2018 377 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy s a t optimalizace 2 - dvousměrné hledání (bidirectional search) ■ současně spouštíme (dopředný) výpočet Dijkstrova algoritmu z vrcholu s a (zpětný) výpočet z vrcholu t, vždy jednu iteraci každého výpočtu ■ dopředný výpočet používá frontu Q f a přiřazuje vrcholům hodnoty .df a .717, zpětný frontu Qt a přiřazuje hodnoty .db a .vr^ ■ výpočet ukončíme když nějaký vrchol w je odstraněn z obou front QfaQb ■ po ukončení najdeme vrchol x s minimální hodnotou x.df + x.d^ (pozor, nemusí to být vrchol w) ■ využitím atributů .717 a .71-5 najdeme nejkratší cestu z s do x a nejkratší cestu z x do t\ jejich spojením dostaneme nejkratší cestu zsdot IB002 Algoritmy a datové struktury I Jaro 2018 378 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Optimalizace Dijkstrova algoritmu pro hledání nejkratší cesty mezi dvěma vrcholy s a t optimalizace 3 - heuristika A* ■ pokud bychom dovedli spolehlivě zjistit, že nejkratší cesta z s do t nepovede přes vrchol v, mohli bychom zpracování vrcholu v a hran s ním incidentních přeskočit pracovali bychom s menší grafem, a tedy rychleji ■ jestliže dva vrcholy jsou stejně daleko od s, chceme při průzkumu preferovat ten, který je blíže k cílovému vrcholu t ■ pro odhad preferencí používáme ohodnocení vrcholů - potenciál h : V —>* M ■ Dijkstrův algoritmus s heuristikou se od klasického liší v tom, že při výběru vrcholu z prioritní fronty vybíráme vrchol s nejnižší hodnotou v.d + h{v) ■ jak volit potenciál a proč může urychlit výpočet? IB002 Algoritmy a datové struktury I Jaro 2018 379 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Heuristika A* - přípustný potenciál Potenciál je přípustný právě když pro každou hranu (u,v) £ E splňuje podmínku h{u) < w(u, v) + h{y) a pro vrchol t platí h[t) — 0. ■ pro libovolnou cestu p = (vq = u, v\,..., Vk = t) z u do t b přípustný potenciál platí k-l > h(v0) - h(vi) + h(vi) - h(v2) + ... + h{yk-i) - h(vk) — h{u) — h{t) — h{u) t.j. potenciál vrcholu u je dolním odhadem délky cesty z u do t IB002 Algoritmy a datové struktury I Jaro 2018 380 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Heuristika A* - úprava ohodnocení grafu pomoci potenciálu vytvoríme nové ohodnocení grafu w : E —>* M, které definujeme jako w'(u, v) — w{u, v) — h{u) + h{v) když h je přípustný potenciál, tak pro nové ohodnocení grafu a pro každou hranu grafu platí w'(u, v) > 0 t.j. pro výpočet nejkratších cest můžeme použít Dijkstrův algoritmus nové ohodnocení w' nemění nejkratší cesty, protože pro každou cestu p z s do t platí wř(p) — w(p) + h{t) — h(s) a potenciálový rozdíl medzi s a t je pro všechny cesty zsdot stejný IB002 Algoritmy a datové struktury I Jaro 2018 381 / 390 N ej kratší cesty Nejkratší cesta mezi dvěma vrcholy Heuristika A* - úprava ohodnocení grafu pomoci potenciálu ■ aby hodnoty h měly příznivý vliv na rychlost výpočtu, měli by hodnoty h(v) být dolním odhadem vzdálenosti z vrcholu v do cílového vrcholu t\ čím je odhad přesnější, tím je výpočet rychlejší ■ Dijkstrův algoritmus s heuristikou se od klasického liší v tom, že při výběru vrcholu z prioritní fronty vybíráme vrchol s nejnižší hodnotou v.d + h{v) ■ za předpokladu, že ohodnocení vrcholů h splňuje pro všechny hrany (x,y) grafu podmínku w(x,y) > h(x) — h(y), Dijkstrův algoritmus s heuristikou je korektní důkaz probíhá analogicky jako pro Dijkstrův algoritmus IB002 Algoritmy a datové struktury I Jaro 2018 382 / 390 N ej kratší cesty Dijkstrův algoritmus a obecné grafy graf se záporně ohodnocenými hranami ale bez cyklů záporné délky ■ algoritmus najde korektní řešení (po každé změně hodnoty u.d vrátime vrchol u do fronty) ■ složitost výpočtu může být až exponenciální vůči velikosti grafu ■ v praxi někdy rychlejší než algoritmus Bellmana a Forda graf s cykly záporné délky ■ výpočet algoritmu není konečný IB002 Algoritmy a datové struktury I Jaro 2018 383 / 390 N ej kratší cesty Lineární nerovnice Úloha lineárního programování pro danou m x n matici A a vektory b — (bi,..., bm) a c — (ci,..., cn) najít vektor x — (xi,... ,xn) G W1, který optimalizuje hodnotu účelové funkce Yľi=i cixí P^' splnenľ ohraničení Ax < b příklad minimalizovat — 2xi — 3x2 — X3 při splnění ohraničení —xi — X2 — x% < 3 3xi + 4x2 - 2x3 < 10 2xi - 4x2 < 2 4xi — X2 + x3 < 0 ^1,^2,^3 > 0 přípustné řešení (0, 0, 0) optimální řešení (0, 5, 5) IB002 Algoritmy a datové struktury I Jaro 2018 384 / 390 N ej kratší cesty Lineární nerovnice Úloha lineárního programování význam • mnoho problémů dokážeme vyjádřit jako úlohu lineárního programování (např. problém nej kratší cesty) • pro řešení těchto problémů potom stačí použít algoritmus pro řešení úlohy lineárního programování 9 algoritmická složitost • existují polynomiální algoritmy pro řešení úlohy lineárního programování • pro řešení speciálních případů úlohy lineárního programování existují mnohem rychlejší algoritmy • problém lineárních ohraničení je příkladem takovéto speciální úlohy • ukážeme postup založený na SSSP viz kurz IA101 Algoritmika pro těžké problémy IB002 Algoritmy a datové struktury I Jaro 2018 385 / 390 N ej kratší cesty Lineární nerovnice Problém lineárních nerovnic je daná množina nerovnic tvaru xi — Xj < bk, kde x jsou proměnné, 1 <, z, j < n b jsou konstanty, 1 < k < m úkolem je najít takové hodnoty proměnných x, které splňují všechny nerovnice (tzv. přípustné řešení; v případě, že neexistuje žádné přípustné řešení, tak výstupem je Falše příklad X\ — X2 < 5 X\ — Xs < 6 < - 1 < - ■2 X4. — X\ < - 3 přípustné řešení x — (0, —4, —5, —3) IB002 Algoritmy a datové struktury I Jaro 2018 386 / 390 N ej kratší cesty Lineární nerovnice Graf lineárních nerovnic ohodnocený, orientovaný graf G — (V, E) ■ V = {v0,vi,... ,vn} (jeden vrchol pro každou proměnnou plus vrchol vq) m E — {(ví, v j) | x j — Xi