hledat
Rozdíly
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/06/13 09:28] lachmanfrantisek Knuth-Morris-Prath |
mgr-szz:in-pos:2-pos [2020/04/12 16:56] (aktuální) |
||
|---|---|---|---|
| Řádek 285: | Řádek 285: | ||
| * struktura může obsahovat víc stromů; ukládáme ukazatel na minimální prvek | * 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é | * 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í. | * Efektivně realizujeme UNION, INSERT a DECREASE_KEY, ale nezhoršujeme amortizovanou složitost ostatních operací. | ||
| Řádek 324: | Řádek 329: | ||
| * komponenty souvislosti | * komponenty souvislosti | ||
| * ekvivalence konečných automatů | * 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)> | <box 100% blue|Reverzní stromy (Reversed trees)> | ||
| Řádek 365: | Řádek 377: | ||
| ==== Algoritmy pro práci s řetězci ==== | ==== Algoritmy pro práci s řetězci ==== | ||
| - | <note tip>Podrobněji viz http://statnice.dqd.cz/home:inf:in17</note> | + | <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: | Algoritmy pro: | ||
| Řádek 375: | Řádek 387: | ||
| ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ | ^ Algoritmus ^ Předspracování ^ Vyhledávání ^ | ||
| - | | Úplné prohledávání | <math>O</math> | <math>O((n-m+1)m)</math> | | + | | Úplné prohledávání | <math>O</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| - | | Karp-Rabin * | <math>\Theta(m)</math> | <math>O((n-m+1)m)</math> | | + | | Karp-Rabin * | <math>\Theta(m)</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| - | | Konečné automaty | <math>O(m |\Sigma|)</math> | <math>\Theta(n)</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> | | | 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> | | + | | Boyer-Moore * | <math>\Theta(m + |\Sigma|)</math> | <math>\mathcal{O}((n-m+1)m)</math> | |
| * Očekávaná složitost je výrazně lepší. | * Očekávaná složitost je výrazně lepší. | ||
| Řádek 421: | Řádek 433: | ||
| <box 100% blue|Boyer-Moore> | <box 100% blue|Boyer-Moore> | ||
| - | * Porovnáváme vzorek a text zprava doleva. | + | * Postupujeme zleva doprava a porovnáváme vzorek a text zprava. |
| - | * Pro posun vzorku vůči textu používáme dvě heuristiky: | + | * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok): |
| - | * Heuristika špatného znaku | + | * **Heuristika špatného znaku** |
| - | * symbol se nevyskytuje ve vzorku => posun o i pozic | + | * nejbližší další pozice znaku z textu ve vzorku |
| - | * Heuristika dobrého suffixu | + | * 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 | * 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) | * => 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 | * nenajdeme nejdelší řetězec v, který je současně prefixem i sufixem P | ||
| * => posun vzorku o m-|v| pozic | * => 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> | </box> | ||
