hledat
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 10:45] lachmanfrantisek analýza složitosti, amortizovaná složitost |
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 === | ||
| - | |||
| - | === Dynamické programování === | ||
| - | |||
| - | === Hladové strategie ==== | ||
| - | |||
| - | |||
| - | ==== Pokročilé datové struktury ==== | ||
| - | |||
| - | === Haldy === | ||
| - | |||
| - | === Union-find struktury === | ||
| - | |||
| - | |||
| - | ==== Algoritmy pro práci s řetězci ==== | ||
| - | |||
| - | === Karp-Rabin === | ||
| - | |||
| - | === KMP === | ||
| - | |||
| - | === Boyer-Moore === | ||
| - | |||
| - | === Užití konečných automatů === | ||
| - | |||
| - | |||
| - | ==== Zdroje: ==== | ||
| - | |||
| - | * slidy IV003 (verze 2016) | ||
