Státnice - Odhady složitosti
Tohle je poněkud obšírnější výcuc ke státnicovým okruhům ze složitosti pro obory Matematická lingvistika a Softwarové systémy, pocházející ze zápisků z předmětu Složitost I -- Tuetschek 22:44, 16 Aug 2010 (CEST)
Dolní odhady složitosti problémů[editovat | editovat zdroj]
Definice (Složitost problému)[editovat | editovat zdroj]
Složitost problému je složitost asymptoticky nejlepšího možného algoritmu, který řeší daný problém (ne nejlepšího známého).
Každý konkrétní algoritmus dává horní odhad složitosti. Dolní odhady (až na triviální -- velikost vstupu, výstupu) jsou složitější.
Věta (Dolní odhad složitosti mediánu)[editovat | editovat zdroj]
Pro výběr $ k\,\! $-tého z $ n\,\! $ prvků je třeba alespoň $ n-1\,\! $ porovnání, tj. problém je $ \Omega(n)\,\! $.
Důkaz[editovat | editovat zdroj]
Intuitivně potřebuju medián, i kdyby mi spadnul z nebe, porovnat se všemi ostatními prvky, abych vůbec zjistil, jestli to je medián ...
Věta (Dolní odhad složitosti třídění)[editovat | editovat zdroj]
Pro každý třídící algoritmus, založený na porovnávání prvků, existuje vstupní posloupnost, pro kterou provede $ \Omega(n\log n)\,\! $ porovnání.
Důkaz[editovat | editovat zdroj]
Nakreslím si rozhodovací strom jako model algoritmu -- všechny vnitřní uzly odpovídají nějakému porovnání, které algoritmus provedl, jejich synové jsou operace, které nasledovaly po různých výsledcích toho porovnání (BÚNO jsou-li prvky různé, bude strom binární). Listy odpovídají setříděným posloupnostem. Aby byl algoritmus korektní, musí mít strom listy se všemi $ n!\,\! $ možnými pořadími prvků.
Pro plýtvající algoritmus mohou existovat listy, neodpovídající žádné permutaci, tj. porovnává stejnou dvojici prvků dvakrát (a jedna z možností už nemůže nastat). Pro rovnoměrné rozdělení je očekávaný čas průměrná délka cesty od kořene k listům, nejhorší čas je výška stromu.
Označím výšku jako $ h\,\! $, pak počet listů je $ \leq 2^h\,\! $ a tedy $ n!\leq 2^h\,\! $, tj. $ h\geq \log n!\,\! $, pro dolní odhad $ \Omega(n\log n) $ stačí odhad faktoriálu $ n! < n^{\frac{n}{2}}\,\! $, případně můžu použít Stirlingův vzorec $ n!\approx \sqrt{2\pi n}(\frac{n}{e})^n\,\! $ a dostávám $ \Theta(n\log n) $.
Amortizovaná složitost[editovat | editovat zdroj]
Definice (Amortizovaná složitost)[editovat | editovat zdroj]
Typicky se používá pro počítání časové složitosti operací nad datovými strukturami, počítá průměrný čas na 1 operaci při provedení posloupnosti operací. Dává realističtější odhad složitosti posloupnosti všech operací, než měření všech nejhorším případem.
Známe 3 metody amortizované analýzy:
Problémy:[editovat | editovat zdroj]
- Inkrementace binárního čítače -- do binárního čítače délky $ k\,\! $ postupně přičteme $ n\,\! $-krát jedničku. Počet bitových operací na 1 přičtení je v nejhorším případě $ O(\log n)\,\! $, ale amortizovaně dojdeme k $ O(1)\,\! $.
- Vkládání do dynamického pole -- začnu s prázdným polem délky $ 1\,\! $ a postupně vkládám $ n\,\! $ prvků. Pokud je stávající pole plné, alokujeme dvojnásobné a kopírujeme prvky. Počet kopírování prvků na jedno vložení je až $ O(n)\,\! $, ale amortizovaně opět $ O(1)\,\! $.
Algoritmus (Agregační metoda)[editovat | editovat zdroj]
Spočítáme nejhorší čas pro celou posloupnost $ n\,\! $ operací -- $ T(n)\,\! $, amortizovaný čas na 1 operaci je pak $ \frac{T(n)}{n}\,\! $.
- Binární sčítání: v průběhu $ n\,\! $ přičtení se $ i\,\! $-tý bit překlopí $ \lfloor \frac{n}{2^i}\rfloor\,\! $-krát, takže celková cena překlopení je $ \leq n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n\,\! $, tj. amortizovaně na jedno přičtení $ \frac{2n}{n} = \Theta(1)\,\! $
- Vkládání: cena $ i\,\! $-tého vložení do pole je $ c_i=\begin{cases}i \mbox{ pokud } \exists k:i-1 = 2^k\\ 1\mbox{ jinak}\end{cases}\,\! $. Celkem dostávám $ T(n) = \sum_{i=1}^n c_i = n + \sum_{j=0}^{\lfloor \log n\rfloor} 2^j\leq n + 2n = 3n\,\! $, takže na jedno vložení vyjde $ \frac{3n}{n} = \Theta(1)\,\! $.
Algoritmus (Účetní metoda)[editovat | editovat zdroj]
Od každé operace vyberu urč. pevný "obnos", kterým onu operaci "zaplatím". Pokud něco zbyde, dám to na účet, pokud bude operace naopak dražší než určený obnos, z účtu vybírám. Zůstatek na účtu musí být stále nezáporný -- pokud uspěji, obnos je amortizovaná cena 1 operace.
- Binární sčítání: Při každém přičtení je právě jeden bit překlopen z 0 na 1. Proto každému bitu zavedeme účet a za přičtení budeme vybírat 2 jednotky. Jedna je použita na překlopení daného bitu z 0 na 1 a druhá uložena na právě jeho účet; překlápění z 1 na 0 jsou hrazeny z účtů (protože každý bit, který má nastavenu 1 má na účtu právě 1 jednotku, projde to). Amortizovaná cena tedy vyjde $ 2=\Theta(1)\,\! $.
- Vkládání: Od každého vložení vyberu 3 jednotky -- na vlastní vložení, na překopírování právě vloženého prvku při příštím vložení a na příští překopírování odpovídajícího prvku v levé polovině pole (na pozici $ n-\frac{s}{2}\,\! $), který obnos ze svého vložení vyčerpal. Po expanzi je celkem na všech účtech $ 0\,\! $, jindy víc, tj. amortizovaná cena operace je $ 3=\Theta(1)\,\! $.
Algoritmus (Potenciálová metoda)[editovat | editovat zdroj]
Je to podobné bankovní, roli účtu hraje nějaká funkce $ w\,\! $, která popisuje vhodnost jednotlivých konfigurací $ D_0,D_1,\dots\,\! $. Potřebuji potom, aby $ w(D_i) \geq 0\ \forall i\,\! $. Amortizovaná složitost $ i\,\; $-té operace $ o\,\! $ je potom:
- $ am(o_i)=T(o_i)+w(D_{i+1})-w(D_i)\,\! $
Složitost nejhoršího případu celé posloupnosti operací může být mnohem "rychlejší" než posloupnost nejhorších případů jednotlivých operací:
- $ \sum_{i=1}^n T(o_i)\leq\sum_{i=1}^n am(o_i)+w(D_0)\,\! $
Státnice -- Matematická lingvistika
Složitost a vyčíslitelnost -- Tvorba algoritmů, Odhady složitosti, NP-úplnost, Aproximační algoritmy, Vyčíslitelné funkce, Rekurzivní množiny, Nerozhodnutelné problémy, Věty o rekurzi.
Datové struktury -- Stromy, Hašování, Dynamizace, Vnější paměť, Třídění.
Formální popis jazyka -- Závislostní syntax, Frázové gramatiky, Obecná lingvistika, FGD, Formální sémantika
Statistické metody -- Korpusy, Strojové učení, Stochastické metody, Experimenty
Automatické zpracování jazyka -- Analýza jazyka, Generování jazyka, Analýza a syntéza řeči, Extrakce informací, Strojový překlad