Toto je starší verze dokumentu! —-

Obsah

IN-POS 2. Algoritmy a datové struktury
- Zadání
- Vypracování

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

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)

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

Nahoru