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/07 15:31]
lachmanfrantisek algoritmy pro práci s textem
+++ mgr-szz:in-pos:2-pos [2020/04/12 16:56]
@@ Řádek 1: / Řádek 1: @@
-====== IN-POS 2. Algoritmy a datové struktury ======
-===== Zadání =====
-  * Analýza složitosti, amortizovaná složitost.
-  * Techniky návrhu algoritmů (rozděl a panuj, dynamické programování, hladové strategie).
-  * Pokročilé datové struktury (haldy, union-find struktury).
-  * Algoritmy pro práci s řetězci (algoritmy Karp-Rabin, KMP, Boyer-Moore, užití konečných automatů).
-  * IV003
-===== Vypracování =====
-==== Analýza složitosti, amortizovaná složitost  ====
-=== 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ů
-FIXME: asymptotická složitost
-=== 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í: <m>n!</m>
-  * => dolní odhad: <m>\Omega(n!)</m>
-  * => složitost problému: <m>\Theta(n!)</m>
-</box>
-<box 90% blue|Polynom>
-Evaluace <m>a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0</m> v bodě <m>x</m>.
-  * Spracování všech koeficientů <m>\Omega(n)</m>
-  * => dolní odhad: <m>\Omega(n)</m>
-  * => složitost problému: <m>\Theta(n)</m>
-</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 <m>>=</m> 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 | <m>\min{(k, |S|)}</m> | 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 <m><=</m> součet kreditů vykonaných operací.
-  * Součet kreditů vykonaných operací je <m><=2n</m>
-</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 <m>>=</m> 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 | <m>1 + (|S|+1) - |S| = 2 </m> |
-| POP | 1 | <m>1 + |S| - (|S|+1) = 0 </m> |
-| 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> |
-  * Celá posloupnost n operací je <m><=</m> součet amortizovaných cen.
-  * Součet amortizovaných cen je <m><=2n</m>
-</box>
-==== Techniky návrhu algoritmů ====
-=== Rozděl a panuj ===
-  - Problém rozděl na podproblémy.
-  - 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 | <m>\Theta(1)</m> | <m>\Theta(1)</m>  | <m>\Theta(1)</m> | <m>\Theta(1)</m> |
-| MINIMUM |  <m>\Theta(n)</m> | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> |
-| INSERT | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * | <m>\Theta(1)</m> |
-| UNION | <m>\Theta(1)</m> | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> |
-| EXTRACT_MIN | <m>\Theta(n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * |
-| DELETE | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> * |
-| DECREASE_KEY | <m>\Theta(1)</m> | <m>\Theta(log n)</m> | <m>\Theta(log n)</m> | <m>\Theta(1)</m> * |
-* amortizovaná složitost
-== 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}}
-== 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é
-  * 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>
-=== 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ů
-== 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 O(log n)
-== 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 O(log n) amortizovaná složitost
-== 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 <m>O(m . \alpha(n))</m>
-==== Algoritmy pro práci s řetězci ====
-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í | <m>O</m> | <m>O((n-m+1)m)</m> |
-| Karp-Rabin * | <m>\Theta(m)</m> | <m>O((n-m+1)m)</m> |
-| Konečné automaty | <m>O(m |\Sigma|)</m> | <m>\Theta(n)</m> |
-| Knuth-Morriss-Pratt | <m>\Theta(m)</m> | <m>\Theta(n)</m> |
-| Boyer-Moore * | <m>\Theta(m + |\Sigma|)</m> | <m>O((n-m+1)m)</m> |
-* Průměrná složitost je výrazně lepší.
-=== 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.
-  - Příprava: <m>\Theta(m)</m>
-    - Výpočet reprezentace hledaného řetězce přes Hornerovo schéma.
-    - Výpočet reprezentace prvního podřetězce přes Hornerovo schéma.
-  - Výpočet: <m>O((n-m+1)m)</m>
-    - Výpočet dalších podřetězců
-=== Užití konečných automatů ===
-  * Pro daný vzorek zkonstruujeme konečný automat.
-    * Využití sufixové funkce <m>\sigma</m> určující délku nejdelšího prefixu vzorku, který je sufixem slova.
-    * <m>\delta(q, a) = \sigma(P[1] ... P[q] a)</m>
-    * Existuje procedura s <m>O(m|\Sigma|)</m>
-  * Text zpracujeme konečným automatem. <m>\Theta(n)</m>
-=== KMP ===
-  * Nekonstruujeme celý automat ale před vyhledáváním vypočteme prefixovou funkci.
-  * FIXME: podrobnosti
-=== Boyer-Moore ===
-  * 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
-===== Zdroje: =====
-  * slidy IV003 (verze 2016)

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

Nahoru