N/Evrh algoritmu I I BOO2 Doplňující text k předn/Ešce Literatura • Thomas H. Cor men, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, 2nd ed., The MIT Press & McGraw-Hill, 2002 • Thomas W. Parsons: Introduction to Algorithms in Pascal, John Wiley & sons, 1 • Steven S. Skiena: The Algorithm Design Manual, Springer, 1998 • http://www.fi.muni.cz/~libor/vyuka/IB002/ • z/Episky z pedn/Esek... Program, algoritmus, funkce Program je form/Elní popis chov/Eníějiak0ho syst0mu (aplikání program, reaktivní syst0m, operační syst0m...). Skl/Ed/E se z popisu algoritmů. Algoritmus lze ch/Epat jako parci/Elní funkci z množiny všechnožných vstupů do množiny všech možných výstupů. funkce : Vstupy —■> Výstupy Pozor, není to definice: sice každ0mu algoritmu odpovíd/E pani/Elní funkce ze vstupů do výstupů, ale naopak ne každou takovou funkci lze vyj/Eit algoritmem. 3 Algoritmus je parci/Elní funkce z množiny vstupů do množinyvýstupů, k níž existuje konečný popis v určit0m formalismu. Tímto formalismem je typicky programovací jazyk, ale existují i další matematick0 formalismy: Turingův stroj, RAM, lambda kalkul, kombin/Bbrový kalkul, vyčísliteln0 funkce, Markovův algoritmus... Slovo algoritmus je odvozeno ze jm0na starověk0ho persk0ho matematika a astronoma al-Chwarezmího (Abú 'Abd Alláh Muhammad ibn MGsä al-Khwärizmľ). 4 Funkce z množiny vstupů do množiny výstupů, kter0 lze vyj/Eřit algoritmem, se nazývají rekursivně spočetnQ Reaktivní syst0m je program, jehož prov/Eění norm/Elě nemusí končit (např. operační syst0my apod.), v obecnějším smyslu jsou to interaktivní programy. Program, který je implementovaným algoritmem, při výpočtu přečte vstup, zpracuje ho (vstupní data transformuje na výstupní), vypíše výstup a skončí. Většina současných programů je interaktivních, ale souč/Estí všech jsou algoritmy. 4-1 Korektnost algoritmu In množina vstupních dat Out množina výstupních dat A : In —■> Out algoritmus (na vstupu z In vypisující výstup z Out) cp : In —> £00/ vstupní podmínka ijj : In x Out —> £00/ výstupní podmínka Vstupní podmínka cp určuje, zda daný vstupní oedaj je pro algoritmuspř/pusfr?/, vymezuje tedy jistou podmnožinu množiny vstupních dat In. Výstupní podmínka tp řík/E, zda daný výstupní oedaj jěi není výsledkem výpočtu algoritmu na dan0m vstupním oedaji. Vstupní podmínka je un/Erní predik/Et na množěivstupních dat, výstupní podmínka je bin/Erní predik/Et na množin/Ech vstupních a výstupních dat. Výstupní podmínka ý řík/E, zda daný výstupní oedaj jěi není (pro nedeterministicko algoritmy zda může či nemůže být) výsledkem výpočtu algoritmu na dan0m vstupním oedaji. 5-1 Příklad: Algoritmus A přečte tři čísla a vypíše je v neklesajícím pořadí; dejme tomu, že funguje korektně jen pro kladn/Ešísla. In = Out = Z x Z x Z, (Pa(x, y,z)=x>0Ay>0Az>0 iPa(%, V-, z, u, v, w) = (ix, v, w) G Permut(x, y, z) A u < v < w Pozn/Emka: Připustíme i algoritmy, kter0 nenačítají ž/Edný vstup. Pro ě položíme /n = {0}. Def: Řekneme, že A je konvergentní vzhledem k cp, když množina {x G In \ (p(x)} je podmnožinou definičního oboru funkce A, tj. když pro každou vstupní hodnotu x, pro niž platí (p(x), je výsledek výpočtu podle algoritmu A definov/En (výpéet se zastaví). Def: Řekneme, že A je parci/Elě korektní vzhledem k cp a tp, když pro každou vstupní hodnotu x z definičního oboru funkce A splňující vstupní podmínku ip (tj. pro každ0£, pro něž je A(x) definov/Eno ap(x)) platí ip(x, A(x)). Def: Řekneme, že A je tot/Elě korektní vzhledem k cp a tp, když je konvergentní vzhledem k cp a parci/Elě korektní vzhledem k cp a tp. Důsledek: Algoritmus A je tot/Elě korektní vzhledem k cp a ijj, pr/Eé když pro každou vstupní hodnotu x splňující vstupní podmínku výpočet podle algorimu A skončí a jeho výsledek splňuje i výstupní podmínku. Vstupní a výstupní podmínce se \ak0ť\k/Especifikace algoritmu. O tot/Elě korektním algoritmu pak řík/Eme, ževyhovuje specifikaci. 7 Výpočetní paradigmata Paradigma (vzor, přístup, pojetí) ud/Ev/E způsob, jakým je algoritmus vyjyflědi. Výpočetní paradigmata: - imperativní - funkcion/Elní - Iogick0 - procedur/Elní - objektovo - sekvenční - paralelní Imperativní paradigma Neform/Elní vymezení: Výpočet je posloupností tzv. výpočetních kroků. Výpočetní krok je realizací instrukce (jednoduch0ho riíkazu) programu. Přenos informace mezi jednotlivými kroky výpočtu zprostředkov/Ev/šfáK. Jinak řečeno, příkazy programu jsou stavov0 transform/Etory— (parci/Elní) funkce z množiny stavů do množiny stavů. Pro form/Elní definici je nutno zav0st abstraktní poítač. V sekvenčním imperativním paradigmatu jím nejčastěji býv/E Turingův stroj nebo RAM (Random-Access Machine). Může jím být tak0 „vyšší" imperativní jazyk, který kromě element/Erních stavových transform/Etorů (typicky {zvpřiřazovacího příkazu) obsahuje složen0 stavov0 transform/Etory realizující sekvenci (begin-end), bin/Erní étvení výpočtu (if-then-else), n/Esobn0štvení (case), opakov/Ení (while-do, for-do), apod. Výpočetním krokem je pak přechod mezi dvěma konfiguracemi Turingova stroje, resp. provedení jedn0 instrukce RAMu, resp. provedení jed noho element/ErníhcpnWazu. 9-1 Abstraktní počítače pro imperativní programy • Tu ringů v stroj • RAM • (abstraktní) programovací jazyk Tu ringů v stroj • Konečn/E nepr/Ezdn/E množiSasymbolů — tzv. abeceda • Nekonečn/^o/£s/ca— spočetn/E posloupnost poliek. Každ0 polčko p/Esky obsahuje jeden symbol abecedy, přičemž skoro všechna políčka obsahují zvl/Eštní symboU. • Čtecí hlava, jejíž pozice na p/Esce je d/Enařpozeným číslem. • Konečn/E množinaS vnitřních stavů s vyznačeným poč/Etěním stavem <7o a koncovými stavy F C S. • Přechodov/E funkce :SxE^SxSx{L,R} 11 RAM • Spočetn/E posloupnostM registrů (paměťových míst) — tzv. paměť. Každý registr obsahuje cel0číslo, vždy však skoro všechny obsahují nulu. • Stav a e S = N x Z* • Konečn/E množina inštrukcií. Každ/E instrukca G X m/E danou s0mantiku — funkci l : S —■> S. • Konečn/E posloupnostP G X* instrukcí, tzv. program J 12 Příklad: Výpočet faktori/Elu (funkcion/Elní verze - Pascal) Faktori/Ehez/Epom0ho cel0hóísla n je číslo n! = 1 • 2 • 3.....(n — 1) • n. Speci/Elě 0! = 1 (součin nulov0ho pcčtu činitelů). function fact (n:Integer): Integer; begin if n==0 then fact:= 1 {return 1} else fact:= n*fact(n-l) {return n*fact(n-l)} end Věta: Funkce fact konverguje vzhledem ke vstupní podmínce (p(ri) = n E N. Věta: Funkce fact je parci/Elě korektní vzhledem k^ak výstupní podmínce ^(n, k) = k — n\. Důsledek: fact je tot/Elě korektní vzhledem k cp, ip. Věta: Funkce f act konverguje vzhledem ke vstupní podmínce (p(n) = n £ N. Důkaz indukcí podle n. Pro n = 0 se výpočet zastaví; zastaví-li se výpočet pro n, zastaví se i pro n + 1. Věta: Funkce f act je parci/Elě korektní vzhledem k

0 a tvrzení platí pro n — 1. Pak f act (n) = n • f act (n — 1) = n • (n — 1)! = n!, tedy tvrzení platí i pro n. 13-1 Výpočet faktori/Elu (imperativní verze - Pascal) function factorial (n:Integer): Integer; var i, k: Integer; begin i : = 0; k := 1; while i < n do begin i := k := k*i end; factorial := k {return k} end Věta: Funkce konverguje vzhledem ke vstupní podmínce (p(ri) = n G N. Funkce je parci/Elě korektní vzhledem kcp ak výstupní podmínce tp(n, k) = k = n\. Věta: Funkce factorial konverguje vzhledem ke vstupní podmínce (f(n) = n G N. Důkaz spočív/E v nalezenčíseln0 hodnoty (z/Evisl0 na obsahu programových proěmných), kter/E v ž/Edn0m okamžiku výptw nemůže být z/Eporn/E arjJonri při každ0m průchodu ělem cyklu klesne nejm0ně o jedničku. V tomto příkladě je touto hodnotou číslo n — i a důkaz nez/Epornosti i kles/Ení je snadný. Věta: Funkce f actorial je parci/Elě korektní vzhledem k

0, n>0 } begin if n==0 then pow := 1 else pow := z * pow(z,n-l) end Věta: Funkce pow konverguje vzhledem ke vstupní podmínce (p(z, n) = z e M, n G N, z > 0. Důkaz: Klesající hodnotou je zde exponent. Věta: Funkce pow je parci/Elě korektní vzhledem ke vstupní podmínce ip a k výstupní podmínce ip(z, n, r) = r — zn. 16 Důkaz věty: Indukcí podle exponentu. Příklad: Algoritmus umocňov/Encísla půlením exponentu (imperativní verze - Pascal) function power (z:Real; n:Integer): Real; { Předpokládá se z>09 n>0 } var y,r:Real; k:Integer; begin k := n; y := z; r := 1; while k > 0 do begin if odd(k) then r := r * y; k := k div 2; y := sqr(y) end; power := r end 17 Věta: Funkce power konverguje vzhledem ke vstupní podmínce (p(z, n) = z e M, n G N, z > 0. Důkaz: Klesající hodnotou je zde exponent. Kles/Ení je terrbkr/Et rychlejší než v předch/Ezejícím píkladě, ale pro k > 0 je vždy ostr0. Věta: Funkce power je parci/Elé korektní vzhledem ke vstupní podmínce (p k výstupní podmínce ip(z, n, r) = r = zn. Invariant: r • yk = zn A k > 0 Věta: Funkce power konverguje vzhledem ke vstupní podmínce (p(z, n)EzGl,nGN,z>0. Důkaz: Klesající hodnotou je zde exponent. Kles/Ení je tertbkr/Et rychlejší než v předch/Ezejícím píkladě, ale pro k > 0 je vždy ostr0. Věta: Funkce power je parci/Elě korektní vzhledem ke vstupní podmínce ^ak výstupní podmínce ^(z, n, r) = r = zn. Důkaz: Invariant cyklu while, který platí vždy v okamžiku testov/Ení podmínky cykluj > 0), je r • yk = zn A k > 0 Po poslední iteraci platí tento invariant v konjunkci spolu s negací podmínky cyklu (-i(k > 0)). Z t0to konjunkce vyplýv/5: = zn, přičemž r je výsledn/E hodnota funkce power. Platí tedy i výstupní podmínka ip(z, n, power (z, n)). 18-1 Příklad: Algoritmus řazení vkl/Ed/Ením (imperativní verze - Pascal) 1 const MAX = 999; 2 type Elem = Integer; 3 Posl = array [1..MAX] of Elem; 4 procedure ilnsSort (n:Integer; var A:Posl); 5 var i, j : Integer; x : Elem; 6 begin 7 for i := 2 to n do 8 begin 9 x := A[i] ; j : = i-1; 10 while (j>0) && (A[j]>x) do 11 begin 12 A[j+1] := A[j] ; 13 j := j-1 14 end; 15 A[j+1] := x 16 end 17 end Věta: Algoritmus ilnsSort je tot/Elě korektní vzhledem k podmínk/Em (p(n, A) = posloupnost A je nepr/Ezdn/E n > 1 je její d0lka ip(n,A,Af) = posloupnost Af je permutací posloupnosti A a je neklesající 20 Věta: Nechť Z* označuje množinu všech konečných celočíselných posloupností, In = N x Z*,Out= Z*. Nechť 1 A \A\ = n, V>(n, A, A') = A' e Permut{A) A Vi, j, 1 < i < j < rc.Aj < A^ Pak ilnsSort je tot/Elě korektní vzhledem k podmínk/Em/?, -0. Důkaz rozložíme na důkaz konvergence a parci/Elní korektosti. Lemma: Algoritmus ilnsSort je konvergentní vzhledem k (p. Důkaz: Vnější cyklus for vždy skončí, protože je vždy předem d/En pevný poet jeho opakov/Ení^i — 1). Vnitřní cyklus while se prov/Edí jen kdyžj > 0. Ale při každ0m průchodu tělem tohoto cyklu hodnota proměnn0 j klesne. To znamen/E, že cyklus while se provede konečněkr/Et (nejvýše(i — l)-kr/Et). Lemma: Algoritmus ilnsSort je parci/Elě korektní vzhledem k podmínk/Em^, ip. 20-1 Důkaz: Vstupní posloupnost označme (ai,..., an), obsah pole A (v dan0m stavu výpočtu) označme (Ai,..., An). Invariantem vnějšího cyklu for (splněným vždy na zač/Etku tohoto cyklu) je podmínka My then maxim (x:s) else maxim (y:s) maxim [4,3,5,1] if 4>3 then maxim [4,5,1] else maxim [3,5,1] -w if True then maxim [4,5,1] else maxim [3,5,1] maxim [4,5,1] if 4>5 then maxim [4,1] else maxim [5,1] if False then maxim [4,1] else maxim [5,1] maxim [5,1] if 5>1 then maxim [5] else maxim [1] if True then maxim [5] else maxim [1] maxim [5] 5 Příklad: Algoritmus řazení vkl/Ed/Ením (funkcion/Elní verze - Haskell) flnsSort [] = [] flnsSort (x:s) = ins x (flnsSort s) where ins x [] = [x] ins x (y:t) = if x<=y then x:(y:t) else y:(ins x t) Nechť In = Out\e množina všech seznamů (posloupností) celých čísel, (p(s) = s je konečný, ip(s, ť) = „t je permutací seznamu s a t je neklesající". Věta: AlgoritmusPak flnsSort je tot/Elě korektní vzhledem k cp, ip. Pozn/Emka: V Haskellu lze definici zapsat i kratčeji: flnsSort = foldr ins [] . Věta: AlgoritmusPak f InsSort je tot/Elě korektní vzhledem k (p, Důkaz: Nechť s je konečný seznam d0lkyn. Konvergence obou funkcí se uk/Eže indukcí pes d0lku seznamu. Při důkazu parci/Elní korektnosti vyjdeme z vlastnosti funfee ins: Je-li seznam u neklesající, pak ins y u je neklesající permutace seznamu y: u. Zbytek indukcí přes d0lku seznamus. 23-1 Složitost Složitost algoritmu vyjadřuje n/Erónost algoritmu na různ0 zdroje v průběhu výpočtu: čas výpočtu, velikost paměti, počet procesorů apod. Podle toho rozlišujeme rúzr\0míry složitosti. Míry složitosti: - časov/E - prostorov/E (paněťov/E) - procesorov/E (hardwarov/E) Pro definici časov0 resp. prostorov0 složitosti zavedeme pojmyd0//ca výpočtu resp. množství výpočtem spotřebováno parrěti. K přesn0 definici obou pojmů však potřebujeme tzv. výpočetní model. Jeho definice z/Evisí navýpočetním paradigmatu. Například pro Turingův stroj d0lkou výpočtu počet výpočetních kroků, tj. vnitřních přechodů. Pro RAM je to počet provedených instrukcí. Pro funkcion/Elní jazyk je to poet jednokrokových redukcí. Složitost probl0mu'\e je zavedena jako složitost optim/Elního algoritmiřešícího tento probl0m. Na řešení nějak0ho probl0mu můžeme použít mnoho různých algoritmů Časovou složitostí probl0mu pak rozumímečasovou složitost algoritmu, který řeší daný probl0m (i na „nejpomalejších datech") nejrychleji. Prostorovou složitostí probl0mu rozumíme prostorovou složitost algoritmu, který řeší daný probl0m (i na nejm0ě příznivých datech) v nejmenší paměti apod. 24-1 Příklad: • Řešíme probl0m: sďadit vzestupně n-prvkovou posloupnost celých čísel. • K řešení použijeme algoritmus řazení vkl/Ed/Ením. • Naše konkr0tní posloupnosti, kter0 budou vstupem, jsou3, 6, 9,... , 3n (tj. jsou už seřazen0). Rozlišujeme tři pojmy: • časovou složitost probl0mu • časovou složitost algoritmu • d0lku výpočtu _) D0lka výpočtu algoritmem ilnsSort na rostoucí posloupnosti d0lkyn je 6n — 4 (tolik se provede výpočetních kroků). Časov/E složitost algoritmuilnsSort je vyj/Eatena kvadratickým polynomem an2 + bn + c, jak později uvidíme. Je tedy větší než d0lka výpočtu na našich (příznivých) datech. Na jiných posloupnostech d0lkyn stejný algoritmus str/Evčasu více. V nejhorším případě až kvadraticky mnoho, proto je časov/E složitost algoritmiřazení vkl/Ed/Ením kvadratick/E. Časov/E složitost probl0mu vzestupn0ho sazení posloupnosti je však lepší než kvadratick/E: existují algoritmy, kter0n-prvkovou posloupnost seřadí v čase c n log n (c je konstanta), a to i v nejhorším případě (tj. i pro „nejzlomyslněji zadan0" vstupní posloupnosti). Proto ječasov/E složitost probl0muřazení vyj/Eatena funkcí c n log n (v proměnn0n). 25-1 D0lka výpočtu výrazů D0lku výpočtu výrazu e označíme r(e). r (e) je rovna součtu d0lek vyhodnocení všech operací, kter0 výraze obsahuje. Vyhodnocení element/Erních aritmetických, logických, reáčních operací nad skal/Erními operandy je konstantní. Proto i d0lku výpočtu výrazu, který obsahuje pouze tyto jednoduch0 operace, považujeme za konstantní. Obsahuje-li však výraz e vol/Ení složijších funkcí, je nutno započítat d0lku jejich výpočtu do r(e). 26 Přesněji: r (c) = O, je-li c konstanta, r (v) = 1, je-li c odkaz na hodnotu skal/Erní (pepisovateln0) proměnn0. Tedy zpřístupnění obsahu proměnn0 považujeme za jednotkovou operaci. r(op a) = 1 + r(a), kde op je primitivní un/Erní oper/Etor, který vyhodnocuje svůj opand, například not. r(a 0 b) = 1 + r (a) + r (6), kde 0 je některý z primitivních bin/Erních oper/Etorů, kter0 vyhodnocují oba svoje operandy, například +,—,*, /, div, mod, <,<,>,>,.... 26-1 Pozor, někter0 oper/Etory a jazykov0 konstrukce nemusí vždy vyhodra©vat všechny svoje operandy. Podle toho se pak určuje d0lka výpočtu výrazů: r(a && b) = 1 + r (a) + r(b) pro a pravdiv0 r (a && b) = 1 + r(a) pro a nepravdiv0 r (a | | b) = 1 + r(a) + r(6) pro a nepravdiv0 r(a I I 6) = 1 + r(a) pro a pravdiv0 r(if a then 6 else c) = 1 + r(a) + r(6) pro a pravdiv0 r(if a then 6 else c) = 1 + r (a) + r(c) pro a nepravdiv0 26-2 D0lka výpočtu vol/Ení funkce Deklarace: Vol/Ení hodnotou (striktní aplikace): r(f (ai,..., an)) = 1 + r(ai) + • • • + r(an) + T(eff), kde výraz e" vznikne z výrazu e nahrazením každ0ho výskytu^ hodnotou výrazu a^. Vol/Ení jm0nem (norm/Elní aplikace): r(f (ai,...,an)) = 1 + r(e/), kde výraz e' vznikne z výrazu e nahrazením každ0ho výskytu Xi celým nevyhodnoceným výrazem ai. 26-3 Bude-li n/Es zajímat pouze tzv'asymptoticko c/7ov/E/7složitosti algoritmů, budeme ztotožňovat složitosti lišící se jen kladnou multiplikativní konstantou. Pro takov0 riípady bude užitečn/E n/Esledující Úmluva: Je-li e výraz obsahující jen skal/Erní konstanty a pronšnn0 a element/Erní operace (na skal/Erních hodnot/Ech), klademe d0lku jeho výptw rovnu jedn0. Výraz e zejm0na nesmí obsahovat vektorov0 operace (nap. aritmetick0 operace na „dlouhých" číslech) ani vol/Ení uživatelských funkcí. 27 Tuto cemluvu zav/Edíme proto, že proČEly zjišťov/Ení asymptotick0ho chov/Ení algoritmů je praktičtější například uvažovat d0lku přiřazení x: =a* (b+c+d) rovnu jedn0, než ji počítat jako 1 + 1 + 2 + 5. Stejně víme, že součet je roven konstantě, a to n/Em stáí. 27-1 U tzv. „čistých" výrazů předpokl/Ed/Eme, že nemají vedlejší efekty. To však nemusí v^ofclatit. D0lka výpočtu výrazů, kter0 obsahují vol/Ení funkcí, z/Evisí najen naamotn0m výrazu, ale i na stavu, v němž se výraz vyhodnocuje. Stavem rozumíme okamžitý obsah programových (přepisovatelných) proměnných. V jazycích s vedlejšími efekty se stav během výpočtu mění. Příklad: var a:Integer; function f (n:Integer):Integer; var i,k:Integer; begin k := 0; for i:=0 to n*a do k := k+i; a := k; f:=a {return a} end 27-2 Glob/Elní pepisovateln/E prorenn/Ea m/E na zá/Etku hodnotu 2, pak ve výrazuf (4) +f (4) trv/E každ0 vyhodnocení stejn0ho podvýrazf (4) různou dobu. (Jakou?) 27-3 D0lka výpočtu příkazů Nechť S je množina stavů, a G S. Každý příkaz p funguje jako stavový transform/Etor v{p) : S —■> S. D0lku výpočtu příkazu p ve stavu a označíme r(p, a). Pr/Ezdný píkaz r(skip, cr) = 0 pro libovolný stav a Přiřazovací příkaz r(v:=e,cr) = 1 +r(e, a), je-li v jednoduch/E pepisovateln/E pronénn/E Sekvence k r(beginpi; ...; Pk end, cr0) = y^r(p^^-i), kde a i = v(pi)((Ti-i) Větvení Nechť a je stav, p, q příkazy, e výraz aa' = i/(e)(a). r(if e thenp else g, a) = r(e, a) + r(p, a7) pro pravdiv0e, r(if e thenp else g, a) = r(e, a) + r(g, a7) pro nepravdiv0( Pokud výraz e nem/E vedlejší efekty, pakr = a a r(if e thenp else g, a) = r(e, a) + r(p, a) pro pravdiv0e, r(if e thenp else g, a) = r(e, a) + r(g, a) pro nepravdiv0e \ Cyklus while Nechť t = (while e do s) je příkaz cyklu a an je stav takový, že ze stavu <7n příkaz cyklu t zopakuje pr/Eé n-kr/Et sv0ěMo s. Pro 0 < i < n označme g\ — v{e){pi), pro 0 < i < n označme cr^+i = v(s)(ai), a nechť pro 0 < i < n je fi(e)((Ti) = pravda, fi(e)(an) = nepravda. Pak 0 N takto: Ta(tí) — max{r(A, ax) \ \x\ — n} Časov/E složitost algoritmu je tedy funkce, kter/E pro každovelikost vstupních dat je rovna 60\cenejdelšího výpočtu na všech možných datech t0to velikosti. 31 Velikost vstupních dat odpovíd/E potu bitů, kterými je vstupní oedaj vyj/Eřén. V praxi m/E často tyto významy: číslo n d0lka jeho bitov0ho z/Episu, tpog2 n\ posloupnost čísel počet jejích prvků graf počet uzlů + počet hran Protože množina v definici složitosti je většinou nekonečn/E, musíme hledan0 maximum určit analýzou nej horšího případu. J 32 V některých případech je výhodnější rozdělit velikost dat na dvě čísla (graf) a upravit defi složitosti TA : N x N N 32-1 Příklad: Algoritmus řazení vkl/Ed/Ením (imperativní verze - Pascal) 1 const MAX = 999; 2 type Elem = Integer; 3 Posl = array [1..MAX] of Elem; 4 procedure ilnsSort (n:Integer; var A:Posl); 5 var i, j : Integer; x : Elem; 6 begin 7 for i := 2 to n do 8 begin 9 x := A[i] ; j : = i-1; 10 while (j>0) && (A[j]>x) do 11 begin 12 A[j+1] := A[j] ; 13 j := j-1 14 end; 15 A[j+1] := x 16 end 17 end Příklad: Analýza nejhoršího případu Algoritmus: ilnsSort Vstup: posloupnost celých čísel A = (ai,..., an) d0lkyn. Výstup: posloupnost celých čísel B, kter/E je permutací posloupnostiA a přitom je neklesající. Označme q d0lku výpočtu příkazu nebo testu na i-t0mř/Edku algoritmuilnsSort, přičemž na sedm0mř/Edku (v z/Ehlaví cyklu for) jsoiíitelement/Erní akcejC7)initJ C7)testJ C7)inc. 33-1 Pak d0lka výpočtu je n / i — l T(n) = c7jinit + ^2 ( C7'test + c9 + Xľ(Cl0 + Cl2 + Cl3) i=2 ^ j=£ + Cio + Ci5 + C7)inc j + C7jtest kde £ je hodnota, při kter0 se vnifní cyklus algoritmu zopakuje nejvícekr/Et, tj. nejmenší možn/E hodnotaj, při níž je ještě splněna podmínka za while (na 10. ř/Edku algoritmu). Takov0 minim/Elní možn(§ je zřejmě rovno 1, a to v každ0m průchodu vnějším cyklem for. Situace, kdy v každ0m průchodu vnějším cyklem je £ = 1, nastane, když vstupní posloupnost A je klesající. 33-2 Po dosazení £ = 1 a po oepra>é dost/Ev/Eme rrí x Cio + C12 + Ci3 2 i (n) = -n + (C7,test + C7,inc + Cg + ClO C12 Cl3 + ci5)n 2 2 + (C7,init — c7,inc ~ Cg — Cio — C15) což je kvadratický polynom v proměnn0n. Podle dřívější oemluvy lze všechny konstanty považovat za jedniky (resp. cg = 2), takže po 3 2 9 dosazení lze pracovat s polynomem —n H—n — 4. 2 2 33-3 Abychom mohli při porovn/Ev/Ení složitostí algoritmů abstrahovat od ryahsti konkr0tního počítače, budeme chtít srovn/Evat funkce podle toho, „jak rychle rstou", přičemž za významný rozdíl v rychlosti růstu nepovažujeme například případ, kdy jedna funkce m/Ec-kr/Et větší hodnoty než druh/E (pro ějakou kladnou konstantu c). 33-4 Rychlost růstu funkcí Nechť g : N —> N. Zavedeme množiny funkcí: Množina funkcí rostoucích nejvýše tak rychle jako g : O (g) = {f I 3c> (EnnVn > n0. 0 < /(n) < c • #(n)} Množina funkcí rostoucích aspoň tak rychle jako g : Q{g) = {/ | 3c> 03n0Vn > n0. 0 < /(n) > c • ^(n)} Množina funkcí rostoucích stejně rychle jako g : O(g) = O(g) n Í2(g) 34 Množina funkcí rostoucích pomaleji než g : o (g) = {/ | Vc > 03nnVn > no- 0 < f(n) < c • g(n)} Množina funkcí rostoucích rychleji než g : uj(g) = {/ | Vc > 03nnVn > no- 0 < c • g (n) < f (n)} n n f e (2(g) Vn >n'.0< c'g(n) < f (n) f e 0(h) & Vn > n", f (n) < c"h(n) 36 Protože se budeme zabývat především funkcemi vyjadřujícími složitost algoritmu (kter/E je vždy nez/Eporn/E), omezíme se d/Ele na nez/Eporn0 funkce. 36-1 Vlastnosti množin O, i?, (9, o, u Věta: Jsou-li /, g : N —» N dvě funkce, pak / G 0(g) pr/Eé když 3ci > 03c2 > 03nnVn > no. c\ • g(n) < /(n) < C2 • Věta: Pro každ0 dva kladn0 funkce/, g : N —» N platí: / G ^ 5 G «(/) / G 0(0) O p G / G 6(g) & g G 6>(/) / G / G 1 V důkazu prvních dvou tvrzení stačí obr/Etit nerovnost a uv/Ežit kladnou konstantu-. c Třetí tvrzení je trivi/Elní. Čtvrt0 tvrzenířík/E, že jist/E vlastnost platí pro všechna kladn^Ale kladn/Ecísla existují, například c = 1. Tedy platí tak0 slabší vlastnost pronějakOc > 0. Důkaz p/Et0ho tvrzení je analogický. 37-1 Věta: Pro každ0 dvě kladn0 funkce/, g : N —» N platí: / e o(g) & lim ^ = 0 f e u)(g) & lim ^ = oo n^oo g[n) 38 /(») Rovnost lim n^oo g[n) = 0 je ekvivalentní s podmínkou Vc > OžInoVn > tíq. f(n) 9ÍP) < c. Obě funkce jsou kladnO, tedy absolutní hodnotu nemusíme uvažo/at a nerovnost lze vyn/Esobičíslem g(n), čímž dostaneme podmínku pro / G o(g). Úprava byla ekvivalentní, takže ekvivalentní jsou i obě podmínky v prvním tvrzení. /(») Rovnost lim n^oo g[n) Vc > OžInoVn > no. = oo je ekvivalentní s podmínkou f in) > c. Obě funkce jsou kladnO, tedy absolutní hodnotu nemusíme uvažovat a nerovnost lze vyn/EsobiĎíslem g(n), čímž dostaneme podmínku pro / G oo(g). Úprava byla ekvivalentní, takže ekvivalentní jsou i obě podmínky v prvním tvrzení. 38-1 Jsou-li /, g : N —>> N dvě kladn0 funkce, pak platí lim M < oo ^ f G 0(5) n—»00 Um M > o ^ / e 12(3) g (n) n—>oo Obr/Ecen0 implikace však obec© neplatí, protože uveden0 limity nemusí existovat. Pro funkce /, g však platí silnější tvrzení: f (n) lim sup < oo o / e O (g) n—>oo liminf > O / e f}(g) 9{n) n—>oo Cvičení: Rozhodněte a zdůvodněte, zda pro každou kladnou funkci g platí 0(g) = o(g) U 9(g), íi(g) = w{g) U 0(g). 38-2 Věta: Nechť f,g,h:N—>N jsou tři kladn0 funkce a nechť funkceg : N —» N je definovZEnag(n) = f(n) + g(n). Pak platí: fe 0(h)Age 0(h) ^ gG 0(h) f e íž(h) Age íž(h) q e íž(h) f e 6{h) Age 6{h) ^ gG 6{h) f e o(h) Age o(h) ^ gG o(h) f e u{h) Age u{h) ^ gG u{h) _) Pozn/Emka: Platí řada podobných odvozených vlastností, například / G Í2(h) Age 0{h) => q G íi(h) f G 9(h) Age 0(h) => q G <9(/i) / G é?(/i) A # G o(/i) g G 9(h) apod. Cvičení: Formulujte a dokažte další vlastnosti, kter0 z věty vyplývají. 39-1 Věta: Nechť /, h : N —> N jsou dvě kladn0 funkce,c, d konstanty, c > 0, a nechť funkce p : N —> N je definovZEnap(n) = c • /(n) + d. Pak platí: / g O(h) => p e O(h) f e Q{h) => p e S2(h) f e 6{h) => p e 6{h) f e o(h) ^ p e o(h) f e u(h) ^ p e u(h) _J Důkaz: Nejprve nechť d = 0; tvrzení obdržíme vhodnou volbou kladn0 konstanty v definidch tříd O, Q, O, o,lj. Pro obecn0d ^ 0 jde o speci/Elní pípad předchozí věty, kdy funkce g z jejích předpokladů je konstantní. 40-1 Věta: Nechť N N jsou tři funkce, pak f e O(g) A g e 0(h) / G 0(h) f e o(g) A g e O(h) / e o(fe) f e O(g) A g e o(h) / e o(fe) feí2(g)Ageí2(h) / G f eu(g)Age Q{h) => f e u(h) /€ Í2(g) Ag eu(h) => f e u(h) Důsledek: Relace „rusí nejvýše tak rychle" tvoří předuspoř/Ed/Erría množině všech funkcí N ->■ N. Pozn/Emka: Relace „růstpr/Eě tak rychle"Xvoť\ ekvivalenci na množině všech funkcí N ->■ N. Tyto relace však nejsou oepln0. Existují dvojice funkcí, ktif) nejsou porovnateln0. Pozn/Emka: Předuspoř/Ed/En[í0žpolouspoř/Ed/Elpíe bin/Erní relace, kter/E je reflexivní a transitivní. Uspoř/Ed/Er\é bin/Erní relace, kter/E je reflexivní, antisymetrick/E arbisativní. Ekvivalence je bin/Erní relace, kter/E je reflexivní, symetrick/E a trarirsirtí. Cvičení: Najděte příklad dvojice funkcí /, g : N —)• N, kter0 nejsou porovnateln0, tj. ftO(g),ftf}(g). Cvičení: Dokažte tvrzení: Je-li kladn/E funkce/ skoro všude majorizov/Ena funkcíg (tj. f(n) < g(n) pro skoro všechna n), pak / G O(g). Cvičení: Dokažte tvrzení: Pro každou kladnou funkci g je o(g) r\oj(g) = 0. 41-1 Růst jednoduchých funkcí Def: Kladný polynom je polynom s kladným vedoucím koeficientem. Věta: Kladný polynom vyššího stupně roste vždy rychleji než polynom nižšího stupně. Dva kladn0 polynomy stejn0ho stupě rostou stejně rychle. Pozn/Emka: Předchozí větu lze zobecnit i na mocninn0 funkce s neceločíselnými exponenty: jestliže 0 < a < b, pakna G o{nb). Věta: Exponenci/Elní funkce se z/Ekladero > 1 roste rychleji než libovolný polynom. Logaritmick0 funkce rostou pomaleji než funkce line/Erní. 42 Cvičení: Dokažte, že pro každ0 pŕirozen0číslo k platí (n + 1) G O (n ). (Vhodnou kladnou konstantu c z definice množiny O určete podle binomick0 vaty.) 42-1 Věta: Nechť 1 < a < b. Pak loga e 0(log6) an e o(bn) Pozn/Emka: Roste-li funkce logaritmicky, pak na z/Ekladu logaritmu nežíleží. (Jen musí být větší než 1, což je však nutn/E podmínka k tomu, aby funkce vůbe rostla.) Věta: Platin! e 0(nn), n\ e 0(2n). Důkaz plyne z definice faktori/Elu. 43 Pozn/Emka: Místo „(9(log)" se často píše „(9(log n)", podobně jako ,,o(n2)" místo ,,o(f), kde f(n) = n2 pro každ0n", a dokonce „(9(1)" místo ,,0(g), kde g(n) = c > 0". Mnozí autoři zach/Ezejí ve zneužív/Ení notace ještd/Ele (nap. pracují s množinami funkcí, jako by to byla čísla). Pozn/Emka: Z tzv. Stirlingovy aproximace VŽ^n~{n/e)n 0 tak, že f e O ((logrc)*). Def: Řekneme, že funkce / roste nejvýše poíynomi/Eíě, když existuje číslo k > 0 tak, že f e 0(nk). Funkce / roste roste aspoň polynomi/Elě, když existuje číslo £ > 0 tak, že f E Q{n£) Def: Řekneme, že funkce / roste nejvýše exponenci/Eíě, když existuje číslo a > 1 tak, že f E 0(an). Funkce / roste aspoň exponenci/Elě, když existuje číslo a > 1 tak, že f E fl(an). Def: Řekneme, že funkce / roste aspoň dvojitě exponenci/Elě, když existuje číslo aa ). 44 Pozn/Emka: Existují funkce, kter0 rostou rychleji než všechny&-n/Esobě exponenci/Elní funkce, a to dokonce pro Iibovoln0fc. Naopak existují kladn0 funkce, kter0 rostou (tedy rychlejhež konstantní), ale rostou pomaleji než funkce log o • • • o log, kde logaritmus můžeme složit sama se sebou libovolněkr/Et. 44-1 Def: Fibonacciho funkce F : N —>■ N je definovan/E rekursivě: F(0) = 0 F(l) = 1 F(n + 2) = F(n) + F(n + 1) pro všechna íiGN. 1 + y/E . 1 - \/5 Věta: Nechť tp = —-—, (p = —-—. Pak pro každ0n platí Důsledek: Pro Fibonacciho funkci F platí i*1 E 0((pn), kde

0 platí F(n) = -——, V5 F(n + 1) =---, a uk/Ežeme, žeF(n + 2) =--- F(n + 2) = F(n) + F(n + 1) = ^ _^ + ^ ^ 4(l + v^)"-4(l-v^)" + 2(l + v^)"+1-2(l-y^)"+1 2"+2\/5 45-1 n (4 + 2(1 + VŠ)) (1 + y/5) - (4 + 2(1 - y/5)) (1 - VŠ) 2"+2\/5 (1 + 2^+5) (1 + VE)n - (l-2>/5 + 5) (l->/5) 2«+2\/5 (l + V5)"+2-(l-V5)"+2 2"+2\/5 n 14VŠ n+2 n+2 45-2 Lemma: Funkce log (n!) roste stejně rychle jako funkce n • log n. Důkaz: Nejdříve uk/Ežeme, že logn! G O (n log n). n n log2n! = log2/c < log2n = n log n, takže log2n! G O (n log n). k=i k=i n n D/Ele funkci lo§n! ohraničíme i zdola: 2 log2n! = 2 log2/c > 2 log2/c > k=l k=[n/2} n n n L2J = 2 n L2J 2 log2 &=Ln/2j Dohromady log n! G 0(n log n) log2 L 2 J G <9(n log n), takže log2n! G i?(n log n) Cvičení: Dokažte, že d0lky výpočtů podle nějak0ho algoritmus jsou v množině O(g), pr/Eé když časov/E složitost algoritmuA je v O(g) a d0lky nejkratších výpočtů patří do fi(g). Cvičení: Seřaďte podle rychlosti růstu funkce (v proměnn0n): log nn, log (log n), ny/ří, olog^n 46-1 Algoritmus řazení slučov/Ením (funke, verze) mergeSort : : [Int] —>- [Int] mergeSort [] = [] mergeSort [x] = [x] mergeSort s = merge (mergeSort u) (mergeSort v) where (u,v) = splitAt (n cdivc 2) s n = length s merge s [] s merge [] t = t merge (x:u) (y:v) = if x < y then x : merge u (y:v) else y : merge (x:u) v 47 Příklad: ms [4,3,1,6,7,2,8,5] mr (ms [4,3,1,6]) ( ms [7,2,8,5]) mr (mr (ms [4,3]) (ms [1,6]) ) ( mr (ms [7,2]) (ms [8,5]) ) mr (mr (mr (ms [4] ) (ms [3] ) ) (mr (ms [1] ) (ms [6] ) ) ) (mr (mr (ms [7] ) (ms [2] ) ) (mr (ms [8] ) (ms [5] ) ) ) mr (mr ( mr [4] [3] ) ( mr [1] [6] ) ) ( mr ( mr [7] [2] ) ( mr [8] [5] ) ) mr Ur [3,4] [1,6]) ( mr [2,7] [5,8]) mr [1,3,4,6] [2,5,7,8] [1,2,3,4,5,6,7,8] _J Věta: Nechť In — Ouť\e množina všech seznamů (posloupností) celých čísel, cp(s) = s je konečný, ^(s, í) = t je permutací seznamu s a t je neklesající. Pak mergeSort je tot/Elě korektní vzhledem k podmínk/Em^, ip. Lemma: Časov/E složitost pomocn0 funkcmerge je Tmerge G O (n). Věta: Časov/E složitost funkcanergeSort je TmergeSort E 0(n - log n). Důkaz tot/Elní korektnosti: Konvergence i parci/Elní koréikost se dok/Eže indukcí podle d0lky seznamu s, parci/Elní korektnost pomocn0 funkceierge se dok/Eže indukcí podle soětu d0lek obou slučovaných seznamů. Line/Erní složitost funkcanerge je zřejm/E: konstantní d0lka porovn/Ení áipojení menšího prvku na zač/Etek posloupnosti se dohromady provede tolikr/Et, kolik jeoučet d0lek obou vstupních posloupností (argumentů funkce merge). Odvození složitosti funkce mergeSort je na n/Esledujících stran/Ech. 49-1 Algoritmus řazení slučov/Ením (imp. verze) type Elem = Integer; Posl = array [1..MAX] of Elem; procedure mergeSort (n:Integer; var A:Posl); var B : Posl; { pomocné pole } procedure msort (p,r:Integer); { seřadí pole od p do r } var q : Integer; begin if p < r then begin q := [(p+r)/2j ; msort (p,q) ; msort (q+l,r) ; merge (p,q,r) end 50 procedure merge (p,q,r:Integer); { sloučí úsek A[p] , . . . ,A[q] s úsekem A[q+1] ,. . .,A[r] } var i,j : Integer; begin i := p ; j := q + 1 ; for k := p to r do if (ir) then begin B[k] := A[i] ; i := i+1 end else if (iA[j]) || (i>q) then begin B[k] := A[j] ; j := j+1 end ; for k := p to r do A[k] := B[k] end begin { mergeSort } msort (l,n) end { mergeSort } Pozn/Emka: Podmíněný příkaz v těle cyklu for procedury merge lze ekvivalentně zapsat kratčeji takto (dokažte) if ( ir || A [i] B[k] := A [i] ; B[k] := A[j] ; (n) T'(l) =a T'(n) = b + 2T'(n/2)+n-c, T' G O (T). Analýza nejhoršího případu je zde trivi/Elní: pro každou vstupní posloupnost ôGfy n algoritmus děl/E stejnou pr/Eci. Pro složitošF : N —)> N tedy platí, že T(n) je rovno d0lce výpočtu na //ibow/n0vstupní posloupnosti d0lkyra. Je-li n < 1, pak T{n) = a, kde a je konstanta. Je-li n > 1, pak T(n) = b + T(\n/2]) +T([n/2\) + D(n), kde D je složitost zbytku těla procedury msort (bez rekursivního vol/Ení), tedy zejm0na pomocn0 procedunjierge. Procedura merge je tvořena cyklem s pevným počtem opakov/Ení^i), takže D(n) = c • n, kde c je konstanta. Tedy D G O (n). Protože /2j a \n/2] se liší nejvýše o 1 (tj. o konstantu), můžeme tento rozdíl zanedbat. Takto upraven/E funkceZ1' roste stejně rychle jako T: T'(l) =a T'{n) = 6 +2T;(ľn/21) + n • c, T' G 9(T). 52-1 Pro několik hodnot n dost/Ev/Eme T'(l) = a Tf(2) = & + 2-T'(l) + 2c = 2a + b + 2c T'(4) = fc + 2-T'(2)+4c = 4a+ 36 +8c T'(8) = & + 2-T'(4)+8c = 8a + 7& + 24c T'(16) = & + 2-T'(8) + 16c = 16a+15& + 64c T'(32) = 6 + 2-T'(16) + 32c = 32a+ 31&+160c Všimneme-li si hodnot T' na mocnin/Ech dvou, můžeme vyslovit tvrzení Věta: Pro každ0& G N je T'{2k) = 2ka + (2k - l)b + 2kkc Vyj/Eateno pomocí n: Tf(n) = a - n + b - (n — 1) -\- c • n log2 n Protože line/Erní funkcea-n, b-n rostou nejvýše tak rychle jako n • log n, tak T' G O {n log n). T roste stejně rychle, takže i TG (9(n log n). 54 Rovnosti T(l) = c T(n) = 2T(\n/2]) + d-n jsou speci/Elním pípadem situace, v níž je T(l) = c T{n) = aT([n/6]) + /(n),kdea > 1, b > 1, O 0 a / je kladn/E funkce. Napíklad pro algoritmus řazení slučov/Ením \ea = 2, 6 = 2, / G (9(n), tedy případ „2" n/Esledující ěty. Věta: Nechť a>l,6>l,/je kladn/E funkce a T(l) = c T(n) = a • T (£) + /(n) Potom: 1. Pokud / G 0(rilogř>a-£) pro nějak0£ > 0, pakT G 6>(nlogř>a). 2. Pokud / G 6>(rilogř>a), pakT G 0(riogba\ogn). 3. Pokud / G í2(nlogř>a+£) pro nějak0£ > 0 a pokud a • /(ra/6) < d • f(n) pro nějak0 |_log2 n\\. To znamen/E, žeT G i?(log n!) = Q{n log n) 55-2 Cvičení: V důkazu věty o dolním odhadu složitosti řadicích algoritmů se mlčky předpokl/Ed/E, že složitost jednoho porovn/Ení dvóísel ai a a j je konstantní. Můžete uv0st lepší (realističtější) odhad časov0 složitosti jednoho porovn/Ení? Cvičení: Ukažte, že log (n • log n) G (9 (log n). Cvičení: Uv/Ežíme-li realistickou složitost jednoho porovn/Ení, j^kvyjde dolní odhad složitosti řadicích algoritmů? Je v rozporu s dok/Ezanou ětou? Je jejím zesílením? 55-3 Algoritmus řazení rozdělov/Ením (funkcion/Elní verze) quicksort :: [Int] —> [Int] quicksort [] = [] quicksort (p:t) = quicksort It ++ [p] ++ quicksort ge where It = [ x | x-<—t, x

p ] Věta: Nechť In — Ouť\e množina všech seznamů (posloupností) celých čísel, cp(s) = „s je konečný", ip(s, ť) = „t je permutací seznamu s a t je neklesající". Pak quicksort je tot/Elě korektní vzhledem k podmínk/Em^, ip. Věta: Časov/E složitost algoritmuquickSort je v 0(n2). Důkaz korektnosti: Konvergence i parci/Elní korektnost seuk/Eže indukcí vzhledem k d0lce seznamu s. 56-1 Řazení rozdělov/Ením (imperativní verze) type Element = Integer; Posl = array [1..MAX] of Element; procedure Quicksort (n:Integer, var A:Posl); procedure Q (l,r:Integer); var p: Integer; begin if l 0 (ostatní případy mají nevýznamnou pravděpodobnost). Ale pak je největší hloubka zanoření rovna log j^n = — logr n. Součet d0lek sěazovaných ceseků v každ0 hloubce je nejvýše^, takže průměrn/Rji0\Wa výpočtu je nejvýše —c • n • logron, tedy v 0(n log n). D/Ele se snadno ověří (například pro ro = 1/2), že n log n je i dolním odhadem, takže průměrn/E d0lka výpočtu je v 0(n log n). 59-2 Prostorov/E složitosřadicích algoritmů Definujeme prostorovou složitost algoritmu analogicky jako časovou složitost, ale za míru složitosti místo počtu kroků výpočtu zvolíme maxim/Elní množství panšti, kter/E bude během výpočtu obsazena. Def: Prostorov/E složitost algoritmuA je funkce, kter/E pro každou velikost vstupních dat je rovna velikosti obsazen0 paměti při výpočtu, jenž t0to paměti spotřebuje nejvíc. Pozn/Emka: Označíme-li p(A, ax) množství paměti spotřebovan0 výpočtem podle algoritmu A z poč/Etěního stavu ax (odpovídajícího umístění dat x na vstupu), potom prostorov/E složitost algoritmuA je Sa(^) — max{p(A, ax) | \x\ — n} 60 Prostorov/E složitost všech zmŤiovaných řadicích algoritmů je line/Erní, \\S G G (n). Důvod je ten, že souč/Estí dat, s nimiž algoritmus pracuje, je samařazen/E posloupnost, a ta m/E d0lkun. Ostatní data (mimo tuto posloupnost, tj. „extrasekvenční") mají v uv/Eéných algoritmech velikost nejvýše 0(n). 60-1 Def: Zavedeme extrasekvenční prostorovou složitost řadicího algoritmu jako funkci zobrazující d0lky vstupní posloupnosti na velikost paměti obsazen0 rii výpočtu v nejhorším případě, ale nezapočít/Ev/Eme paět' obsazenou seřazovanou posloupností. Řadicí algoritmy, kter0 mají extrasekvenční prostorovou složitost konstantní, se nazývají in situ. Řazení rozdělov/Ením není/V? situ. Věta: První varianta algoritmu quickSort m/E extrasekveční prostorovou složitost 0(n), druh/E (modifikovan/E) varianta tohoto algoritmu m/E extrá&©nční prostorovou složitost (9 (log n). J 61 Pozn/Emka: Hovořit o řadicích algoritmech, zda jsou in situ, a zav/Eět jejich extrasekvenční prostorovou složitost m/E praktický význam jen tehdy, je-lposloupnost reprezentov/Ena polem a uložena v souvisl0m ceseku pareti. Při jiných datových reprezentacích posloupnosti (např. seznamem) se extrasekvenční prostorov/E složitost nezav/Edí. 61-1 Řazení haldou Def: Nechť K je oeplrě uspoř/Edan/E množina XzMíčů (typicky množina čísel s přirozeným uspoř/Ed/Enírr<). Bin/Erní hald^e bin/Erní strom, jehož uzly jsou ohodnoceny prvky množiny K, a který splňuje tyto vlastnosti: 1. D0lky všech větví se liší nejvýše o 1: mají Ó0\kuk, případně k — 1. Číslu k pak řík/Eme/7/o^jb/ca haldy. 2. Hodnoty uzlů na každ0 větvi jsou vzestupně (sestupně) uspoř/Ed/Eny. Jsou-li hodnoty uzlů na každ0 větvi seřazeny vzestupně (čím d/Ele od kéene, tím větší hodnoty), je v kořenu haldy nejmenší prvek. Hovoříme pak o minimov0ha\óě (min-heap). Jsou-li hodnoty uzlů na každ0 větvi seřazeny sestupně (čím d/Ele od kčene, tím menší hodnoty), je v kořenu haldy největší prvek. Hovoříme pak o maximov0ha\óě (max-heap). ___J Ve funkcion/Elní implementaci algoritmiřazení haldou, kde se pracuje s explicitní haldou (datovou strukturou bin/Erní strom), použijeme minimovou laldu. Naopak v imperativní implementaci, kde se pracuje s implicitní haldou (reprezentovanou polem), je výhodnější použít maximovou haldu. 62-1 Operace s bin/Erní haldou data Heap = Empty I Node Elem Heap Heap Z/Ekladní operace - konstruktory a selektory - mají konstanhí složitost. Konstruktory Empty : Heap Node : Elem —» Heap —» Heap —» Heap Selektory rootVal : Heap —-> Elem lef tHeap : Heap —■> Heap rightHeap : Heap —■> Heap isEmpty : Heap —> Bool Další operace pro pr/Eci s bin/Erní haldou Vyhled/Ení minim/Elního prvku (v minimov0 hátyJ minH : Heap —■> Elem minH = rootVal (složitost 0(1)) Odstranění minim/Elního prvku (z minimov0 haldy) extractMinH : Heap —■> Heap (složitost 0(log ri)) Odstranění maxim/Elního prvku (z maximovO haldy) extractMaxH : Heap —■> Heap (složitost 0(log ri)) Přid/Ení prvku insertH : Elem —> Heap —> Heap (složitost 0(log ri)) Odstranění prvku removeH : Heap —> Heap —■> Heap (složitost 0(log n)) Věta: Nepr/Ezdn/E bin/Erní halda mauzlech m/E hloubkuLlog2nJ. Důkaz indukcí podle n. Def: Bin/Erní strom, v jehož každ0m podstromu se poet uzlů Iev0ho a prav0ho podstromu liší nejvýše o jednu, se nazýv/Euzlově vyv/Eženýom/Emí strom. Věta: Každý uzlově vyv/Ežený bin/Erní strom je haldou (až na ohodnocení uzlů). Důkaz: Je třeba dok/Ezat, že d0lky všechš^ví uzlově vyv/Ežen0ho stromu se liší nejvýše o jednu. Předpokl/Edejme sporem, že tvrzení neplatí, áT je nejmenší strom, který tvrzení porušuje. Tedy v každ0m podstromu stromuT se počet uzlů vlevo a vpravo liší nejvýše o jednu, ale existují zde dvě větve d0lekm a k, přičemž m > k + 2. Z minimality stromu T plyne, že jedna z těchto dvou větví, řekněme ta delší, d0lkym, leží v Iev0m podstromuX/ stromu T, a druh/E, kratší, o0\Wjz, v prav0m podstromuTr stromu T. Navíc, rovněž z minimality, všechny větve jdoucí do T\ mají d0lkum nebo m — 1, všechny větve jdoucí do Tr mají d0lku& nebo k + 1. To znamen/E, žeZ] m/E aspá o dva uzly víc než Tr. Ale podle předpokladu věty m/E nejvýše o jeden uzel více, což je spor. 67-1 Algoritmus řazení bin/Erní haldou (funkcion/Ení verze) data Heap = Empty I Node Int Heap Heap insHeap : : Int —>• Heap —>• Heap insHeap u Empty = Node u Empty Empty insHeap u (Node v p q) = if u > v then Node v (insHeap u q) p else Node u (insHeap v q) p toHeap : : [Int] —>• Heap toHeap s = foldr insHeap Empty s toList : : Heap —>• [Int] toList Empty = [] toList (Node x 1 r) = x : merge (toList 1) (toList r) heapSort : : [Int] —>> [Int] heapSort = toList • toHeap _J 68 Korektnost řazení haldou Věta: Algoritmus heapSort je tot/Elě korektní řadicí algoritmus. Konvergence algoritmu je zřejm/E. Důkaz parci/Elní korektnosti vyplýv/E z n/EsledoJicí lemmat. Lemma: Funkce toList vytvoří z haldy h seznam s týmiž prvky jako měla halda h, ale uspoř/Edaný vzestupe. Lemma: Je-li u číslo a h uzlově vyv/Ežen/E halda, paknsHeap u h je halda obsahující pr/Eé prvky z haldy h a prvek u. Lemma: Funkce toHeap vytvoří ze seznamu s haldu obsahující tyt0ž prvky jako seznam s. Důkaz prvního lemmatu indukcí podle velikosti haldy. Důkaz druh0ho lemmatu: indukcí podle počtu prvků v h se uk/Eže, že bin/Erní strom insHeap u h bude opět uzlově vyv/Ežený. Podle věty o bin/Erních stromech vyv/Ežených vzhledem k přcbu uzlů bude výsledek opět halda. Uspoř/Ed/Ení hodnot pod0ěto/í vyplýv/E z definice funkceinsHeap. Třetí lemma indukcí podle d0lky seznamu a z definice kombin/Etnu f oldr. foldr insHeap Empty \_x\ 9X2 ,... ,xn] = insHeap X\ (insHeap X2 (• • • (insHeap xn Empty)...)) 69-1 Složitost řazení haldou Lemma: Procedura insHeap m/E složitost vO(log n). Důkaz: Funkce insHeap se rekursivně vyhodnotí pr/Eé tolikr/Et, jako je hloubka haldy. Ale ta je logaritmick/E vzhledem k potu jejích uzlů, jichž je vždy nejvýše n. Věta: Algoritmus řazení haldou m/E složitost v0(n log n). Důkaz: Z předchozího lemmatu vyplýv/E, že složitost funkcetoHeap je v 0(n log n). Ve funkci toList je hloubka rekursivního zanoření logaritmick/E, protože seznamy se půlí. Složitost pomocn0 funkcemerge je line/Erní a oehrnn/E d0lka vyfia>všech vol/Ení ti/ funkce merge ve stejn0 hloubce k (tj. se stejně dlouhými seznamy) je —r • 2k = n. 2K Funkce toList m/E tedy složitost tak0 \0(n log n). Celkem je tedy horní odhad složitosti funkce heapSort n log n, ale podle Věty o dolním odhadu složitosti řadicích je toto i dolním odhadem. V imperativním algoritmu heapSort se použív/E maximov/E halda, tj. bin/Erní halda, kter/E m/E položky ve ětvích seřazeny sestupně. Tedy největší položka je vždy v kořeni. Jelikož algoritmus m/E haldu efektivě reprezentov/Enu polem, je zde výhodější uvažovat bin/Erní haldu nikoliv uzloě vyv/Eženou, ale naopak s levým podstromem ,$žším". Def: Vlevo zarovnan/E haldqe bin/Erní halda, jejíž všechny ětve 60\kyk leží nalevo od větví d0lky/c — 1. 71 72 Věta: Reprezentujme vlevo zarovnanou bin/Erní haldu nan uzlech posloupností hodnot jejích uzlů (ai,..., an) takto: a\ reprezentuje kořen haldy a je-li uzel u reprezentov/En prvkerra^ pak levý n/Esledník uzluu je reprezentov/En prvkem^ a pravý n/Esledník uzluu je reprezentov/En prvkerra2i+i. Pak posloupnost (ai,..., an) je haldou určena jednoznačně. Věta umožňuje pracovat s vlevo zarovnanou bin/Erní haldou reprezentovanou v paměti polem. Vlevo zarovnan/E bin/Erní halda je tot0ž jako pole ropean0 „po vrstv/Ech". 73 Algoritmus řazení bin/Erní haldou (imp. verze) type Element = Int; Posl = array [1..MAX] of Element; procedure heapSort (n:Int, var A:Posl); var 1,r: Int; x: Element; procedure createHeap (l,r:Int); { vytvoření haldy A[l]...A[r] ze dvou podhald začínajících A[2*1] a A[2*1+1] } var i,j:Int; {pom. indexy} y:Element; {zařazovaný prvek} p:Bool; {sestupovat?} begin i := 1; j := 2*i; y := A[i]; p := True; while p && (jy, takže posuneme A[j] o patro výš } begin A[i] := A[j]; i := j; j := 2*i end end; A[i] := y { prvek y zařazen na své místo } end {createHeap}; 74 begin {heapSort} { postupně vytvoříme haldu A [1],...,A[n] } for 1 := n div 2 downto 1 do createHeapd,n); { V kořenu (A[l]) je prvek s největším ohodnocením.} { Vyměníme ho s koncem pole, haldu zkrátíme } { a restaurujeme zařazením A[l] na správné místo } for r := n downto 2 do begin x := A[l]; A[l] := A[r] ; A[r] := x; createHeap (l,r-l) end end {heapSort}; Korektnost a složitost imperativního algoritmu heapSort Věta: Mějme vlevo zarovnanou bin/Erní haldu reprezentovanou poslopností (a/,..., ar) a nechť oba podstromy pod kořenem splňují podmínky haldy. Pak posloupnost (aj,..., a'r) ve stavu po provedení createHeap(a, Z, r) splňuje podmínky (vlevo zarovnan0) bin/Erní haldy. Důkaz indukcí podle hloubky haldy. Věta: Provedení procedury heapSort (A) seřadí posloupnost A Idea důkazu: Jednoprvkov0 podstromy reprezentováno drubu polovinou posloupnosti A jsou trivi/Elní podhaldy. První f/Eze algoritmu vyt#lž těchto podhald větší podhaldy. Na konci první f/Eze je posloupnostA bin/Erní haldou. Druh/E f/Eze algoritmu vytvbz haldy seřazenou posloupnost. To vyplýv/E z toho, že největší prvek haldy je vždy v jejím kořenu: největší prvky se skl/Edají na konec posloupnosti. Věta: Algoritmus řazení haldou konverguje. Důkaz: Tvrzení věty vyplýv/E z koněn0 velikosti a hloubky haldy. Věta: Řazení haldou (imperativní algoritmus) m/E složitost v0(n log n). Důkaz: První f/Eze (vytvoření haldy) m/E složitostO ^— log , druh/E f/Eze m/E složitost 0(n log n), obě tedy dohromady 0(n log n). Podle Věty o dolním odhadu složitosti musí být rovněž v (2{n log n). Z obou odhadů pak plyne tvrzení. Datov0 struktury Typy rozlišujeme datov0a funkcion/Elní Datov0 typy lze zav0st pomocí funkcion/Elních,řqoadně funkcion/Elní typy lze simulovat pomocí nekonečných datových typů, ale kvůli efektivnosti implementace se rozlišují a uvažují se zvl/Ešť. Hodnoty funkcion/Elních typů \soufunkce a procedury. Jednotliv0 funtôní hodnoty (či vedlejší efekty procedur) nejsou zn/Emy pedem, ale dospěje se k nim po výpočtu. Ten je spuštěn tzv. vol/Enírrc\\\ aplikací na argumenty. Hodnoty datových typů jsou obvykle zn/Emy a uloženy v panšti, ale jejich složky je třeba najít a zpřístupnit (například najít prvek pole podle indexu apod). 78 Datov0 typy mohou býts/ca/^Er/7/nebo složen0 Skal/Erní datov0 typy v dan0m programovacím jazyce obvykleaiirnují číseln0 typy (cel/E nebo desetinn/Ešísla z určit0 kone5n0 množiny), znakov0 typy, typ pravdivostních hodnot apod. Data skal/Erního typu zabírají vždy konstantní a mal0 množství paměti (typicky do 10 B). Zpřístupnění hodnoty skal/Erního typu trv/E konstantní dobu. Složen0 datov0 typy jsou napíklad z/Eznamy#,-tice s pojmenovanými složkami), uniony, posloupnosti, množiny apod. Data složených typů se nazývají datov0 struktury • Datov0 struktury pevn0 velikosti ^-tice, statick/E pole,...) — \zvstatick0 datov0 struktury • Datov0 struktury prorrěnn0 velikosti — \zv.dynamick0 datov0 struktury _) Statick0 datov0 struktury mají konstantní velikost ačasov/E složitost zpístupnění Iibovoln0ho prvku je konstantní. Dynamick0 datov0 struktury mají velikost danou ějakou proměnnou n, jejíž hodnota se může měnit. Časov/E složitost zpístupnění Iibovoln0ho prvku dynamick0 datov0 struktury je neklesající funkcí z/Evislou nan; často line/Erní, u efektivních datových struktur lepší, typcky logaritmick/E. 79-1 Dynamick0 datov0 struktury Seznam Seznam nad b/Ezovým typemB je line/Erní datov/E struktura typS s n/Esledujícími operacemi: nil : S cons : B x S -> S head : S —> B tail : S —> S null : S -> Bool Pro tyto operace a každou hodnotu x typu B a každý seznam s typu S musí platit Axiomy seznamu null(nil) = True null(cons(x,s)) = False head(cons(x,s)) = x tail(cons(x,s)) = s 81 Z/Esobnik Z/Esobnik nad b/Ezovym typerB je line/Erni datov/E struktura typS s n/Esledujicimi operacemi: empty : S push : B x S -> S top : S —> B pop : S —■> S isempty : S —> Bool Pro tyto operace a každou hodnotu x typu B a každý z/Esobníks typu S musí platit tzv. Axiomy z/Esobníku isempty(empty) = True isempty(push(x,s)) = Falše top(push(x,s)) = x pop(push(x,s)) = s 83 Jak je vidět, z/Esobník a seznam je tat/Ež datov/E struktura. Liší se pouze v použití: O z/EsobníkuDbvyk\e mluvíme, když na něm použív/Eme jen z/Ekladní operace a pracujeme jen s jedním z/Esobníkem nebo pevě daným malým počtem z/Esobníků. Z/Esobníky bývají d/Enyřpdem: během výpočtu se mění jejich obsah, ale nemění se počet z/Esobníků, tj. neruší se a nevznikají nov0 z/Esobníkyrdfto se v imperativních jazycích z/Ekladní operacečasto implementují jako procedury; navíc jejich parametr z/Esobník se vynech/Ev/E, pracuje-li se jen s jedním z/Esobníike U seznamů často definujeme složitější operace (zpřístupnění či změnu n-t0ho prvku rozdělení seznamu na dva, spojení dvou seznamů,...) a během výpočtu seznamy vytv/Eíme a rušíme. Například změnu třetího prvku (alespoň tříprvkov0ho) seznamu s na číslo 5 lze realizovat složenou operací cons (a, cons(b, cons (5,t)))), kde a = head(s) b = head(taiKs)), t = tail(tail(tail(s))). Fronta Fronta nad b/Ezovým typemB je line/Erní datov/E struktura typQ s n/Esledujícími operacemi: empty : Q head : Q —■> B enqueue : B x Q —> Q dequeue : Q —■> Q isempty : Q —> Bool Pro tyto operace a každ0 hodnoty^, y typu B a každou frontu g typu Q musí platit Axiomy fronty isempty(empty) = True isempty(enqueue(x,g)) = False head(enqueue(x,empty)) = x head(enqueue(x,enqueue(y, g))) = head(enqueue(y, g)) dequeue(enqueue(x,empty)) = empty dequeue(enqueue(x,enqueue(y, g))) enqueue(x,dequeue(enqueue(y, g))) 87 Implementace datových struktur Jestliže typ datov0 struktury není souč/Estí jazyka, je nutn0 vyj/Etldatovou strukturu a operace nad ní pomocí jiných struktur a operací. Takov0 koláčci definic řík/Eme implementace datov0 struktury Například z/Esobník (omezen0 d0lky) lze implementovat pomoc6l(atick0ho) pole, frontu lze implementovat pomocí dvou z/Esobníků, frontu omezen0 d0lky pomocí cyklick0ho pole apod. Pozn/Emka: Jazyky s malou podporou dynamických datových struktur (Pascal, C,...) často poskytují alespoň dynamickou datovou strukturu „nízk0 cerové": paměť M spolu s typem ukazatel (adresa) P, nul/Erní operacíiil: P pr/Ezdn0ho ukazatele a un/Erní operací zpístupnění (dereferencov/Ení)67Esti panšti deref :P—*M. Pak například seznam se běžně implementuje pomocí z/Eznamů \M, jejichž složky jsou ukazatele na další z/Eznamy, apod. 88-1 Příklad: Implementace ohraničen0 fronty pomocí cyklick0ho pole { procedury pracují pouze s jedinou globální frontou const M = 256; { délka pole } MAX = M-l; { kapacita fronty } type R = 0..MAX; Elem = Integer; var Q : record a : array [R] of Elem; h, t : Integer end; \ procedure mkemptyq; begin Q.h := 0; Q.t := 0 end; function isempty : Boolean; begin isempty := Q.h = Q.t end; function isfull : Boolean; begin isfull := Q.h = (Q.t + 1) mod M end; _J 91 function headq : Elem; begin if isemptyq then err("headq prázdné fronty") else headq := Q.a[Q.h] end; procedure enqueue (x:Elem); begin if isfull then err("enqueue do plné fronty") else begin Q.a[Q.t] := x; Q.t := (Q.t + 1) mod M end end; procedure dequeue; begin if isemptyq then err("dequeue prázdné fronty") else Q.h := (Q.h + 1) mod M end; Příklad: Implementace fronty pomocí dvou seznamů data Queue = Q [Int] [Int] emptyq :: Queue emptyq = Q [] [] isemptyq : : Queue —>- Bool isemptyq (Q [] []) = True isemptyq _ = False enqueue : : Int —>- Queue —>- Queue enqueue x (Q h t) = Q h (x:t) headq : : Queue —>- Int headq (Q (x:_) _) = x headq q = head h where Q h _ = revq q dequeue : : Queue —>- Queue dequeue (Q (_:h) t) = Q h t dequeue q Q u [] where Q (_:u) [] = revq q revq (Q [] t) Q (reverse t) [] 95 Cvičení: Funkce headq a dequeue z predešl0 strany zůst/Evají nedefinov/Enyipaplikaci na pr/Ezdnou frontu. Doplite jejich definice tak, aby jejich aplikace na pr/Ezdnou froitu způsobila chybov0 hl/Ešení. Využijte haskellovsk0 funkcerror : : String—>>a. D/E se lehce spóítat, že časov0 složitosti operacíisemptyq a enqueue z předchozího příkladu jsou konstantní, zatímco obě operace headq a dequeue jsou line/Erní vzhledem k velikosti fronty. V nepřízniv0m pfípadě je totiž nutn0 volat pomocnou operacirevq, kter/E je sama line/Erní. Přesto i na tyto „dražší" operace lze v kontextu programu, v němž jsou použity, pohlížet v jist0m smyslu jako na operace v průrrěrn0m (oček/Evan0m) ppadě konstantní. 95-1 Amortizovan/Easov/E složitost Def: Nechť / je operace na dan0 datov0 struktĚe D velikosti (nejvýše) n. Uvažujme všechny výpočty Ci,..., Cm podle algoritmů pracujících s datovou strukturou D. Z každ0ho takov0ho výpétu vybereme všechna vol/Ení operace/ (tj. všechny aplikace / na D), čímž dostaneme m posloupností vol/Ení operace/. Průměrnou d0lku výpočtu operace / v i-t0m výpočtu označíme rfv. Potom amortizovan/E s/oz/řostoperace / na datov0 struktiře D je funkce Tamort : N —> N definovan/E pro každou velikost datn takto Tamort(n) = max{rfv|l T rootval : T —■> B left : T —► T right : T —■> T isempty : T —> Bool Pozn/Emka: Z/Ekladní operace mají konstantní složitost, slouží k popis datov0 struktury a k její implementaci a k implementaci dalších operací, jako například vyhled/Ení/pid/Ení/odebr/Ení uzlu, vyv/Ežení stromu a podoŠDn Pro z/Ekladní operace, každou hodnotux typu B a každ0 bin/Erní stromy, r typu T musí platit Axiomy bin/Erního stromu isempty(empty) = True isempty(node(x,Z,r)) = False rootval(node(x ,1,r)) = x left(node(x,l,r)) = I right(node(x ,1,r)) = r J 103 Implementace bin/Ernich stromu v Haskellu data Tree b = Empty I Node b (Tree b) (Tree b) isempty : : Tree b —>• Bool isempty Empty = True isempty (Node _ _ _) = False rootval : : Tree b —>• b rootval (Node x _ _) = x left :: Tree b -> Tree b left (Node _ 1 _) =1 right : : Tree b —>• Tree b right (Node r) = r _j 104 Stromy s neomezeným větvením Def: Je d/Ena b/Ezov/E množina (tyfl. Nechť b E B. Pak pro každ0 p%ozen0číslo k > 0 a každou /c-prvkovou posloupnost nepr/Ezdných stromů nad£? je dvojice (6, [Ti,..., Tk\) nepr/Ezónýmstromem s neomezeným větvením nad B. Pozn/Emka: Druhou složkou uspoř/Edan0 dvojice(6, [Ti,..., T^]) je /c-prvkov/E posloupnost stromů, tj. seznam d0lky/c. Je-li k = 0, je seznam pr/Ezdný a dvojice reprezentuje jednouzlový strom (list) s ohodnocením b. Stromy s neomezeným větvením se od stromů pevn0 arity liší tím, žečíslo k není předem pevně dan0, ale může být v jednom stromu pro různ0 uzly různ0. Pozn/Emka: Stromy s neomezeným větvením lze reprezentovat bin/Erními stromy. 105 Stromy s neomezeným větvením a bin/Erní stromy data NTree a = NNode a data BTree a = BEmpty f b : : fb [] fb (NNode v fr : frb) = nb :: NTree a —> BTree a nb t = fb [t] bf bf BEmpty bf (BNode v bn :: BTree a —> NTree a bn t = head (bf t) [ NTree a ] I BNode a (BTree a) (BTree a) [ NTree a ] -> BTree a BEmpty BNode v (fb fr) (fb frb) :: BTree a -> [ NTree a ] = [] ec ys) = NNode v (bf ec) : bf ys 107 Vyhled/Ev/Ení Def: Nechť (K, <) je oeplrě uspoř/Edan/E množina XzMíčů, V je libovoln/E množina tzv. doplňujících oedajů. Nechť/7 = K x V je množina dvojic (k,v),v níž se každý klíč k vyskytuje nejvýše jednou (tj. každý z/Eznam z množiny/7 je určen jednoznačně svým klíčem). Probl0mu nal0zt k dan0mu ktí k z/Eznam(/c, v) E U se V\k/Evyhled/Evacíprobl0m Pozn/Emka: Například z/Eznamy mohou být osobní data a klíi jsou rodn/Eísla, anebo z/Eznamy jsou oedaje o knih/Ech v knihám klíče jsou knihovní signatury apod. 108 Pozn/Emka: V praxi m/E ětšinou smysl pouze případ, kdy množina V je netrivi/Elní, aby bylo co hledat. V uk/Ezkových algoritmech se však dopňující oedaječasto neuvažují, tj. vyhled/Evají se jen klíče. Příslušn0 rozšření těchto algoritmů je totiž přímočar0. 108-1 Algoritmus bin/Erního vyhled/Ev/Ení type Elem = Integer; Pole = array [1..999] of Elem; function bSearch (k: Elem; var D: Pole; n: Integer): Integer; { Posl. D je rostoucí. Když D[i]=k, tak bSearch(k)=i, jinak bSearch(k) function bs (1, r: Integer) : Integer; var m : Integer; begin if 1 > r then bs := -1 {nenalezeno} else begin m := (1+r) div 2; if k < D[m] then bs else if k > D[m] then bs else {k = D[m]} bs end end {bs}; = bs(l,m-l) = bs(m+l,r) = m begin bSearch := bs (l,n) end Věta: Algoritmus bin/Erního vyhled/Ev/Ení m/E logaritmiclšseovou složitost, tj. jeho složitost je v (9 (log n), kde n je d0lka prohled/Evan0ho pole. Pozn/Emka: Extrasekvenční paměťov/E složitost algoritmu je konstantní, protože rekursivní vol/Ení v ěm jsou prost/E 110 Cvičení: Implementujte algoritmus bin/Erního vyhled/Ev/Ení bez potížekurse. Cvičení: Dokažte tot/Elní korektnost algoritmu bin/Erního vyhled/Eřu/E 110-1 Hašov/Ení 0 množině K všech možných klíčů obecně předpokl/Ed/Eme jen to, že na ní existuje oepln0 uspoř/Ed/Ení.ělkdy však tato množina může mít další speci/Elní vlastnosti jichž lze využít pro efektivní vyhled/Ev/Ení. Náfklad je-li K = {1,..., m} a číslo m je mal0, můžeme data z množiny V uložit do jednorozměrn0ho pole a klce využít jako indexy. Vyhled/Ev/Ení v takov0to datov0 struktioe je efektivní - stejně rychl0 jako indexov/Ení pole. Navíc, pokud se počet n skutečně uložených prvků bude blížit počtu m všech možných klíčů, bude efektivní 1 využití paměti. Pokud je \K\ = m, ale klíče nejsou čísla, lze to obejít pomocí bijektivní funkce h : K —>> {1,..., m} a pole indexovat pomocí fukčních hodnot h(k), kde k G K. Je však důležit0, aby výpočet hodnot funkce h byl rychlý, v ide/Elním pípadě aby měl konstantní časovou složitost. Funkci h nazýv/Emehašovací funkcí a pole indexovan0 jejími hodnotami nazýv/Emeftašoi/ac/' tabulkou. 110-2 Hašovací tabulky Hašovací tabulka je datov/E struktura, pomocí níž lze praktiky efektivně realizovat „slovníkov0" operace vyhled/Ení, pd/Ení a zrušení položky. „Prakticky efektivně" znamen/E, že operace mají píznivou průměrnou časovou složitost (tedy ne nutně časovou složitost v nejhorším případě). Hašovací tabulka je jednorozměrn0 poleií indexovan0čísly 1,..., n. Převod klíčů na čísla realizuje hašovací funkce h : K —> {1,..., n}. Výpočet hodnot hašovací funkce musí být efektivní, nejl0pe složitosti 0(1). ni Častým případem však je, že počet n skutečně uložených prvků je podstatně menší než počet m všech možných klíčů. I v tomto případě lze postupovat podobně a data ukl/Edat do n-prvkov0ho pole, až na to, že funkce/i : K —>> {1,..., n} nebude injektivní. Bude tedy existovat index i a klíče fci,..., kr, tak, že h{k\) = • • • = h(kr) = i. To nemusí vadit, pokud je splněna n/Esledující podmínka. Oznáme K' podmnožinu klíčů, K' C K, těch dat, kter/E budou skutěně uložena (tedy \K'\ < n). Pak požadujeme, aby z každ0 množiny klíčů, kter0 hašovací funkce zobrazí na stejný index, byl v mncžině K' nejvýše jeden klíč. M/E-li pro pevě danou množinu K' klíčů skutečně uložených dat hašovací funkce tuto vlastnost, nazýv/Eme \dokonalou hašovací funkcí pro klíče z K'. Výhodou tabulek s dokonalými hašovacími funkcemi je optim/Elní složitost výiled/Ení, vložení i zrušení prvku; je stejn/E jako pro pole. 111-1 Označme K' podmnožinu klíčů, K' C K, těch dat, kter/E budou skutěně uložena. Klíče z množiny K' nazveme použit0 klče. Je-li zcežení/ilx7 • K' —> {1,..., n} injektivní, řík/Eme, že hašovací funkce je do/co/7a//B/zhledem k množině použitých klíčů K'. Věta: M/E-li výpčet hašovací funkce konstantní složitost a hašov/Ení je dokoal0 pro množinu použitých klíčů K', pak operace vyhled/Ení, vložení, resp. zrušení prvku v hašovací tabulce mají stejnou časovou složitost, jako vyhled/Ení, vložení, resp. zrušení prvku v poli. 112 Nevýhodou dokonalých hašovacích funkcí je, že z/Evisí na mnáině K'. Tato množina musí být zn/Ema pedem, abychom mohli dokonalou hašovací funkci sestrojit. V praxi však ukl/Edan/E datařpdem nezn/Eme a tato data se nšní. Proto v praxi používan0 hašovací funkce většinou nebývají dokonal0 a musí se počítat s takzvanými kolizemi. Kolize je případ, kdy m/E být více dat uloženo na jedn0 pozici hašovací tlaulky, tj. chceme uložit data s různými klíči fci,..., kr a h(k\) = • • • = h(kr). 112-1 Kolize Tzv. kolize vznikají při nedokonal0m hašov/Ení: hašovací funkce zobrazuje více požitých klíčů na stejnou pozici pole. Nejjednodušší řešení kolizí je ukl/Edat do každ0 pozice po\®eznam prvků. V něm se pak hled/E sekvečně. Složitost přid/Ení prvku zůst/Ev/E stejn/E jako složitost indexov/Ere,|sd)é složitost vyhled/Ení i složitost zrušení prvku je(9(n). To je sice velmi špatný výsledek, ale v praxi nevadí, protože průměrn/E;asov/E složitost dopadne pro vhodě sestrojenou hašovací funkci mnohem I0pe. Věta: Nechť hašovací funkce zobrazuje použit0 klče na indexy 1,..., n rovnoměrně, tj. pravděpodobnost, že h(k) = i, je stejn/E pro všechny indexyi, 1 < i < n. Pak průměrn/Ešasov/E složitost vyhled/Ení,řj3d/Ení a zrušení prvku pak jeO ( K'\ /n), za předpokladu, že složitosti výpočtu hašovací funkce i indexov/Ení pole jsou konstantní. 113 Pravděpodobnostní rozložení výskytů klíčů v množině K' nemusí být rovnoměrn0, ale dobře navržen/E hašovací funkce transformuje toto rozložení na r©noměrn0 v množině indexů {1,..., n}. To znamen/E, že pro n/Ehodhzvolený klíč k G K' a index i, 1 < i < n, je 1 pravděpodobnost, že hodnota h(k) = i, stejn/E nez/Evisle nžc a i a rovn/E—. Nyní pro jednoduchost předpokl/Edejme, žeK = {1,..., m} am > n, kde n je velikost hašovací tabulky. Nechť p je prvočíslo, p > m, a nechť a, 6 jsou cel/E5ísla, 0 < a < p, 0 < b < p. Hašovací funkci ha^ zavedeme takto: ha,b{h) = ((ak + b) mod p) mod n Pak při volbě parametrů a, 6 nez/Evisle noK (což je v praxi splněno) mají hodnoty h{k) rovnoměrn0 pravcěpodobnostní rozložení na množině indexů {0,..., n — 1}. 113-1 Bin/Erní vyhled/Evací stromy Def: Bin/Erní vyhled/Evací strofy® bin/Erní strom nad oepěnuspoř/Edanou množinou (tzv. klíčů) (if, <) takový, že pro každý jeho podstrom t platí: hodnoty uzlů v podstromu left (ŕ) jsou menší než rootval(t) a hodnoty uzlů v podstromu right (t) jsou větší než root val (ŕ). Operace nad bin/Erními vyhled/Evacími stromy Datový typ data STree a = Empty I Node a (STree a) (STree a Zjišf ov/Ení píslušnosti member : : a —>• STree a —>• Bool member _ Empty = False member k (Node v 1 r) = k == v I I k < v && member k 1 I I k > v && member k r Vyhled/Ev/Eni search : : a —>• STree a —>• STree a search _ Empty = Empty search k t@(Node v 1 r) I k == v = t I k < v = search k 1 I otherwise = search k r Vkl/Ed/Ení uzlu insert insert k Empty insert k t@(Node v 1 r) I k < v I k > v I otherwise :: a -> STree a -> STree = Node k Empty Empty = Node v (insert k 1) r = Node v 1 (insert k r) = t Rušení uzlu delete : : a —>• STree a —>• delete _ Empty delete k (Node v 1 r) I k < v I k > v I otherwise STree a Empty = Node v (delete k 1) = Node v 1 (delete k = join 1 r join :: STree a -> STree a -> STree a join 1 Empty = 1 join Empty r = r join 1 r = Node u (delete u 1) r where u = rightmostkey 1 rightmostkey (Node v _ Empty) = v rightmostkey (Node r) = rightmostkey r Cvičení: Vybudujte vyhled/Evací strom z posloupnosti klíů 9,12,10,7,12,1,8, 5,11,4,0,14,13,3,6,2. Cvičení: Zrušte v něm uzel s klíčem 5. Cvičení: Definujte v Haskellu funkci lef tmostkey. Cvičení: Dokažte, že bin/Erní strom vzniklý vložením resp. zrušením izlu z vyhled/Evacího stromu pomocí funkcí insert resp. delete bude opět vyhled/Evací. 118-1 Cvičení: Modifikujte funkce member, search, insert, delete tak, aby pracovaly s realističtějším vyhled/Evacím stromem, v ěmž jsou kromě klíčů uložena i vlastní data: data STree a b = Empty I Node (a,b) (STree a b) (STree a b) member : : a —)> STree a b —)> Bool search : : a —> STree a b —>• Maybe b insert :: (a,b) -> STree a b -> STree a b delete :: a -> STree a b -> STree a b 118-2 Složitost vyhled/Ev/Ení ve vyhled/Evacích stromech Označíme-li T : N -> N složitost funkce search, pak T(0) = c T(h) = c' + max{T(/i'),T(/i")} kde h je hloubka vyhled/Evacího stromu/i' je hloubka jeho Iev0ho podstromu,^" je hloubka jeho prav0ho podstromu ac, c' jsou konstanty. Zřejmě max{T(/z/), T(h")} = fc-la řešením uveden0 rekursivní soustavy rovnic je line/Erní funkce. 118-3 Složitost vyhled/Ev/Ení ve vyhled/Evacích stromech Složitosti operací vyhled/Ení, pid/Ení a zrušení položky ve vyhled/Evacím stroěijsou přímo oeněrn0 hloubce stromu. Ta je v nejhorším riípadě line/Erě z/Evisl/E na velikosti stromu (počtu jeho uzlů). Složitost vyhled/Ev/Ení, vkl/Ed/Ení a rušení v obecn0m vyľtaiŕfr stromě je tedy line/Erní. 119 AVL stromy Nazvan0 podle G. M. Adeľsona-Veľsk0ho a E. M. Landise. Def: Vyhled/Evací bin/Erní strom \áVL, když hloubka Iev0ho a prav0ho podstromu Iibovoln0ho uzlu se liší nejvýše o jednu. Věta: Hloubka AVL stromu v z/Evislosti na potu jeho uzlů je vždy v (9 (log). AVL stromy tedy mají logaritmickou hloubku — použijeme-li je jako vyhled/Evací stromy, pak m/E operace vyhled/Ení položky logaritmickou složitost. 120 Def: Fibonacciho strom ř/Edufc definujeme takto: FTq = empty FTi = node(empty, empty) pro k e N je FTk+2 = node(FTfc, FTk+1) Lemma: Pro k > 1 je Fibonacciho strom FTk minim/Elní(vzh\eóerr\ k počtu uzlů) AVL strom hloubky k — 1. Důkaz: Indukcí přes k se snadno uk/Eže, že hloubka nepr/Ezdn0ho stromET^ je A: — 1. Odtud a z definice Fibonacciho stromů vyplýv/E, že Fibonacdiio stromy jsou AVL. Minimalita je důsledkem předchozích dvou bodů: odebr/Ením ějakOho uzlu z jin0 než nejpravější větve by někde vznikly sousední podstromy s hloubkami lišícími se aspoň o dvě; odebr/Ením uzlu z nejpraější větve by se snížila hloubka cel0ho stromu. 120-1 Věta: Hloubka AVL stromu v z/Evislosti na potu jeho uzlů je vždy v (9(log). Důkaz: Označme N(k) velikost stromu FT^. Tedy N : N —>- N a N(0) = 0 N(l) = 1 pro A: G N je N (k + 2) = 1 + N (k) + iV(fe + 1) Protože funkce TV majorizuje Fibonacciho funkci, je N G Í2((p ), kde (p = -a za k 2 bereme ř/Ed stromu. Ale víme, žeř/Ed stromu a hloubka je (skoro) tot0ž, takže dost/Ev/Eme, že počet uzlů Fibonacciho stromu hloubky h roste aspoň tak rychle jako (ph. Protože Fibonacciho strom je minim/Elní AVL strom, m/Eme, žeqžet uzlů každOhoAVL stromu hloubky h roste aspoň tak rychle jako (ph. Obr/Eceě, každý AVL strom velikosti n m/E hloubku 0(log^ n). 120-2 Víme, že hloubka každ0ho bin/Erního stromu velikosti je /2(log2 n). Dohromady m/Eme hloubku vO(log^ n) fl i7(log2 rc) = <9(log). 120-3 Operace na AVL stromech Datov/E struktura: data AVL a = Empty | Node Int a (AVL a) (AVL a) Každý uzel nese informaci o hloubce (jakožto parametr konstruktorov0 funkceNode). Vyhled/Ev/Ení v AVL stromu se neliší od vyhled/Ev/Eníežrlx0m vyhled/Evacím stromu. Po přid/Ení nebo odebr/Ení položky ovšem může nastat situace, ž^yhled/Evací strom přestane splňovat podmínku AVL. Pak je nutn0 pozměnit strukturu stromu. _) Přid/Ev/Ení položky (nov0ho uzlu) do AVL stromu Stejn0 jako u běžn0ho vyhled/Evacího stromu, ale s kontrolou vyv/Eženosti. Přid/Evaný uzel oznáíme x. Pokud se poruší vyv/Eženost stromu, nalezne se nejmenší podírom F, který je nevyv/Ežený. Oznáíme-li h jeho hloubku před přid/Ením uzlur, bude po přid/Ení jeho hloubka h + 1. Kořen stromu F označíme /. Bez oejmy na obecnosti lze pedpokl/Edat, že uzetc je přid/Ev/En dfev0/7opodstromu stromu F. Nechť B je levý podstrom stromu F, G je pravý podstrom stromu F. Strom B je nepr/Ezdný (jinak by pid/Ev/Ení uzlfir nemohlo porušit vyv/Eženost stromuF). Označíme A resp. D jeho levý resp. pravý podstrom, b bude kořen stromu B. _J Rozlišíme dva případy: 1. Uzel x je přid/En do stromuA Pak strom A m/E hloubku/i — 1, stromy D, G mají hloubku h — 2. Vytvoříme strom T = Node h b A (Node (h-1) f DG). Pak T je AVL strom hloubky h se stejnými uzly jako v F. 2. Uzel x je přid/En do stromuD. Pak stromy A, G mají hloubku h — 2, strom D m/E hloubku h — 1. Označíme d resp. (7 resp. E1 kořen resp. levý podstrom resp. pravý podstrom stromu D. Vytvoříme strom T = Node h d (Node (h-1) b A C) (Node (h-1) f EG) 123 Dva dílčí podpřípady jsou: (a) Uzel x byl přid/En do stromuC. Pak C m/E hloubku/i — 2, E m/E hloubku/i — 3 (b) Uzel x byl přid/En do stromuE. Pak C m/E hloubku/i - 3, E m/E hloubku/i - 2 V obou případech však strom T m/E hloubku/i, je AVL a m/E stejn0 uzly jako strom F. V původním AVL stromu nahradíme podstrom F stromem T. Jelikož T m/E stejnou hloubku jako měl původní podstrom bez uzlu x, zůstane celý strom vyv/Ežený (AVL). Přepočít/Eme hloubky na cesi od kořene stromu T k uzlu x. Byl-li uzel x přid/Ev/En dprav0/7opodstromu stromu F, je postup analogický (stranově převr/Ecený). 126 Složitost operace přid/Ení položky do AVL Hloubka AVL stromu je logaritmick/E vzhledem k potu jeho uzlů. Přid/Ení uzlíte: 0(log n). Nalezení nejmenšího nevyv/Ežen0ho podstromu: Protože hloubky podstromů jsou spočteny a uloženy v datov0 struktiře, stačí po cestě k uzlu x testovat, zda rozdíl spočtených hloubek Iev0ho a prav0ho podstromu každ0ho uzlu je v množině { — 1,0,1}. Nejnižší uzel, který tuto podmínku nesplňuje, je kořen podstromu F. Jeho nalezení trv/E0(log n). Hloubky podstromů se přepočít/Evají jen po cesš od kořene k x, tedy složitost t0to oepravy je0(log n). Celkov/E složitost pid/Ení uzlu je tedy0(log n). 127 Rušení položky (uzlu) z AVL stromu Rušení vnitřního uzlu převedeme na rušení listu (podobně jako u vyhled/Evacího stromu). Odebíraný list označíme x. Pokud se poruší vyv/Eženost stromu, nalezne se nejmenší podírom B, který je nevyv/Ežený. Oznáíme h jeho hloubku (před i po zrušení uzlu x je stejn/E). Bez oejmy na obecnosti lze pedpokl/Edat, že uzetc byl odebr/En z/ev0/7opodstromu stromu B. Nechť A je levý podstrom stromu B, F je pravý podstrom stromu B. Strom F je nepr/Ezdný (jinak by rušení uzlur nemohlo porušit vyv/Eženost stromufí). Označíme D resp. G jeho levý resp. pravý podstrom, / bude kořen stromu F. J 128 Rozlišíme dva případy: 1. Hloubka stromu G je větší nebo rovna hloubce stromu D. Vytvoříme strom T = Node tí f (Node (tí-1) b AD) G. Pak T je AVL strom hloubky h! se stejnými uzly jako v B,h! — h nebo h! — h — 1 2. Hloubka stromu G je menší než hloubka stromu D. Označíme d resp. C resp. E kořen resp. levý podstrom resp. pravý podstrom stromu D. Vytvoříme strom T = Node h' d (Node {h'—ľ) b A C) (Node {h'-ľ) f E G) Pak strom T m/E hloubkiiť = h — 1, je AVL a m/E stejn0 uzly jako rél strom B. V původním AVL stromu nahradíme podstrom B stromem T. Přepočít/Eme hloubky na cesi od kořene stromu T k uzlu x. V případě rušení uzlu se může st/Et, že hloubka podstromiíT bude menší než hloubka původního podstromu, který byl na jeho místě. Proto je nutn0 proces vyvažov/Ení opakovat: nalezne se nejmeší nadstrom T2 stromu T — Ti, který není vyv/Ežený, vyv/Ežíme ho, nalezneme další nevyv>§ny nadstrom T3... atd., až je vyv/Ežený celý stromy. Hloubky však stačí přepočít/Evat vždy od kčene stromu T ke kořenu nejbližšího vyvažovan0ho nadstromu. 130 Složitost operace rušení položky z AVL Zrušení listu: 0(log n). Nechť hloubka nejmenšího nevyv/Ežen0ho podstromúTi je h\. Nalezení tohoto podstromu trv/E 0(hi), jeho vyv/Ežení (rotace uzlů) trv/E konstantní dobu,řppočít/Ení hloubek trv/E 6(h\). Nechť pro 1 < i < k je h{ d0lka cesty z kďene podstromu T^_i do kořene stromu Ti Pak každ0 nalezení dalšího nevyv/Ežen0ho podstromy trv/E 0(hi), jeho vyv/Ežení trv/E 0(1), přepočít/Ení hloubek \rv/89(hi). To znamen/E, že celkov/E složitost rušení uzlu \& j ^ J = 0(log n). 131 Cvičení: Na vstupu jsou čísla 8, 3, 5, 0, 2,4,1, 6, 9, 7 a při jejich načít/Ení se postupe vytv/Eí AVL strom s uzly ohodnocenými těmito čísly. Nakreslete tento AVL strom v každ0m kroku vytv/Eení (tj. po přid/Ení každ0ho uzlu). Cvičení: Do AVL stromu, který je zpoč/Etku pr/Ezdný, se postupaipřid/Evají položky 4,1, 2, 7, 5, 6, pak se odebere položka 7, přid/E položka3, odeberou se postupně 5,6,1. Určete stav AVL stromu v každ0m kroku. Cvičení: AVL strom m/E uzly ohodnocen0ísly 1 až 20 a m/E strukturu Fibonacciho stromu Šest0hoř/Edu. Popište a nakreslete proces rušení listu obsahujícíb klíč 2. Cvičení: Fibonacciho strom Čtvrt0hoř/Edu na sedmi uzlech je ohodnocen jako AVL strom čísly 1, 3, 5, 7, 9,11,13. Do tohoto stromu přid/Eme jako další položku n/Ehodhzvolen0 sud0číslo k, 0 < k < 14. Jak/E je pravěpodobnost, že budeme muset rotovat uzly, abychom zachovali AVL vyv/Eženost? 131-1 Černobíl0 stromy Černobíl0 stromy jsou bin/Erní vyhled/Evací stromy, jejiclwly nesou kromě klíče další atribut — barvu — černou nebo bílou. v _ _ Def: Černobílý strom je bin/Erní vyhled/Evací strom, jehož každý uzel je obarven černou nebo bílou barvou. Musí splňovat tyto podmínky: 1. Kořen stromu je černý. 2. Je-li vnitřní uzel bílý, jeho n/Esledníci (pokud existují) jsoučerní. 3. Všechny větve obsahují stejný počet černých uzlů. Pozn/Emka: Vedle n/Ezv\jčernobíl0 stromyse lze setkat i s doslovnými překlady anglick0ho n/Ezvwed-black tree (drzewo czerwono-czarne, rot-schwarzer Baum, rugnigra arbo, ...). Def: Čern/E hloubkebemob\\0ho stromut je počet černých uzlů na Iibovoln0 větvi. Značíme ji bh(t). Lemma: Hloubka černobíl0ho stromut na n uzlech je nejvýše 2 log2(n + 1). Důkaz: Indukcí podle hloubky stromu se uk/Eže, že každýčernobílý strom ť m/E aspá 2bh(ť) - 1 uzlů. Odtud vyplýv/E bUjí') < log2(n + 1). Ale podle definice černobíl0ho stromu jeho hloubka nepřevyšuje dvojn/Esobek jehočern0 hloubky. Odtud plyne tvrzení. Důsledek: Vyhled/Ev/Ení (operacmember a search) v černobílOm strorrě mají složitost 0(log n). 133 Cernobil0 stromy v Haskellu data Barva = Ce I Bi data CBS a = E I N Barva a (CBS a) (CBS a) Vyhled/Ev/Eni ®ernobil0m stromu je stejn0 jako v nevyv/Ezen0m vyhled/Evacst Zjisfov/Eni pislusnosti member : : a —>- CBS a —>- Bool member E = False member k (N _ v 1 r) = k == v II k < v && member k 1 II k > v && member k r Vyhled/Ev/Eni search :: a CBS a CBS a search E = E search k t@(N _ v 1 r) I k == v = t I k < v = search k 1 I otherwise = search k r Přid/Ev/Ení uzlu dóernobíl0ho stromu Přid/Evaný uzel bude bílý. Tím se neznění čern/E hloubka podstromů, ale mohou se dostat pod sebe dva bíl0 uzly. Se dvěma bílými uzly nad sebou a s černým uzlem nad nimi provedeme takovou rotaci, abychom snížili hloubku stromu, ale přebarvíme je tak, aby čern/E hloubka stromu zůstala zachov/Ena: kčen bude bílý a jeho dva n/Eslednícčerní. Tím se opět mohly dostat pod sebe dva bíl0 uzly. Proto celý postup opakijeme tak dlouho, dokud jsou někde pod sebou dva bíl0 uzly. Zůstane-li bílý kořen, přebarvíme ho na černo. Tím se čern/E hloubka cel0ho stromu zvýší o jedničku. _) Přid/Ev/Ení uzlu insert : : a ->> CBS a ->> CBS a insert k s = N Ce y tl tr where N _ y tl tr = ins s ins E = N Bi k E E ins t@(N b y 1 r) I k < y = bal (N b y (ins 1) I k > y = bal (N b y 1 (ins i I otherwise = t bal • • CBS a ĺ ->> CBS a bal (N Ce z (N Bi y (N Bi x a b) c) d) = rt bal (N Ce z (N Bi x a (N Bi y b c)) d) = rt bal (N Ce x a (N Bi z (N Bi y b c) d)) = rt bal (N Ce x a (N Bi y b (N Bi z c d))) = rt bal t = t where rt = N Bi y (N Ce x a b) (N Ce z c d) 138 Složitost operace přid/Ení uzlu Věta: Operace insert přid/Ení položky dočernobíl0ho stromu velikostin m/E časovou složitost 0(log n). Důkaz: Vyplýv/E z Iogaritmick0 hloubk>pernobíl0ho stromu a z toho, že operace vyv/Eženíbal m/E konstantní složitost. Cvičení: Proč se při přid/Ev/Ení položky dóernobíl0ho stromu obarvuje kďen cel0ho stromu na černo? Cvičení: Na vstupu je posloupnost 6, 5,4, 2, 3,1, 0, z jejíchž prvků se postupně vytv/Eí černobílý strom. Jak0 jsou tyto stromy v každ0m kroku? Cvičení: Nechť černožlutobílý strom je bin/Erní strom spňující podmínky: • každý uzel je obarven jednou barvou — černou, žlutou, anebo bílou • počet černých uzlů na každ0 větvi je stejný • bezprostřední předchůdce žlut0ho uzlu nesmí být žlutý • bezprostřední předchůdce bíl0ho uzlu nesmí být bílý ani žlutý • kořen stromu je vždy černý Jak/E je minim/Elní a jak/E maxim/Elní hlouloleanožlutobíl0ho stromu nan uzlech? Dokažte. 139-1 Rušení uzlu z černobíl0ho stromu Rušení vnitřního uzlu převedeme zn/Emým způsobem na rušení listu. Je-li rušený liš bílý, je zrušení trivi/Elní — strom i bez listu zůstanečernobílý. Je-li rušený list černý, je nutno ho nejdříve „odbarvit". Odbarvíme-li černý list, stane se tento list bílým a můžeme ho snadno zrušit. Operace odbarvení spočív/E v pesunutí přebytečn0čern0 barvy blíže ke kďenu tak, aby čern0 d0lky všech étví zůstaly stejn0. ffitom může dojít k „přibarvení" černOho uzlu -přesuneme-li černou barvu na uzel, který byl s/Errčerný, stane se tento uzel „dvojn/Esobě černý" a je nutno ho d/Ele odbarvovat (pesouvat čerň st/Ele blíže ke kořenu), aby byl každý uzel „nejvýše jednou černý". Stane-li se dvojn/Esobě černý kořen cel0ho stromu, přebytečnou černou barvu z něho smažeme a nech/Eme ho „jednoučerný". Tím se sníží čern/E hloubka cel0ho stromu. 140 1. Bratr odbarvovan0ho uzlu je bílý — převede se na případ 2 Bratr odbarvovan0ho uzlu ječerný 2a bližší synovec je bílý 2. Bratr odbarvovan0ho uzlu ječerný 2b vzd/Eleější synovec je bílý 2. Bratr odbarvovan0ho uzlu ječerný 2c ž/Edný synovec není bílý Rušení uzlu delete :: a -> CBS a -> CBS a delete k t = cbs (del t) where del E del (N b v 1 r) I k < v I k > v I otherwise lbal b v (del 1) rbal b v 1 (del join b 1 r join :: Barva -> CBS a -> CBS a -> CCBS a -- definice jako u binárního vyhledávacího stromu lbal : : Barva -> CCBS a -> CBS a -> CCBS a lbal Ce d (CeCe tb) (N Bi h tf tj) = -- m N Ce h (lbal Bi d (CeCe tb) tf) tj lbal co d (CeCe tb) (N Ce h (N Bi f te tg) ti) = -- (2a) N co f (N Ce d tb te) (N Ce h tg ti) lbal co d (CeCe tb) (N Ce f te (N Bi h tg ti)) = -- (2b) N co f (N Ce d tb te) (N Ce h tg ti) lbal co d (CeCe tb) (N Ce h tf tj) = -- (2c) cern (N co d tb (N Bi h tf tj)) lbal co d tb tf = o) N co d tb tf rbal :: Barva -> CBS a -> CCBS a -> CCBS a -- analogicky jako lbal _J data CCBS a = CeCe (CBS a) I Cbs (CBS a) cern :: CBS a -> CCBS a cern E = Cbs E cern (N Bi v 1 r) = Cbs (N Ce v 1 r) cern (N Ce v 1 r) = CeCe (N Ce v 1 r) cbs : : CCBS a ->> CBS a cbs (CeCe t) = t cbs (Cbs t) = t J Složitost rušení uzlu z černobíl0ho stromu Element/Erní pesun čern0 barvy trv/E konstantní dobu, ale v nejhorším ppadě je nutn0 odbarvovat až ke kořenu, tj. 0(log n). Nalezení rušen0ho uzlu a n/Ehrada rušení vrřtíího uzlu za rušení listu trv/E tak0 logaritmickou dobu, takže cel/E operace rušení zaberečas 0(log n). J 148 Cvičení: Implementujte v Haskellu vyvažovači operaci rbal. Cvičení: Napište definici funkce join. 148-1 Další typy vyhled/Evacích stromů s logaritmickou složitoší operací B-stromy Stromy s proměnným počtem n/Esledníků, ale omezeným zdolačíslem k a shora číslem 2k pro pevně zvolenou konstantu k, tzv. ř^EaB-stromu (viz PV062). Složitost operací přid/Ení/zrušení položky je0(log&n). 2-3-4-stromy Speci/Elní pípad B-stromů. Každý vnitřní uzel m/E buď dva, rii, anebo čtyři n/Esledníky. Mají opt logaritmickou hloubku. 149 Hranově a uzlově ohodnocen0 grafy Def: Nechť V, Hy, H e jsou množiny, E CV2,hv :V -> Hv,hE : E -> Čtveřici (V, £7, hy,riE) nazýv/Emetyz/ové a hranově ohodnocený orientovaný graf. Vynech/Ením hranov0ho ohodnoceny dostaneme uzlově ohodnocený orientovaný graf (V,E,hv). Vynech/Ením uzlov0ho ohodnocenfoy dostaneme hranově ohodnocený orientovaný graf (V,E,hE)- Nepřipustíme-li v množině E dvojice tvaru (x, x), m/Eme (ohodnocen0) orientovan0 grafy bez smyček. 150 Def: Nechť V, Hy, H e jsou množiny, E je nějak/E množina dvouprvkových a jednoprvkových podmnožin množiny V, hy : V —> Hy, He ' E —> Čtveřici (V, £7, hy,riE) nazýv/Emetyz/ové a hranově ohodnocený neorientovaný graf. Vynech/Ením hranov0ho ohodnoceny dostaneme uzlově ohodnocený neorientovaný graf (V,E,hv). Vynech/Ením uzlov0ho ohodnocenfoy dostaneme hranově ohodnocený neorientovaný graf (V,E,hE)- Nepřipustíme-li v množině E jednoprvkov0 množiny, dost/Ev/Eme (ohodnocen0) neorientovan0 grafy bez smyček. 151 Pozn/Emka: Obecnější definice grafu připouští, aby množina hran E nebyla podmnožinou V2 (resp. množiny všech dvouprvkových a jednoprvkových podmnožin množiny V), ale aby to byla libovoln/E koněn/E množina, na níž je d/Eno zobrazena : E —> V , kter0 učuje, mezi kterými uzly dan/E hrana vede. Není-li zobrazenie injektivní, hovoří se o tzv. multigrafu. 151-1 Reprezentace Graf lze reprezentovat maticísousednosti: neohodnocený graf G = (V, E) na n uzlech je reprezentov/Erčtvercovou maticí G = [gij]1 He, jsou v matici sousednosti přímo hodnoty hran: pro G E \e gij = h(i,j), pro ^ E \e gij = v, Wóev £ He- J 152 Pro tzv. řfdk0grafy tj. grafy, v nichž počet hran je v o(n2), je výhodn/E reprezentace pomocí množin sousedů: neohodnocený graf G = (V, E) na n uzlech je reprezentov/En posloupností [si,... , sn] množin n/Esledníků každ0ho uzlu. Jsou-li>i,..., všichni n/Esledníci uzluu (tj. uzly, do nichž vede z u hrana), je su — ..., v^}. Nejčastější reprezentace posloupnosti množin sousedů je polem seznamů. Je-li graf uzlově ohodnocený, obsahuje i-tý prvek pole G dvojici (s^, hy(i)). Je-li graf hranově ohodnocený, obsahuje j-tý prvek i-t0ho seznamuj dvojici (vj,hE(i,Vj))- J 153 Proch/Ezení grafu Probl0m: Projít systematicky všechny uzly grafu. Proch/Ezení grafu do hloubky Algoritmus df s {depth-first search) G=(V,E), y = {l,...,n}, WCV Budeme označovat všechny navštíven0 uzly pomocí procedurymark. Na zač/Etku jsou všechny uzly nenavštíven0n(arked(^) = False). Pro každý uzel u je Successors (u) seznam uzlů - n/Esledníků uzluu. Vych/Ezíme z uzlů z množinyW a postupujeme st/Ele d/EI po hran/Ech do dosud nenavštívených uzlů. Cesty z označených do nově navštívených uzlů tvoří les s kořeny ve W. Proch/Ezeni grafu do hloubky - imperativni pseudokod procedure dfs (G:Graph; var W:Nodeset; var P:Nodearray) ; procedure dfsl (u:Node); begin if not marked (u) then begin mark (u); for v G Successors (u) do begin P[v] := u; dfsl (v) end end end; 155 begin {dfs} for u G V do begin unmark (u); P [u] : = empty-end; for u G W do if not marked (u) then dfsl (u) end; Chceme-li projít do hloubky všechny uzly grafu G = (V, E), položíme W = V. Věta: Algoritmus df s navštíví všechny uzly grafu dosažiteln0 z uzlů z množiny W. Důkaz je zřejmý a plyne z toho, že se opakovaně označují všechny uzly, kter0 dosud označeny nebyly. Množina neoznačených uzlů se zmenšuje, takže algoritmus konverguje. Pozn/Emka: Algoritmus funguje stejně pro orientovan0 i neorientovan0 grafy. _) Pozn/Emka: Algoritmus obecně není deterministický, protože nemusí být (a nebýv/E) specifikov/Eno póadí uzlů v množin/EchSuccessors(u) ani v množině W. Proch/Ezení grafu do hloubky tedy neurčuje pořadí navštívených uzlů jednoznačně. Cvičení: Nechť G = (V, E) je neorientovaný graf, V = {1, 2, 3,4, 5, 6}, E = {{1,2}, {2,3}, {4,5}, {5,6}, {1,4}, {2,5}, {3,6}}, W = {!}. Jak/E jsou všechna možn/E pádí navštívených uzlů při vol/Enídf s (G, W) ? Pozn/Emka: Významnou praktickou aplikací algoritmu df s je nalezení tzv. silně souvislých komponent orientovan0ho grafu. 157-1 Proch/Ezení grafu do šiky Řešíme probl0m Projít systematicky všechny uzly grafu G = (V, E) dosažiteln0 (orientovanou) cestou z někter0ho z poč/Etěních uzlů zadaných množinou W C V. Algoritmus bf s (breadth-first search) proch/Ezí uzly v jin0m pčadí než při prohled/Ev/Ení do hloubky: uzly, kter0 leží blíže poč/Etěním uzlům (uzlům, v nichž proch/Ezení záín/E), jsou navštíveny dříve než uzly ležící d/Ele od po/Etěních uzlů. Pomocn0 datov0 struktury: frontaQ uzlů, les nejkratších cest (uložený v poli P) Navštíven0 uzly se opět označují pomocí procedury mark, uzel u bude označen, pr/Eě když marked(^) = True. 158 Proch/Ezeni grafu do snky - imperativni pseudokod procedure bfs (G:Graph; var W:Nodeset; var P:Nodearray); var Q:Queue; procedure bfsl (q:Queue); begin while not (isempty(q)) do begin u := headq(q); dequeue(q); for v G Successors (u) do if not (marked(v)) then begin mark (v); enqueue (v,q); P[v] := u end end end{bfsi}; 159 begin {bfs} for u G V do begin unmark (u); P[u] := empty-end; Q := emptyq; for u G W do begin mark (u); enqueue (u,Q) end; bfsl (Q) end {bfs} Korektnost proch/Ezení grafu do šiky Def: D0lkou sledu{v hranově neohodnocen0m grafu) rozumíme počet hran na tomto sledu. Vzd/Elenost z uzluu do uzlu v je d0lka minim/Elního sledu vedoucího z uz\w do uzlu v, pokud takový sled existuje; pokud z uzlu u do uzlu v ž/Edný sled neexistuje, pak vzd/Elenost položíme+oo. V neorientovan0m grafu mluvíme stručně o vzd/Elenosti mezi uzlyu a v. J 161 Věta: Nechť G — (V, E), s,u,v E V a nechť vzd/Elenost zs do u je menší než vzd/Elenost zs do v. Pak uzel u bude při výpočtu bf s (G, {s}) označen dříve než uzel v. Důkaz: Stačí uk/Ezat, že do frontyQ jsou vžy přid/Ev/Eny uzly s aspbtak velkou vzd/Eleností ods, než jakou měl poslední přidaný uzel. To však lehce plyne indukcí podle vzd/Elenosti od uzlus. Věta: Nechť G = (V, E), s E V. Pak po provedení výpočtu bf s(G ,{s}) jsou navštíveny pr/Eě všechny uzly, do nichž vede z uzlu s (orientovan/E) cesta. Důkaz: Indukcí podle vzd/Elenosti od uzlus. 162 Složitost proch/Ezení grafu do šiky Věta: Nechť G — (V, E) je graf a W C V je množina poč/Etěních uzlů (vstupního stupně 0). Pak d0lka výpočtu bf s(G, W) v nejhorším případě je v 0(| W| + \E\). Důkaz věty: Každý uzel bude označen a zařazen do fronty a u všech uzlů z fronty se pt/Eme na označenost jejich n/Esledníků. Tedy d0lka výpčtu bude jistě v Í2(\E\). Jelikož zařazujeme do fronty všechny uzly z W, je d0lka výpočtu tak0 vf2(\W\).Z těchto dvou faktů vyplýv/E, žejevJ2(|£|) fi Í2(\W\) = Í2(\W\ + \E\). Do fronty zařazujeme jen uzly kter0 až do t0 doby nebyly oznáenO, a přitom je hned označíme. Odtud plyne, že každý uzel je do fronty zařazen jen jednou. Tedy vnější cyklus while proběhne 0(| W| + |£|)-kr/Et. Test ve vnřhím cyklu for proběhne vždy tolikr/Et, kolik hran vych/Ezí z uzlu, dohromady tolikr/Et, kolik m/E celý graf hran. Odtud opět dost/Ev/Eme, že d0lka výptw je v 0(\W\ + \E\ + \E\) = 0(\W\ + \E\). Dohromady dost/Ev/Emé^(|l/|^| + |£|),čímžje tvrzení dok/Ez/Eno 163-1 Minim/Elní kostra grafu Def: Nechť G — (V, E,Iie), h e ' E —> R, je hranově ohodnocený neorientovaný graf. Faktor grafu G je podgraf F = (V, Ef, HeIe') Q^u G. Def: Takový faktor grafu G, který je strom, se nazýv/Ekostra grafu G. Def: Nechť G je souvislý neorientovaný graf s číselně ohodnocenými hranami. Kostra grafu G, kter/E m/E ze všech jeho koster nejmenší sonet hranových ohodnocení, se nazýv/Eminim/Elní kostrag rafu G. Pozn/Emka: Kostry mají jen souvisl0 grafy, protože kostra musí podle déinice být strom. Tento požadavek však není z/Esadní a ětšinu oevah o kostr/Ech lzeřpn0st i na nesouvisl0 grafy: stačí uvažovat zvl/Ešť kostru každ0 komponenty. 164 Cvičení: M/Eme neorientovaný grař? = (V,E),V = {1, 2, 3,4}, E = {{1,2}, {2,3}, {3,4}, {4,1}, {1,3}}. Kolik m/E tento graf podgrafu, faktoru a koster? V každ0m zächto tří případů spočítejte, kolik je všech podgrafů (faktorů, koster), a kolik z nich je navz/Ejem neisomorfních 164-1 Generický algoritmus pro nalezení minim/Elní kostry Probl0m: Je d/En souvislý hranol ohodnocený neorientovaný graf G — (V, E^He)-Úkolem je nal0zt jeho minim/Elní kostru. type SpT = Set of Edges; proceduře genericMST (G:Graph; var A:SpT); begin A := 0; while A ještě netvoří kostru do begin najdi hranu {u, v} bezpečnou vzhledem k A; A := Au{{u,v}} end end _j Def: Nechť G je souvislý hranově ohodnocený graf a A takový jeho podgraf, že A je podgrafem nějak0 minim/Elní kostry grafu G. Pak každ/E hrana zG — A, kter/E leží v minim/Elní koale T, se nazýv/E6ezpec/7/^/zhledem k A. Def: Nechť G = (V, E) je graf, Vi C V, V2 C F, Vi ^ 0, V2 + 0, Vi U V2 = V, Vi H V2 = 0. Pak množině C = {{x,y}e£|xe Vi.yeVfc} řík/E m erez grafu G. Je-li navíc G' — (V7, E1\ h!) podgraf grafu G takový, že V' C V\ nebo V7 C V2, řík/Eme, žeřez (7 respektuje podgraf G'. _) Věta: Nechť G — (V, E, h e) je souvislý hranově ohodnocený neorientovaný graf, He ' E —> R. Nechť množina hran A C E \e obsažena v nějak0 minim/Elní košfe grafu G, nechť C je řez respektující podgraf indukovaný hranami z A a nechť i>} G (7 je hrana s minim/Elním ohodnocením vC. Pak hrana {u, v} je bezpečn/E vzhledem k A. Důsledek: Nechť G = (V, je souvislý hranově ohodnocený neorientovaný graf, množina hran A C E \e obsažena v nějak0 minim/Elní košfe grafu G a nechť T je nějak/E souvisl/E komponenta v les^V, A). Pak každ/E hrana spojujícíT s nějakou jinou komponentou v lese (V, A) a mající minim/Elní ohodnocení je bezpěn/E vzhledem kA. 167 Kruskalův (Borůvkův-Kruskalův) algoritmus Je d/En hranoé ohodnocený neorientovaný graf G — (V, E^He), hled/Eme množinu hran A c E tvořící minim/Elní kostriíT = (V, A, He\a)- type SpT = Set of Edges; Component = Set of Nodes; {„vhodně reprezentovan/E" množine-procedure kruskal (G:Graph; var A:SpT); var W: Set of Component; begin A := 0; W := 0; for v e V do W := WU{{v}}; seřadíme množinu E podle ohodnocení; for (u, v) G E {v pořadí od nejníže ohodnoceny do if WU^=WV {tj. u, v leží v různých komponent/Ecŕ} then begin A := A U {(u, v)}; sjednotíme obě tyto komponenty end end Korektnost Kruskalova algoritmu Věta: Po skončení výpočtu kruskal(G, A) je v A množina hran grafu G tvořících jeho minim/Elní kostru. Důkaz vyplýv/E z pedchozího Důsledku. Složitost Kruskalova algoritmu Složitost algoritmu z/Evisí na datov0 struklfe reprezentující množinu komponent W. Pro reprezentaci komponent lesa můžeme použít tzv. binomi/Elih haldy. Dotaz WU^WV vyj/E<9íme dotazem, zda halda, v níž se nach/Ezí uzelu, je shodný s haldou, v níž se nach/Ezí uzelľ. Tento dotaz m/E logaritmickou složitost. Složitost takto implementovan0ho Kruskalova algoritmu jepak 0(m log m), kde rn — E . 169