Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
Obě strany předchozí revize Předchozí verze Následující verze | Předchozí verze Následující verze Obě strany příští revize | ||
mgr-szz:in-pos:2-pos [2019/06/07 13:43] lachmanfrantisek haldy |
mgr-szz:in-pos:2-pos [2019/06/13 09:59] lachmanfrantisek Boyer-Moore |
||
---|---|---|---|
Řádek 14: | Řádek 14: | ||
==== Analýza složitosti, amortizovaná složitost ==== | ==== Analýza složitosti, amortizovaná složitost ==== | ||
+ | |||
+ | <box 90% red|Časová složitost> | ||
+ | Časová složitost je funkce velikosti vstupu. | ||
+ | |||
+ | Vyjadřuje závislost času potřebného pro provedení výpočtu na rozsahu (velikosti) vstupních dat. | ||
+ | |||
+ | Rozlišujeme časovou složitost v nejlepším, nejhorším a průměrném případě. | ||
+ | </box> | ||
+ | |||
+ | |||
+ | === Asymptotická notace === | ||
+ | |||
+ | * abstrakce od detailů při udávání složitosti | ||
+ | |||
+ | <box 90% blue|Θ notace> | ||
+ | Pro danou funkci <math>g(n)</math> označuje symbol <math>\Theta(g(n))</math> množinu funkcí: | ||
+ | |||
+ | |||
+ | <math>\Theta(g(n)) = \lbrace f(n) \mid \exists c_1, c_2, n_0 : \forall n \geq n_0: 0\leq c_1g(n) \leq f(n) \leq c_2g(n)</math> | ||
+ | |||
+ | --- | ||
+ | |||
+ | <math>f(n) \in \Theta(g(n))</math>: //f roste asymptoticky stejně rychle jako g// | ||
+ | </box> | ||
+ | |||
+ | <box 90% blue|O notace> | ||
+ | Pro danou funkci <math>g(n)</math> označuje symbol <math>\mathcal{O}(g(n))</math> množinu funkcí: | ||
+ | |||
+ | |||
+ | <math>\mathcal{O}(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq f(n) \leq cg(n)</math> | ||
+ | |||
+ | --- | ||
+ | |||
+ | <math>f(n) \in \mathcal{O}(g(n))</math>: //f roste asymptoticky rychleji než g// | ||
+ | </box> | ||
+ | |||
+ | <box 90% blue|Ω notace> | ||
+ | Pro danou funkci <math>g(n)</math> označuje symbol <math>\Omega(g(n))</math> množinu funkcí: | ||
+ | |||
+ | |||
+ | <math>\Omega(g(n)) = \lbrace f(n) \mid \exists c, n_0 : \forall n \geq n_0: 0 \leq cg(n) \leq f(n)</math> | ||
+ | |||
+ | --- | ||
+ | |||
+ | <math>f(n) \in \Omega(g(n))</math>: //f roste asymptoticky pomaleji než g// | ||
+ | </box> | ||
+ | |||
+ | |||
=== Složitost problému === | === Složitost problému === | ||
Řádek 20: | Řádek 68: | ||
* **Horní odhad složitosti problému**: složitost konkrétního algoritmu pro daný problém | * **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ů | * **Složitost problému**: určeno dolním a horním odhadem, problém těsných odhadů | ||
- | |||
- | |||
- | FIXME: asymptotická složitost | ||
Řádek 37: | Řádek 82: | ||
Generování všech permutací n-prvkové posloupnosti | Generování všech permutací n-prvkové posloupnosti | ||
- | * počet různých permutací: <m>n!</m> | + | * počet různých permutací: <math>n!</math> |
- | * => dolní odhad: <m>\Omega(n!)</m> | + | * => dolní odhad: <math>\Omega(n!)</math> |
- | * => složitost problému: <m>\Theta(n!)</m> | + | * => složitost problému: <math>\Theta(n!)</math> |
</box> | </box> | ||
Řádek 45: | Řádek 90: | ||
<box 90% blue|Polynom> | <box 90% blue|Polynom> | ||
- | Evaluace <m>a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0</m> v bodě <m>x</m>. | + | Evaluace <math>a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0</math> v bodě <math>x</math>. |
- | * Spracování všech koeficientů <m>\Omega(n)</m> | + | * Spracování všech koeficientů <math>\Omega(n)</math> |
- | * => dolní odhad: <m>\Omega(n)</m> | + | * => dolní odhad: <math>\Omega(n)</math> |
- | * => složitost problému: <m>\Theta(n)</m> | + | * => složitost problému: <math>\Theta(n)</math> |
</box> | </box> | ||
Řádek 96: | Řádek 141: | ||
* přebytek vrácen na účet | * přebytek vrácen na účet | ||
* Počáteční stav kreditů je 0. | * 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í. | + | * Pokud je stav kreditů po celou dobu výpočtu nezáporný. Součet kreditů je <math>\geq</math> složitosti vykonaných operací. |
* Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují. | * Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují. | ||
Řádek 105: | Řádek 150: | ||
| PUSH | 1 | 2 | | | PUSH | 1 | 2 | | ||
| POP | 1 | 0 | | | POP | 1 | 0 | | ||
- | | MULTIPOP | <m>\min{(k, |S|)}</m> | 0 | | + | | MULTIPOP | <math>\min(k, \mid S \mid)</math> | 0 | |
* Nezápornost kreditů dokážeme pomocí invariantu: "Počet kreditů na účtu je rovný počtu prvků na zásobníku." | * Nezápornost kreditů dokážeme pomocí invariantu: "Počet kreditů na účtu je rovný počtu prvků na zásobníku." | ||
Řádek 112: | Řádek 157: | ||
* POP a MULTIPOP zaplatí kredity z účtu | * POP a MULTIPOP zaplatí kredity z účtu | ||
- | * Celá posloupnost n operací je <m><=</m> součet kreditů vykonaných operací. | + | * Celá posloupnost n operací je <math>\leq</math> součet kreditů vykonaných operací. |
- | * Součet kreditů vykonaných operací je <m><=2n</m> | + | * Součet kreditů vykonaných operací je <math>\leq 2n</math> |
</box> | </box> | ||
Řádek 121: | Řádek 166: | ||
* Po celou dobu výpočtu nesmí hodnota klesnout pod počáteční mez. | * 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. | * 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í.) | + | * Součet amortizovaných cen je <math>\geq</math> součtu skutečných cen. (Tedy je i horním odhadem složitosti posloupnosti operací.) |
Řádek 127: | Řádek 172: | ||
^ operace ^ složitost ^ amortizovaná cena ^ | ^ operace ^ složitost ^ amortizovaná cena ^ | ||
- | | PUSH | 1 | <m>1 + (|S|+1) - |S| = 2 </m> | | + | | PUSH | 1 | <math>1 + (|S|+1) - |S| = 2 </math> | |
- | | POP | 1 | <m>1 + |S| - (|S|+1) = 0 </m> | | + | | POP | 1 | <math>1 + |S| - (|S|+1) = 0 </math> | |
- | | 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> | | + | | MULTIPOP | <math>\min(k, \mid S \mid)</math> | <math> |
+ | \begin{cases} | ||
+ | k + (\mid S \mid - k) - \mid S \mid = 0 \text{ pro } \mid S \mid \textgreater k \\ | ||
+ | \mid S \mid + 0 - \mid S \mid = 0 \text{ pro } \mid S \mid \leq k | ||
+ | \end{cases} | ||
+ | </math> | | ||
- | * Celá posloupnost n operací je <m><=</m> součet amortizovaných cen. | + | * Celá posloupnost n operací je <math>\leq</math> součet amortizovaných cen. |
- | * Součet amortizovaných cen je <m><=2n</m> | + | * Součet amortizovaných cen je <math>\leq 2n</math> |
</box> | </box> | ||
Řádek 139: | Řádek 189: | ||
=== Rozděl a panuj === | === Rozděl a panuj === | ||
+ | |||
+ | - Problém rozděl na podproblémy (stejného typu). | ||
+ | - 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í === | === 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 ==== | === 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 | ||
Řádek 161: | Řádek 262: | ||
^ Operace ^ Seznam ^ Binární halda ^ Binomiální halda ^ Fibonacciho halda ^ | ^ 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> | | + | | MAKE_HEAP | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | |
- | | MINIMUM | <m>\Theta(n)</m> | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> | | + | | MINIMUM | <math>\Theta(n)</math> | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | |
- | | INSERT | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * | <m>\Theta(1)</m> | | + | | INSERT | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | <math>\Theta(1)</math> | |
- | | UNION | <m>\Theta(1)</m> | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> | | + | | UNION | <math>\Theta(1)</math> | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | |
- | | EXTRACT_MIN | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * | | + | | EXTRACT_MIN | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * | |
- | | DELETE | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * | | + | | DELETE | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * | |
- | | DECREASE_KEY | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * | | + | | DECREASE_KEY | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | |
* amortizovaná složitost | * amortizovaná složitost | ||
- | == Binomiální halda == | + | <box 100% blue|Binomiální halda> |
* Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů. | * Na rozdíl od **binární haldy** tvořena lesem binomiálních stromů. | ||
Řádek 177: | Řádek 278: | ||
{{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}} | {{https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png}} | ||
+ | </box> | ||
- | == Fibonacciho halda == | + | <box 100% blue|Fibonacciho halda> |
* zobecnění binární haldy | * zobecnění binární haldy | ||
Řádek 207: | Řádek 309: | ||
{{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}} | {{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}} | ||
+ | </box> | ||
</box> | </box> | ||
=== Union-find struktury === | === 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ů | ||
+ | |||
+ | <box 100% blue|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 <math>\mathcal{O}(\log n)</math> | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|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 <math>\mathcal{O}(\log n)</math> amortizovaná složitost | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|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 <math>O(m . \alpha(n))</math> | ||
+ | |||
+ | </box> | ||
+ | |||
==== Algoritmy pro práci s řetězci ==== | ==== Algoritmy pro práci s řetězci ==== | ||
- | === Karp-Rabin === | + | <note tip>Některé algoritmy (naivní, Karp-Rabin, automaty) jsou podrobněji rozepsány zde: http://statnice.dqd.cz/home:inf:in17</note> |
- | === KMP === | + | Algoritmy pro: |
+ | * Vyhledávání vzorku v textu. | ||
+ | * Vzdálenosti řetězců a transformace řetězců | ||
+ | * Společná podposloupnost | ||
+ | * Aproximace řetězců | ||
+ | * Opakující se podřetězce | ||
- | === Boyer-Moore === | + | ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ |
+ | | Úplné prohledávání | <math>O</math> | <math>O((n-m+1)m)</math> | | ||
+ | | Karp-Rabin * | <math>\Theta(m)</math> | <math>O((n-m+1)m)</math> | | ||
+ | | Konečné automaty | <math>O(m |\Sigma|)</math> | <math>\Theta(n)</math> | | ||
+ | | Knuth-Morriss-Pratt | <math>\Theta(m)</math> | <math>\Theta(n)</math> | | ||
+ | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>O((n-m+1)m)</math> | | ||
- | === Užití konečných automatů === | + | * Očekávaná složitost je výrazně lepší. |
+ | <box 100% blue|Karp-Rabin> | ||
+ | |||
+ | * Řetězce chápeme jako čísla v desítkové soustavě. | ||
+ | * Vzorek i jednotlivé podřetězce hašujeme (pomocí Hornerova schématu) a porovnáváme tyto haše. | ||
+ | * Při posunutí o jednu pozici jsme schopni přepočíst haš v konstantním čas. | ||
+ | |||
+ | - Příprava: <math>\Theta(m)</math> | ||
+ | - Vypočteme haš hledaného řetězce. | ||
+ | - Vypočteme haš prvního podřetězce. | ||
+ | - Výpočet: <math>O((n-m+1)m)</math> | ||
+ | - Porovnáme haš vzorku a haš aktuálního podřetězce. (Pokud je roven, porovnáme řetězce a případně uložíme nalezenou pozici.) | ||
+ | - Posuneme se o jednu pozici v prohledávaném textu a přepočteme haš (v konstantním čase). | ||
+ | - Porovnáváme a posouváme se dokud jsme nedosáhli <math>(m-1)</math>-té pozice od konce. Poté vrátíme všechny nalezené pozice. | ||
+ | |||
+ | * Očekávaná složitost pro //c// nálezů: <math>\mathcal{O}((n-m+1) + cm)</math> | ||
+ | * ➕ vhodné pro delší vzorky s malým počtem očekávaných nálezů | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|Užití konečných automatů> | ||
+ | * Pro daný vzorek zkonstruujeme konečný automat. | ||
+ | * Využití sufixové funkce <math>\sigma</math> určující délku nejdelšího prefixu vzorku, který je sufixem slova. | ||
+ | * <math>\delta(q, a) = \sigma(P[1] ... P[q] a)</math> | ||
+ | * Tato metoda v <math>\mathcal{O}(m^3 \times \mid\Sigma\mid)</math>. | ||
+ | * Existuje procedura s <math>\mathcal{O}(m \times \mid\Sigma\mid)</math>. | ||
+ | * Text zpracujeme konečným automatem. <math>\Theta(n)</math> | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|KMP> | ||
+ | * Nekonstruujeme celý automat ale před vyhledáváním vypočteme **prefixovou funkci** pro vzorek. | ||
+ | * Postupně pro každou pozici ve vzorku určíme délku největšího podvzorku, který je zároveň prefixem i sufixem dosud zpracované části vzorku. | ||
+ | * <math>\mathcal{O}(m)</math> | ||
+ | * Samotný výpočet pak probíhá obdobně jako naivní prohledávání, ale při neshodě (nebo nalezení vzorku) se: | ||
+ | * na textu nevracíme | ||
+ | * na vzorce posuneme na pole dle prefixové funkce | ||
+ | * <math>\mathcal{O}(n)</math> | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|Boyer-Moore> | ||
+ | * Postupujeme zleva doprava a porovnáváme vzorek a text zprava. | ||
+ | * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok): | ||
+ | * **Heuristika špatného znaku** | ||
+ | * nejbližší další pozice znaku z textu ve vzorku | ||
+ | * symbol se nevyskytuje ve vzorku => posun o i pozic | ||
+ | * **Heuristika dobrého suffixu** | ||
+ | * najdeme nejpravější výskyt u = T[j+i+1...m-1], před kterým je symbol různý od a | ||
+ | * => posun o i-r pozic (r = index znaku různého od a) | ||
+ | * nenajdeme nejdelší řetězec v, který je současně prefixem i sufixem P | ||
+ | * => posun vzorku o m-|v| pozic | ||
+ | * Tabulky pro heuristiky si lze ze vzorku předpočítat před samotným výpočtem. <math>\mathcal{O}(m \times |\Sigma|)</math> | ||
+ | * Vyhledávání <math>\mathcal{O}(m \times n)</math>, ale očekávaně výrazně lepší. | ||
+ | * nejlepší případ: <math>\mathcal{O}(\frac{n}{m})</math> | ||
+ | </box> | ||
===== Zdroje: ===== | ===== Zdroje: ===== | ||
* slidy IV003 (verze 2016) | * slidy IV003 (verze 2016) |