Toto je starší verze dokumentu! —-

Obsah

IN-POS 2. Algoritmy a datové struktury

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ů

: 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.

Permutace

Generování všech permutací n-prvkové posloupnosti

počet různých permutací:
⇒ dolní odhad: $\Omega(n!)$
⇒ složitost problému: $\Theta(n!)$

Polynom

Evaluace $a_{n}x^{n} + a_{n-1}x^{n-1} + ... + a_0$ v bodě .

Spracování všech koeficientů $\Omega(n)$
⇒ dolní odhad: $\Omega(n)$
⇒ složitost problému: $\Theta(n)$

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ě.

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.

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 složitosti vykonaných operací.
- Pro přehlednost lze kredity lze přiřazovat/odebírat objektům, na kterých se operace realizují.

Zásobník

operace	složitost	kredity
PUSH	1	2
POP	1	0
MULTIPOP	$\min{(k, \|S\|)}$	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 součet kreditů vykonaných operací.
Součet kreditů vykonaných operací je

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 součtu skutečných cen. (Tedy je i horním odhadem složitosti posloupnosti operací.)

Zásobník

operace	složitost	amortizovaná cena
PUSH	1
POP	1
MULTIPOP	$\min{(k, \|S\|)}$

Celá posloupnost n operací je součet amortizovaných cen.
Součet amortizovaných cen je

Techniky návrhu algoritmů

Rozděl a panuj

Dynamické programování

Hladové strategie

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	$\Theta(1)$	$\Theta(1)$	$\Theta(1)$	$\Theta(1)$
MINIMUM	$\Theta(n)$	$\Theta(1)$	$\Theta(log n)$	$\Theta(1)$
INSERT	$\Theta(1)$	$\Theta(log n)$	$\Theta(1)$ *	$\Theta(1)$
UNION	$\Theta(1)$	$\Theta(n)$	$\Theta(log n)$	$\Theta(1)$
EXTRACT_MIN	$\Theta(n)$	$\Theta(log n)$	$\Theta(log n)$	$\Theta(log n)$ *
DELETE	$\Theta(1)$	$\Theta(log n)$	$\Theta(log n)$	$\Theta(log n)$ *
DECREASE_KEY	$\Theta(1)$	$\Theta(log n)$	$\Theta(log n)$	$\Theta(1)$ *

* 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ů.

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í.

EXTRACT_MIN

Odebrání prvku (1) a rozpad potomků.

Spojení a finální stav po EXTRACT_MIN

DECREASE_KEY

Snížení hodnoty z (9) na (0)

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 $O(m . \alpha(n))$

Algoritmy pro práci s řetězci

Karp-Rabin

KMP

Boyer-Moore

Užití konečných automatů

Zdroje:

slidy IV003 (verze 2016)

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

Nahoru