Rozdíly

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/12 20:58]
lachmanfrantisek asymptotická složitost
+++ mgr-szz:in-pos:2-pos [2020/04/12 16:56] (aktuální)
@@ Řádek 141: / Řádek 141: @@
       * 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>>=</math> 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í.
@@ Řádek 150: / Řádek 150: @@
 | PUSH | 1 | 2 |
 | POP | 1 | 0 |
-| MULTIPOP | <math>\min{(k, |S|)}</math> | 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."
@@ Řádek 157: / Řádek 157: @@
   * POP a MULTIPOP zaplatí kredity z účtu
-  * Celá posloupnost n operací je <math><=</math> 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 <math><=2n</math>
+  * Součet kreditů vykonaných operací je <math>\leq 2n</math>
 </box>
@@ Řádek 166: / Řádek 166: @@
     * 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>>=</math> 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 174: / Řádek 174: @@
 | PUSH | 1 | <math>1 + (|S|+1) - |S| = 2 </math> |
 | POP | 1 | <math>1 + |S| - (|S|+1) = 0 </math> |
-| MULTIPOP | <math>\min{(k, |S|)}</math> | <math>delim{lbrace}{matrix{3}{1}{{k + (|S|-k) - |S| = 0 pro |S| > k} {|S|+0-|S| = 0 pro |S|<=k}}}{ }</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><=</math> součet amortizovaných cen.
+  * Celá posloupnost n operací je <math>\leq</math> součet amortizovaných cen.
-  * Součet amortizovaných cen je <math><=2n</math>
+  * Součet amortizovaných cen je <math>\leq 2n</math>
 </box>
@@ Řádek 185: / Řádek 190: @@
 === Rozděl a panuj ===
-  - Problém rozděl na podproblémy.
+  - Problém rozděl na podproblémy (stejného typu).
   - Vyřeš podproblémy.
   - Z řešení podproblému sestav řešení problému.
@@ Řádek 258: / Řádek 263: @@
 ^ 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> |
+| 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> |
+| 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> |
+| 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> * |
+| 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> * |
+| 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> * |
+| DECREASE_KEY | <math>\Theta(1)</math> | <math>\Theta(\log n)</math> | <math>\Theta(\log n)</math> | <math>\Theta(1)</math> * |
 * 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ů.
@@ Řádek 273: / Řádek 278: @@
 {{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
   * 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í.
@@ Řádek 303: / Řádek 314: @@
 {{https://upload.wikimedia.org/wikipedia/commons/thumb/0/09/Fibonacci_heap-decreasekey.png/375px-Fibonacci_heap-decreasekey.png}}
+</box>
 </box>
@@ Řádek 318: / Řádek 330: @@
     * ekvivalence konečných automatů
-== Reverzní stromy (Reversed trees) ==
+^ 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.
@@ Řádek 334: / Řádek 353: @@
     * Ke každému vrcholu asociujeme hloubku stromu jehož je kořenem.
     * MAKE_SET konstantní složitost
-    * UNION, FIND_SET O(log n)
+    * UNION, FIND_SET <math>\mathcal{O}(\log n)</math>
+</box>
-== Plytké stromy (Shallow threaded trees) ==
+<box 100% blue|Plytké stromy (Shallow threaded trees)>
   * Množinu reprezentujeme jako spojovaný seznam, první prvek je reprezentantem.
@@ Řádek 343: / Řádek 363: @@
   * MAKE_SET, FIND_SET konstantní složitost
-  * WEIGHTED_UNION O(log n) amortizovaná složitost
+  * WEIGHTED_UNION <math>\mathcal{O}(\log n)</math> amortizovaná složitost
+</box>
-== Stromy s kompresí (Trees with path compresion) ==
+<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>
@@ Řádek 357: / Řádek 377: @@
 ==== 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:
@@ Řádek 367: / Řádek 387: @@
 ^ 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> |
-| 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> |
-* Průměrná složitost je výrazně lepší.
+* Očekávaná složitost je výrazně lepší.
-=== Karp-Rabin ===
+<box 100% blue|Karp-Rabin>
   * Řetězce chápeme jako čísla v desítkové soustavě.
-  * Problém nalezení posunu redukujeme na hledání správného ciferného rozkladu.
+  * 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>
-    - Výpočet reprezentace hledaného řetězce přes Hornerovo schéma.
+    - Vypočteme haš hledaného řetězce.
-    - Výpočet reprezentace prvního podřetězce přes Hornerovo schéma.
+    - Vypočteme haš prvního podřetězce.
   - Výpočet: <math>O((n-m+1)m)</math>
-    - Výpočet dalších podřetězců
+    - 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.
-=== Užití konečných automatů ===
+  * 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>
-    * Existuje procedura s <math>O(m|\Sigma|)</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>
-=== KMP ===
+<box 100% blue|Boyer-Moore>
+  * Postupujeme zleva doprava a porovnáváme vzorek a text zprava.
-  * Nekonstruujeme celý automat ale před vyhledáváním vypočteme prefixovou funkci.
+  * Při neshodě můžeme využít dvě pravidla pro přeskočení pozic (vybereme větší skok):
-  * FIXME: podrobnosti
+    * **Heuristika špatného znaku**
+      * nejbližší další pozice znaku z textu ve vzorku
-=== Boyer-Moore ===
+      * symbol se nevyskytuje ve vzorku => posun o i pozic
+    * **Heuristika dobrého suffixu**
-  * Porovnáváme vzorek a text zprava doleva.
-  * Pro posun vzorku vůči textu používáme dvě heuristiky:
-    * Heuristika špatného znaku
-      * 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)

mgr-szz/in-pos/2-pos.1560365887.txt.gz · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru