Státnice - Metody tvorby algoritmů

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)

Popis složitosti algoritmů

Definice (Velikost dat, krok algoritmu)

Velikost dat je obvykle počet bitů, potřebných k jejich zapsání, např. data $ D\,\! $ jako pro čísla $ a_1,\dots,a_n\,\! $ je velikost dat $ |D|=\sum_{i=1}^n \lceil \log a_i \rceil\,\! $.

Krok algoritmu je jedna operace daného abstraktního stroje (např. Turingův stroj, stroj RAM), zjednodušeně jde o nějakou operaci, proveditelnou v konstantním čase (např. aritmetické operace, porovnání hodnot, přiřazení -- pro jednoduché číselné typy).

Definice (Časová složitost)

Časová složitost je funkce $ f:\mathbb{N}\to\mathbb{N}\,\! $ taková, že $ f(|D|)\,\! $ udává počet kroků daného algoritmu, pokud je spuštěn na datech $ D\,\! $.

Definice (Asymptotická složitost)

Řekneme, že funkce $ f(n)\,\! $ je asymptoticky menší nebo rovna než $ g(n)\,\! $, značíme $ f(n)\,\! $ je $ O(g(n))\,\! $, právě tehdy, když

$ \exists c>0 \exists n_0 \forall n>n_0: 0 \leq f(n) \leq c \cdot g(n)\,\! $

Funkce $ f(n)\,\! $ je asymptoticky větší nebo rovna než $ g(n)\,\! $, značíme $ f(n)\,\! $ je $ \Omega(g(n))\,\! $, právě tehdy, když

$ \exists c>0 \exists n_0 \forall n>n_0: 0 \leq c \cdot g(n) \leq f(n)\,\! $

Funkce $ f(n)\,\! $ je asymptoticky stejná jako $ g(n)\,\! $, značíme $ f(n)\,\! $ je $ \Theta(g(n))\,\! $, právě tehdy, když

$ \exists c_1,c_2>0 \exists n_0 \forall n>n_0: 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)\,\! $

Funkce $ f(n)\,\! $ je asymptoticky ostře menší než $ g(n)\,\! $ ($ f(n)\,\! $ je $ o(g(n))\,\! $, když

$ \forall c>0 \exists n_0 \forall n>n_0: 0\leq f(n) < c\cdot g(n)\,\! $

Funkce $ f(n)\,\! $ je asymptoticky ostře větší než $ g(n)\,\! $ ($ f(n)\,\! $ je $ w(g(n))\,\! $, když

$ \forall c>0 \exists n_0 \forall n>n_0: 0\leq c\cdot g(n) < f(n)\,\! $

Poznámka

Asymptotická složitost zkoumá chování algoritmů na velkých datech, zařazuje je podle toho do kategorií. Zanedbává multiplikativní a aditivní konstanty.

Rozděl a panuj

• Pasáž knihy Jakuba Černého - Rozděl a panuj

Definice (Metoda rozděl a panuj)

Rozděl a panuj je metoda návrhu algoritmů (ne strukturované programování), která má 3 kroky:

1. rozděl -- rozdělí úlohu na několik podúloh stejného typu, ale menší velikosti
2. vyřeš -- vyřeší podúlohy a to buď přímo pro dostatečně malé, nebo rekurzivně pro větší
3. sjednoť -- sjednotí řešení podúloh do řešení původní úlohy

Aplikace

• QUICKSORT
• Hledání mediánu

Tato část je neúplná a potřebuje rozšířit. Strassen

Analýza složitosti algoritmů rozděl a panuj

Poznámka (Vytvoření rekurentní rovnice)

Pro časovou složitost algoritmů typu rozděl a panuj zpravidla dostávám nějakou rekurentní rovnici.

• $ T(n)\,\! $ budiž doba zpracování úlohy velikosti $ n\,\! $, za předpokladu, že $ T(n)=\Theta(1)\,\! $ pro $ n\leq n_0\,\! $.
• $ D(n)\,\! $ budiž doba na rozdělení úlohy velikosti $ n\,\! $ na $ a\,\! $ podúloh stejné velikosti $ \frac{n}{c}\,\! $.
• $ S(n)\,\! $ budiž doba na sjednocení řešení podúloh velikosti $ \frac{n}{c}\,\! $ na jednu úlohu velikosti $ n\,\! $. Dostávám rovnici

$ T(n)=\begin{cases} D(n)+aT(\frac{n}{c})+S(n) \quad\quad & n > n_0 \\ \Theta(1) & n \leq n_0 \end{cases}\,\! $

Poznámka

Při řešení rekurentních rovnic:

• Zanedbávám celočíselnost ($ \frac{n}{2}\,\! $ místo $ \lceil\frac{n}{2}\rceil\,\! $ a $ \lfloor\frac{n}{2}\rfloor\,\! $)
• Nehledím na konkrétní hodnoty aditivních a multiplikativních konstant, asymptotické notace používám i v zadání rekurentních rovnic, i v jejich řešení.

Věta (Substituční metoda)

1. Uhodnu asymptoticky správné řešení
2. Indukcí ověřím správnost (zvláště horní a dolní odhad)

Věta (Metoda "kuchařka" (Master Theorem))

Nechť $ a\geq 1, c>1,d\geq 0\in\mathbb{R}\,\! $ a nechť $ T:\mathbb{N}\to\mathbb{N}\,\! $ je neklesající funkce taková, že $ \forall n\,\! $ tvaru $ c^k\,\! $ platí

$ T(n)=aT(\frac{n}{c}) + \Theta(n^d)\,\! $

Potom

1. Je-li $ \log_c a \neq d\,\! $, pak $ T(n)\,\! $ je $ \Theta( n^{\max\{\log_c a, d\}} )\,\! $
2. Je-li $ \log_c a = d\,\! $, pak $ T(n)\,\! $ je $ \Theta( n^d \log_c n )\,\! $

Věta (Master Theorem, varianta 2)

Nechť $ 0<a_i<1\,\! $, kde $ i\in\{1,\dots,k\}\,\! $ a $ d\geq 0\,\! $ jsou reálná čísla a nechť $ T:\mathbb{N}\to\mathbb{N}\,\! $ splňuje rekurenci

$ T(n)=\sum_{i=1}^k T(a_i\cdot n) + \Theta(n^d)\,\! $

Nechť je číslo $ x\,\! $ řešením rovnice $ \sum_{i=1}^k a_i^x = 1\,\! $. Potom

1. Je-li $ x \neq d\,\! $ (tedy $ \sum_{i=1}^k a_i^d \neq 1\,\! $), pak $ T(n)\,\! $ je $ \Theta( n^{\max\{x, d\}} )\,\! $
2. Je-li $ x = d\,\! $ (tedy $ \sum_{i=1}^k a_i^d = 1\,\! $), pak $ T(n)\,\! $ je $ \Theta( n^d \log n )\,\! $

Dynamické programování

Převzato z vypracovaných otázek V. Bedecse -- Tuetschek 10:34, 30 Aug 2010 (CEST)

Zážitky ze zkoušek

Dynamické programování (2012, Dvořák) - U dynamickýho programování jsem nějak sesmolil princip fungování a napsal jsem tam jeden konkrétní algoritmus (z grafiky - matchování vrcholů dvou mnohoúhelníků), na kterym jsem ukazoval, jak to funguje. To bylo OK, ale tahal ze mě pořád nějakej obecnej princip, jak to funguje. V rámci toho jsem ještě za pochodu vymýšlel algoritmus na batoh (to se mi vůbec nedělalo dobře, když vedle mě seděl a čekal na výsledek). Na konec jsme se teda asi dobrali toho, co chtěl slyšet - že se řešení konstruuje z menších podúloh stylem zdola nahoru (narozdíl od rozděl&panuj, kde to je v zásadě shora dolů).

Dynamické programování je metoda řešení problemů, které v sobě obsahují překrývající se subproblémy (subproblémy jsou závislé narozdíl od Rozděl a panuj).

Příklad

Typickým příkladem je výpočet fibonaciho čísla. Fib. posloupnost je definována jako:

$ f(0) = 1, f(1) = 1 $

$ f(n+2) = f(n+1) + f(n) $

Výpočet třeba 4. čísla by pak byl $ f(4) = f(3) + f(2) = f(2) + f(1) + f(1) + f(0) = f(1) + f(0) + f(1) +f(1) +f(0) = 5 $. Vidíme, že jsme $ f(2) $ počítali dvakrát, $ f(1) $ třikrát a $ f(0) $ dvakrát. Ve větším měřítku toto zbytečně počítání vede k exponenciální složitosti algoritmu. Lepší cestou je počítat "od spodu", kdy pomoci $ f(0) $ a $ f(1) $ spočteme $ f(2) $, pak s jeho pomoci $ f(3) $ nakonec $ f(4) $ s lineární složitosti.

V dynamickém programování se například vytvoří mapa Fibonacciho čísel a jejich hodnot. Před tím, než začnu počítat hodnotu nějakého Fibonacciho čísla, se podívám do mapy.

Nutné podmínky

V dynamickém programování využíváme:

1. Překrývání podproblému - problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně.
2. Optimální podstruktury - optimální řešení lze zkonstruovat z optimálních řešení podproblémů.

Postupy

Obvykle se používá jeden ze dvou přístupů k dynamickému programování:

• Top-down - problém se rekurzivně dělí na podproblémy a po jejich vyřešení se zapamatují výsledky, které se použijí při případném opětovném řešení daného podproblému.
• Bottom-up - nejdříve se spočítají všechny možné podproblémy (viz příklad s Fibonacciho posloupnosti), které se potom skládají do řešení větších problémů. Tento přístup je výhodnější z hlediska počtu volání funkci a místa na zásobníků, ale ne vždy musí být zřejmě, které všechny subproblémy je třeba předem spočítat.

Použití

Problém batohu -- máme věci různé váhy a batoh určité nosnosti. Které věci máme dát do batohu, abychom jej co nejlépe zaplnili (jednorozměrná varianta problému batohu)? Speciální případ je součet podmnožiny (SP). Algoritmus je popsán v sekci o NP-úplnosti.

Uzávorkování součinu matic (Matrix chain multiplication) tak, aby počet skalárních součinů byl co nejmenší. Dělá se pomocí 2 čtvercových matic ($ M $ a $ K $) řádu rovného počtu násobených matic, kde pracujeme jen nad diagonálou. Hodnota na $ M_{ij} $ udává minimální počet skalárních součinů při nejlepším uzávorkování matic $ i $ až $ j $, hodnota $ K_{ij} $ určuje matici, která rozděluje závorkování na dvě podmnožiny matic. Hodnotu $ M_{ij} $ lze zkonstruovat ze všech $ M_{ik} $ a $ M_{kj} $ pro $ i<k<j $.

Hladové algoritmy

Motivace

Problém 1

Dán souvislý neorientovaný graf $ G=(V,E)\,\! $ a funkce $ d:E\to\mathbb{R}^+\,\! $, udávající délky hran. Najděte minimální kostru grafu $ G\,\! $, tj. kostru $ G'=(V,E')\,\! $ tak, že $ \sum_{e\in E'} d(e)\,\! $ je minimální.

Problém 2

Je dána množina $ S=\{1,\dots,n\}\,\! $ úkolů jednotkové délky. Ke každému úkolu je dána lhůta dokončení $ d_i\in\mathbb{N}\,\! $ a pokuta $ w_i\in\mathbb{N}\,\! $, kterou je úkol $ i\,\! $ penalizován, není-li hotov do své lhůty. Najděte rozvrh (permutaci úkolů od času $ 0\,\! $ do času $ n\,\! $), který minimalizuje celkovou pokutu.

Problém 3

Je dána množina $ S=\{1,\dots,n\}\,\! $ úkolů. Ke každému úkolu je dán čas jeho zahájení $ s_i\,\! $ ukončení $ f_i\,\! $, $ s_i\leq f_i\,\! $. Úkoly $ i\,\! $ a $ j\,\! $ jsou kompatibilní, pokud se intervaly $ [s_i,f_i)\,\! $ a $ [s_j,f_j)\,\! $ nepřekrývají. Najděte co největší množinu (po dvou) kompatibilních úkolů.

Matroid

Definice (Matroid)

Matroid je uspořádaná dvojice $ M=(S,I)\,\! $, splňující:

• $ S\,\! $ je konečná neprázdná množina (prvky matroidu $ M\,\! $)
• $ I\,\! $ je neprázdná množina podmnožin $ S\,\! $ (nezávislé podmnožiny), která má

1. dědičnou vlastnost: $ B\in I \wedge A\subseteq B\quad \Rightarrow\quad A\in I\,\! $,
2. výměnnou vlastnost: $ A,B\in I \wedge |A|<|B|\quad \Rightarrow\quad \exists x\in B\backslash A: A\cup\{x\}\in I\,\! $.

Věta (O velikosti maximálních nezávislých podmnožin)

Všechny maximální (maximální vzhledem k inkluzi) nezávislé podmnožiny v matroidu mají stejnou velikost.

Důkaz

Z výměnné vlastnosti, nechť $ A, B\in I\,\! $ maximální, $ |A|<|B|\,\! $, pak $ A\cup\{x\}\in I, x\notin A\,\! $, což je spor.

Definice (Vážený matroid)

Matroid $ M=(S,I)\,\! $ je vážený, pokud je dána funkce $ w:S\to\mathbb{R}^+\,\! $ a její rozšíření na podmnožiny množiny $ S\,\! $ je definováno předpisem:

$ A\subseteq S \Rightarrow w(A)=\sum_{x\in A}w(x)\,\! $

Problém 1 a 2 -- zobecněný

Pro daný vážený matroid nalezněte nezávislou podmnožinu s co největší vahou (optimální množinu). Protože váhy jsou kladné, vždy se bude jednat o maximální nez. množinu.

Problém 1 je spec. případ tohoto, protože můžeme uvažovat grafový matroid (nad hranami) -- $ M_G = (S, I)\,\! $, kde $ S = E\,\! $ a pro $ A\subseteq E\,\! $ platí $ A\in I\,\! $, pokud hrany z $ A\,\! $ netvoří cyklus (tj. indukovaný podgraf tvoří les).

Dědičná vlastnost této struktury je zřejmá, výměnnost se dá dokázat následovně: mějme $ A,B\subseteq E, |A|<|B|\,\! $. Pak lesy z $ A, B\,\! $ mají $ n-a > n-b\,\! $ stromů (vč. izolovaných vrcholů). V $ B\,\! $ musí být strom, který se dotýká $ \geq 2\,\! $ různých stromů z $ A\,\! $. Ten obsahuje hranu, která není v žádném stromě $ A\,\! $ a netvoří cyklus a tak ji můžu k $ A\,\! $ přidat.

Váhovou funkci převedu na hledání maxim: $ w(e) = c - d(e)\,\! $, kde $ c\,\! $ je dost velká konstanta, aby všechny váhy byly kladné. Algoritmus pak najde max. množinu, kde hrany netvoří cyklus. Implicitně bude mít $ n-1\,\! $ hran, takže půjde o kostru a její $ w\,\! $ bude maximální, tedy původní váha minimální.

Pro problém 2 zavedeme pojem kanonického rozvrhu -- takového rozvrhu, kde jsou všechny včasné úkoly rozvrženy před všemi zpožděnými a uspořádány podle neklesající lhůty dokončení (tohle na celkové pokutě nic nezmění a máme bijekci mezi množinou včasných úkolů a kanonickými rozvrhy).

Optimální množinu pak lze hledat jen nad kanonickými rozvrhy -- nezávislou množinou úkolů nazvu takovou, pro kterou existuje kanonický rozvrh tak, že žádný úkol v ní obsažený není zpožděný. Potom hledání max. nezávislé množiny při ohodnocení pokutami je hledání nejmenší pokuty (odeberu co nejvíc z možné celkové pokuty).

Pak zbývá dokázat, že takto vytvořená struktura je matroid. Dědičná vlastnost je triviální -- vyhodím-li něco z nezávislé množiny, nechám v rozvrhu mezery a bude platit stále. Pro výměnnou vlastnost zavedu pomocnou funkci $ N_t(C) = |\{i\in C| d_i\leq t\}|\,\! $, udávající počet úkolů z množiny $ C\,\! $ se lhůtou do času $ t\,\! $. Pak množina $ C\,\! $ je nezávislá, právě když $ \forall t\in\{1,\dots,n\}: N_t(C)\leq t\,\! $.

Pak máme-li 2 nezávislé $ A\,\! $, $ B\,\! $, $ |B|>|A|\,\! $, označíme $ k\,\! $ největší okamžik takový, že $ N_k(B)\leq N_k(A)\,\! $, tj. od $ k+1\,\! $ dál platí $ N_t(A) < N_t(B)\,\! $. To skutečně nastane, protože $ |B| = N_n(B) > N_n(A) = |A|\,\! $. Pak určitě v $ B\,\! $ je ostře víc úkolů s $ d_i = k+1\,\! $ než v $ A\,\! $, tj. $ \exists x\in B\backslash A\,\! $ se lhůtou $ k+1\,\! $. $ A \cup \{x\}\,\! $ je nezávislá, protože $ N_t(A\cup\{x\}) = N_t(A)\,\! $ pro $ t\leq k\,\! $ a $ N_t(A\cup\{x\}) \leq N_t(B)\,\! $ pro $ t\geq k+1\,\! $.

Hladový algoritmus na váženém matroidu

Algoritmus (Greedy)

Mám zadaný matroid $ M=(S,I)\,\! $, kde $ S = \{x_1,\dots,x_n\}\,\! $ a $ w:S\to\mathbb{R}^+\,\! $. Potom

1. $ A:=\emptyset\,\! $, setřiď a přeznač $ S\,\! $ sestupně podle vah
2. pro každé $ x_i\,\! $ zkoušej: je-li $ A\cup\{x_i\}\in I\,\! $, tak $ A:=A\cup\{x_i\}\,\! $
3. vrať $ A\,\! $ jako maximální nezávislou množinu

Pokud přidám nějaké $ x_i\,\! $, nikdy nezruším nezávislost množiny; s už přidanými prvky se nic nestane. Časová složitost je $ \Theta(n\log n)\,\! $ na setřídění podle vah, testování nezávislosti množiny závisí na typu matriodu ($ f(n)\,\! $), takže celkem něco jako $ \Theta(n\log n + n\cdot f(n))\,\! $.

Důkaz

• Vyhození prvků, které samy o sobě nejsou nezávislé množiny, nic nezkazí (z dědičné vlastnosti).
• První vybrané $ x_i\,\! $ je "legální" (nezablokuje mi cestu), protože mezi max. nez. množinami určitě existuje taková, která jím mohla vzniknout (z výměnné vlastnosti -- vezmeme první prvek, který je sám o sobě nez. mn. a s pomocí nějaké max. nez. množiny $ B\,\! $ ho doplníme, vzniklé $ \{x_i\}\cup (B\backslash \{ x_j\})\,\! $ musí být také maximální).
• Nalezení optimální množiny obsahující pevné (první vybrané) $ x_i\,\! $ v $ M=(S,I)\,\! $ je ekvivalentní nalezení optimální množiny v $ M' = (S', I')\,\! $, kde $ S' = \{ y \in S | \{ x_i,y\}\in I\}\,\! $ a $ I' = \{ B\subset S\backslash \{x_i\} | B\cup \{x_i\} \in I\}\,\! $ (je-li $ S'\,\! $ neprázdná, je to matroid, vlastnosti se přenesou z původního; pokud je $ S'\,\! $ prázdná, tak algoritmus končí) a tedy když vyberu $ x_i\,\! $, nezatarasím si cestu k optimu -- stačí ukázat, že $ A\cup\{x\}\,\! $ je optimální v $ M\,\! $ právě když $ A\,\! $ je optimální v $ M'\,\! $.
• Takže když budu vybírat (indukcí opakovaně) $ x_i\,\! $ podle váhy, dojdu k optimální množině.

Algoritmus (Hladový algoritmus na problém 3)

Máme $ S=\{1,\dots,n\}\,\! $ množinu úkolů s časy startů $ s_i\,\! $ a konců $ f_i\,\! $. Provedeme:

1. $ A:=\emptyset\,\! $, $ f_0:= 0, j:= 0\,\! $
2. setřiď úkoly podle $ f_i\,\! $ vzestupně a přeznač
3. pro každé $ i\,\! $ zkoušej: je-li $ s_i \geq f_j\,\! $, pak $ A:=A\cup\{i\}\,\! $ a $ j:=i\,\! $
4. vrať $ A\,\! $ jako max. množinu nekryjících se úkolů

Složitost je $ n\log n\,\! $ na setřídění, zbytek už lineární. Sice to funguje, ale tahle struktura NENÍ matroid -- nesplňuje výměnnou vlastnost. Algoritmus má ale stejný důkaz jako předchozí na matroidech (legálnost hladového výběru -- existuje max. množina obsahující prvek $ 1\,\! $ -- a existenci optimální množiny -- převod na "menší" zadání).

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