Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
mgr-szz:in-pos:2-pos [2019/06/07 14:33] lachmanfrantisek techniky návrhu algoritmů |
mgr-szz:in-pos:2-pos [2020/04/12 16:56] |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
- | ====== IN-POS 2. Algoritmy a datové struktury ====== | ||
- | ===== Zadání ===== | ||
- | |||
- | * Analýza složitosti, amortizovaná složitost. | ||
- | * Techniky návrhu algoritmů (rozděl a panuj, dynamické programování, hladové strategie). | ||
- | * Pokročilé datové struktury (haldy, union-find struktury). | ||
- | * Algoritmy pro práci s řetězci (algoritmy Karp-Rabin, KMP, Boyer-Moore, užití konečných automatů). | ||
- | |||
- | |||
- | * IV003 | ||
- | |||
- | ===== Vypracování ===== | ||
- | |||
- | ==== Analýza složitosti, amortizovaná složitost ==== | ||
- | |||
- | === Složitost problému === | ||
- | |||
- | * **Dolní odhad složitosti problému**: důkazové techniky | ||
- | * **Horní odhad složitosti problému**: složitost konkrétního algoritmu pro daný problém | ||
- | * **Složitost problému**: určeno dolním a horním odhadem, problém těsných odhadů | ||
- | |||
- | |||
- | FIXME: asymptotická složitost | ||
- | |||
- | |||
- | === Techniky === | ||
- | |||
- | |||
- | == Informační metoda == | ||
- | |||
- | * Řešení obsahuje určité množství informace. | ||
- | * V každém kroku jsme schopni určit pouze část této informace. | ||
- | |||
- | <box 90% blue|Permutace> | ||
- | |||
- | Generování všech permutací n-prvkové posloupnosti | ||
- | |||
- | * počet různých permutací: <m>n!</m> | ||
- | * => dolní odhad: <m>\Omega(n!)</m> | ||
- | * => složitost problému: <m>\Theta(n!)</m> | ||
- | |||
- | </box> | ||
- | |||
- | <box 90% blue|Polynom> | ||
- | |||
- | Evaluace <m>a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0</m> v bodě <m>x</m>. | ||
- | |||
- | * Spracování všech koeficientů <m>\Omega(n)</m> | ||
- | * => dolní odhad: <m>\Omega(n)</m> | ||
- | * => složitost problému: <m>\Theta(n)</m> | ||
- | |||
- | </box> | ||
- | |||
- | == Metoda redukce == | ||
- | |||
- | * známe dolní odhad pro **Q** | ||
- | * **Q** redukujeme na **P** (**Q** řešíme za pomoci **P**) | ||
- | * dolní odhad pro **Q** je i dolním odhadem pro **P** | ||
- | |||
- | == Metoda sporu == | ||
- | |||
- | * Snažíme se dokázat dolní odhad složitosti. | ||
- | * Dvě varianty: | ||
- | * Předpokládáme, že má algoritmus asymptoticky menší složitost a konstruujeme vstup, pro který nevypočte korektní řešení. | ||
- | * Předpokládáme, že algoritmus najde vždy korektní řešení a konstruujeme vstup, pro který složitost přesáhne uvažovanou mez. | ||
- | |||
- | === Amortizovaná složitost === | ||
- | |||
- | Technika pro přesnější určení složitosti. | ||
- | |||
- | * Analyzujeme posloupnost operací jako celek, ne složitost každé operace. | ||
- | |||
- | == Používané metody == | ||
- | |||
- | * **Seskupení:** Operace seskupíme do skupin a analyzujeme složitost celé skupiny operací současně. | ||
- | |||
- | <box 90% blue|Zásobník> | ||
- | |||
- | * Skupina 1: operace PUSH: součet složitostí nepřesáhne n | ||
- | * Skupina 2: operace POP a MULTIPOP | ||
- | * Součet složitostí (= počet prvků vybraných ze zásobníku) nepřesáhne počet operací PUSH (= počet vložených prvků) | ||
- | * Složitost celé skupiny je n | ||
- | |||
- | |||
- | * Celá posloupnost n operací má v nejhorším případě složitost 2n. | ||
- | |||
- | |||
- | </box> | ||
- | |||
- | |||
- | * **Metoda účtů:** | ||
- | * Každé operaci přiřadíme kredit (číslo), které může být různé od skutečné složitosti. | ||
- | * Při realizaci zaplatíme skutečnou cenu kredity | ||
- | * nedoplatek placen z účtu | ||
- | * přebytek vrácen na účet | ||
- | * Počáteční stav kreditů je 0. | ||
- | * Pokud je stav kreditů po celou dobu výpočtu nezáporný. Součet kreditů je <m>>=</m> složitosti vykonaných operací. | ||
- | * Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují. | ||
- | |||
- | |||
- | <box 90% blue|Zásobník> | ||
- | |||
- | ^ operace ^ složitost ^ kredity ^ | ||
- | | PUSH | 1 | 2 | | ||
- | | POP | 1 | 0 | | ||
- | | MULTIPOP | <m>\min{(k, |S|)}</m> | 0 | | ||
- | |||
- | * Nezápornost kreditů dokážeme pomocí invariantu: "Počet kreditů na účtu je rovný počtu prvků na zásobníku." | ||
- | * Invariant platí na začátku. | ||
- | * PUSH zaplatí jeden kredit, 1 kredit dáme na účet | ||
- | * POP a MULTIPOP zaplatí kredity z účtu | ||
- | |||
- | * Celá posloupnost n operací je <m><=</m> součet kreditů vykonaných operací. | ||
- | * Součet kreditů vykonaných operací je <m><=2n</m> | ||
- | |||
- | </box> | ||
- | |||
- | * **Potenciálová funkce** | ||
- | * Zvolíme potenciálovou funkci, která přiřadí každého hodnotě datové struktury číslo. | ||
- | * Po celou dobu výpočtu nesmí hodnota klesnout pod počáteční mez. | ||
- | * Definujeme amortizované ceny operací pomocí skutečné ceny a změně potenciálu. | ||
- | * Součet amortizovaných cen je <m>>=</m> součtu skutečných cen. (Tedy je i horním odhadem složitosti posloupnosti operací.) | ||
- | |||
- | |||
- | <box 90% blue|Zásobník> | ||
- | |||
- | ^ operace ^ složitost ^ amortizovaná cena ^ | ||
- | | PUSH | 1 | <m>1 + (|S|+1) - |S| = 2 </m> | | ||
- | | POP | 1 | <m>1 + |S| - (|S|+1) = 0 </m> | | ||
- | | MULTIPOP | <m>\min{(k, |S|)}</m> | <m>delim{lbrace}{matrix{3}{1}{{k + (|S|-k) - |S| = 0 pro |S| > k} {|S|+0-|S| = 0 pro |S|<=k}}}{ }</m> | | ||
- | |||
- | * Celá posloupnost n operací je <m><=</m> součet amortizovaných cen. | ||
- | * Součet amortizovaných cen je <m><=2n</m> | ||
- | |||
- | </box> | ||
- | |||
- | ==== Techniky návrhu algoritmů ==== | ||
- | |||
- | === Rozděl a panuj === | ||
- | |||
- | - Problém rozděl na podproblémy. | ||
- | - Vyřeš podproblémy. | ||
- | - Z řešení podproblému sestav řešení problému. | ||
- | |||
- | |||
- | * Příklady: | ||
- | * Merge sort | ||
- | * Quick sort | ||
- | * Násobení celých čísel | ||
- | * Násobení matic | ||
- | * Fast Fourier Transformation | ||
- | |||
- | === Dynamické programování === | ||
- | |||
- | * Charakteristická struktura problému: | ||
- | * Problém lze rozdělit na podproblémy. | ||
- | * Vhodné pro optimalizační problémy s překryvem podproblémů. | ||
- | * Počet různých podproblémů je polynomiální. | ||
- | * Optimální řešení problému v sobě obsahuje optimální řešení podproblému. | ||
- | * Existuje přirozené uspořádání podproblémů od nejmenšího po největší. | ||
- | | ||
- | - Rekurzivní definice hodnoty optimálního řešení. | ||
- | - Výpočet hodnoty optimálního řešení **zdola-nahoru**. | ||
- | - Z vypočítaných hodnost sestav optimální řešení. | ||
- | |||
- | |||
- | * **Memoizace** = Pamatování si hodnot podproblémů. | ||
- | * ➕ jednoduché na pochopení | ||
- | * ➖ nutné určit pořadí řešení podproblémů ručně | ||
- | |||
- | * **Bottom-up** | ||
- | * ➕ nemá overhead způsobený rekurzí | ||
- | * ➖jednodušší analýza složitosti | ||
- | |||
- | * Příklady: | ||
- | * Floydův alg. | ||
- | * Warshallův alg. | ||
- | |||
- | |||
- | === Hladové strategie ==== | ||
- | |||
- | * Vhodné pro optimalizační problémy, kde optimální řešení obsahuje optimální řešení podproblémů. | ||
- | * Stačí získat optimální řešení jediného podproblému. (Výběr na základě **lokální optimality**.) | ||
- | * Postup **shora-dolů** | ||
- | |||
- | |||
- | * Příklady: | ||
- | * Dijkstrův algoritmus pro problém nejkratších cest z daného vrcholu | ||
- | * Kruskal a Prim pro nejlehčí kostry | ||
- | * Huffmanovy kódy | ||
- | * Problém mincí (placení co nejmenším počtem mincí) | ||
- | * Problém pásky | ||
- | * n souborů různých délek ukládáme postupně na pásku | ||
- | * minimalizace přístupového času | ||
- | |||
- | |||
- | ==== Pokročilé datové struktury ==== | ||
- | |||
- | === Haldy === | ||
- | |||
- | * **Halda** = Datová struktura pro reprezentaci prvků, nad kterými je definované úplné uspořádání. | ||
- | * Podporované operace: | ||
- | * MAKE_HEAP() vytvoří prázdnou haldu | ||
- | * INSERT(H, x) do haldy H | ||
- | * MINIMUM(H) najde minimální prvek v H | ||
- | * EXTRACT_MIN(H) z haldy H odstraní minimální prvek | ||
- | * DELETE(H, x) z hlady H odstraní prvek x | ||
- | * UNION(H1, H2) vytvoří novou haldu sjednocením H1 a H2 | ||
- | * DECREASE_KEY(H, x, y) nahradí klíč x klíčem y (y < x) | ||
- | |||
- | |||
- | ^ Operace ^ Seznam ^ Binární halda ^ Binomiální halda ^ Fibonacciho halda ^ | ||
- | | MAKE_HEAP | <m>\Theta(1)</m> | <m>\Theta(1)</m> | <m>\Theta(1)</m> | <m>\Theta(1)</m> | | ||
- | | MINIMUM | <m>\Theta(n)</m> | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> | | ||
- | | INSERT | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * | <m>\Theta(1)</m> | | ||
- | | UNION | <m>\Theta(1)</m> | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> | | ||
- | | EXTRACT_MIN | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * | | ||
- | | DELETE | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * | | ||
- | | DECREASE_KEY | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * | | ||
- | |||
- | * amortizovaná složitost | ||
- | |||
- | == Binomiální halda == | ||
- | |||
- | * Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů. | ||
- | * Umožňuje snadné spojování stromů. | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}} | ||
- | |||
- | == Fibonacciho halda == | ||
- | |||
- | * zobecnění binární haldy | ||
- | * struktura může obsahovat víc stromů; ukládáme ukazatel na minimální prvek | ||
- | * odkládáme operace až na dobu, kdy je to nutné | ||
- | * Efektivně realizujeme UNION, INSERT a DECREASE_KEY, ale nezhoršujeme amortizovanou složitost ostatních operací. | ||
- | |||
- | <box 90% blue|EXTRACT_MIN> | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Fibonacci_heap.png/375px-Fibonacci_heap.png}} | ||
- | |||
- | * Odebrání prvku (1) a rozpad potomků. | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/5/56/Fibonacci_heap_extractmin1.png/255px-Fibonacci_heap_extractmin1.png}} | ||
- | |||
- | * Spojení a finální stav po EXTRACT_MIN | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/9/95/Fibonacci_heap_extractmin2.png/195px-Fibonacci_heap_extractmin2.png}} | ||
- | |||
- | </box> | ||
- | |||
- | <box 90% blue|DECREASE_KEY> | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/4/45/Fibonacci_heap.png/375px-Fibonacci_heap.png}} | ||
- | |||
- | * Snížení hodnoty z (9) na (0) | ||
- | |||
- | {{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}} | ||
- | |||
- | </box> | ||
- | |||
- | === Union-find struktury === | ||
- | |||
- | * Reprezentace disjunktních množin. | ||
- | * Operace: | ||
- | * MAKE_SET(x) vytvoří množinu obsahující prvek x | ||
- | * UNION(H1, H2) vytvoří novou množinu sjednocením H1 a H2 | ||
- | * FIND_SET(x) najde reprezentanta množiny obsahující x | ||
- | |||
- | * Aplikace: | ||
- | * Kruskalův agoritmus | ||
- | * komponenty souvislosti | ||
- | * ekvivalence konečných automatů | ||
- | |||
- | == Reverzní stromy (Reversed trees) == | ||
- | |||
- | * Každá množina reprezentována stromem. | ||
- | * Jeden vrchol stromu odpovídá jednomu prvku množiny. | ||
- | * Každý vrchol obsahuje odkaz na rodiče. | ||
- | * Kořen ukazuje na sebe a je reprezentantem množiny. | ||
- | |||
- | |||
- | * Implementace pomocí pole/seznamu. | ||
- | * MAKE_SET, UNION: konstantní složitost | ||
- | * FIND_SET: až lineární k počtu prvků prohledávané množiny | ||
- | |||
- | * Optimalizace: | ||
- | * Při spojení dvou množin se kořen menší množiny stane synem kořene větší množiny. | ||
- | * Ke každému vrcholu asociujeme hloubku stromu jehož je kořenem. | ||
- | * MAKE_SET konstantní složitost | ||
- | * UNION, FIND_SET O(log n) | ||
- | |||
- | == Plytké stromy (Shallow threaded trees) == | ||
- | |||
- | * Množinu reprezentujeme jako spojovaný seznam, první prvek je reprezentantem. | ||
- | * Každý prvek má ukazatele na následníka a na reprezentanta. | ||
- | * Reprezentant obsahuje údaj o kardinalitě množiny. | ||
- | |||
- | * MAKE_SET, FIND_SET konstantní složitost | ||
- | * WEIGHTED_UNION O(log n) amortizovaná složitost | ||
- | |||
- | |||
- | == Stromy s kompresí (Trees with path compresion) == | ||
- | |||
- | |||
- | * FIND_SET: Při postupu zpět napojíme vrcholy na cestě přímo na kořen. | ||
- | * Posloupnost m operací UNION, FIND_SET a MAKE_SET, z toho n operací MAKE_SET má složitost <m>O(m . \alpha(n))</m> | ||
- | |||
- | |||
- | |||
- | |||
- | ==== Algoritmy pro práci s řetězci ==== | ||
- | |||
- | === Karp-Rabin === | ||
- | |||
- | === KMP === | ||
- | |||
- | === Boyer-Moore === | ||
- | |||
- | === Užití konečných automatů === | ||
- | |||
- | |||
- | ===== Zdroje: ===== | ||
- | |||
- | * slidy IV003 (verze 2016) |