IB002 ALGORITMY A DATOVÉ STRUKTURY I Ivana Cerná Jaro 2019 Fakulta informatiky, Masarykova univerzita 1 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, Jan Obdržálek, Petr Novotný, Jaromír Plhák, Tomáš Effenberger, Dominik Velan, Jan Horáček, Jan Koniarik, Mária Michalíková, Juraj Pančík, Viktoria Vozárová, Tatiana Zbončáková (vedení cvičení) • Jan Horáček, Adam Matoušek, Tatiana Zbončáková (konzultace) interaktivní osnova předmětu - kompletní informace o výuce • organizace výuky přednášky, cvičení, domácí úkoly, konzultace • studijní materiály slajdy z přednášky, sbírka příkladů, zadání úkolů, rozcestníky, video přednáška ... • hodnocení předmětu odpovědníky, domácí úkoly, speciální domácí úkol, implementační a znalostní část zkoušky • diskusní fórum předmětu v IS 2 LITERATURA T. Cormen, Ch. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Third Edition. MIT Press, 2009 obrázky použité v prezentaci jsou částečně převzaty z uvedené monografie další odkazy v Interaktivní osnově SYLABUS 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 prohledávání grafu, souvislost grafu, cesty v grafu 4 MOTIVACE řešit jinak neřešitelné problémy... X- Chicago road networks, http://csun.uic.edu/dataviz.html 5 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 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. — Nikiaus Wirth š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 8 pro zábavu a zisk. Google facebook amazon.com Adobe SECURITY5 IL NETSUITE ORACLE Honeywell redňat central european institute of technology BfiHŮ j CZECH REPUBLIC v Část I Návrh a analýza algoritmů 10 SLOŽITOST A KOREKTNOST ALGORITMŮ SLOŽITOST A KOREKTNOST ALGORITMŮ MOTIVACE PŘÍKLAD najdi nej kratší cestu pro rozvoz čerstvé pizzy ALGORITMUS??? 11 řešení 1 vyber počáteční vrchol v <— počáteční vrchol while existuje nenavštívený vrchol do vyber nenavštívený vrchol, který je nejblíž k v v <— vybraný vrchol od vrať se do počátečního vrcholu return pořadí, v němž byly vrcholy navštíveny 12 reseni 2 while existují vrcholy, které nejsou spojeny cestou do vyber vrcholy, které nejsou spojeny cestou a jejichž vzdálenost je nejmenší vybrané vrcholy spoj hranou od přidáním hrany vytvoř cyklus korektní algoritmus prozkoumej každý z n\ Hamiltonovských cyklů grafu vyber nejkratší cyklus • algoritmus je korektní, protože prověří všechny možnosti • složitost algoritmu je úměrná počtu všech Hamiltonovských cyklů a algoritmus je proto nepoužitelný již pro velmi malé grafy 14 SLOŽITOST A KOREKTNOST ALGORITMŮ ANALÝZA SLOŽITOSTI SLOŽITOST 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? — Charles Babage, 1864 kolikrát musíme zatočit klikou? 15 ČASOVÁ SLOŽITOST časová složitost výpočtu je 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 nejhorším případě 16 VYHLEDÁVÁNÍ PRVKU V POSLOUPNOSTI vstup posloupnost prvků A[l... n] a prvek x výstup index / takový, že A[i] = x, resp. hodnota N, jestliže prvek x se v posloupnosti nevyskytuje Linear Search(/1) 1 answer ^- N 2 for / = 1 to n do 3 if A[i] = x then answer <— i fi 4 od 5 return answer 17 optimalizace I Better Linear Search(/1) 1 for / = 1 to n do 2 if A[i] = x then return / fi 3 od 4 return N • první výskyt x ukončí prohledávání • každý průchod cyklem znamená 2 testy: v řádku 1 testujeme nerovnost / < n, v řádku 2 testujeme rovnost A[i] = x • stačí 1 test? 18 optimalizace II Sentinel Linear Search(/1) 1 last <- A[n] 2 A[n] x 3 i <- 1 4 while A[i] ^ x do /V / + 1 od 5 A[n]<- last 6 if / < n V A[n] = x 7 then return / 8 else return N fi • první výskyt x ukončí prohledávání • sentinel (zarážka) pro případ, že pole neobsahuje prvek x • každý průchod cyklem znamená 1 test • 2 testy na závěr (řádek 6) 19 časová složitost vyhledávání 1 answer N 2 for / = 1 to n do 3 if A[i] = x 4 then answer / fi od 5 return answer • označme t; složitost operace na řádku / • operace z řádků 1 a 5 se vykonají jednou • řádek 2 se vykoná r? + 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ě t\ + t2 • (r? + 1) + ť$ • n + t% • 0 + t$ časová složitost v nej horším případě t\ + t2 • (r? + 1) + ť$ • n + t% • n + t$ 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 20 Better Linear Search(/1) 1 for / = 1 to n do if A[i] = x then return / fi od 2 return N • č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) 1 last <- A[n],A[n] <- x, / <- 1 2 while A[i] ^ x do /V / + 1 od 3 A[ri\±- last 4 if / < n V y4[r?] = x then return / else return N 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 21 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 22 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 23 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čí a po jeho ukončení platný invariant garantuje požadovaný efekt cyklu Better Linear Search(/1) for / = 1 to n do if A[i] = x then return / fi od return N 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 / a n. inicializace Na začátku je / = 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 / + 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 /, platnost tvrzení po ukončení iterace je zřejmá. ukončení Cyklus skončí buď proto, že je nalezena hodnota x anebo proto, že / > n. V obou případech z platnosti tvrzení po ukončení iterace cyklu plyne korektnost vypočítaného výsledku. 25 SLOŽITOST A KOREKTNOST ALGORITMŮ ŘAZENÍ VKLÁDÁNÍM PROBLÉM ŘAZENÍ vstup posloupnost n čísel (ai, a2,..., an) výstup permutace (přeuspořádání) (a'l5 a^,.. •, a;n) vstupní posloupnosti taková, že a^ < a^ < ... < a;n 26 ALGRITMUS ŘAZENÍ VKLÁDÁNÍM (a) 7 (b) 2 7 4 9 1 3 (c) 2 4 7 9 1 3 (d) 2 4 7 9 1 3 \OOuOj (e) 1 2 4 7 9 3 (f) 1 2 3 4 7 9 27 Insert Sort(/1) Vstup: A[l... n] 1 for j = 2 to A.length do 2 key +- A\j] 3 JI Vlož A\j] do seřazené postupnosti /A[l.. J — 1] 5 while / > 0 A A[i] > key do s A[i + 1] <- /4[/] 7 / «— / — 1 <§ od 5 A[i + 1] <- /cey i0 od 28 Korektnost - 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 nejmenšího po nejvě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 — l],A[j — 2],... se 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é. 29 složitost řazení vkládáním Insert Sort(/4) cena počet i for j = 2 to A.length do Cl n 2 key <— A\J] n- 1 3 i <—j — 1 n-1 4. while / > 0 A A[i] > key do c4 EU tj 5 /*[/ + 1] <- A[i] <% £"=2(t; -1) 6 /■<—/ — 1 od 05 -1) 7 /4[/ + !]•<— /cey od C7 n-l ty 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 30 složitost — nejlepší případ Insert Sort(/4) cena počet 1 for j — 2 to A.length do Cl /7 2 key <- A\J] n — 1 3 n — 1 A while / > 0 A A[i] > key do C4 =2 ŕJ 5 A[i + 1] "I) 6 i ^— / — 1 od C6 =2(í/ "I) 7 A[i + key od C7 n — 1 n n T (n) = cľn + c2(n - 1) + c3{n - 1) + c4 ^ «/ + Q> ^(t; " X) n 7=2 7=2 + C6^(ŕ/-l) + c7(n-l) 7=2 = cín + c2(n - 1) + c4(n - 1) + c4(n - 1) + c7(n - 1) = a r? + b lineární složitost složitost — nejhorší případ Insertion Sort(/4) cena počet i for j = 2 to A.length do Cl n 2 key A\J] C2 n- 1 3 i <- j - 1 C3 n-1 4 while / > 0 A A[i] > key do C4 e;=2 $ 5 /*[/ + 1] <- A[i] C5 1) 6 /■<—/ — 1 od C6 1) 7 A[i + 1] ^— key od C7 n- 1 T(n) = cín + c2(n - 1) + c3(n - 1) + c4( - l) + Q>( V 2 0 + c6( V 2 ;) + c7(n - 1) = arr + bn + c kvadratická složitost SLOŽITOST A KOREKTNOST ALGORITMŮ ASYMPTOTICKÁ NOTACE ASYMPTOTICKÁ NOTACE asymptotickou notaci využíváme při popisu složitosti algoritmů umožňuje abstrahovat od detailů / zdůraznit podstatné příklad T(n) = cín + c2{n - 1) + c3(n - 1) + c4(^y-^ - l) + Q>( V 2 -) + c6( 2 0 + c7(n - 1) = (y + y + y )n + (ci + c2 + Q + y - y - y + c7)n - (C2 + C3 + C4 + C7) — an + bn + c T{n)e 0(n2) 33 TYPY NOTACÍ f G O(g) znamená, že C • g(n) je horní hranicí pro f(n) f £ znamená, že C • g(n) je dolní hranicí pro f(n) f £ Q(g) znamená, že C\ • g{rí) je horní hranicí pro f{rí) a C2 • g"(r?) je dolní hranicí pro f(n) fg" jsou funkce, ŕ, g" : N —>> N C, Ci, C2 jsou konstanty nezávislé na n 34 O NOTACE f G 0{g) právě když existují kladné konstanty r?o a c takové, že pro všechna n > r?o platí f(n) < cg(n) • zápis f £ 0{g) ms zápis ŕ = 0{g) (historické důvody) • funkce f neroste asymptoticky rychleji než funkce g • alternativní definice f £ právě když lim sup -^4 < oc 35 O notace - příklady • 8n2 - 88n + 888 e 0(n2) protože 8n2 — 88n + 888 < 8n2 pro všechna n > 11 • 8n2 - 88n + 888 e 0(n3) protože 8n2 — 88n + 8 < ln3 pro všechna n > 10 • 8n2 - 88n + 888 0 0{n) protože cn < 8n2 — 88n + 888 pro n > c 36 fiNOTACE f e ^(áO právě když existují kladné konstanty no a c takové, že pro všechna n > r?o platí ^(r?) > cg(n) funkce f neroste asymptoticky pomaleji než funkce g 37 Q notace - příklady • 8n2 - 88n + 8 E Q(n2) protože 8n2 - 88/7 + 8 > n2 pro n > 13 • 8n2 - 88n + 8 £ Q(n3) protože 8n2 - 88n + 8 < cn3 pro n > f • 8/72 - 88n + 8 n pro n > 11 0 NOTACE f G ©(á") právě když existují kladné konstanty r?o, ci a ci takové, že pro všechna n > r?o platí cig"(r?) < ^(r?) < C2g(n) funkce f{n) a g{n) rostou stejně rychle Donald E. Knuth: Big Omicron and big Omega and big Theta. ACM SIGACT, Volume 8 Issue 2, April-June 1976, pp. 18 - 24. 39 0 notace - příklady • 8n2 — 88n + 8 G 0(n2) protože 8n2 — 88n + 8 G 0(n2) a současně 8n2 — 88n + 8 G Q{n2) • 8n2 - 88n + 8 g" 0(n3) protože 8n2 - 88n + 8 £ Q(n3) • 8n2 - 88n + 8 g" 0(n) protože 8n2 - 88n + 8 g" £>(n) 0 notace - příklad chceme dokázat platnost vztahu ^n2 — 3n £ 0(r?2) • musíme najít kladné konstanty ci,C2 a r?o takové, že Cir?2 < -n2 — 3n < con2 2 ~ platí pro všechna n > r?o • po úpravě dostáváme • 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 ci < 1/14 • volba ci = 1/14, C2 = 1/2 a r?o = 7 dokazuje platnost vztahu 1 3 - < c2 in2-3n = 0(n2) ASYMPTOTICKÁ NOTACE - VLASTNOSTI tranzitivita f{n) G 0(g(n)) a g{n) G 0(/?(n)) implikuje f{n) G 0(/?(n)) f (n) G a G C?(/?(n)) implikuje f (n) G C?(/?(n)) f (n) G Q(g(n)) a G implikuje f{n) G reflexivita G 0(f(n)) podobně pro O a Q symetrie f(n) G 0(g"(r?)) právě když g(n) G 0(f (n)) transpozice f(n) G č>(g"(r?)) právě když g(n) G íí(f(n)) poznámka: ne každá dvojice funkcí je asymptoticky srovnatelná 42 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 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 postupem (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. 44 ROZDĚL A PANUJ MAXIMÁLNÍ A MINIMÁLNÍ PRVEK PROBLÉM MAXIMÁLNÍHO A MINIMÁLNÍHO PRVKU vstupem je pole S[l... n] MaxMin Iterative(S) 1 max <(— S[l] 2 min <— S[l] 3 for / = 2 to n do 4 if S[/] > max then max «— S[/] fi 5 if S[/] < min then m/r? ^— S[/] fi 6 od složitost výpočtu = počet porovnání prvků celkem 2(n — 1) porovnání 45 aplikace přístupu Rozděl a panuj • posloupnost rozděl na dvě (stejně velké) podposloupnosti • najdi minimální a maximální prvek v obou podposloupnostech • kombinuj řešení podproblémů: maximálním prvek posloupnosti je větší z maximálních prvků podposloupnosti; symetricky pro minimálním prvek MaxMin(S, /, r) 1 if r — I then return (S[/], S[r]) fi 2 if r = / + 1 then return (max(S[/], S[r]), min(S[/], 5[r])) fi 3 if r > I + 1 then (A, B) <- MaxMin(S, /, [(/ + r)/2j) 4 (C, D) ^ MaxMin(S, [(/ + r)/2j + 1, r) 5 return (max(yA, C), min(6, D)) fi iniciální volání MaxMin(S, 1, n) 46 korektnost algoritmu 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 (r? > 1) platnost tvrzení pro n dle indukčního předpokladu jsou čísla A a B maximálním a minimálním prvkem posloupnosti S[l,..., + n)/2j], stejně tak čísla C a D jsou maximálním a minimálním prvkem posloupnosti S[|_(l + n)/2\ + 1,..., n] větší z čísel >A, C je pak maximálním prvkem posloupnost /4[1,..., n] a menší z čísel 6, D jejím minimem 47 složitost algoritmu • n je velikost (délka) vstupní posloupnosti • podproblémy mají velikosti [n/2\ a \n/2 • 7~(r?) je počet porovnání ve výpočtu na vstupu délky n T(n) = složitost rozdělení + složitost řešení podproblémů + složitost kombinace Un) = { 0+ T{[n/2\)+ T{\n/2]) + 2 pro n > 2 1 pro n = 2 0 pro n = 1 48 složitost algoritmu - explicitní vyjádření Un) = T([n/2\) + 7(\n/2\) + 2 pro n > 2 1 pro n — 2 0 pro r? = 1 indukcí vzhledem k n ověříme, že pro n > 1 platí 7"(r?) < |r? — 2 indukční základ 7(2) = 1 < § - 2 — 2 7(3) = 0 + 1 + 2 < §-3-2 indukční předpoklad nerovnost platí pro všechny hodnoty /, 2 < / < n platnost pro n T(n)=T([n/2\)+T(\n/2]) + 2 5 n 5 < - n/2 -2 + - 'n/2 ~ 3 1 3 1 využijeme indukční predpoklad 3 49 Kdo je nej rychlejší? MiNl(S,/,r) minimum ^- S[l] for / = / + 1 to r do if minimum > S[i] then minimum ^- S[/] f i od return minimum MiN2(S,/,r) if r = / then return S[r] fi if r > / then A <- Min2(S, /, |_(/ + r)/2J) B I then >4 <- Min3(S, /, r - 1) return min(/4, S[r]) fi ROZDĚL A PANUJ SLOŽITOST REKURZIVNÍCH ALGORITMŮ SLOŽITOST REKURZIVNÍCH ALGORITMŮ • nechť 7~(r?) je časová složitost výpočtu na vstupu délky n • složitost zapíšeme pomocí rekurentní rovnice, která vyjadřuje 7~(r?) pomocí složitosti výpočtů na menších vstupech • pro malý vstup (r? < c) je časová složitost ohraničená konstantou • velký vstup rozdělíme na k podproblémů velikosti r?i,..., n^\ řešení podproblému velikosti r?; má časovou složitost 7~(r?;) • nechť D(n) je složitost konstrukce podproblémů a C(r?) je složitost kombinaci řešení podproblémů a nalezení řešení původního problému jak najít řešení (explicitní vyjádření funkce T(n)) rekurentní rovnice? pro n < c 51 Ř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) 52 SUBSTITUČNÍ METODA 1. „uhodni" řešení 2. matematickou indukcí dokaž jeho korektnost příklad 1 pro n — 1 T(n) = 2T([n/2\) + n jinak 1. T(n) e 0(n\ogn) 2. indukcí dokážeme, že T(n) < cn log n pro dostatečně velké n a vhodně zvolenou konstantu c 53 dokazujeme T(n) < cn\ogn pro rovnici 7» = J 1 \2T(Ln/2j) indukční základ n — 2 a n = 3 • dosazením do rovnice zjistíme, že 7(2) = 4 a 7~(3) = 5 • zvolíme konstantu c > 1 tak, aby pro n — 2 a r? = 3 platilo 7~(r?) < cr? log n • dobrá volba je c > 2, protože platí 7(2) < c • 2 log 2 a současně platí 7(3) < c • 3 log 3 54 pro n — 1 jinak dokazujeme T(n) < cnlogn pro rovnici T(n) = 1 pro n = 1 2T([n/2\) + 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(Ln/2j) • využitím indukčního předpokladu dokážeme platnost tvrzení pro n T(n)<2(c[n/2\ log(Ln/2j)) + n < cn\og(n/2) + n = cn log n — cn log 2 + n = cnlogn — cn + n < cnlogn za předpokladu c > 1 dokázali jsme, že pro všechna n > 2 platí 7~(r?) < 2r?logr? 55 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 56 T(n)={1 Pr°n = 1 3T([n/4\) + cn2 jinak metodu rekurzivního stromu použijeme pro získání odhadu řešení, můžeme proto předpokládat, že n je mocninou 4 58 A log4 n I I i / I \ / I \ ' I * ' I * ' I * / I t / I \ / I i I I i / I i I I \ err I I I I I I I I I I I I I I I I T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) T(l) v nlo§4 3 log4 3 |7'^B4 Total: C(n2) 59 • kořen má hloubku 0 • vnitřní vrchol v hloubce / je označen složitostí c(r?/4')2 • počet vrcholů s hloubkou / je 3' • součet složitostí vrcholů v hloubce / je 3/c(/?/4/)2 = (3/16)'cn2 • list je označen složitostí 1 (základ rekurentní rovnice) a má hloubku / = |0g4 n (protože n/Alo^n = 1) • počet listů je 3log4n = nl°^3 • sumací přes všechny úrovně dostáváme T(n) = cn2 + ^-cn2 + ■■■ + (A)^ "^W + n1^3 60 T(n) = cn2 + ^-cn2 + ■ ■ ■ + (A)log< ""W + „iog43 v 7 16 v16; log4n-l = E (4)'"2+"log<3 1=0 oo ~ <£(4)i«'2 + ''l°g'3 ;=o 1 cn2 + nlog43 1 - (3/16) = ^cn2 + nlog43 13 jako odhad pro substituční metodu použijeme T(n) e C(n ) 61 KUCHAŘKOVÁ VĚTA (MASTER METHOD) Nechť a > 1 a b > 1 jsou konstanty, f(n) je polynomiální funkce, a nechť 7"(r?) je definována na nezáporných číslech rekurentní rovnicí T(n) = aT(n/b) + f(n) . Potom platí e(ř») T{n) = { 0(nlosta) když af(n/b) = cf(n) pro konstantu c < 1 když af(n/b) = df(n) pro konstantu d > 1 0(r»logí,/j) když af{n/b) = f(n) 62 KUCHAŘKOVÁ VĚTA - ALTERNATIVNÍ VARIANTA Nechť a>l, b>lac>0 jsou konstanty a nechť 7~(r?) je definována na nezáporných číslech rekurentní rovnicí T(n) = aT(n/b) + Q(nc) . Potom platí Q(nc) když a < b( T(n) = { Q(nc log n) když a = b( 0(n'°^a) když a > b( případ 1 případ 2 případ 3 věta platí i ve variantě pro O a Q 63 príklady použití kuchařkové věty I • T{n) = 4T(n/2) + l =^ 7~(n) G Q(n2) případ 3, a = 4, b = 2, c = 0, 4 > 2° • T{n) = 4T{n/2) + n => 7~(n) G 0(n2) případ 3, a = 4, b = 2, c = 1, 4 > 21 • T{n) = 4T{n/2) + n2 => T (n) G Q(n2 log případ 2, a = 4, b = 2, c = 2, 4 = 22 • T(n) = 4T(n/2) + n3 =>• T(n) £ G(n3) případ 1, a = 4, b = 2, c = 3, 4 < 23 príklady použití kuchařkové věty II • T(n) = 2T(n/2) + l =^ T (n) G ®{n) prípad 3, a = 2, b = 2, c = 0, 2 > 2° • T(n) = 2T(n/2) + n ==>■ 7~(n) G 0(n log prípad 2, a = 2, b = 2, c = 1, 2 = 21 • T{n) = 2T{n/2) + n2 => T{n) G 0(n2) prípad 1, a = 2, b = 2, c = 2, 2 < 22 • T(n) = 2T(n/2) + n3 T(n) G 0(n3) prípad 1, a = 2, b = 2, c = 3, 2 < 23 příklady použití kuchařkové věty III Hanojské věže T(n) = 2T{n - 1) + 1 T(n) = 2" - 1 MergeSort T(n) < 2T(n/2) + Q(n) T(n) e G(nlogn) násobení celých čísel T(n) = 4T(n/2) + 0(n) T(n) e 0(n2) Strassenův algoritmus pro násobení celých čísel T(n) = 7T(n/2) + 0(n2) T{n) e 0{n]0^7) 66 ROZDĚL A PANUJ JAK NEPOUŽÍVAT REKURZI JAK NEPOUŽÍVAT REKURZI nedefinovaný výpočet chybí základ rekurze Bad_Factorial(a7) return n • BAD_FACTORiAL(r? - 1) nekonečný výpočet Awful_Factorial(a7) if n = 0 then return 1 else return AwFUL_FACTORiAL(r? + 1) fi BETA(r?) if n = 1 then return 1 else return n(n — l)BETA(r? — 2) fi 67 neefektivní výpočet Fibonacciho posloupnost Fq = 0, F\ = 1, Fn — Fn_i + Fn_2 REcFiBo(r?) if n < 2 then return n else return REcFiBo(r? - 1) + REcFiBo(r? - 2) fi algoritmus RecFibo má exponenciální časovou zložitost 7(0) = 1, 7(1) = 1, 7(n)= 7(n-l)+ 7(n - 2) + 1 7(#i) = 0(0"), 0 = (>/5 + l)/2 68 neefektivní výpočet - pokračování iterativní algoritmus pro výpočet Fibonacciho posloupnosti lTERFlBO(r?) F[0] <- 0 F[l] <- 1 for / = 2 to n do F[/] <- F[/ - 1] + F[/ - 2] od return F[n] algoritmus IterFibo má lineární časovou zložitost, 7~(r?) £ ROZDĚL A PANUJ PROBLÉM MAXIMÁLNÍ PODPOSLOUPNOSTI JAK POUŽÍVAT REKURZI - DEFINICE PODPROBLÉMŮ problém maximální podposloupnosti • dané je pole celých čísel /4[l..r?] • 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ů i J • kvadratická složitost • existuje lepší řešení? rozděl a panufi 70 definice podproblémů daná je posloupnost /4[/cm/i/ ... high] a hodnota mid hledané řešení A[i.. J] (A) je pod posloupností /4[/cm/i/ ... mid] (iow < i leftsum then leftsum ^- sum 6 maxleft <— i fi od 7 rights um <--oo 8 sum ±- 0 9 for j = mid + 1 to high do 10 sum ^- si/rn + /4[y] ü if sum > rightsum then rightsum ^- si/rn íjg maxright <— j fi od í5 return (maxleft, maxright, leftsum + rightsum) 72 algoritmus Find_Maximum_Subarray(/1, low, high) 1 if high = low 2 then return (low, high, A[low]) 3 else mid = [(/cw + high)/2] 4 (leftlow, lefthigh, leftsum) <- F_M_S(>4, /cw, m/c/) 5 (rightlow, righthigh, righttsum) <— F_M_S(/4, mid + 1, /7/g/?) ^ (crosslow, crosshigh, crosssum) <— F_M_C_S(/4, low, mid, high) f i 7 if leftsum > rightsum A leftsum > crosssum 8 then return (leftlow, lefthigh, leftsum) f i p if leftsum < rightsum A rightsum > crosssum ío then return (rightlow, righthigh, rightsum) íl else return (crosslow, crosshigh, crosssum) f i 73 složitost algoritmu procedura Find_Max_Crossing_Subarray(/1, low, m id, 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(r?) algoritmus Find_Maximum_Subarray • dekompozice a kompozice v konstantním čase • řešení problému (C) v čase 0(r?) 1 • T(n) = e(n\ogn) 74 ROZDĚL A PANUJ REKURZIVNÍ VS ITERATIVNÍ PŘÍSTUP REKURZIVNÍ VS ITERATIVNÍ PŘÍSTUP • 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í 75 TAIL REKURZE • každý rekurzivní algoritmus lze převést na iterativní • simulace zásobníku volání • jednoduchý přepis v případě tail rekurze tail rekurze -speciální případ rekurze, kde se po rekurzivním volání nedělá žádný výpočet ANO NE else y <— G (x — 1) f i return x • y 76 přepis tail rekurze na iterativní algoritmus — příklad 1 F(x,y) if y = 0 then return x else F(x • y + x, y — 1) f i F(x,y) /abe/ : if y = 0 then return x else x <— x • y + x y <-y-l goto /abe/ fi F(x,y) reŕ ^- x for / = 1 to y do ret <— ret • y + ret od return ret 77 přepis tail rekurze na iterativní algoritmus — příklad 2 Bin Search(x, A, left, right) if right — left then return /4[/e/t] == x fi if right < left then mid = [(left + right)/2J if /4[m/c/] = x then return true fi if A[mid] < x then left <— mid + 1 else right <— mid fi Bin Search(x, A, left, right) fi Bin Search(x, A, left, right) while right < left do mid = [(left + right)/2J if /4[m/c/] = x then return true fi if /4[m/c/] < x then /eft «— mid + 1 else r/g77r <— mid fi Cast Razení 79 PROBLÉM ŘAZENÍ • je daná množina K, nad kterou je definované úplné uspořádání • vstupem problému řazení je posloupnost A = (/ci,..., kn) prvků z K • výstupem je posloupnost A' — (/c{,..., kfn), která je takovou permutací posloupnosti A, že V/,7,1 < / < j < n, platí k\ < k1- 80 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 Í2(r?), 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) 81 PŘEHLED časová složitost časová složitost algoritmus v nej horším případě v průměrném případě řazení vkládáním 0(n2) 0(n2) řazení výběrem 0(n2) 0(n2) řazení sléváním 0(r? log n) 0(n log n) řazení haldou Q(n log n) 0(n log n) řazení rozdělováním 0(n2) 0(n log n) řazení počítáním Q(k + n) 0(/c + n) číslicové řazení e(d{n + k)) 0(c/(n + /c)) přihrádkové řazení 0(n2) 0(n) 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 0(r?logr?)) 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 83 ŘAZENÍ SLÉVÁNÍM Ř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é 84 spojení dvou seřazených posloupností - Merge otázkou je, jak spojit dvě seřazené posloupnosti dojedná, 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 a indexy p, q, 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 85 L L 8 9 10 11 12 13 14 15 16 17 A • • • 2 4 5 7 1 2 3 6 • • • 1 2 /c 3 4 5 i 2 3 4 5 2 4 5 7 oo R 1 2 3 6 OO / 00 8 9 10 11 12 13 14 15 16 17 A • • • 1 2 5 7 1 2 3 6 • • • 1 2 3 4 k 5 i 2 3 4 5 2 4 5 7 OO 1 2 3 6 OO (c) ; Z. Z. 8 9 10 11 12 13 14 15 16 17 A • • • 1 4 5 7 1 2 3 6 • • • 1 2 3 k 4 5 i 2 3 4 5 2 4 5 7 OO /? 1 2 3 6 OO / 8 9 10 11 12 13 14 15 16 17 >A • • • 1 2 2 7 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 (d) J 86 L L L 8 9 10 11 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 / (e) j 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 /c 2 3 4 5 2 4 5 7 OO /? 1 2 3 6 OO / (*) j 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 L L 8 9 10 11 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 / (0 j 8 9 10 11 12 13 14 15 16 17 • • • 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) Merge(/1, p, q, r) předpoklad: posloupnosti A[p... q] a A[q + 1... r] jsou seřazené 1 r?i 4r- q - p + 1 2 r?2 <— r ~ Q 3 //nechť L[l... r?i + 1] a R[l... r?2 + 1] jsou nová pole 4 for / = 1 to ni do L[i] «- >4[p + / - 1] od 5 for j = 1 to n2 do /?[/] + j] od ^ L[#7i + 1] oc 7 R[n2 + 1] oc s /' «— 1 s y <- 1 í0 for k = p to r do 12 11 «f < R\J] then ^] <" /<-/ + ! 13 else A[k] <- R\j] j^j + lfi 88 15 od korektnost procedury Merge invariant for cyklu Na začátku každé iterace cyklu for v řádcích 10 - 15 posloupnost A[p... /c — 1] obsahuje k — p nejmenších prvků z L[l... r?i + 1] a R[l... n2 + 1] a to v pořadí podle velikosti. Navíc, /_[/] a R\j] jsou nejmenšíprvky mezi těmi prvky ve svých posloupnostech, které ještě nebyly zkopírované do A. inicializace Na začátku je k = p. Navíc / =j = 1 a tedy /_[/] a R\j] jsou nejmenší prvky v L a R. iterace Předpokládejme, že /_[/] < /?[/]. Potom /_[/] je nejmenší prvek z těch, které ještě nebyly zkopírované do A. Protože A[p... /c — 1] obsahuje k — p nejmenších prvků, pole A[p... k] bude obsahovat k — p + 1 nejmenších prvků. Zvýšením /ca / zaručíme platnost invariantu i po ukončení iterace. ukončení Cyklus končí když k = r + 1. Z platnosti invariantu posloupnost A[p... k — 1] = /4[p... r] obsahuje seřazených /c — p = r — p+1 nejmenších prvků z Z_[l... A7i + 1] a ... n2 + 1]. Pole /_ a /? obsahují v součtu A7i + A?2+2 = r — p + 3 prvků. Všechny prvky, s výjimkou dvou nej větších, byly zkopírované do A. Dva největší prvky jsou sentinely. 89 složitost procedury Merge • řádky 1 - 2 a 6 - 9 mají konstantní složitost • for cykly v řádcích 4 a 5 mají v součtu složitost 0(r?i + n2) = ®(n), kde n = r — p + 1 • for cyklus v řádcích 10 - 15 iteruje n krát, všechny příkazy v řádcích 11 - 14 mají konstantní složitost • složitost procedury Merge je 0(r?) 90 algoritmus Merge Sort • využívá proceduru Merge • pro seřazení celé posloupnosti voláme Merge Sort(/4, 1, A.length) Merge Sort(/1, p, r) 1 if p < r then q <- [(p + r)/2j 2 Merge Sort(/1, p, q) s Merge Sort(/1, q + 1, r) 4 Merger, p, q, r) fi 91 složitost algoritmu Merge Sort rozděl rozdělení znamená výpočet indexu, proto má složitost 0(1) vyřeš rekurzívně zpracujeme dvě posloupnosti velikosti n/2, časová složitost je 2T(n/2) kombinuj složitost procedury Merge je 0(r?) T(n) = 0(1) akn = l 2T(n/2) + Q(n) jinak složitost algoritmu Merge Sort je T(n) e 0(nlogn) 92 ŘAZENÍ SLÉVÁNÍM PROBLÉM INVERZÍ PROBLÉM INVERZÍ motivace porovnání seznamu preferencí formulace problému • je daná posloupnost vzájemně různých čísel ai,..., an • inverzí v posloupnosti je dvojice indexů i J takových, že / < j a současně a; > aj • úkolem je najít všechny inverze v dané posloupnosti čísel příklad posloupnost 1, 4, 6, 8, 2, 5 má 5 inverzí naivní algoritmus otestuje všechny dvojice indexů, složitost 0(n2) 93 problém inverzí - přístup Rozděl a panuj rozděl posloupnost rozdělíme na dvě (stejně velké) podposloupnosti vyřeš v každé z podposloupnosti spočítáme inverze kombinuj k počtu inverzí z podposloupnosti připočítáme inverze mezi prvky různých podposloupnosti • cílem je navrhnout algoritmus s lepší složitostí než je složitost naivního algoritmu • jestliže chceme, aby časová složitost rekurzivního algoritmu byla T(n) g 0(n\ogn), tak musí platit 7~(r?) < 27~(r?/2) + c • n, tj. složitost výpočtu rozdělování a kombinace nesmí být větší než lineární jak spočítat inverze mezi prvky různých posloupností v čase O(n) ? problém inverzí - kombinuj - pokus 1 otázka jak spočítat inverze mezi prvky z posloupnosti A a posloupnosti BI odpověď jednoduchá za předpokladu, že A i B jsou seřazené algoritmus • seřaď A a B • pro každý prvek b g B binárním vyhledáváním v A urči, kolik prvků v A je větších než b • složitost není lineární 95 problém inverzí - kombinuj - pokus 2 vstupem jsou posloupnosti A = (ai, a2,..., a^) a 6 = (bi, £>2,..., b/) předpokládáme, že • prvky v obou posloupnostech jsou seřazeny vzestupně • všechny prvky posloupnosti A mají ve vstupní posloupnosti menší index než prvky posloupnosti B postupujeme stejně jako v proceduře Merge • prvky ai,..., a,-_i a bi,..., b/_i jsou již zařazené • porovnáváme prvek a,- s prvkem by • menší z porovnávaných prvků zařadíme do výstupní posloupnosti • jestliže a\ bj, tak a; není v inverzi se žádným z prvků bj, b/+i,..., b\ • jestliže aj bj, tak bj je v inverzi se všemi prvky a,-,..., a/c, a proto k počtu inverzí připočteme k — i + 1 96 zařazené prvky / A B J inverze mezi prvky zařazenými do výsledné posloupnosti jsou započítané jestliže a; < bj, tak do výsledné posloupnosti přesuneme a; a; < bj < by+i < < • • • a i není v inverzi se žádným z bj, fa/+2 • • • jestliže a; > bj, tak do výsledné posloupnosti přesuneme bj bj < a; < a;+i < ay+2 < • • • bj je v inverzi s každým z a,-, a/+2 • • • Merge_and_Count(/1, 6) 1 i <— 1; j <— 1 2 11i (J) je index prvného nezařazeného prvku z A (6) s Count <— 0 4 II Count je počet nalezených inverzí 5 while seznamy A, B jsou neprázdné do 6 porovnej a; a bj 7 menší z prvků zařaď do výsledného seznamu 8 if bj < 3j then zvyš Count o počet nezařazených prvků z A fi 9 zvyš index / resp. j od 10 if jeden seznam je prázdný i i then zařaď zbývající prvky do výsledného seznamu f i 12 return Count a výsledný seznam 98 Sort_and_Count(L) 1 if length(L) = 1 2 then r <— O 3 else >A «— levá polovina L 4 B <(— pravá polovina Z. 5 (rA, A) <- Sort_and_Count(/1) 6 (re, 6) <- Sort_and_Count(6) 7 (r, Z.) <- Merge_and_Count(/1, 6) 8 r <- r + rA + rB f i 9 return (r, Z.) složitost algoritmu 7(n) = 0(1) pro n 27~(n/2) + 0(n) jinak 7~(n) g o(nlogn) QUICKSORT ŘAZENÍ ROZDĚLOVÁNÍM - QUICKSORT rozděl posloupnost A[p... r] na dvě podposloupnosti A[p... q — 1] a A[q... r] tak, aby všechny prvky v A[p... q — 1] byly menší nejvýše rovné prvkům v A[q... r] vyřeš obě posloupnosti (rekurzivně) seřaď kombinuj protože obě podposloupnosti jsou seřazené, není nutný žádný další výpočet Mergesort rozděl posloupnost na dvě posloupnosti poloviční velikosti, vyřeš obě podposloupnosti (rekurzivně) seřaď kombinuj spoj dvě seřazené podposloupnosti do jedné 100 Quicksort — principy • hlavní částí algoritmu je rozdělování posloupnosti do dvou posloupností požadovaných vlastností • při rozdělování využíváme pivota • každý prvek posloupnosti porovnáváme s pivotem • podposloupnosti prvků menších / větších než pivot 101 / P,J r P r (a) 2 8 7 1 3 5 6 4 (f) 2 1 3 8 7 5 6 4 p, i j r p / j r (b) 2 8 7 1 3 5 6 4 (g) 2 1 3 8 7 5 6 4 p, i j r p / r (c) 2 8 7 1 3 5 6 4 (h) 2 1 3 8 7 5 6 4 p, i j r p / r (d) 2 8 7 1 3 5 6 4 (i) 2 1 3 4 7 5 6 8 p / j r (e) 2 1 7 8 3 5 6 4 Quicksort^, p, r) 1 if p < r 2 then q «— Partition^, p, r) 5 Quicksort^, p, q - 1) 4 Quicksort^, q + 1, r) fi Partition^, p, r) 1 p/Vo ŕ «— /4[r] 2 / «— p — 1 5 for j = p to r do 4 if ^[y] < pivot then /'«—/' + 1 5 vyměň A[i] a /A[y] fi od 6 return / 103 Quicksort — korektnost chceme dokázat, že procedura Partition vrátí index / takový, že • A[i] = pivot • pro p < k < i platí A[k] < A[i] • pro / < k < r platí A[k] > A[i] Invariant cyklu na začátku iterace for cyklu v řádcích 3-6 platí pro každý index k 1. jestliže p < k < i, tak A[k] < pivot 2. jestliže / + 1 < k < j - 1, tak A[k] > pivot Inicializace iniciální přiřazení je pivot <— A[r], i <— p — 1 a j <— p invariant (triviálně) platí 104 Invariant cyklu na začátku iterace for cyklu v řádcích 3-6 platí pro každý index k 1. jestliže p < k < i, tak A[k] < pivot 2. jestliže / + 1 < k < j - 1, tak A[k] > pivot iterace A [y] > pivot efektem iterace cyklu je zvýšení hodnoty j o 1; invariant platí A\j] < pivot efektem iterace cyklu je zvýšení hodnoty / 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 105 Invariant cyklu na začátku iterace for cyklu v řádcích 3-6 platí pro každý index k 1. jestliže p < k < i, tak A[k] < pivot 2. jestliže / + 1 < k < j - 1, tak A[k] > 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 / < k < r platí A[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 106 Quicksort — složitost složitost v nej horším případě např. pro vstupní posloupnost, která je již seřazená, nebo která obsahuje stejné prvky T(n) = T(n - 1) + 7(0) + 0(n) = T(n - 1) + 0(n) T(n) G Q(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 7» = 27(n/2) + 0(n) T(n) G Q(n\ogn) průměrná složitost T(n) G Q(n\ogn) 107 Quicksort — Hoare Partition • pivotem je první prvek posloupnosti • postupujeme od obou konců posloupnosti až do chvíle, než jsou detekovány prvky, které jsou v opačném pořadí vůči pivotu; prvky si vymění svou pozici • funkce vrátí index j takový, že všechny prvky v A[p... j] jsou menší anebo rovny prvkům v A\j + 1... r] Hoare Partition(/1, p, r) 1 x <- A[p] 2 i <- p - 1 3 j <- r + 1 4 while true do 5 repeat j j — 1 until A\j] < x od 6 repeat / ^— / + 1 until A[i] > x od 7 if / < j then swap A[i] a A\j] 8 else return j fi Quicksort — alternativní rozdělování obě uvedená schémata se chovají špatně v případě, že ve vstupní posloupnosti se prvky opakují rozdělovači schéma, které řeší posloupnosti s opakujícími se prvky • při rozdělování se hledají prvky menší než pivot a větší než pivot • prvky stejné jako pivot jsou již na své pozici • prvky menší (větší) než pivot se seřadí rekurzivně 109 Quicksort — iterativní verze Tail Recursive Quicksort^, p, r) 1 while p < r do 2 q <- Partition^, p, r) 3 Tail Recursive Quicksort^, p, q - 1) 4 p «— q + 1 od Iterative Quicksort^, p, r) 1 stack — [ ] 2 stack.push(p, r) 3 while stack do 4 pos = stack.pop() 5 p,r = pos[l], pos[2] ^ q «— Partition^, p, r) 7 if q — 1 > p then stack.push((p, q — 1)) fi 5 if q + 1 < r then stack.push((q + 1, r)) fi 0 od 110 SLOŽITOST PROBLÉMU ŘAZENÍ složitost řadících algoritmů založených na vzájemném porovnávání prvků posloupnosti je fi(r? log n) • búno vstupní posloupnost obsahuje vzájemně různé prvky • každé porovnání určí větší ze dvou prvků • výpočet algoritmu můžeme popsat rozhodovacím stromem, každý vnitřní uzel stromu reprezentuje jedno porovnání a jeho synové odpovídající výsledku porovnání < resp. > • 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 • každý list jednoznačně určuje seřazení vstupních prvků • algoritmus musí mít možnost vypočítat každou možnou permutaci vstupních prvků; počet různých permutací je n\ • strom musí mít alespoň n\ listů =4> má hloubku alespoň log(r?!) G fi(r? log n) 3 ŘAZENÍ HALDOU RAZENI HALDOU ŘAZENÍ HALDOU ŘAZENÍ 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 • efektivně najít nej větší prvek • efektivně z ní odstranit největší prvek 112 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 definice viz učebný text Matematické Základy Informatiky prof Hliněného 113 stupeň vrcholu v kořenovém stromě T je počet jeho synů hloubka vrcholu x v T je délka cesty {tj. 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 /c-ární strom je strom, ve kterém má každý vrchol nejvýše k synů STROMOVÁ DATOVÁ STRUKTURA • 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ů (pointrů) 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 115 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 c/-regulární halda, binomiální halda, Fibonacciho halda 116 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 / uložíme do A[i] • klíč levého syna uzlu k bude uložen v poli na pozici 2k a klíč pravé syna uzlu k na pozici 2k + 1 • klíč otce uzlu k se bude nacházet na pozici [k/2\ 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 / vypočteme indexy synů a otce uzlu A[i] předpisem Parent(/) return [i/2 Left(/) return 2/ Right(/) return 2/ + 1 118 VYBUDOVANÍ HALDY vstupem je posloupnost klíčů uložená v poli A[l... r?] 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 O(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 0(n log n) 119 vybudování haldy — varianta A • postupujeme od uzlu n k uzlu 1 • nechť / je aktuálně spracovávaný uzel; pak všechny uzly j, pro i i procedura Max_Heapify(/1, /') • předpokládá, že binární stromy s kořeny Left(/) a Right(/) 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 / má vlastnost haldy • úprava je založena na přesunu klíče A[i] směrem dolů 120 Max_Heapify(/4, 2) 121 Max_Heapify(>4, /) 1 I 4- LeFT(/) 2 r A[i] 4 then largest <— I 5 else largest <— i fi 6 if r < A.heapsize A A[r] > A[largest] 7 then largest ^— r fi 8 if largest ^ i 9 then swap A[i] a A[largest] io Max_Heapify(/1, largest) fi složitost je O(h), kde A? je hloubka stromu s kořenem korektnost indukcí vzhledem k hloubce stromu využitím procedury Max.Heapify zkonvertujeme pole A[l... r?] na maximovou haldu klíce A[[n/2\ + l],>4[|n/2j +2]...>4[n] jsou uloženy v listech stromu a proto každý tvoří haldu s 1 vrcholem proceduru Max.Heapify aplikujeme na zbylé klíče v poli v pořadí odspodu směrem nahoru a na dané úrovni směrem zprava doleva Build_Max_Heap(/1) 1 A.heapsize <— A.length 2 f or / = [A.length/2\ downto 1 do s Max_Heapify(/1, /) od 123 Build_Max_Heap(/4) Build_Max_Heap — korektnost invariant cyklu Na začátku každé iterace for cyklu je každý z uzlů / + 1, / + 2,..., n kořenem haldy. inicializace na začátku je / = [n/2\, uzly [n/2\ + 1, [n/2\ +2 , ... ,n jsou listy a jsou tedy kořeny (triviální) haldy iterace levý a pravý podstrom vrcholu / jsou maximové haldy (platí pro ně invariant), vlastnost haldy může být porušena jedině klíčem A[i] uloženým v uzlu /; procedura Max_Heapify(/4, /) vybuduje haldu s kořenem / ukončení cyklus skončí když / = 0 a z platnosti invariantu plyne, že A je maximová haldu 125 Build_Max_Heap — složitost • pro strom s hloubkou A? je složitost Max_Heapify 0{h), t.j. je ohraničená funkcí c • h (c je konstanta) • počet podstromů hloubky A? je nejvýše {^htt • kořen má hloubku [log nj • celková složitost je proto nejvýše \}ogn\ \}ogn\ °° h ch í {cn E žä) ^ (cnE žä) = 2cn e °W h=0 h=0 h=0 při zjednodušování výrazu jsme využili rovnost ALGORITMUS ŘAZENÍ HALDOU, HEAPSORT • použitím procedury Build_Max_Heap vybudujeme haldu nad polem A[l... r?] • maximální prvek pole A je uložený v kořeni A[l] a proto ho můžeme přesunout na jeho finální pozici A[n] (vyměníme prvky A[l] a A[n]) • prvek, který jsme přesunuli do kořene, může porušit vlastnost haldy a pro obnovení vlastnosti haldy použijeme Max_Heapify(/4, 1) • celý proces opakujeme pro haldu velikosti n — 1 Heapsort(ZI) 1 Build_Max_Heap(/1) 2 for / = A.length downto 2 do vyměň A[ľ\ a A[i] 3 A.heapsize <— A.heapsize — 1 4 Max_Heapify(/1, 1) od 127 Heapsort (d) (e) (f) 128 Heapsort — složitost • procedura Build_Max_Heap má složitost O(n) • každé z/i-1 volaní procedury Max.Heapify má složitost 0(\ogn) • algoritmus Heapsort má složitost 0(n\ogn) 129 OPTIMALIZACE A VARIANTY optimalizace • budování haldy výměnou zdola nahoru — halda je na začátku prázdná a postupně do ní vkládáme prvky vstupní posloupnosti; prvek vložíme na poslední místo (jako list) a v případě porušení vlastnosti haldy ho (rekurzivně) zaměníme s jeho rodičem; časová složitost vybudování haldy je 0(r? log n) • bottom - u p heapsort — optimalizuje etapu seřazování prvků; maximální prvek z kořene si vymění místo s posledním prvkem haldy a pro obnovení vlastnosti haldy výměnami se postupuje zdola nahoru varianty • strom vyšší arity • ve vrcholu stromu uložených několik klíčů • haldy binomiální, Fibonacciho ... 130 ŘAZENÍ HALDOU PRIORITNÍ FRONTA PRIORITNÍ FRONTA • datový typ pro reprezentaci množiny prvků, nak kterými je definováno uspořádání • efektivní realizace operací Insert(S,x) vloží prvek x do množiny S Maximum(S) vrátí největší prvek množiny S Extract_Max(S) odstraní z množiny S největší prvek Increase_Key(S, x, k) nahradí prvek x prvkem k za předpokladu, že k > x • prioritní frontu implementujeme jako haldu alternativně můžeme definovat prioritní frontu vůči minimálnímu prvku a pro implementaci využít minimovou haldu 131 prioritní fronta — Maximum 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(/1) i return A[l\ prioritní fronta — Extract.Max odstranění maximálního prvku se implementuje stejně jako v algoritmu řazení haldou; složitost operace je 0(\ogn) Heap_Extract_Max(/1) 1 if A.heapsize < 1 then return prázdná fronta f i 2 max <— A[l] 3 A[l] <- A[A.heapsize] 4 A.heapsize <— A.heapsize — 1 5 Max_Heapify(/1, 1) 6 return max prioritní fronta — Heap_lncrease_Key(/4, /, key) • index / 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 tak, že nový prvek posouváme směrem ke kořeni • složitost operace je 0(\og n) Heap_Increase_Key(/1, /', key) 1 if key < A[i] then return nová hodnota je menší než původní fi 2 A[i] <— key 3 while / > 1 A /1[Parent(/)] < A[i] do 4 vyměň A[i] a /1[Parent(/)] 5 i <- Parent(/) od 133 prioritní fronta — Insert • na konec pole vložíme nový prvek, který je menší než všechny ostatní prvky, symbolicky ho označujeme —oc • zvýšíme hodnotu vloženého prvku na hodnotu prvku, který chceme vložit do fronty • složitost operace je 0(\og n) Max_Heap_Insert(/1, key) 1 A.heapsize <— A.heapsize + 1 2 A [A. h eapsize] <--oc 3 Heap_Increase_Key(/1, A.heapsize, key) 134 ŘAZENÍ V LINEÁRNÍM ČASE RAZENI V LINEÁRNÍM CASE COUNTING SORT ŘAZENÍ POČÍTÁNÍM - COUNTING SORT předpoklad vstupní posloupnost obsahuje celá čísla z intervalu 0,..., k, kde k je nějaké pevně dané přirozené číslo k není závislé na délce posloupnosti 135 Counting sort — idea • vstupní posloupnost je uložena v A[l... n] • výstupní (seřazená) posloupnost je uložena v B[l... n] • pole C[0... k] se využívá v průběhu výpočtu • pro každou hodnotu / = 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel /, výsledný počet uložíme do C [i] • pro každou hodnotu / = 0,1,..., k spočítáme, kolik je ve vstupní posloupnosti čísel menších nebo rovných /, 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 136 1 2 3 4 5 6 7 8 2 5 3 0 2 3 0 3 0 i 2 3 4 5 2 0 2 3 0 1 0 1 2 3 4 5 2 2 4 7 7 8 b 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 1 2 3 4 5 6 7 8 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 12345678 0 0 2 2 3 3 3 5 137 Counting_Sort(/1, 6, k) 1 j/inicializace C [O ... k] 2 for / = 0 to k do s C[i] ^ 0 od 4 for j = 1 to A.length do 5 C[A\j\\ <- C[/\[/]] + 1 od rj //C[/] obsahuje počet čísel rovných / 7 for / = 1 to k do 5 C[/] <- C[/] + C[i - 1] od p //C[i] obsahuje počet čísel menších nebo rovných / ío for j — A.length downto 1 do u B[C[A\j]]\ +- A\j] 12 C[A\j}\ <- C[A[i]\ - 1 od 138 Counting sort — časová složitost • cyklus na řádcích 2-3 (inicializace C) - složitost 0(/c) • cyklus na řádcích 4-5 (počet čísel = /) - složitost 0(r?) • cyklus na řádcích 7-8 (počet čísel < /) - složitost 0(/c) • cyklus na řádcích 10 - 12 (přesun z A do B) - složitost 0(r?) • celková složitost 0(/c + n) • algoritmu je stabilní, protože prvky se stejnou hodnotou se ve výstupní posloupnosti vyskytují ve stejném pořadí jako ve vstupní posloupnosti • stabilita algoritmu Counting sort se využívá v algoritmu Radix sort 139 Counting sort — 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 Q(n + k) 140 RAZENI V LINEÁRNÍM CASE 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(/1, d) 1 for / = 1 to d do 2 použij stabilní řazení a seřaď položky podle ite číslice 3 od 141 Radix Sort — složitost Danou posloupnost n čísel, z nichž každé má d číslic, přičemž číslice můžou nabývat k různých hodnot, seřadí algoritmus Radix.Sort v čase Q(d(n + k)) za předpokladu, že stabilní řazení, které využívá, má složitost 0(r? + k). • složitost je garantovaná např. při použití algoritmu Counting sort • jestliže d a k jsou konstanty, tak časová složitost číslicového řazení je lineární 142 Radix Sort — řazení binárních čísel • necht každé číslo má b bitů, zvolíme r < b • číslo rozdělíme na \b/ŕ\ skupin po r bitech • každou skupinu chápeme jako číslo z intervalu 0 až 2r — 1 • pro řazení ve skupině použijeme Counting sort pro k — 2r — 1 Danou posloupnost n binárních b bitových čísel Radix.Sort korektně seřadiv čase 0((b/r)(r? + 2r)) za předpokladu, že stabilní řazení, které využívá, má složitost 0(r? + k). otázka volby parametru r pro dané n a b závisí od poměru veličin n a b [b < log n\ pro r — b celková složitost číslicového řazení 0(r?) [b > log n\ pro r = [log n\ je složitost je Q(bn/ log n) pro r > [log n\ je složitost je Q(bn/ log n) pro r < [log r?J hodnota výrazu (b/r) klesá a hodnota výrazu n + 2r zůstává 0(r?) 143 RAZENI V LINEÁRNÍM CASE BUCKET SORT PŘIHRÁDKOVÉ ŘAZENÍ - BUCKET SORT předpoklad • 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 144 A B Bucket_Sort(/1) 1 JIB[0 ... r? — 1] je nové pole 2 n 4— A.length 3 for / = 0 to n — 1 do 4 B[i] <— prázdny seznam od 5 for / = 1 to n do 6 přidej A[i] do seznamu B[[n • A[i]\] od 7 for / = 0 to n — 1 do 8 seřaď prvky seznamu B[i] použitím řazení vkládáním od 9 spoj seznamy 6[0], 6[1],..., B[n — 1] do jednoho seznamu • nechť rij označuje počet prvků v koši B[i] • složitost je T(n) = 0(n) + Y1"ZÍ 0{n}) • očekávaná složitost je pro vstup s uniformně rozdělenými čísly 0(r?) 146 Část III Datové struktury 147 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 148 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 149 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 150 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(S,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ž klíč x.key je maximální Predecessor(S,x) symetricky k Successor 151 VYHLEDÁVACÍ STROMY 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 může být potvrzen, právě když v intervalu (t — /c, t + k) není žádná jiná rezervace (/c je délka trvání události) a současně t je aktuální • mazání realizovaných aktualizací příklad: k = 3, aktuální čas je 20, R = {21, 26, 29, 36} • rezervace 24 není validní (nemůže být potvrzena), protože je v kolizi s rezervací 26 z R • rezervace 15 není validní, protože aktuální čas je 20 • rezervace 33 je validní 152 ? datový typ pro reprezentaci R a realizaci požadovaných operací? uspořádaný seznam ověření rezervace v čase O(n), záznam rezervace v čase 0(1) uspořádané pole ověření rezervace v čase (D(\ogn), záznam rezervace v čase O(n) neuspořádaný seznam / pole ověření rezervace v čase O(n), záznam rezervace v čase 0(1) minimová halda ověření rezervace v čase O(n), záznam rezervace v čase (D(\ogn), 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í? potřebujeme současně efektivní vyhledávání i vkládání! 153 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í 154 BINÁRNÍ VYHLEDÁVACÍ STROMY (BVS) • kořenový strom, v němž každý uzel má nejvýše dva následníky • každý uzel stromu představuje jeden objekt, obsahující • klíč key • ukazatele leň, right a p na levého syna, pravého syna a na otce; ukazatel má hodnotu Nil právě když uzel nemá příslušného syna, resp. otce • případné další data • pro všechny uzly binárního vyhledávacího stromu platí jestliže x je uzel BVS a y je uzel v levém podstromu uzelu x, tak platí y.key < x.key y je uzel v pravém podstromu uzelu x, tak platí y.key > x.key 155 BVS — PROCHÁZENÍ STROMU • cílem je projít strom tak, aby každý uzel byl navštíven právě jednou • využití: provedení operace nad každým uzlem, 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 uzly levého podstromu kořene • (rekurzivně) navštívíme všechny uzly pravého podstromu kořene 156 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ě 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ě 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ě inorder (2 3 5 5 7 8), preorder (5 3 2 5 7 8), postorder (2 5 3 8 7 5) Inorder_Tree_Walk(x) 1 if x ŕ Nil 2 then Inorder_Tree_Walk(x.left) 3 print x.key 4 Inorder_Tree_Walk(x. right) 5 fi • Inorder_Tree_Walk(T.root) vypíše klíče uložené v BVS T v pořadí od nejmenšího po největší • časová složitost je Q(n), kde n je počet uzlů stromu T BVS Sort - časová složitost ??? 158 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 3 if k < x.key 4 then return tree_search(x./e/t, k) 5 else return Tree_Search(x. right, k) f i 159 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 160 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é • 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) pro stromy, které můžou obsahovat uzly se stejnými klíči, se pojmy a operace definují analogicky 161 BVS — následník uzlu x • jestliže pravý podstrom uzlu x je neprázdný, tak následníkem x j uzel jeho pravého podstromu s nejmenší klíčem • jestliže pravý podstrom uzlu x 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ý, y.key > x.key (x patří do levého podstromu uzlu y) Tree_Successor(x) 1 if x.right ^ Nil 2 then return tree_MiNiMUM(x.r/g77ŕ) f i 3 y <— x.p 4 while y / W/1 A x = y.right 5 dox^y 6 y^y.pod 7 return y BVS — PŘIDÁNÍ NOVÉHO UZLU • procházíme strom stejně jako kdybychom klíč nového uzlu vyhledávali • hledáme uzel, jehož příslušný podstrom je prázdný (levý podstrom, když klíč nového uzlu je menší než klíč uzlu, pravý podstrom když je větší) a nový uzel se stane jeho příslušným synem 163 Tree_Insert( 7, z) 1 y i.low 4 then x <— x.left 5 else x <— x. right f i ^ od 7 return x složitost • vyhledávání začína v kořeni • po každé iteraci cyklu testujeme uzel, jehož hloubka je o 1 vyšší • složitost je úměrná hloubce stromu 179 intervalové stromy — vyhledávání intervalu Interval_Search(7, /) 1 x <— T.root 2 while x 7^ Nil A intervaly / a (x.low, x.high) se nepřekrývají do 3 if x.left Nil A x.left.max > i.low 4 then x <— x.left 5 else x <— x. right f i od 5 return x korektnost, případ 1 - ve vyhledávání postupujeme doprava co když hledaný interval je v levém podstromu?? • předpokládejme, že levý podstrom není prázdný • platí x.left.max < i.low (jinak bychom postupovali doleva) • pro každý interval (a, b) z levého podstromu platí b < x.left.max (z definice hodnoty max) • b < i.low znamená, že / se nepřekrývá s žádným intervalem v levém podstromu v intervalové stromy — vyhledávání intervalu Interval_Search(7, /) 1 x <— T.root 2 while x 7^ Nil A intervaly / a (x.low, x.high) se nepřekrývají do 3 if x.left Nil A x.left.max > i.low 4 then x <— x.left 5 else x <— x. right f i od 5 return x korektnost, případ 2 - ve vyhledávání postupujeme doleva co když hledaný interval je v pravém podstromu?? • předpokládejme, že žádný interval levého podstromu se nepřekrývá s intervalem / • v levém podstromu leží interval (c, d) takový, ze d — x.left.max • / a (c, d) se nepřekrývají a tedy /./7/g"/7 < c • pro každý (a, b) z pravého podstromu platí c < a (vlastnost BVS) • i.high < a znamená, že / se nepřekrývá se žádným intervalem v pravém podstromu intervalové stromy — modifikace • vyhledávání všech překrývajících se intervalů • intervaly vyšší dimenze • namísto obecného binárního vyhledávacího stromu můžeme použít vyvážený binární vyhledávací strom 182 RADIX TREES • využití binárních vyhledávacích stromů pro lexikografické řazení binárních řetězců • řetězce postupně vkládáme do vyhledávacího stromu • po vložení všech řetězců strom prohledáme a klíče vypíšeme v pořadí preorder • časová složitost je 0(r?), kde n je součet délek všech řetězců • zobecnění pro řetězce nad libovolnou abecedou - použijeme stromy, jejichž arita je stejná jako velikost abecedy 183 ČERVENO ČERNÉ STROMY ČERVENO ČERNE STROMY ČERVENO ČERNÉ STROMY ČERVENO ČERNÉ STROMY červeno černý strom je binární vyhledávací strom, jehož každý uzel je obarvený červenou anebo černou barvou a splňuje podmínky 1. kořen stromu je černý 2. listy stromu nenesou žádnou hodnotu, tj. jsou označeny Nil, a mají černou barvu 3. když je uzel červený, tak jeho otec je černý 4. pro každý uzel x stromu platí, že všechny cesty z uzlu x do listů obsahují stejný počet černých uzlů alternativně: oba synové červeného uzlu mají černou barvu každý uzel obsahuje atributy key color, left, right, p jestliže uzel nemá některého syna anebo otce, tak příslušný atribut má hodnotu Nil 184 VÝŠKA UZLU A ČERNÁ VÝŠKA UZLU • výška uzlu x je rovna počtu hran na nejdelší cestě z x do listu • černá výška uzlu x, bh(x), je rovna počtu černých uzlů na cestě z x do listu (uzel x nezapočítavame) (díky vlastnosti 4 je černá výška dobře definovaná!) NIL NIL NIL NIL NIL NIL 185 Každý uzel s výškou h má černou výšku alespoň h/2. • z vlastnosti 4 plyne, že v nejhorším prípade je každý druhý uzel na cestě červený Každý podstrom s kořenem x má alespoň 2bh^ — 1 vnitřních uzlů. • důkaz indukcí k výšce h uzlu x • pro h = 0 je x list; bh(x) — 0 a současně počet vnitřních uzlů podstromu s kořenem x je 0 • nechť x má výšku /)>0a č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)-l _ X vnitfnfch UZ|Q • podstrom s kořenem x má alespoň 2(2^W-i _ i) + i = 2bh^ - 1 vnitřních uzlů vnitřním uzlem rozumíme uzel, který nese hodnotu, tj. list není vnitřním uzlem 186 Červeno černý strom s n vnitřními uzly má výšku nejvýše 2log2(n + l) • nechť strom má výšku h a černou výšku b • z předchozích tvrzení plyne n > 2b - 1 > 2h/2 - 1 • po úpravě log2(r? + 1) > h/2, a tedy h < 2 log2(r? + 1) 187 ČERVENO ČERNÉ STROMY - OPERACE • Search, Min, Max, Successor, Predecessor se implementují stejně jako pro binární vyhledávací stromy • vyjmenované operace mají složitost 0(\ogn) • 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 188 ROTACE RlGHT_ROTATE(y) -> Left_Rotate(x) rotace zachovává vlastnost binárního vyhledávacího stromu časová složitost 0(1) 189 Left_Rotate( 7, x) 1 yf- 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 8 else if x = x.p.left 9 then x.p.left <— y 10 else x.p.right ^ y n y.left <— x 12 x.p <— y PRIDANÍ 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 • vlastnost 4. (stejný černý výška) zůstává v platnosti • může dojít k porušení vlastností 1. (kořen stromu nemusí být černý) a vlastnosti 3. (otec červeného uzlu nemusí být černý) • po vložení uzlu vykonáme korekce, které obnoví platnost všech vlastností 191 RB_Insert(7, a) 1 Tree_Insert(7, a) 2 a. col or 4— 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 ío else případ 3 j j fi 12 fi i5 else stejně jako THEN se záměnou left a right 14 fi 15 od itf 7.root.color <— black případ 1 a. p. co I or 4— black d. co I or 4— black a.p.p.color 4— red a 4— a.p.p případ 2 a ^- a.p Left_Rotate(7, a) případ 3 a. p. col or 4— black a.p.p.color 4— red Right_Rotate(7, a.p.p) 193 přidání nového uzlu - korekce - případ 1 • uzel a je červený • jeho otec b je červe a je levým synem svého otce [pravý syn symetricky) • 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 y x y stromy z,x,y,p, q mají černý kořen a všechny mají stejnou černou výškou 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 3 x y Left_Rotate(6) z x 195 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 b uzlu a a jeho novým bratrem c 196 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 0(\ogn) 197 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 198 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 199 odstranění uzlu a - případ 3 a má dva syny, následník uzlu a je jeho pravým synem • levý syn uzlu a se stane levým synem následníka c uzlu a • odstraň a a nahraď ho jeho následníkem c • po přesunu obarvíme c barvou uzlu a • jestliže c měl původně černou barvu, tak černou barvu dostane jeho pravý syn, tj. syn má dvě barvy (červenou a černou anebo černou a černou) • problém dvou barev vyřešíme při korekci odstranění uzlu a - případ 4 a má dva syny, následník uzlu a není jeho pravým synem • následníka d nahraď jeho pravým synem e • odstraň a a nahraď ho jeho následníkem d, synové uzlu a se stanou syny následníka (d) • po přesunu obarvíme d barvou uzlu a • jestliže d 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 KOREKCE DVOU BAREV bazální případ uzel a má červenou a černou barvou • obarvi uzel a černou barvu 202 korekce dvou barev - případ 1 uzel a má dvě černé barvy bratr c uzlu a je červený proveď levou rotaci kolem otce b uzlu a vyměň barvy mezi otcem b a praotcem c uzlu a pokračuj některým z následujících případů z w p q Rotate_Left(£>) x y z w ; x y z w v._________________ jiný případ stromy x,y,z, i/i/,p, q neporušují žádnou vlastnost červeno černého stromu korekce dvou barev - případ 2 uzel a má dvě černé barvy bratr c uzlu a stejně jako oba jeho synové c/, 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á • uzel se dvěma barvami se přesunul blíž ke kořenu, problém jeho dvou barev řešíme rekurzivně výška) z w p q z w p q 204 korekce dvou barev - případ 3 uzel a má dvě černé 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, t.j. mezi uzly d a c • pokračuj případem 4 205 korekce dvou barev - případ 4 uzel a má dvě černé barvy bratr c uzlu a má černou barvu, jeho pravý syn e má červenou barvu • proveď levou rotaci kolem otce b uzlu a • uzel c dostane barvu uzlu b • uzel b dostane černou barvu z uzlu a • uzel e změní barvu na černou X z w p q RotateJLeft x y z w x y z w ČERVENO ČERNE STROMY RANK PRVKU POŘADÍ (RANK) PRVKU problém ranku • množina A obsahující n vzájemně různých čísel • číslo x g A má rank / právě když v A existuje přesně / — 1 čísel menších nežx jak efektivně určit rank prvku? • jestliže prvky A jsou uložené v poli, tak v čase O(n) můžeme najít číslo s rankem / a 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 0{\og n) 207 ROZŠÍŘENÍ ČERVENO ČERNÝCH STROMŮ požadujeme • efektivní implementaci standardních operací nad červeno černým stromem • efektivní implementaci operace RB_Select(x, /), která najde /-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 208 PRINCIP ke každému uzlu x přidáme atribut x.size, který udává 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 209 VYHLEDÁNÍ KLÍČE S DANÝM RANKEM RB_Select(x, /) 1 r <— x.left.size + 1 2 if / = r then return x s else if / < r then return RB_select(x./e/t, /) 4 else return RB_select(x.r/g77r, / — r) f i f i korektnost • 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ž / = r, tak x je hledaný uzel • když / < r, tak /-ty nejmenší klíč se nachází v levém podstromě uzlu x a je /-tým nejmenším klíčem v tomto podstromě • když / > r, tak /-ty nejmenší klíč se nachází v pravém podstromě uzlu x a jeho pořadí v tomto podstromě je / snížené o počet uzlů levého podstromu vyhledání klíče s daným rankem — složitost • každé rekurzivní volání se aplikuje na strom, jehož hloubka je o 1 menší • hloubka červeno černého stromu je 0(\ogn) • složitost RB.Select je 0(\ogn) 211 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 212 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 fi 6 y <— y.p od 7 return r 213 určení ranku daného prvku — 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 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) ukončení výpočet končí když y = T.root, z platnosti invariantu plyne korektnost algoritmu 214 určení ranku daného prvku — složitost • po každé iteraci se sníží vzdálenost y od kořene o 1 • hloubka červeno černého stromu je 0(\ogn) • složitost RB_Rank je 0(\ogn) PRIDANÍ NOVÉHO UZLU přidání uzlu postupujeme od kořene do listu, kde vytvoříme nový uzel, přitom se změní (o 1) pouze velikost podstromů těch uzlů, kterými procházíme korekce stromu změna barvy uzlu nemění velikost podstromu při rotaci se může změnit velikost podstromů proceduru Left.Rotate doplníme o příkazy y.size <— x.size a x.size <— x.left.size + x.right.size + 1 Left_Rotate( 7, x) <- 216 ODSTRANĚNÍ UZLU odstranění uzlu ze stromu • na pozici odstraněného uzlu se přesune uzel y • pro aktualizaci hodnot s/ze 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 s/ze o 1 • složitost operace se navýší o 0(\ogn) 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á 217 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á ŕ 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ů • 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 se může pohybovat od jednotek po tisíce; cílem je minimalizovat počet přístupů na disk • existují různé varianty, podrobněji viz např. PV062 • Bayer, McCreight 1972 218 STUPEŇ B STROMU minimálni stupeň stromu je číslo ŕ, 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—l 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 219 VÝŠKA B STROMU všechny listy B stromu mají stejnou hloubku B strom s n > 1 klíči a minimálním stupněm t > 2 má hloubku nejvýše • kořen obsahuje alespoň jeden klíč, 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ň 2t2 uzlů hloubky 3, obecně alespoň 2th~ľ uzlů hloubky h h h-1 E 1=0 n > l + (ŕ-l)^2ť'-1 = = i+2(t-i)(^r) = 2th - 1 • z toho th <^ a tedy logŕ ŕ < logŕ ^ 720 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./ceyi, x./cey2, • • • , x./ceyx.n, 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, . . . , X.CX • klíče x.key; definují intervaly, z kterých jsou klíče uložené v každém z podstromů; jestliže k\ je klíč uložený v podstromě s kořenem x.q, tak platí k\ < x.keyi < k2 < x.key2 < ... < x.keyx.n < kx.n+i 221 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 • kořen B stromu je vždy uložený v operační paměti • asymptotická složitost všech operací je úměrná hloubce stromu, tj. (D(\ogn), 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 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 a hledaný klíč k jestliže klíč k je v B stromě, operace vrátí dvojici (y, /), kde y je uzel a / index takový, že y./cey/ = k v opačném případě vrátí hodnotu Nil vyhledání klíče R T.root Q.T.X B C F G J K L N P R S VW Y Z 223 B-Tree_Search(x, k) 1 i <- 1 2 while / < x.n A x.key; < k do 3 i <— i + 1 od 4 if / < x.n A x.key i = /c 5 then return (x, /) fi 6 if x.leaf then return A//7 7 else Disk_Read(x.q) 5 return B-Tree_Search(x.q, k) fi • počet Disk.Read operací je ohraničený hloubkou stromu h • počet opakování cyklu 2 - 3 je nejvýše 2t (t je minimální stupe stromu) • celková složitost je 0(th) — 0(t\ogtn) VYTVOŘENÍ PRÁZDNÉHO STROMU B-Tree_Create( 7) 1 x «- Allocate_Node() 2 x.leaf ^— true 3 x.n 4— 0 4 Disk_Write(x) 5 T .root «— x celková složitost operace 0(l) PRIDANÍ KLÍČE • podobně jako u BVS hledáme list, do kterého uložíme nový klíč • nemůžeme vytvořit nový list (jako u BVS), protože bychom porušili vlastnost minimálního počtu klíčů v uzlu • klíč vložíme do existujícího listu • když vložením klíče dojde k porušení vlastnosti maximálního počtu klíčů, tak list rozdělíme na dva nové listy • rozdělením se zvýší počet následníků předchůdce původního listu • pokud se tím poruší vlastnost maximálního počtu následníků, tak musíme (rekurzivně) rozdělit i předchůdce • proces rozdělování uzlů se v nej horším případě zastaví až v kořeni stromu 226 přidání klíče B do listu, který není plný, minimální stupeň stromu je 3 J K N 0 R S T U V Y Z GM_PX A B C D E J K NO R S T U V Y Z 227 přidání klíče Q do plného listu, minimální stupeň stromu je 3 JLMJLX A B C D E J K NO R S T U V Y Z G M P T X J K N 0 Q R S U V Y Z 228 rozdělení uzlu schéma, minimální stupeň stromu je 4 X X +• +• +• • N W • y = x.Cj | A/ S 1/1/ ••• y = x. c,- T T T P Q R S T U V p Q R \1 \ 1 \ t 1 f \ f V T U V H 1 Z X.C/+1 T T T T Ti 72 73 74 75 7g 77 7s 7i T2 T3 T4 75 7g T j Ts argumentem operace B-Tree_Split je • vnitřní uzel x, který není plný • index / takový, že x.c; je plný následník uzlu x 229 rozdělení kořene - schéma T .root T .root H A D F H L N P i V T T Ti 72 73 T4 T$ 7g T j Ts A D F 1 \ L N P H 1 Ti 72 73 T4 75 7g T j Ts • 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 230 B-Tree_Split(x, /) 1 z <- Allocate_Node() 2 y <— X.C; 3 z.leaf <— y.leaf 4 z.n <— t — 1 5 for j — 1 to t — 1 do z.keyj <— y.keyj+t od 6 if ^y.leaf then for j — 1 to t do z.cj «— yc/+t od fi 7 y.r? «— t — 1 ^ for y = x.n + 1 downto / + 1 do x.c/+i «— x.c7 od p x.c/+1 z i# for j = x.r? downto / do x.keyj+i ^- x.keyj od 11 x.keyj <— y.keyt 12 x.n 4— x.n + 1 13 DlSK_write(y) Disk_Write(z) i5 Disk_Write(x) 231 rozdělení uzlu - složitost • rozdělujeme uzel y (řádek 2) • když y není list, tak má před rozdělením 2t následníků a po rozdělení počet jeho následníků klesne na t • zje nový uzel (řádek 1) a jeho následníky tvoří t největších následníků uzlu y • celková složitost je 0(t) • počet operací Disk.Write a Disk.Read je 0(1) 232 PRIDANÍ KLÍČE - OPTIMALIZACE základní varianta • rozdělení uzlu způsobí navýšení počtu následníků předchůdce rozdělovaného uzlu • pokud se tím poruší vlastnost maximálního počtu následníků, tak musíme (rekurzivně) rozdělit i předchůdce • proces rozdělování se v nej horším případě zastaví až v kořeni stromu optimalizace • cílem je realizovat celou operaci přidání klíče při jednom průchodu stromu od kořene k listu (optimalizace počtu přístupů na disk!!!) • rozdělování může nastat pouze u těch uzlů, které jsou plné • vždy, když procházíme přes plný uzel, rozdělíme ho na dva nové uzly a to tak, že každý ze dvou nových uzlů dostane t — 1 klíčů a jeden klíč se přesune do jejich otce • korektnost postupu je garantována, protože předchůdce 233 rozdělovaného uzlu není plný přidání klíče L - procházíme přes plný uzel minimální stupeň stromu je 3 ,G M PJJ( A B C D E J K N O Q R S U J K L N 0 Q R S B-Tree_Insert(7, k) 1 r <— T.root 2 if r.n = 2t-l 3 then s <- Allocat_Node() 4 T.root <— s 5 s.leaf <— false 6 s.n <— 0 7 s.ci <— r 8 B-Tree_Split(s, 1) 9 B-Tree_Insert_Nonfull(s, k) 10 else B-TREE_lNSERT_nonfull(r, k) 11 fi řádky 3-9 řeší plný kořen stromu na konci se volá procedura B-Tree_Insert_Nonfull, která vloží klíč do stromu, jehož kořen není plný 235 B-Tree_Insert_Nonfull(x, k) 1 i «— x.n 2 if x.leaf 3 then while / > 1 A x. key; > k 4 do x./cey/+i x.key; 5 i <— i — 1 od 6 x./cey/+i «— /c 7 x.r? «— x.r? + 1 8 Disk_Write(x) 9 else while / > 1 A x.key; > k do i: i — 1 od iö / «— / + 1 í í Disk_Read(x.q) 12 if x.Cj.n = 2t—l then B-Tree_Split(x, /') í5 if x.key; < k then / ^— / -hl f i fi 14 B-Tree_Insert_Nonfull(x.q, k) 15 fi 236 přidání klíče — složitost • počet operací Disk_Write a Disk_Read je O(h) (vždy jenom jedna mezi dvěma voláními B-Tree_Insert_Nonfull ) • celková složitost je 0(th) — 0(t\ogtn) • 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í 237 ODSTRANĚNÍ KLÍČE • 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 (resp. předchůdce) odstraníme z listu ve kterém se původně nacházel samotné mazání klíče se vždy realizuje v listu 238 odstranění klíče k z listu x list x obsahuje alespoň t klíčů anebo je kořenem stromu • klíč k odstraníme odstranění klíče k z listu x list x není kořenem a obsahuje přesně t — 1 klíčů • po odstranění klíče k klesne počet klíčů v x pod minimum t — 1 • vezmi toho bratra y uzlu x, který má více klíčů • vytvoř seznam obsahující klíče z uzlů x a y a navíc ten klíč z otce p uzlu x, který tvoří hranici mezi x a y • jestliže seznam obsahuje alespoň 2t — 1 klíčů • seznam rozdělíme na 3 části: Left, Middle a Right, kde Middle je medián seznamu, /_e/r jsou klíče menší než medián a /?/£"/?£ 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 vložíme do uzlu x, klíče Right do y • uzly x a y mají alespoň t — 1 klíčů, počet klíčů v uzlu p zůstal nezměněný • jestliže seznam obsahuje 2t — 2 klíčů • uzly x a y nahradíme jediným uzlem obsahujícím všechny klíče seznamu • nový uzel 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, ^ ooakuieme (rekurzivně) oostuo oro uzel d ODSTRANĚNÍ KLÍČE - OPTIMALIZACE motivace • po odstranění klíče z listu může klesnout počet klíčů listu pod minimální hranici t — 1 • upravíme strom tak, aby každý uzel obsahoval alespoň t—1 klíčů • může nastat situace, že při úpravě stromu musíme projít od listu až ke kořeni stromu {napr. když všechny uzly na cestě od kořene do listu obsahujícího klíč mají stupeň přesně t) • podobně jako při vkládaní klíče optimalizujeme proces odstranění klíče tak, abychom minimalizovali počet přístupů na disk optimalizace • při vyhledávání klíče k, který má být odstraněn, postupujeme od kořene směrem dolů • 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 241 optimální odstranění klíče k - pravidla postupně přecházíme uzly stromu od kořene; nechť x je aktuální uzel případ 1 - x je list • jestliže strom neobsahuje klíč k tak ukonči výpočet • jestliže x obsahuje klíč k, odstraň k z listu x • jestliže x obsahuje předchůdce resp. následníka k! klíče k, tak nahraď klíč k klíčem k' a odstraň k' z listu x případ 2 - x je vnitřní uzel a obsahuje k • zapamatuj si uzel x; po dosažení listu klíč k nahradí jeho následník nebo předchůdce • nechť y (z) je syn uzlu x takový, že v podstromu s kořenem y (z) leží předchůdce (následník) klíče k • 2a jestliže y resp. z má alespoň ŕ klíčů, tak aktuální uzel se změní na y resp. z • 2b v opačném případě přesuň do uzlu y klíč k a všechny klíče z uzlu z, aktuální uzel se změní na y 242 optimální odstranění klíče k - pravidla, pokračování případ 3 - x je vnitřní uzel a neobsahuje k • nechť y je syn uzlu x takový, že k musí být v podstromu s kořenem y • 3a jestliže y obsahuje t — 1 klíčů a jeho pravý nebo levý bratr obsahuje alespoň t klíčů, tak zvyš počet klíčů v y a to tak, že přesuneš klíč z x do y, přesuneš klíč z bratra do y a přesuneš příslušný ukazatel na následníka z bratra do y • 3b jestliže y i jeho jeho pravý a levý bratr obsahují jen t — 1 klíčů, tak přesuň do y jeden klíč z x a všechny klíče z jednoho z bratrů • aktuální uzel se změní na y 243 odstranění klíče F — případ 1 minimální stupeň stromu je 3 A B D E F J K L N 0 Q R S U V Y Z C.G.M A B || DE || J K L || N 0\ \Q R S\\U V\\Y Z 244 odstranění klíče M — případ 2a minimální stupeň stromu je 3 A B D E J K N 0 Q R S\\U V\\Y Z 245 odstranění klíče G — případ 2b minimální stupeň stromu je 3 A B D E J K N 0 Q R S U V Y Z A B\\ D E J K\\ N 0\ | Q /? S || 1/ 1/|| V Z 246 odstranění klíče B — případ 3a minimální stupeň stromu je 3 A B E J K N 0 Q R S U V Y Z .E, L.PJX. A C J K N 0 Q R S U V Y Z 247 odstranění klíče Z - případ 3b minimální stupeň stromu je 3 ELPTX A C J K N 0 Q R S U V Y Z A C J K N 0 Q R S U V X Y 248 odstranění klíče D — případ 3b minimální stupeň stromu je 3 A B D E J K NO Q R S U V Y Z I CL.P.TX A B E J K N 0 Q R S U V Y Z CL.P.TX A B E J K N 0 Q R S U V Y Z 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 2a, 2b) • pro každý uzel se vykoná nanejvýš jedna operace Disk.Write a jedna operace Disk.Read • celková složitost operace je 0(th) — 0(t\ogt n) 250 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 251 HAŠOVANÍ SLOVNÍK dynamický datový typ pro reprezentaci množiny objektů s operacemi Insert(S,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 O(n) (r? je mohutnost množiny S) vyhledávací strom se dá použít za předpokladu, že objekty mají klíč, které se dají vzájemně porovnávat; při použití vyváženého stromu je složitost operací 0(\og n) cíl: složitost všech operací v nejhorším případě 0(r?) v očekávaném případě 0(1) 252 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 7[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í 253 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 U 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 255 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 0(|/^|) • složitost operací zůstává konstantní avšak v očekávaném (a ne v nejhorším) případě přímé adresování prvek x s klíčem k uloží v tabulce na pozici T[k] rozdíly hašování prvek x s klíčem k uloživ tabulce na pozici T[h(k)] • h je funkce h : U —> {0,1,... • h se nazývá hašovacífunkce m-1} 256 hašovací tabulka - problémy k řešení řešení kolizí kolize « dva anebo více klíčů zahašujeme na stejnou pozici pro x^y je h(x) = h(y), x a y mají stejný otisk • zřetězené hašování (chaining) • otevřená adresace (open adressing) výběr hašovací funkce • minimalizovat počet kolizí • efektivní výpočet funkce 257 VLASTNOSTI HAŠOVACÍCH FUNKCÍ problém ani nejlepší hašovací funkce negarantuje dobré chovaní 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 ze zvolené množiny hašovacích funkcí složitost volba množiny hašovacích funkcia způsob výběru hašovací funkce určují složitost (v nejhorším i očekávaném případě) jednotlivých operací 258 množina % hašovacích funkcí z U do {0,1,..., m — 1} je uniformní když pro uniformně vybranou funkci z % a každý klíč je pravděpodobnost zahašování klíče na každou z pozic tabulky stejná, 1 Pr^^Ahix) — i] = — pro každý klíč x a pozici / m univerzální když pro každou dvojici klíčů je pravděp. kolize co nejmenší 1 Pr^^Ahix) — h(y)] < — pro každou dvojici klíčů x^y m téměř univerzální 2 Pr^^Ahix) — h(y)] < — pro každou dvojici klíčů x^y m /c-uniformní když pro každých k vzájemně různých klíčů x±.... ,Xk z hodnot /'i,..., ik je pravděpodobnost kolize stejná k 1 Prhen[/\h{xi) = iA = -k m' HAŠOVANÍ ZŘETĚZENÉ HAŠOVÁNÍ ZŘETĚZENÉ 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)\ 260 zřetězené hašování — schéma 261 zřetězené hašování — složitost nechť /(x) označuje délku seznamu 7~[/7(x)] klíčů zahašovaných na pozici h(x) složitost v nej horším případě Insert konstantní (za předpokladu, že vkládaný prvek není v tabulce) Search konstantní složitost výpočtu h(x) plus konstantní složitost za každý prvek seznamu T[h(x)]1 celkově (9(1 + /(x)) Delete (asymptoticky) stejná jako složitost Search (za předpokladu dvousměrného seznamu) složitost v očekávaném případě záleží od výběru hašovací funkce 262 zřetězené hašování — očekávaná složitost • je úměrná očekávaná délce E[/(x)] seznamu 7~[/7(x)] • pro každou dvojici klíčů x,y nechť Cx?y je náhodní proměnná, Cx?y = 1 když h{x) = h{y) a Cx?y = 0 když h{x) ^ h{y) • délka seznamu je rovna počtu kolizí, /(x) = ^yer C*,y • když A? je vybraná uniformně z univerzální množiny hašovacích funkcí, tak 1 pro x — y E[Q,y] = Pr[Cx,y = 1] = { / l/m jinak E[/(x)] = ^ E[C,r] = £ i = £ yGT yeT hodnotu n/m nazýváme faktor naplnění, označujeme a pro téměř univerzální funkce je E[/(x)] < 2a místo seznamu můžeme použít jinou datovou strukturu, např. vyvážený binární vyhledávací strom HAŠOVANÍ PŘÍKLADY HAŠOVACÍCH FUNKCÍ METODA DĚLENÍ předpoklad: klíčem je číslo h(k) — k mod m výhody • rychlost nevýhody — závislost na volbě m • pro m — 2P je hodnota h(k) vždy p nejpravějších bitů z k • když k 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 příklad: m = 20, k = 91 /?(/c) = 11 264 METODA BINÁRNÍHO NÁSOBENÍ předpoklad: univerzum je U množina binárních čísel délky w předpoklad: velikost tabulky je mocninou dvojky, m — 2p cílem je zahašovat w-bitové čísla na p-bitové čísla pro zvolenou konstantu A, 0 < A < 1, hA(k) =[m (k A mod 1)J Množina funkcií /7/\,pro 0 < A < 1, je téměř univerzální. 265 metoda binárního násobení — postup výpočtu hodnoty h/\{k) — m [k A mod 1)J 1. vynásob klíč k konstantou A a ze součinu vezmi desetinnou část 2. výsledek vynásob číslem m a ze součinu vezmi celou část jestliže zvolíme A tvaru s/2w • vynásobíme čísla k a s • výsledkem násobení je 2w bitové číslo, kde r± je celočíselná část součinu kA 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 • protože 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 aq 266 metoda binárního násobení — příklad • w — 5, m — 8, i/i/ = 3 • hašujeme klíč k = 21 • vybíráme konstantu 0 < A < 1 tvaru s/2w, vybereme /4 = 13/32 /o4 = 21 • 13/32 = 8g výpočet /7/\(/c) podle vzorce /7/\(/c) = [m (k A mod 1)J li • /c/4 mod 1 = 17/32 • m(kA mod 1) = 8 • 17/32 = 4± • [m(kA mod 1)J = 4 = /?^(/c) implementace • ks = 21 • 13 = 273 = 8 • 25 + 17 • n = 8, ro = 17; bitový zápis ro je 10001 • vezmeme p = 3 nejvýznamnější bity ro, tj. 100 • M/0 = 4 267 METODA NÁSOBENÍ zvolíme prvočíslo p takové, že žádný klíč není větší než p pro libovolná čísla a G {1, 2,... p — 1} a b G {0,1,... p — 1} definujeme hašovací funkci předpisem hab(k) = ((a/c + b) mod p) mod m) • množina H = {hab: a G {1, 2,... p — 1}, b G {0,1,... p — 1}} je univerzálni množinou hašovacích funkcí presné 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 268 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°) 269 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í) 270 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á / je rovna pořadovému číslu testu • iniciální hodnota / 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 /?(/c, /) 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 2 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 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íč 273 otevřená adresace — výpočet sekvence sond nejčastěji se používají k výpočtu sekvence sond tři tech • lineární adresace (linear probing) • kvadratická adresace (quadratic probing) • dvojité hašování (double hashing) OTEVŘENÁ ADRESACE - LINEÁRNÍ využívá pomocnou hašovací funkci h' : U —> {0,1,..., m — 1} h(k, i) = {h'(k) + i) mod m • pro daný klíč je nejdříve prozkoumána pozice T[hf(k)]t pak pozice T[tí(k) + 1].....T[m - 1] a pak zase od T[0] až k Tlft^/c) - 1] • problémem je tzv. primární shlukování, které může výrazně zvýšit složitost operací 275 OTEVŘENÁ ADRESACE - KVADRATICKÁ využívá pomocnou hašovací funkci h' : U —> {0,1,..., m — 1} a pomocné konstanty ci, C2 ^ 0 /7(/c, /) = {h'{k) + cii + c2i2) mod m • pro daný klíč je nejdříve prozkoumána pozice T[hf(k)]t 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 hf(ki) = /7;(/c2), tak mají stejnou celou posloupnost sond - tzv. sekundární shlukování 276 OTEVŘENÁ ADRESACE - DVOJITÉ HAŠOVÁNÍ využívá dvě pomocné hašovací funkce /71, A?2 h(k, i) = (/?i(/c) + ih2(k)) mod m • pro daný klíč je nejdříve prozkoumána pozice T[hi(k)], následující pozice je posunuta o offset h2(k) mod m • hodnota h2(k) 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 h2 tak, že výsledkem bude vždy liché číslo, nebo • zvolit m jako prvočíslo a navrhnout h2 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 0(m) jako kvadratická adresace OTEVŘENÁ ADRESACE - SLOŽITOST Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a = n/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 použití uniformních hašovacích funkcí. Pro hašovací tabulku s otevřenou adresaci s faktorem naplnění a = n/m < 1 je očekávaný počet sond při úspěšném hledání nejvýše ^ In a to za předpokladu použití uniformních hašovacích funkcí. 278 HAŠOVANÍ KUKAČČÍHAŠOVÁNÍ KUKAČČÍ HAŠOVÁNÍ (CUCKOO HASHING) • pro hašování se používají dvě tabulky velkosti m a dvě hašovací funkce hi2 : U —> {0,1,... m — 1} • každý klíč k je zahašovaný buď na pozici /?i(/c) v první tabulce, anebo na pozici /?2(/c) 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 /?i(/c) • když je pozice /7i(/c)obsazena, tak klíč y uložený na pozici /?i(/c) přesuneme do druhé tabulky na jeho alternativní pozici /?2(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 - 14479 HAŠOVANÍ DOKONALÉ HAŠOVÁNÍ DOKONALÉ HAŠOVÁNÍ (PERFECT HASHING) • hašování, které má konstantní složitost i v nejhorším případě • předpokladem je statická množina klíčů • využívá dvě úrovně hašování první úroveň • zřetězené hašování • velikost tabulky je lineární vůči počtu klíčů 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 předpokladem pro dosažení konstantní složitosti je vhodný výběr hašovacích funkcí! Část IV Grafové algoritmy 281 PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST GRAF A JEHO REPREZENTACE graf G = (V, E) • orientovaný / neorientovaný • ohodnocené hrany / vrcholy • jednoduché / násobné hrany reprezentace grafu • 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) resp. 0(n + m) 282 MATICE SOUSEDNOSTI 12 3 4 11 0 1 1 0 2 10 10 3 110 1 4 0 0 1 0 12 3 4 11 0 1 1 0 2 0 0 0 0 3 0 10 0 4 0 0 1 0 matice A = (a,y) rozměrů \ V\ x \ V\, kde 3ij = 1 pokud (i J) G E 0 jinak prostorová složitost: Q(V2) vhodné pro husté grafy časová složitost výpisu všech sousedů vrcholu u je O(V) časová složitost ověření zda (u, v) G E je 0(1) 283 SEZNAM NÁSLEDNÍKŮ • pole Adj velikosti \ V\, seznam pro uložení všech následníků vrchola • prostorová složitost: Q(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 (l/, v) 6 E je 0(deg(u)) varianta: použít místo seznamu jinou datovou strukturu podporující vyhledávaní, vkládání a odebíraní, např. vyhledávací strom, hašovací tabulka 284 SROVNÁNÍ matice soused nosti seznam následníků hašovací tabulka test {u, v} G E O(V) 0(i) test (i/, v) G E 0(i) O(V) 0(i) seznam sousedů vrcholu v O(V) 0(1 + deg(v)) 0(1 + deg(v)) seznam hran 0(V2) 0{V + E) 0(V + E) přidání hrany 0(1) 0(1) 0(1)* odstranění hrany 0(1) O(V) 0(1)* * očekávaná složitost 285 PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST PRŮZKUM GRAFU PRŮZKUM GRAFU pro daný graf G a vrchol s 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) základní způsoby průzkumu grafu • do šírky • do hloubky jaké další informace o grafu zjistíme v průběhu průzkumu? 286 PRŮZKUM GRAFU DO HLOUBKY Theseus si před bludištěm uváže jeden konec nitě na strom a vstoupí dovnitř Na první křižovatce (vrcholu) 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 vrátí se do výchozího vrcholu. 287 Jakub Černý: Základní grafové algoritmy http://kam.mff.cuni.cz/~kuba/ka 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íku. Namotávání nitě při návratu zpět odpovídá odebrání vrcholu ze zásobníku. 288 PRŮZKUM GRAFU DO ŠÍŘKY 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. 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. Průzkum grafu do sirky a do hloubky se liší pouze použitím fronty a zásobníku. NE 290 PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST PRŮZKUM DO ŠÍŘKY PRŮZKUM DO ŠÍŘKY - STRATEGIE cílem je prozkoumat všechny vrcholy dosažitelné z daného vrcholu s • postupujeme od iniciálního vrcholu s po vrstvách • L0 = {s} • Li = všechny vrcholy, do kterých vede hrana z s • L-2 = všechny vrcholy, které nepatří do Lq ani do L\ a vede do nich hrana z vrcholu patřícího do L\ • = všechny vrcholy, které nepatří do žádné z předcházejících úrovní a vede do nich hrana z vrcholu patřícího do L\ implementace • použití fronty • atribut, který indikuje, zda vrchol již byl objeven (=vložen do fronty) 291 BFS(G,s) 1 foreach u G V \ {s} do u. visited <— false od 2 s. visited <— true 4 Enqueue(Q,s) 5 while Q ^ 0 do 6 u <— Dequeue(Q) 7 foreach v G /Ac//[u] do 8 if noi v. visited 9 then v. visited <— true 10 Enqueue(Q, v) fi 11 od 12 od 292 PRŮZKUM DO ŠÍŘKY - SLOŽITOST • operace vložení a odstranění vrcholu z fronty mají konstantní složitost, každý vrchol je ve frontě maximálně jednou; celkově O(V) • seznam následníků každého vrcholu se prochází maximálně jednou; průzkum hrany má konstantní složitost; celkově O(E) • inicializace má složitost O(V) • celková složitost BFS je O {V + E) 293 PRŮZKUM DO ŠÍŘKY - ATRIBUTY VRCHOLU V 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 vrchol v objeven v.d • délka (počet hran) cesty z s do v, na které byl v objeven 294 295 BFS(G,s) 1 foreach u e V \ {s} 2 do u.color <— white; u.d <— oc; u.tt <— Nil od 3 s.color 4— gray; s.d <— 0; s.tt <— Nil 4 5 Enqueue(Q, s) 6 while Q ^ 0 do 7 u 4— Dequeue(Q) 8 foreach v e /Ac//[l/] do 5 if v. co I or = w/7/te i0 then v.color <— gray n v.d <— u.d + 1 12 v.7t <— u is Enqueue(Q, v) fi 14 od 15 u. col or 4— black BFS A DÉLKA NEJKRATŠÍ CESTY Délka nej kratší cesty z s do v v neohodnoceném grafu, značíme 5(s, v), je definována jako minimální počet hran na cestě z s do v. Když neexistuje žádná cesta z s do v, tak 5(s, v) = oc. Nej kratší cestou z s do v je každá cesta z s do v která má 5(s, \/) hran. Nechť algoritmus BFS aplikujeme na graf G = (\/, E) a vrchol s6 I/. Pak po ukončení výpočtu pro každý vrchol v G V platí \/.c/ = 5(s, v) důkaz - viz Dijkstrův algoritmus 297 BFS STROM A NEJKRATŠÍ CESTY algoritmus BFS definuje přes atributy 7r graf předchůdců (BFS strom) pro graf G = (\/, E) a iniciální vrchol s je graf předchůdců Gtt = (W? En) definovaný předpisem Vn = {veV\ v.tt ŕ Nil} U {s} Ett = {(1/.7T, V) | v G \4 \ {s}} Pro každý vrchol v G Vn obsahuje BFS strom jedinou cestu z s do v, která je současně nej kratší cestou z s do v 298 BFS STROM A HRANY GRAFU Nechť G je orientovaný graf a s jeho vrchol. Pak po provedení BFS průzkumu grafu G z vrcholu s pro každou hranu (i/, v) grafu platí • v.d = u.d + 1 a hrana patří do BFS stromu • v.d = u.d + 1 a hrana nepatří do BFS stromu • v.d = l/. c/ • v.d < u.d Pro hrany neorientovaného grafu platí některá z prvních tří možností. BFS strom grafu není určen jednoznačně, závisí od pořadí, ve kterém zkoumáme následníky vrcholu BFS A GRAF S OHODNOCENÝMI HRANAMI namísto fronty použijeme prioritní frontu • do fronty vkládáme dvojici (vrchol; délka hrany, po které by objeven) • prioritou je délka hrany • z fronty vybíráme vrchol s nejmenší prioritou • BFS strom je nejlevnější kostrou grafu • Primův algoritmus • vrcholu ve frontě aktualizujeme hodnotu v.d pokaždé, když je po nějaké hraně objeven • prioritou je hodnota v.d • z fronty vybíráme vždy vrchol s nejnižší prioritou • BFS strom je strom nejkratších cest z s do ostatních vrcholů grafu • Dijkstrův algoritmus 300 podrobnosti o obou algoritmech pozděii APLIKACE A ALGORITMY VYUŽÍVAJÍCÍ BFS • Peer to Peer Networks • Crawlers in Search Engines • Social Networking Websites - hledání osob ve vzdálenosti nejvíce k • GPS navigační systémy • broadcasting • garbage collection • Fordův Fulkersonův algoritmus pro hledání maximálního toku v síti • testování bipartitnosti 301 PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST BIPARTITNI GRAFY BIPARTITNÍ GRAFY Neorientovaný graf se nazývá bipartitní právě když se jeho množina vrcholů dá rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy patřící do stejné množiny nejsou spojeny hranou. alternativní formulace: vrcholy grafu je možné obarvit dvěma různými barvami tak, že každé dva vrcholy spojené hranou mají různou barvu aplikace: vytváření dvojic, rozvrhu, .. . 302 BIPARTITNÍ GRAFY Neorientovaný graf se nazývá bipartitní právě když se jeho množina vrcholů dá rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy patřící do stejné množiny nejsou spojeny hranou. alternativní formulace: vrcholy grafu je možné obarvit dvěma různými barvami tak, že každé dva vrcholy spojené hranou mají různou barvu aplikace: vytváření dvojic, rozvrhu, .. . Bipartitní graf neobsahuje cyklus liché délky. 302 TESTOVANÍ BIPARTITNOSTI S VYUŽITÍM BFS • zvolíme libovolný vrchol grafu jako iniciální vrchol s • BFS průzkum z vrcholu s definuje vrstvy Lq? ^-i? ^-2? • • • • do vrstvy L; patří vrcholy, jejichž vzdálenost od s je / (t.j. v.d = /) žádné dva vrcholy patřící do stejné vrstvy nejsou spojeny hranou • obarvení vrcholů je určené vrstvami: vrcholy jejichž vzdálenost od s je sudá (lichá) mají modrou (červenou) barvu • korektnost obarvení plyne z předpokladu o neexistenci hrany mezi vrcholy ze stejné vrstvy existují dva vrcholy spojeny hranou a patřící do stejné vrstvy • necht u, v jsou vrcholy takové, že u, v G L; a {u, v} G E • necht y je nejmenší společný předchůdce vrcholů u, v v BFS stromu • cesta z y do u, hrana {u, v} a cesta z v do y tvoří cyklus, jehož délka je lichá, protože cesty z y do íí a z v do y mají stejnou délku 3( • graf není bipartitní PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST PRŮZKUM DO HLOUBKY PRŮZKUM GRAFU DO HLOUBKY- MOTIVACE pořadí, v němž BFS zkoumá vrcholy, netvoří souvislou cestu v grafu FORMULACE PROBLÉMU • průzkum do šírky a stejně tak i průzkum do hloubky je možné použít buď k prozkoumání té části grafu, která je dosažitelná z iniciálního vrcholu, anebo k prozkoumání celého grafu • průzkum se dá aplikovat na orientované i neorientované grafy • prezentace průzkumu do hloubky předpokládá, že • vstupem je orientovaný graf a • cílem je prozkoumat celý graf 305 PRŮZKUM DO HLOUBKY - STRATEGIE • na začátku výpočtu a vždy po dokončení průzkumu vybereme jeden z dosud neprozkoumaných vrcholů a zvolíme ho za nový iniciální vrchol • označ iniciální vrchol jako objevený • vyber neprozkoumanou hranu (l/, v), která vychází z naposledy objeveného vrcholu u, a když její koncový vrchol v ještě nebyl prozkoumán, tak ho označ jako objevený • když všechny hrany vycházející z naposledy objeveného vrcholu u byly prozkoumány, tak ukonči průzkum vrcholu u a pokračuj vrcholem, ze kterého byl vrchol u objeven • průzkum končí když jsou prozkoumány všechny vrcholy dosažitelné z iniciálního vrcholu • pro manipulaci s vrcholy používáme zásobník 306 PRŮZKUM DO HLOUBKY - ATRIBUTY VRCHOLU V v.color • v průběhu výpočtu je vrchol postupně objeven (je vložen do zásobníku) 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, tj. byly prozkoumáni všichni následníci vrcholu • 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 vrchol v objeven v.d • značka udávající čas první návštěvy (objevení) vrcholu (discovery time) • značka udávající čas ukončeni průzkumu vrcholu (finishing time) DFS(G) l foreach u G V do u.color ^- white; u.tt <— A/// o j8 t/me 0 5 foreach u G V do 4 if u.color = w/7/te then Dfs_Visit(G, u) fi od DFS_Visit(G,ü) 1 t/me «— t/rne + 1 2 u.d <— time 3 u. color <— gray 4 foreach v G Adj[u] do 5 if v.color — white then v.7r ü 6 Dfs_Visit(G, v) fi od 7 u.co I or 4— black 8 time time + 1 9 u.f <— time PRŮZKUM DO HLOUBKY - SLOŽITOST • oba cykly v DFS mají složitost O(V) • DFS-Visit se pro každý vrchol grafu volá jednou, protože bezprostředně po zavolání dostává vrchol šedivou barvu • každá hrana se v cyklu procedury DFS.Visit prozkoumá právě jednou; ostatní operace mají konstantní složitost • celková složitost DFS je O {V + E) 309 iterativní implementace DFS_Iterative_Visit(G, u) 1 S^0 2 S.push(u) 3 time time + 1; u.d <— time 4 u. co I or <— gray 5 while S 7^ 0 do 6 u i— S.popQ 7 if existuje hrana (u, v) taková, že v.color = white 8 then S.push(u) 9 S.push(v) 10 v.color <— gray 11 V.7V <— u 12 time ^- t/rne + 1; v.d <— time 13 else u.color <— b/ac/c ^ ř/rne «— ř/me + 1; u.f <— time fi DFS STROM • analogicky jako u BFS definují atributy .tt graf předchůdců • G^ = (V, Ett) = {(u.7T, i/) | V 6 1/ a v.7t NU} • protože prohledáváme celý graf, který nemusí být nutně souvislý, graf předchůdců je DFS les, který se skládá z DFS stromů 311 DFS- VLASTNOSTI ČASOVÝCH ZNAČEK • časové značky, které DFS přiřadí vrcholům grafu, obsahují informace o struktuře grafu a DFS stromů • pro každý vrchol u platí u.d < u.f • s každým vrcholem u je asociovaný interval [u.d, u.f] • časové značky určují uspořádání vrcholů preoder uspořádání podle značky .d (discovery time) v rostoucím pořadí postorder uspořádání podle značky .f (finishing time) v rostoucím pořadí reverse postorder uspořádání podle značky .f v klesajícím pořadí 312 vlastnosti časových značek podmínky správného uzávorkování pro každé dva vrcholy u, v platí právě jedna z podmínek • intervaly [u.d, u.f] a [v.d, v.f] jsou disjunktní u není následníkem v v DFS stromu a symetricky v není následníkem u v DFS stromu • interval [u.d, u.f] je celý obsažen v intervalu [v.d, v.f] u je následníkem v v DFS stromu • interval [v.d, v.f] je celý obsažen v intervalu [u.d, u.f] v je následníkem u v DFS stromu 313 vlastnosti časových značek dosažitelnost vrchol v je dosažitelný z vrcholu u v DFS stromu grafu G právě když u.d < v.d < v. f < u. f vlastnost bílé cesty v DFS stromu grafu G je vrchol v je dosažitelný z u právě když v čase u.d existuje cesta z u do v obsahující jenom bílé vrcholy 314 vlastnosti časových značek — klasifikace hran stromová hrana {tree edge) je hrana (u, v) obsažená v DFS lese při průzkumu hrany je vrchol v bílý u.d < v.d < v.f < u.f zpětná hrana [back edge) je hrana (u, v), která spojuje vrchol u s jeho předchůdcem v v DFS stromu, nebo smyčka při průzkumu hrany je vrchol v šedivý v.d < u.d < u.f < v. f dopředná hrana ( forward edge) je hrana (u, v), která nepatří do DFS stromu a která spojuje vrchol u s jeho následníkem v DFS stromu při průzkumu hrany je vrchol v černý u.d < v.d < v.f < u.f příčná hrana (cross edge) všechny ostatní hrany při průzkumu hrany je vrchol v černý v.d < v.f < u.d < u.f všechny hrany v neorientovaném grafu jsou buď stromové anebo zpětné (s (z (y (x x) y)(w w) z) s) (ŕ (v v) (u u) t) stromové hrany jsou zvýrazněné, zpětné hrany jsou označeny písmenem B, dopředně písmenem F a příčné písmenem C 316 APLIKACE A ALGORITMY VYUŽÍVAJÍCÍ DFS • topologické uspořádání • komponenty souvislosti • artikulace a mosty • testování planarity • hledání cesty v bludišti • generování bludiště 317 PRŮZKUM GRAFŮ A GRAFOVÁ SOUVISLOST TOPOLOGICKÉ USPOŘÁDÁNÍ TOPOLOGICKÉ USPOŘÁDÁNÍ VRCHOLŮ GRAFU Topologické uspořádání vrcholů orientovaného grafu je takové očíslování vrcholů čísly 1 až n (n je počet vrcholů grafu), že každá hrana grafu vede z vrcholu s nižším číslem do vrcholu s vyšším číslem. otázky • existuje v daném grafu topologické uspořádání? • jak najít topologické uspořádání? 318 Orientovaný graf G má topologické uspořádání právě když je acyklický. =4> existence topologického uspořádání implikuje acykličnost <^= acyklický graf má topologické uspořádání • tvrzení platí pro n = 1 • předpokládejme platnost pro všechny grafy s k < n vrcholy • nechť G má r? vrcholů • v G 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) • graf G \ v, který vznikne z G odstraněním vrcholu v, je acyklický a má n — 1 vrcholů • dle indukčního předpokladu má G \ v topologické uspořádání • topologické uspořádání vrcholů grafu G má na prvním místě vrchol v následovaný topologickým uspořádáním vrcholů grafu G \ v 319 naivní algoritmus Topological_Sort_Visit( G) i n V 2 for / = 1 to n do 3 v <— libovolný vrchol, do kterého nevstupuje žádná hrana 4 S[i] v 5 odstraň z G vrchol v a všechny jeho hrany 6 od 7 return S[l... r?] • algoritmus předpokládá, že graf je acyklický • nalezení vrcholu do kterého nevstupuje žádná hrana má složitost ? • celková složitost algoritmu je ? existuje efektívnejší algoritmus (ideálně s lineární složitostí)? 320 Orientovaný graf G je acyklický právě když DFS průzkum grafu neoznačí žádnou hranu jako zpětnou. =4> zpětná hrana (u, v) spojuje vrchol u s jeho předchůdcem v v DFS stromu, tj. uzavírá cyklus <^= necht žádná hrana není zpětná • předpokládejme, že v grafu existuje cyklus c, necht v je první vrchol cyklu c navštívený při DFS průzkumu grafu a necht (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 — spor 321 TOPOLOGICKÉ USPOŘÁDÁNÍ — ALGORITMUS 1. aplikuj DFS na G 2. když průzkum označí některou hranu jako zpětnou, tak graf nemá topologické uspořádání 3. v opačném případě vypiš vrcholy v uspořádání reverse postorder, tj. podle značky .f (finishing time) v klesajícím pořadí 322 korektnost potřebujeme dokázat, že pro libovolnou dvojici vrcholů u, v platí jestliže G obsahuje hranu (l/, v), tak u.f > v.f jaké jsou barvy vrcholů u a v při průzkumu hrany (l/, v)? • vrchol l/ je šedivý • vrchol v je šedivý nemůže nastat, protože (l/, v) by v takovém případě byla zpětnou hranou a graf by nebyl acyklický bílý v takovém případě je (l/, 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 323 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 ^ vt právě když v G existuje orientovaná cesta z u do v • Reach(u) je množina všech vrcholů dosažitelných z u • vrcholy u a v jsou silně dosažitelné {strongly connected) právě když u je dosažitelný z v a současně \/ je dosažitelný z ü • silně souvislá komponenta grafu je maximální množina vrcholů C C V taková, že pro každé u,v E C platí u ^> v a současně v ~> u • graf nazýváme silně souvislý právě když má jedinou silně souvislou komponentu jak najít všechny silně souvislé komponenty grafu? 324 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 v neorientovaném grafu můžeme použít BFS nebo DFS • jednotlivé DFS (BFS) stromy korespondují s komponentami souvislosti • složitost 0(V + E) 325 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,u) • najdi množinu Reach~ľ(u) všech vrcholů, ze kterých je dosažitelný u • pro výpočet Reach~ľ(u) využijeme transponovaný graf rev(G), na který aplikujeme DFS_Visrr(re\/(G), u) • silně souvislá komponenta obsahující u je průnikem množin Reach(u) n Reach~ľ(u) • časová složitost výpočtu je 0(V + E) transponovaný graf rev(G) = (V, rev(E)) je graf G s obrácenou orientací hran, rev(E) = {(x,y) | (y,x) G E} 326 výpočet všech silně souvislých komponent orientovaného 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 0(V • E) existuje efektivnější algoritmus, optimálně s lineární časovou složitostí ? 327 KOMPONENTOVÝ GRAF • komponentový graf (graf silně souvislých komponent, scc(G) ) je orientovaný graf, který vznikne kontrakcí každé silně souvislé komponenty grafu do jednoho vrcholu a kontrakcí paralelních hran do jedné hrany • scc(G) je orientovaný acyklický graf, jeho vrcholy můžeme topologicky uspořádat • kořenem grafu scc(G) nazýváme vrchol do kterého nevstupuje žádná hrana; kořenu grafu scc(G) odpovídá kořenová silně souvislá komponenta grafu G • listem grafu scc(G) nazýváme vrchol ze kterého nevystupuje žádná hrana; listu grafu scc(G) odpovídá listová silně souvislá komponenta grafu G • komponentový graf transponovaného grafu rev(G) je práve transponovaný graf rev(scc(G)) kořenová komponenta A listové komponenty D, GHIJK • z vrcholu u listové silně souvislé komponenty C jsou dosažitelné právě a pouze vrcholy z C • DFS průzkum z u navštíví všechny vrcholy z C a žádné jiné; na tomto pozorování můžeme postavit algoritmus pro detekci komponent • potřebujeme (efektivně) najít vrchol patřící listové komponentě • využijeme fakt, že listová komponenta grafu G je kořenovou komponentou grafu rev(G) • pro hledání kořenové komponenty využujeme fakt, že vrchol s nejvyšší časovou značkou .f leží v kořenové komponentě; tento fakt je důsledkem obecnějšího pozorování 330 Necht Ci a C2 jsou silně souvislé komponenty takové, že z C\ vede hrana do C2. Potom nej větší hodnota .ŕ v komponentě C\ je větší než nej vě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 C\ • 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 pak se teprve vrátí do v 331 ALGORITMUS KOSARAJU SHARIR vstup: orientovaný graf G{V, E) výstup: silně souvislé komponenty grafu G 1. prozkoumej graf G průzkumem do hloubky 2. uspořádaj vrcholy grafu G podle časové značky .f v klesajícím pořadí (reverse postorder) 3. dokud graf G není prázdný • nechť v je vrchol s nejvyšší časovou známkou .f v G • v transponovaném grafu rev(G) průzkumem do hloubky najdi množinu C všech vrcholů dosažitelných z v • vrcholy množiny C tvoří silně souvislou komponentu grafu G • odstraň vrcholy C z grafu G 332 Kosaraju_Sharir(G(\/, E)) 1 foreach u e V do u.color <— white od 2 foreach i/g V do if u.color = w/7/te then Push_DFS(G, ü) fi o 3 foreach u e V do u.color <— white od 4 count «— 0 5 while S 7^ 0 do 0 ü i— S.popQ 7 if u.color = w/7/te then count ^- count + 1 5 label_DFS(/?e\/(G), count) fi 5 od Push_DFS(G,u) 1 u.color <— gray 2 foreach v G Adj[u] do 3 if v.color = white then Push_DFS(G, v) fi 4 od 5 u. co I or 4— black 6 S.push(u) Label_DFS(G, u, count) 1 u.color <— gray 2 foreach v G Adj[u] do 3 if v.color = w/7/te then Label_DFS(G, v, count) 4 od 5 u. co I or 4— black 6 u.label ^- coi/r?t algoritmus Kosaraju Sharir má časovou složitost 0(V + E) další algoritmy lineárni časové složitosti pro dekompozici grafu na silně souvislé komponenty: Tarjan, Gabow 335 NEJKRATŠÍ CESTY NEJKRATSI CESTY FORMULACE PROBLÉMU NEJ KRATŠÍCH CEST CESTA V GRAFU cesta v grafu G = (V, E) je posloupnost vrcholů p = (vq, vi, ..., v^} taková, že v\) G E pro / = 1,..., k jednoduchá cesta je cesta, která neobsahuje dva stejné vrcholy terminologie cesta jednoduchá cesta path simple path walk path sled cesta v je dosažitelný z u (značíme u ^ v) právě když existuje cesta p = (vq, ví, ..., Vk) taková, že vq = u a = v 336 DÉLKA CESTY graf G — (\/, E), váhová funkce {ohodnocení, délka hran) w : E —>> K. délka cesty p = (vq, ví,..., v^) je součet délek hran cesty, k i=i délka nejkratší cesty z vrcholu u do vrcholu \/je definovaná předpisem def I min{w(p) | p je cesta z l/ do v} když u-wi/ oc jinak nejkratší cesta z u do v ]e libovolná cesta p z u do v t.ž. i/i/(p) = 8(u, v) pro neohodnocené grafy se délka cesty definuje jako počet hran cesty 337 VARIANTY PROBLÉMU NEJKRATŠÍ CESTY nejkratší cesty z daného vrcholu do všech vrcholů tato přednáška single source shortest path, SSSP 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ů tato přednáška speciální případ SSSP, nejsou známy asymptoticky rychlejší algoritmy než pro SSSP nejkratší cesty mezi všemi dvojicemi vrcholů ADS II řešení opakovanou aplikací algoritmu pro SSSP existují efektivnější algoritmy nejdelší, nejširší, nejspolehlivější ... cesty viz literatura 338 ALGORITMY PRO SSSP - ORIENTOVANÉ GRAFY neohodnocený graf průzkum do šírky, BFS acyklický graf relaxace hran respektující topologické uspořádáni graf s nezáporným ohodnocením hran Dijkstrův algoritmus a jiné obecný graf algoritmus Bellmana Forda a jiné 339 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í nejlevně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 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 341 NEJKRATŠÍ CESTA VS NEJKRATŠÍ JEDNODUCHÁ CESTA graf obsahuje hrany záporné délky • cyklus (fo, 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, 5(x,y) = —oo v případě, že graf obsahuje hrany se zápornou délkou, problém nejkratší cesty je formulovaný jako úloha rozhodnout, zda graf obsahuje cyklus záporné délky a když ne, tak najít nejkratší (jednoduchou) cestu 342 VLASTNOSTI N EJ KRATŠÍCH CEST Každá podcesta nejkratší cesty je nejkratší cestou. • necht p je nejkratší cesta z u do v w(p) = w(pux) + w(pxy) + Pux Pxy Pyv • předpokládejme, že existuje kratší cesta z x do y, w(prxy) < w(pxy) i . . / Pux Pxy Pyv • zkonstruujeme novou cestu p—u^x^y-^v w{p') = w{pux) + w{p'xy) + w{pyv) = w(p) což je spor s předpokladem, že p je nejkratší cesta z u do v 343 NEJKRATŠÍ CESTY GENERICKÝ SSSP ALGORITMUS REPREZENTACE NEJKRATŠÍCH CEST otázka efektivní reprezentace nejkratších cest z daného vrcholu do všech vrcholů grafu strom nejkratších cest pozor na rozdíl mezi stromem nejkratších cest a nej levnější kostrou grafu! 344 reprezentace stromu nejkratších cest z vrcholu s atribut vzdálenost, v.d distance • iniciální nastavení v.d = oc • hodnota v.d se v průběhu výpočtu snižuje • hodnota v.d je horním odhadem délky nejkratší cesty, v.d > 5(s, v) • na konci výpočtu je v.d = 5(s, v) atribut předchůdce, v.tv parent • 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.tv předchůdce vrcholu v na nejkratší cestě z s do v, resp. v.tv = Nil když neexistuje cesta z s do v 345 graf předchůdců Gp — (Vp, Ep) je definovaný hodnotami .71 Vp = {veV\ v.tt 7^ A///} U {s} Ep = {(v.tt, v) | v G Vp \ {s}} strom nej kratších cest na konci výpočtu je Gp stromem nej kratších cest • s je kořen stromu, Vp je množina vrcholů dosažitelných z vrcholu s • pro každý vrchol v G Vp, (jediná) cesta z s do v v Gp je nejkratší cestou z s do v v G 346 RELAXACE • technika, kterou využívají algoritmy pro hledání nejkratších cest • relaxací hrany (l/, v) rozumíme test, zda je možné zkonstruovat kratší cestu do v tak, že projedeme přes vrchol u • když aktuálně známá cesta do vrcholu u prodloužená o hranu (l/, v) je kratší než aktuálně známá cesta do v (u.d + w(u, v) < v.d), tak jsme našli novou, kratší, cestu do v a podle toho aktualizujeme hodnoty v.d a v.tt (v.d ^- u.d + w(u, v) a v.tt <— u ) • hranu (l/, v) nazýváme napjatou právě když u.d + w(u, v) < v.d 347 generický SSSP algoritmus Init_SSSP(G,s) 1 foreach v G V do v.d <— oc; v.tt <— Nil 2 s.d <- 0 Relax(l/, v, i/i/) 1 \/.c/ <— u.d + w(u, v) 2 v.tt <— u Generic_SSSP(G, w, s) 1 Init_SSSP(G,s) 2 S <— s 3 while S 7^ 0 do 4 vyber u z S 5 foreach (u, v) G E do 6 if v.d > u.d + w(u, v) 7 then Relax(l/, v, w) 8 S^SU {v} fi od od KOREKTNOST GENERICKÉHO SSSP ALGORITMU • pro každý vrchol v platí, že hodnota v.d je buď oc, anebo je rovna délce nějaké cesty z s do v důkaz indukcí na počet relaxací • když graf neobsahuje cyklus záporné délky, tak hodnota v.d je buď oc, anebo je rovna délce nějaké jednoduché cesty z s do v důsledek: generický algoritmus pro graf bez záporných cyklů skončí, protože v grafu existuje jenom konečný počet jednoduchých cest • když žádná hrana grafu není napjatá, tak hodnota v.d je rovna délce cesty s v.tt.tt —> v.tt —> 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 ^ 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 .d) • v jakém pořadí budeme prozkoumávat vrcholy z množiny S 350 NEJKRATŠÍ CESTY ALGORITMUS BELLMANA A FORDA ALGORITMUS BELLMANA A FORDA • algoritmus pro hledání nejkratších cest z daného vrcholu s do všech vrcholů grafu • graf může obsahovat hrany záporné délky • algoritmus vráti hodnotu falše právě, když graf neobsahuje cyklus záporné délky dosažitelný z vrcholu s • v opačném prípade vráti hodnotu true a vypočítá nej kratší cesty • algoritmus je založený relaxaci hran • vždy, když vrcholu u zlepšíme hodnotu u.d, tak relaxujeme všechny hrany vycházející z vrcholu u • pro přehlednost rozdělujeme výpočet do iterací; v jedné iteraci se relaxují všechny hrany grafu 351 Bellman-Ford(G, i/i/, s) 1 Init_SSSP(G,s) 2 for / = 1 to I V\ — 1 do 5 foreach (l/, i/) G F do 4 if u.c/ > l/.c/ + w(u, v) then Relax(l/, v, w) fi 5 od 6 od 7 foreach (i/, v) £ E do 5 if \/.cř > i/.c/ + w(u, v) then return Fa/se fi 9 od í0 return True optimalizace: • jestliže v iteraci for cy/c/i/ v řádcích 2-6 nebyla nalezena žádná napjatá hrana, výpočet můžeme ukončit s návratovou hodnotou True • hranu (u, v) relaxujeme v iteraci i + 1 pouze pokud v iteraci i byla změněna hodnota u.d 352 (a) (b) (c) (d) graf G p (e) hledáme nejkratší cesty z vrcholu a v každé iteraci cyklu algoritmu relaxujeme hrany v pořadí (c, e), (c/, e), (b, c/), (c, d), (b, c), (a, c), (a, b) barevně jsou vyznačeny hrany grafu předchůdců G, 353 korektnost algoritmu Bellmana a Forda 1 Když graf G obsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vrátí hodnotu Falše. • nechť c = (vq, ví? • • • ? ^/c}> = v/c je cyklus záporné délky dosažitelný z s, u/) < 0 • předpokládejme, že algoritmus vrátí hodnotu True, tj. pro každou hranu cyklu platí v,.d < v7_1.cZ + v i) • sumací přes všechny vrcholy cyklu k k k k ^2 ví'd - ^2(vi-i-d+w(ví-i> vi)) = ^2 vi-i-d+^2 w(vi-i> vi) í=i í=i í=i í=i • __?=i vi-i-d = __?=i vi-d Protože v0 = vk • 0 < __?=i w(ví-i> vi) • spor s předpokladem o délce cyklu c 354 korektnost algoritmu Bellmana a Forda 2 Pro každý vrchol v platí 1. v.d je délka nějaké cesty z s do v 2. hodnota v.d neroste 3. po / iteracích platí, že v.d < délka nejkratší cesty z s do v obsahující nejvýše / hran důkaz tvrzení 3 indukcí vzhledem k / • tvrzení platí pro / = 0 • předpokládejme platnost po iteraci / • nechť p je cesta z s do v mající nejvýše < / + 1 hran • nechť (x, v) je poslední hrana p a nechť p je podcesta p z s do x • dle indukčního předpokladu po iteraci / platí x.d < w(p) • po relaxaci hrany (x, v) v iteraci / + 1 platí v.d < w(x. v) + l/l/(p) = i/i/(p) 355 korektnost algoritmu Bellmana a Forda 3 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak algoritmus vrátí hodnotu True a pro každý vrchol v platí v.d = 5(s, v). • z neexistence cyklu záporné délky plyne existence jednoduché nej kratší cesty • rovnost v.d = 5(s, v) je důsledkem vlastnosti 3 • po ukončení výpočtu platí pro každou hranu (l/, i/)gF = u.d + w(u, v) t.j., žádná hrana není napjatá a test na řádku 8 nevrátí hodnotu Falše 356 korektnost algoritmu Bellmana a Forda 4 V průběhu výpočtu algoritmu ukazatele .7r určují orientovanou cestu z s do v délky v.d. NEPLATÍ 357 korektnost algoritmu Bellmana a Forda 5 Orientovaný cyklus C v grafu předchůdců Gp má zápornou délku. • z v.tt = u plyne v.d > u.d + w(u, v) • nechť c = (vi,..., v^, vi) je orientovaný cyklus v grafu Gp a nechť (^7o ui) Je ta hrana cyklu, která byla do Gp přidána jako poslední • bezprostředně před přidáním hrany (v^, v\) do Gp platilo V2.d > v\.d + w(v\, V2) v$.d > V2.d + w(v2, V3) vk.d > vk_i.d + w(vk_i, vk) v\.d > vk.d + w(vkl v\) • sečtením nerovností dostáváme w{y\, V2) + 1/1/(^2, V3) + ... + w(vk, v\) < 0 358 korektnost algoritmu Bellmana a Forda 6 Když graf G neobsahuje cyklus záporné délky dosažitelný z s, tak po ukončení výpočtu graf předchůdců Gp obsahuje nej kratší cesty. • Gp neobsahuje cyklus • pro každé v, ukazatele .7r jednoznačně určují cestu (v±,..., vk) kde v\ — s a vk = v • po ukončení výpočtu žádná hrana není napjatá, t.j. v2.d = v\.d + w(v\, v2) v3.d = V2.d + w(v2, V3) vk.d = vk-\.d + w(vk-i, vk) • sečtením rovností dostáváme v.d = vk.d = s.d + w(vi, v2) + w(v2, v3) + ... + w(Vk-l, Vk) 359 složitost algoritmu Bellmana a Forda • inicializace má složitost 0(V) • relaxace hrany má konstantní složitost • cyklus 3 - 5 má složitost 0(E); počet jeho opakování je V — 1 • celková složitost je 0(VE) jiný zápis: O(mn), kde n je počet vrcholů a m je počet hran grafu existuje efektivnější řešení? lehce najdeme graf a takové pořadí relaxace jeho hran, pro které je nutných V — 1 iterací • otázka vhodného pořadí relaxace hran • vhodné pořadí hran dokážeme určit pro speciální typy grafů • acyklické grafy • grafy bez záporných hran 360 NEJKRATŠÍ CESTY ACYKLICKÉ GRAFY NEJKRATŠÍ CESTY V ORIENTOVANÉM ACYKLICKÉM GRAF • optimálně pořadí relaxace hran v Bellmanově - Fordově algoritmu je takové, že vždy relaxujeme hranu (l/, v) pro kterou u.d = 5(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(l/, v, w) fi 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ě 362 NEJKRATŠÍ CESTY DIJKSTRŮV ALGORITMUS 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 363 Dijkstra(G, i/i/, s) 1 Init_SSSP(G,s) 2 S u.d + w(u, v) then Relax(l/, v, i/i/) fi 9 od i0 od • S je množina vrcholů, pro které je již vypočtena délka nej kratší cesty • Q je prioritní fronta, Q = V \ S • algoritmus vybírá vrchol u G Q s nejmenší hodnotou u.d a relaxuje hrany vycházející z u 364 DIJKSTRŮV ALGORITMUS - PŘÍKLAD x vrcholy se přidávají do množiny S v pořadí s,y,z,x korektnost Dijkstrova algoritmu Invariant: Na začátku iterace while cyklu platí v.d = 5(s, v) pro všechny vrcholy v £ S. inicializace na začátku S = 0 a tvrzení platí triviálně ukončení na konci Q = 0, tj. S = V a v.d = 5(s, v) pro všechny v £ V iterace máme prokázat, že když l/ přesuneme do S, tak l/.c/ = 5(l/.s) • když u není dosažitelný z s tak l/.c/ = 5(s, ív) = 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^íitak, že bezprostředně před zařazením u do S všechny vrcholy cesty pi patří do S a y 0 S • x G S =^> x.c/ = 5(s, x) • při zařazení x do S byla relaxovaná hrana (x, y), s^x-^yje nejkratší cesta do y =^> y.c/ = 5(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) 366 složitost Dijkstrova algoritmu ©(V) operací insert (do prioritní fronty přidá nový objekt) ©(V) operací extract_MlN ( z fronty odstraní objekt s minim, klíčem) 0(E) operací decrease_key (objektu v prioritní frontě sníží hodnotu klíče) složitost algoritmu závisí od implementace prioritní fronty Q pole složitost Q(V • V + E • 1) = Q(V2) Insert 0(1), Extract_Min ©(V), Decrease_Key 0(1) binární halda složitost 0( V log V + E log V) Insert 0(log V), Extract_Min 0(log V), Decrease.Key ©(log V) Fibonacciho halda složitost Q (V log V + E) Insert 0(1), Extract.Min 0(log V), Decrease_Key 0(1) 368 NEJKRATSI CESTY NEJKRATŠI CESTA MEZI DVĚMA VRCHOLY OPTIMALIZACE DIJKSTROVA ALGORITMU pro hledání nejkratší cesty mezi dvěma vrcholy s a ŕ optimalizace 1 • výpočet ukončíme když vrchol t odebereme z prioritní fronty 369 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 .7it> • výpočet ukončíme když nějaký vrchol w je odstraněn z obou front Qf a Qb • po ukončení najdeme vrchol x s minimální hodnotou x.df + x.dt> (pozor, nemusí to být vrchol w) • využitím atributů .717 a .7it> najdeme nejkratší cestu z s do x a nejkratší cestu z x do ŕ; jejich spojením dostaneme nejkratší cestu z s do ŕ imalizace 3 - heuristika A pokud bychom dovedli spolehlivě zjistit, že nejkratší cesta z s do ŕ nepovede přes vrchol v, mohli bychom zpracování vrcholu v a hran s ním incidentních přeskočit =4> 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 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? heuristika A přípustný potenciál Potenciál je přípustný právě když pro každou hranu (i/, v) e E splňuje podmínku h(u) < w(u, v) + h(v) a pro vrchol t platí h{t) — 0. Pro libovolnou cestu p = (vq = u, v\,..., vk = ť) z u do t a přípustný potenciál platí k-i i=0 > h(v0) - h(vľ) + h(vľ) - h{v2) + ... + h(vk_ľ) - h{vk) = h(u) - h(t) = h(u) t.j. potenciál vrcholu u je dolním odhadem délky cesty z u do ŕ 372 heuristika A úprava ohodnocení grafu pomoci potenciálu • vytvoříme nové ohodnocení grafu w' : E —>> IR, které definujeme jako • když A? 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 ŕ platí a potenciálový rozdíl mezi s a ŕ je pro všechny cesty z s do ŕ stejný w(u, v) — h(u) + h(v) w\p) w(p) + h{t) - h(s) 373 • 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 ŕ; čí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 i/i/(x,y) > h(x) — h(y), Dijkstrův algoritmus s heuristikou je korektní důkaz probíhá analogicky jako pro Dijkstrův algoritmus 374 DIJKSTRŮV ALGORITMUS A OBECNÉ GRAFY modifikace Dijkstrova algoritmu jestliže se vrcholu u, který již byl odebrán z prioritní fronty, změní hodnota u.d, tak vrchol u znovu vložíme do prioritní fronty pro graf, ve kterém hrany mohou mít zápornou délku • jestliže z počátečního vrcholu není dosažitelný cyklus záporné délky, tak modifikovaný Dijkstrův algoritmus najde korektní řešení, ale složitost výpočtu je v nejhorším případě až exponenciální vůči velikosti grafu • jestliže z počátečního vrcholu je dosažitelný cyklus záporné délky, tak výpočet modifikovaného Dijkstrova algoritmu je nekonečný 375 NEJKRATŠÍ 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 IR", který optimalizuje hodnotu účelové funkce X)ľ=i C/X/ P^' SP'nění ohraničení >Ax < b příklad minimalizovat — 2xi — 3x2 — X3 při splnění ohraničení —x\ — X2 — X3 < 3 3xi + 4x2 - 2x3 < 10 2xi - 4x2 < 2 4xi — X2 + X3 < 0 xi,x2,x3 >0 přípustné řešení (0, 0, 0) optimální řešení (0, 5, 5) 376 motivace • mnoho problémů dokážeme vyjádřit jako úlohu lineárního programování (napr. 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í 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 nerovnic je příkladem takovéto speciální úlohy • ukážeme algoritmus založený na SSSP 377 PROBLÉM LINEÁRNÍCH NEROVNIC • je daná množina nerovnic tvaru x — y < b, kde x, y jsou proměnné a b je konstanta • úkolem je najít takové hodnoty proměnných, 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 *i ~~ x2 < 5 xi — X3 < 6 X2 — X4 < — 1 x3 - x4 < -2 X4 — xi < —3 přípustné řešení x = (0, —4, —5, —3) 378 graf lineárních nerovnic pro danou množinu M lineárních nerovnic nad proměnnými xi,... ,xn definujeme orientovaný graf G = (\/, E) • V = {\/o, ví, . . . , vn} (jeden vrchol pro každou proměnnou plus vrchol vq) • E = {(v;, Vj) | -x/ vn)) 2. když G má cyklus záporné délky, tak systém nemá přípustné řešení. zdůvodnění — část 1. • neexistence cyklu záporné délky implikuje, že pro každou hranu (v,-, vj) grafu platí 5(vo,vj) < 5(vo, v i) + w{vt, vj) • hraně (v,-, vj) odpovídá nerovnost xj — x\ < w{y-n vj), která je pro hodnoty x\ — 5(vq, v i) a xj = 5(vq, vj) splněna 380 zdůvodnění — část 2. • nechť c = (vi, ..., v^}, kde v\ — vk, je cyklus záporné délky • hrany cyklu c odpovídají nerovnostem X3-X2 < w(v2,v3) přípustné řešení x musí splňovat všechny tyto nerovnosti po sečtení všech nerovností dostaneme 0 < i/i/(c), což je spor s předpokladem o záporné délce cyklu c algoritmus pro problém lineárních nerovnic 1. vytvoř graf lineárních nerovnic • n + 1 vrcholů • m + n hran • časová složitost 0(m + n) 2. najdi nej kratší cesty z vrcholu vq algoritmem Bellmana a Forda • časová složitost 0((n + l)(m + n)) = 0(n2 + nm) 3. když algoritmus vrátí hodnotu Falše, tak problém lineárních nerovnic nemá přípustné řešení když algoritmus vrátí hodnotu True, tak přípustným řešením je x = (5(v0, vi), 5(v0, v2), • • •, 8(v0, vn)) 382