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 | ||
mgr-szz:in-pos:2-pos [2019/05/22 12:05] lachmanfrantisek |
mgr-szz:in-pos:2-pos [2020/04/12 16:56] (aktuální) |
||
---|---|---|---|
Řádek 1: | Řádek 1: | ||
- | ====== Algoritmy a datové struktury. ====== | + | ====== IN-POS 2. Algoritmy a datové struktury ====== |
===== Zadání ===== | ===== Zadání ===== | ||
Řádek 12: | Řádek 12: | ||
===== Vypracování ===== | ===== Vypracování ===== | ||
+ | |||
+ | ==== 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 === | ||
+ | |||
+ | * **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ů | ||
+ | |||
+ | |||
+ | === 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í: <math>n!</math> | ||
+ | * => dolní odhad: <math>\Omega(n!)</math> | ||
+ | * => složitost problému: <math>\Theta(n!)</math> | ||
+ | |||
+ | </box> | ||
+ | |||
+ | <box 90% blue|Polynom> | ||
+ | |||
+ | 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ů <math>\Omega(n)</math> | ||
+ | * => dolní odhad: <math>\Omega(n)</math> | ||
+ | * => složitost problému: <math>\Theta(n)</math> | ||
+ | |||
+ | </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 <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í. | ||
+ | |||
+ | |||
+ | <box 90% blue|Zásobník> | ||
+ | |||
+ | ^ operace ^ složitost ^ kredity ^ | ||
+ | | PUSH | 1 | 2 | | ||
+ | | POP | 1 | 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." | ||
+ | * 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 <math>\leq</math> součet kreditů vykonaných operací. | ||
+ | * Součet kreditů vykonaných operací je <math>\leq 2n</math> | ||
+ | |||
+ | </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 <math>\geq</math> 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 | <math>1 + (|S|+1) - |S| = 2 </math> | | ||
+ | | POP | 1 | <math>1 + |S| - (|S|+1) = 0 </math> | | ||
+ | | 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 <math>\leq</math> součet amortizovaných cen. | ||
+ | * Součet amortizovaných cen je <math>\leq 2n</math> | ||
+ | |||
+ | </box> | ||
+ | |||
+ | ==== Techniky návrhu algoritmů ==== | ||
+ | |||
+ | === 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í === | ||
+ | |||
+ | * 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 | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | <math>\Theta(1)</math> | | ||
+ | | MINIMUM | <math>\Theta(n)</math> | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | | ||
+ | | INSERT | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | <math>\Theta(1)</math> | | ||
+ | | UNION | <math>\Theta(1)</math> | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> | | ||
+ | | EXTRACT_MIN | <math>\Theta(n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * | | ||
+ | | DELETE | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> * | | ||
+ | | DECREASE_KEY | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * | | ||
+ | |||
+ | * amortizovaná složitost | ||
+ | |||
+ | <box 100% blue|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}} | ||
+ | </box> | ||
+ | |||
+ | <box 100% blue|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é | ||
+ | * dvě hlavní mota (viz video [[https://www.youtube.com/watch?v=CEvUqy1uF1E|Amortized analysis of Fibonacci heap]]): | ||
+ | * //Někdy se vyplatí nechat nepořádek narůst. (A uklidit hromadně.)// | ||
+ | * = Nové uzly přidáváme jako jednouzlové stromy. Stromy se stejným stupněm spojujeme hromadně až při ''extract-min''. | ||
+ | * //Tvoji rodiče chtějí hodně vnoučat a pokud nemáš moc dětí, tak tě zavrhnou.// | ||
+ | * = Uzel, který již dvakrát ztratil při ''decrease-key'' potomka je přesunut jako nový strom. | ||
+ | * 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> | ||
+ | </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ů | ||
+ | |||
+ | ^ algoritmus ^ MAKE_SET ^ UNION ^ FIND_SET ^ | ||
+ | | reverzní stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(n)</math> | | ||
+ | | reverzní stromy (optimalizace) | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(\log n)</math> | | ||
+ | | plytké stromy | <math>\mathcal{O}(1)</math> | <math>\mathcal{O}(\log n)</math> | <math>\mathcal{O}(1)</math> | | ||
+ | |||
+ | Stromy s kompresí: 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 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 ==== | ||
+ | |||
+ | <note tip>Některé algoritmy (naivní, Karp-Rabin, automaty) jsou podrobněji rozepsány zde: http://statnice.dqd.cz/home:inf:in17</note> | ||
+ | |||
+ | 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 | ||
+ | |||
+ | ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ | ||
+ | | Úplné prohledávání | <math>O</math> | <math>\mathcal{O}((n-m+1)m)</math> | | ||
+ | | Karp-Rabin * | <math>\Theta(m)</math> | <math>\mathcal{O}((n-m+1)m)</math> | | ||
+ | | Konečné automaty | <math>\mathcal{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>\mathcal{O}((n-m+1)m)</math> | | ||
+ | |||
+ | * 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: ===== | ||
+ | |||
+ | * slidy IV003 (verze 2016) |