Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

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/13 09:29]
lachmanfrantisek
mgr-szz:in-pos:2-pos [2019/06/13 10:53]
lachmanfrantisek poznámka a odkaz na video k Fibonacciho haldě
Řá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 421: Řádek 426:
  
 <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ůčtextu používáme ​dvě heuristiky+  * 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>​
  
mgr-szz/in-pos/2-pos.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0