{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke <Státnice> ze <Státnice_-Informatika-Složitost%28obory_Matematická_lingvistika_a_Softwarové_systémy%29> pro obor <Státnice_-Informatika-_I2:_Softwarové_systémy>, pocházející ze zápisků z předmětu Složitost I a Státnice_-_Metody_tvorby_algoritmů

}}

Amortizovaná složitost (🎓)

{{zkazky|

  • Amortizovana zlozitost (2009,Fiala)

}} Asymptotická složitost - složitost pro jednu operaci

  • asymptoticky ≤ -- f(n) je O(g(n)) ⇔ ∃c>0 ∃n₀ ∀n ≥ n₀: 0 ≤ f(n) ≤ c.g(n)

  • asymptoticky ≥ -- f(n) je Ω(g(n)) ⇔ ∃c>0 ∃n₀ ∀n ≥ n₀: 0 ≤ c.g(n) ≤ f(n)

  • **asymptoticky = **-- f(n) je Θ(g(n)) ⇔ ∃c₁,c₂>0 ∃n₀ ∀n ≥ n₀: 0 ≤ c₁.g(n) ≤ f(n) ≤ c₂.g(n)

Amortizovaná složitost - pro posloupnost operací

  • Typické použití pro odhad časové složitosti posl. operací na dat. struktuře

  • Počítá amortizovanou cenu (průměrný čas na 1 operaci při provedení posloupnosti op) každé operace v nejhorším případě(v nejhorší možné posloupnosti operací)

  • Dává realističtější odhad slož, než klasický odhad složitosti každé operace nejhořším možným případem

  • **Nejedná se o složitost v průměrným případě **

Amortizovaná analýza:

  1. Agregační metoda - Spočítáme nejhorší možný čas T(n) pro posl. N operací. Amortizovaná cena 1 op je pak T(n)/n

  2. Účetní metoda - Od každé op. Vybereme určitý peněžný obnost, ze kterého zaplatíme za danou operaci. Jedna jednotka stačí na konstatní množství práce. Pokud po zaplacení nějaké peníe zbudou, jdou na "účet". Pokud pro zaplacení operace nějaké peníze chybí, tak lze z účtu čerpat. Účet musí být pořád v nezáporny.

Příklad 1: Inkrementace bin. čítače.

  • k-bit binární čítač, všude 0, pak ho nkrát inkrementujem (cíl je spočítat bitové operace (bit-flipy) na jednu inkrementaci.

    • Klasicky počítaný nejhorší případ: n inkrementací a log n bit-flipů na jednu inkrementaci v nejhorším případě -> celkem O(n log n) bitflipů

    • Ukážeme, že amortizovaná cena jedné inkrementace je 2 = O(1) a tímpádem je celkový počet bitflipů jen O(n)

D(účetní): Každá inkrementace změní právě jeden bit z 0 na 1 -> 1 peníz za flip, druhý do banky (každý byt, jež má 1 má 1 peníz v bance) -> ten se použije v momentě, kdy se má změnit z 1 na 0.

D (agregační): l = [ log n ] dolní celá část. V průběhu n flipů se 0 tý byt překlopí nkrát, 1ní - n/2 krát (dcč), 2hý- n/4 atd....

Suma vyjde =2n -> Amortizovaná cena 1 přičtění je 2n/n = 2 = 2 O(1)

Příklad 2: Vkládání do dynamického pole:

Prázdné pole s délkou 1 a postupně do něj vložíme n prvků. Pokud je pole plné vytvoří se 2násobné a zkopíruje se současné. Cíl:Spočítat operace s

prvky pole na jedno vložení.

  • Klasicky v nejhorším případě: n vložení a O(n) opearací s prvky pole na jedno vložení v nejhorším případě -> O(n2) operací s prvky pole

  • Amortizovaán složitost jednoho vložení je 3 = O(1) a tím pádem je celkový počet operací s prvky pole jenom O(n).

D (agregační): cena i-tého vložení ci = i (pokud existuje K: i-1=2k) jinak 1.

Celková cena n vložení je suma ci = n + Suma (j=0..log n) 2j <= n+ 2n = 3n.

Amortizovaná složitost je 3n/n = 3 = O(1)

D (účetní): 3. Jedna na vložení, při expanzi druhá polovina pole platí kopii celého pole, proto každý prvek potřebuje 2 penízky.

Metody tvorby algoritmu: rozdel a panuj, dynamické programování, hladový algoritmus.

Rozděl a panuj (🎓)

{{zkazky|

*Rozdel a panuj (2010,Kratochvil) - vedet o co jde, priklad }}

Rozděl a panuj je metoda návrhu algoritmů, která má 3 kroky (+ vytvoření rekurentní rovnice):

  1. rozděl -- rozdělí úlohu na a (nezávislých) podúloh stejného typu velikosti n/c ( doba D(n) )

  2. vyřeš -- vyřeší podúlohy a to buď přímo pro dostatečně malé, nebo rekurzivně pro větší ( doba T(n/c) )

  3. sjednoť -- sjednotí řešení podúloh do řešení původní úlohy velikosti n ( doba S(n) )

⇒ rekurentní rovnice T(n) = D(n) + aT(n/c) + S(n) (pro triviální n je to celé Θ(1))

Analýza časové složitosti (2 metody řešení):

  1. substituční metoda - uhodneme správné řešení a indukcí jej ověříme (zvlášť shora a zvlášť zdola)

  2. "kuchařka" (Master Theorem)

'''Master Theorem''' (mnemotechnicky)

Nechť a ≥ 1, b > 1, c ≥ 0 ∈ ℝ a nechť T : ℕ → ℕ je neklesající fce taková, že pro ∀n ve tvaru bᵏ (kde k ∈ ℕ) platí

T(n) = aT(n/b) + Θ(n<sup>c</sup>)

Potom

  • je-li a > b<sup>c</sup>, potom platí T(n) = Θ(n<sup>log</sup><sub>''b''</sub><sup>'' a''</sup>) (práce přibývá cestou dolů ve stromu rekurze, tedy ~ #listů stromu)

  • je-li a <b<sup>c<sup>c</sup>) (práce ubývá cestou dolů ve stromu, tedy ~ původní práci v kořenu)

    • ☀ spojení do 1: a ≠ b<sup>c</sup>, potom platí T(n) = Θ(n<sup>max{log</sup><sub>''b''</sub><sup>'' a'','' c''}</sup>),

  • je-li a = b<sup>c</sup>, potom platí T(n) = Θ(n<sup>c</sup> log<sub>''b''</sub> n) (práce stejná cestou dolů ve stromu, tedy ~ hloubce stromu × práce na ∀úrovni)

Aplikace

  • <Státnice%20-%20Třídění%20I2> (rozdel na pulky az do delky 1 a pak slevej monotonni posloupnosti)

    • T(n) = 2T(n/2) + Θ(n)  ⇒ Θ(n log n)

  • <Státnice%20-%20Třídění%20I2#Quicksort>

    • nejhorší složitost - pivot špatně: T(n)=T(n-1)+Ө(n) = Ө(n<sup>2</sup>)

    • průměr složitost - pivot náhodně: O(n log n)

    • nejlepší složitost - pivot medián: T(n)=2T(n/2)+O(n) ⇒ a=2 b=2 c=1 ; 2=2<sup>1</sup>  ⇒ Ө(n log n)

  • <Státnice%20-%20Třídění%20I2#Pořadové%20statistiky%20%28hledání%20mediánu%29> v linearnim case (pomoci pivotu rozdelujeme posloupnost tak dlouho, nez mame prostredni prvek. pivot vybirame pomoci rozdeleni na petice a vyber medianu z medianu petic. median z medianu je poduloha, median z petice trivialita)

    • T(n) = c . n/5 + T(n/5) + (n-1) + T(7/10)  → Θ(n)

Poznámky:

  • oproti dynamickému prg. dělá více práce na podproblémech a proto je více časově náročná (shora dolů)

  • u *Rozděl a panuj *jsou podproblémy navzájem nezávislé

{{zdroje|1=

}}

Dynamické programování (7×🎓)

{{image

| image = Fib.png | width = 100

| caption = Graf subproblémů pro fibonacciho posloupnost. To že to není strom naznačuje překrývající se subproblémy. }}

function Fibonacci(n: integer): integer; begin if n <= 2 then Fibonacci := 1 else Fibonacci := Fibonacci(n-1) + Fibonacci(n-2) end;

{{zkazky|

  • Dynamické programování (2014, neznamy drsny mlady teoretik) - Mel jsem srovnat s metodou Rozdel a panuj + ukazat nejaky priklad

  • Dynamické programování (2014, Fiala) - Motivaci a základní princip dynamického programování. Ukázáno na algoritmech výpočtu Fibonacciho čísel, batohu a Floyd-Warshalova algoritmu. U posledního jmenovaného ze mě zkoušející dostával formální důkaz proč požadujeme nezáporné hrany.

  • Dynamicke programovani (2013, Dvorak) - idea, srovnani s rozdel a panuj, priklady (efektivni) a jejich casova slozitost, prejiti do souvisejicich oblasti - popsal sem floyd-washall a batoh od nej jsme presli pres pseudopolynomialni alg, aproximacni batoh (schema) k UPAS, ale byla to volna diskuse ale nevadilo to.

  • 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í (2012) - co to je, porovnat s Rozděl a panuj a ukázat na konkrétní úloze, jak se dynamické programování realizuje.

  • Dynamicke programovani (2010) - Vsude mi stacily zakladni informace (to, co bylo na prednasce + nejaky priklad) + zodpovedet par doplnujicich otazek, ktere nebyly nikterak zakerne.

  • Dynamicke programovani (2009, Fiala) - Nastesti zadna veta o dynamickem programovani. Stacilo rict k cemu je, jak se pouziva (odshora, odspodu). A uvest par prikladu - Fib. cisla, batoh a floyd warshall. Dal nasledovala otazka, jak jde pomoci algo pro soucet podmnozin - odpoved UPAS s prorezavanim seznamu.

}} je metoda řešení komplexních problémů, využíváme v něm:

  1. Překrývání podproblémů - problém lze rozdělit na podproblémy, jejichž řešení se využívá opakovaně

    • tj. subproblémy jsou závislé <u>narozdíl</u> od Rozděl a panuj

    • řeší subproblémy pouze jednou a pak je většinou uloží do tabulky (aby se výsledky daly znovu použít)

  2. Optimální podstruktury - optimální řešení lze zkonstruovat z optimálních řešení podproblémů.

    • 💡 pro srovnání: hladové algoritmy používají jenom optimální podstruktury

💡 prakticky je to technika, kterou jde z pomalého rekurzivního algoritmu vyrobit pěkný polynomiální (až na výjimečné případy)

Příklad pro výpočet '''Fibonacciho čísla'''

Fib. posloupnost je definována jako:

:f<nowiki/>(0)* = 1, f*(1)* = 1 *** :f<nowiki/>(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.

Přístupy

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. ;Př.(top-down rekurzivního alg.): {| style="font-size: 85%"| var P: array[1..MaxN] of integer; function Fibonacci(n: integer): integer; begin if P[n] = 0 then begin if n <= 2 then P[n] := 1 else P[n] := Fibonacci(n-1) + Fibonacci(n-2) end; Fibonacci := P[n] end;

| width="50%" style="vertical-align:top; padding-left: 10px" |

'''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 (můžeme počítat zbytečně).

Př.(bottom-up nerekurzivního alg.) ::

<pre> function Fibonacci(n: integer): integer;

var P: array[1..MaxN] of integer;

i: integer; begin

P[1] := 1; P[2] := 1;

for i := 3 to n do P[i] := P[i-1] + P[i-2];

Fibonacci := P[n] end;

  • 💡 použití(v NMgr): 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. Speciální případ je součet podmnožiny (SP). Bottom-up pseudopolynomiální alg. pro Batoh je popsán v <Státnice%20-%20NP-úplnost%20I2> (☠ je dost slozity ke statnicim).

|}

{{zdroje|1= prakticky otázka z bakaláře, očekává se nějaké naroubování na to co jsme se naučili na NMgr

ROZDILY oproti metode Rozdel a panuj (jsou to dve ruzne metody tvorby algoritmu)

Divide and conquer:

  • Does more work on the sub-problems and hence has more time consumption.

  • In divide and conquer the sub-problems are independent of each other.

Dynamic programming:

  • Solves the sub-problems only once and then stores it in the table.

  • In dynamic programming the sub-problem are not independent.

  • http://wiki.matfyz.cz/index.php?title=St%C3%A1tnice_-_Metody_tvorby_algoritm%C5%AF#Dynamick.C3.A9_programov.C3.A1n.C3.AD

  • http://www.quora.com/What-is-the-difference-between-dynamic-programming-and-divide-and-conquer

  • http://cs.wikipedia.org/wiki/Dynamick%C3%A9_programov%C3%A1n%C3%AD

  • https://onedrive.live.com/view.aspx?cid=388a82b3c4ce1dfe&id=documents&resid=388A82B3C4CE1DFE%211759&app=OneNote&authkey=!ABoWVv2NQ4DuOcQ&&wd=target%28%2F%2FSlo%C5%BE.one%7C4a6ac938-39bb-4a44-a4e0-55bbd289b47b%2FMetody%20tvorby%20algoritm%C5%AF%7Cf7e91395-dd92-4345-b02e-e8f43a837b66%2F%29

  • https://ksp.mff.cuni.cz/tasks/24/cook2.html

}}

Hladové algoritmy (🎓)

[[Soubor:MST kruskal en.gif|náhled|vpravo|Př.Kruskalův hladový alg. pro hledání min.kostry:<br>

• střídíme hrany podle velikosti<br> • od nejmenší přidáváme hrany do kostry, pokud nevytvoří cyklus (IO)]]

Soubor:Greedy-search-path-example.gif {{zkazky|

  • Hladové algoritmy (2012, Dvořák) - Popsal jsem intuitivně o co jde (oiptimalizační hladové algoritmy), popsal jsem, jak to funguje a popsal jsem Krustalův hladový algoritmus. Bavili jsme se o jeho složitosti (kde jsem neznal způsob, jak to je "ideální"), potom o jeho korektnosti (to jsem taky detaily neznal - nikdy jsem to úplně 100% nepochopil a když jsem se na to koukal do Kapitol z diskrétní matematiky před šesti týdny znova, tak jsem to také úplně nepochopil). Nicméně mi se mě pan Dvořák snažil trochu popostrčit, ale kde nic není, ani smrt nebere. Ukončili jsme to s tím, že to hlavní jsem věděl a že to není fatální.

}} "Dokud můžeš, neohlížej se a jdi rovnou za nosem." neboli splňují tyto 2 podmínky:

  1. Optimální podstruktury - V každém kroku zvolí lokálně nejlepší řešení.

  2. Žádný backtracking - Provedené rozhodnutí již nikdy neodvolává (tedy nebacktrackuje).

Pokud ale od hladového algoritmu chceme, aby nám našel globálně nejlepší řešení, musí naše úloha splnit předpoklad, že si výběrem lokálně nejlepšího řešení nezhoršíme to globální. Tento předpoklad se nedá formulovat obecně a je nutné se nad ním zamyslet zvlášť u každé úlohy.

hladový algoritmus

  • setridime mnozinu podle velikosti

  • vybirame od prvniho prvku do posledniho. Kazdy novy prvek, ktery neporusi integritni omezeni (napr. u hledani minimalni kostry pokud novy vrchol uzavre nejakou kruznici a tudiz by vybrana mnozina nebyla kostrou) pridame do vybrane mnoziny

Př. Automat na colu

První hladovou úlohou bude (jak jinak) automat na jídlo vracející mince. Automat by měl vracet peníze nazpět tak, aby vrátil daný obnos v co možná nejmenším

počtu mincí. Pro náš měnový systém (máme mince hodnot 1, 2, 5, 10, 20 a 50 Kč) lze tuto úlohu řešit hladovým algoritmem – v každém kroku algoritmu vrátíme tu největší minci, kterou můžeme (tedy pro vrácení 42 Kč to bude 42 = 20 + 20 +2 Kč).

Měnové systémy většiny států jsou postavené tak, aby fungovaly takto pěkně, neplatí to ale obecně. Zkusme si vrátit 42 Kč, pokud bychom měli jen mince hodnoty 20, 10 a 4 Kč. Správným řešením je 42 = 20 + 10 + 4 + 4 +4 Kč, hladový algoritmus by ale zkusil vrátit 42 = 20 + 20 + … a tady by selhal.

{{zdroje|1=

https://ksp.mff.cuni.cz/tasks/27/cook1.html#Hladov%C3%A9%20algoritmy }}

{{Statnice I2}}