Problémy a algoritmy

Problémy a algoritmy ˇ Algoritmus. Vlastnosti algoritmu. ˚ Delení algoritmu. ˚ Složitost algoritmu. ˚

Tomáš Bayer | [email protected] ˇ Katedra aplikované geoinformatiky a kartografie. Pˇrírodovedecká fakulta UK.

ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

1 / 68

Obsah pˇrednášky 1

ˇ Úvodní informace o pˇredmetu

2

Problém a algoritmus

3

Algoritmus

4

Analýza efektivity algoritmu Složitost algoritmu Asymptotická složitost

5

Složitost problému

6

Základní techniky návrhu algoritmu

7

Volba algoritmu a problém


2 / 68

ˇ Úvodní informace o pˇredmetu

1. Plán pˇrednášek Tematické celky: (1,2) Problémy a algoritmy. (3) Úvod do výpoˇcetní geometrie. (4) Geometrické vyhledávání. (5) Konvexní obálky. (6,7) 2D triangulace. (8) Voroného diagramy. (9) Topologická kostra. (10, 11) Kartografická generalizace. (12) Operace s uzavˇrenými oblastmi v GIS. Cviˇcení: Implementace algoritmu˚ v jazyce C++ pod GNU/Linux. Literatura: [1] Rourke O. J.: Computational Geometry in C, 2005, Cambridge University Press. [2] de Berg, van Kreveld, Overmars M., Schwarzkopf O.: Computational Geometry, 2000, Springer. [3] Bayer T.: Algoritmy v digitální kartografii, 2008, UK v Praze. [4] Žára J. & kol.: Moderní poˇcítaˇcová grafika, 2004, Computer Press. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

3 / 68


2. Problém Termín mající více významu. ˚ ˇ Definice 1 (Slovník spisovného jazyka ceského) ˇ k rˇešení, nerozˇrešená sporná otázka, otázka k rozhodnutí, nesnadná vec” ˇ “Vec Definice 2 (Wikipedia). ˇ “Podmínky nebo situace nebo stav, který je nevyˇrešený, nebo nechtený, nebo nežádoucí.” Problém vyžaduje ˇrešení. ˇ aspekty problému. Pro nalezení ˇrešení nutné pochopit nejduležit ˚ ejší ˇ eˇ a efektivneˇ Ne všechny problémy jsme v souˇcasné dobeˇ schopni úspešn vyˇrešit !!!


4 / 68


3. Problém & poˇcítaˇcová kartografie

Zajímají nás problémy, které lze pˇresneˇ formulovat s využitím matematického aparátu, jejichž ˇrešení lze mechanizovat (napˇr. s využitím poˇcítaˇce). ˇ ˇ Kartografie je veda a souˇcasneˇ umení, u ˇrady problému˚ neexistuje exaktní ˇrešení: barevnost mapy, cˇ itelnost mapy, kartografická generalizace. ˇ Rešení problému˚ v poˇcítaˇcové kartografii (Digital Cartography) založeno na kombinaci exaktních a subjektivních postupu. ˚ Snaha nalézt exaktní postupy ˇrešení a omezovat vliv lidského faktoru pˇri zpracování geodat. V každém okamžiku pˇribývá mnohem více dat, než lze ruˇcneˇ zpracovat.


5 / 68


4. Popis problému Problém v geoinformatice/poˇcítaˇcové kartografii lze formálneˇ zapsat takto: NÁZEV PROBLÉMU: Slovní popis problému VSTUP: Popis pˇrípustného vstupu (množina vstupních dat). VÝSTUP: Popis výstupu, tj. výsledku, který je pro daný vstup oˇcekáván. Musí existovat funkce f pˇriˇrazující vstupním datum ˚ požadovaný výstup. Nalezení ˇrešení problému ⇒ nalezení pˇríslušné funkce f . Definice: Každý problém P je urˇcen uspoˇrádanou trojicí (IN , OUT , f ), kde IN pˇredstavuje množinu pˇrípustných vstupu, ˚ OUT množinu oˇcekávaných výstupu˚ a f : IN → OUT funkci pˇriˇrazující každému vstupu oˇcekávaný výstup. VSTUP/VÝSTUP: Kombinace znaku, ˚ celých cˇ ísel cˇ i pˇrirozených cˇ ísel pˇredstavující kódování. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

6 / 68

Algoritmus

5. Algoritmizace problému˚ ˇ pˇrináší ˇradu nových problému. Dynamický rozvoj pˇrírodních/technických ved ˚ Poptávka po odbornících: kteˇrí se orientují v souˇcasné problematice a jsou schopni problémy efektivneˇ ˇrešit, kteˇrí jsou schopni hledat ˇrešení nových problému. ˚ ˇ ˇ je nejak ˇ ˇrešitelná s Vetšina souˇcasných problému˚ z oblasti pˇrírodních/technických ved využitím knihoven cˇ i specializovaného software. ˇ Vždy lze nalézt nejakou variantu problému, která ješteˇ nebyla zpracována, cˇ i problém drobneˇ modifikovat. ˇ ˇ ˇ Jak postupovat dále? Cekat, až problém nekdo nekdy vyˇreší? ˇ Rešení problému hledáno ve formeˇ obecného pˇredpisu zahrnujícího posloupnost jednotlivých kroku, ˚ tzv. algoritmus rˇešení. Algoritmizace problému˚ rozvíjí logické myšlení, zejména schopnost abstraktního uvažování. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

7 / 68

Algoritmus

6. Algoritmus Pojem cca 1000 let starý, poprvé použit významným perským matematikem Abú Abdallahem Muhammadem ibn Musa al-Khwarizmim. 1 Algoritmus je obecný pˇredpis sloužící pro ˇrešení zadaného problému. ˇ Pˇredstavuje posloupnost kroku˚ doplnených jednoznaˇcnými pravidly. ˇ ˇ kuchynský ˇ Setkáváme se s ním i v bežném živote: recept, lékaˇrský pˇredpis. Algoritmicky rˇešitelné problémy Algoritmus A rˇeší problém P, pokud libovolnému vstupu x, x ∈ IN, pˇriˇrazuje v koneˇcném poˇctu kroku˚ (alesponˇ jeden) výstup y, y ∈ OUT , tak, že platí: y = f (x ). Poznámky: Pˇredpokládáme, že algoritmus A rozumí vstupnímu kódování a je schopen uložit data ve výstupním kódování. ˇ Pro zadaný vstup x muže ˚ existovat více než jedno ˇrešení y , algoritmus A by mel nalézt alesponˇ jedno. 1

Fibonacci jeho pˇríjmení zkomolil na “Algorizmi” a zaˇcal tento termín používat.


8 / 68

Algoritmus

7. Vlastnosti algoritmu A) Determinovanost Algoritmus musí být jednoznaˇcný jako celek i v každém svém kroku. Tohoto stavu nelze dosáhnout pˇrirozenými jazyky, proto jsou pro zápis algoritmu používány formální jazyky. Algoritmus je invariantní vuˇ ˚ ci formálnímu jazyku !!! B) Rezultativnost Algoritmus vede vždy ke správnému výsledku v koneˇcném poˇctu kroku. ˚ C) Hromadnost Algoritmus lze použít pro ˇrešení stejné tˇrídy problému˚ s ruznými ˚ vstupními hodnotami. Pro jejich libovolnou kombinaci obdržíme jednoznaˇcné ˇrešení. D) Opakovatelnost Pˇri opakovaném použití stejných vstupních dat vždy obdržíme tentýž výsledek.

Pozor na heuristiky! E) Efektivnost ˇ být efektivní. Každý krok algoritmu by mel ˇ v koneˇcném cˇ ase. Krok využívá elementární operace, které lze provádet ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

9 / 68

Algoritmus

ˇ 8. Rešitelnost problému ˇ ˇ je nutné stanovit urˇcitá omezení. Rešitelnost problému nelze posuzovat obecne, Omezení problému na speciální typ problému, tzv. ANO/NE problém Problém musí být ˇrešitelný v koneˇcném cˇ ase. ANO/NE problém (tzv. rozhodovací problém): Vstupní množina IN = {0, 1} a výstupní množina OUT = {0, 1} jsou dvouprvkové, algoritmus A, problém P. VSTUP: x1 , x2 VÝSTUP: f (x1 ) = f (x2 )? (tj. ANO/NE) ˇ a Pokud algoritmus A ˇreší rozhodovací problém problém P (pˇriˇradí správneˇ odpovedi skonˇcí v koneˇcném cˇ ase), problém P oznaˇcujeme jako algoritmicky rozhodnutelný. ˇ 1, pˇriˇradí správnou odpoved’ ˇ 1a Pokud algoritmus A vstupu, na který je odpoved’ ˇ 0, pˇriˇradí odpoved’ ˇ 0 nebo je jeho beh ˇ skonˇcí a pro vstup, na který je odpoved’ nekoneˇcný, problém P oznaˇcujeme jako algoritmicky cˇ ásteˇcneˇ rozhodnutelný. V jiném pˇrípadeˇ oznaˇcujeme problém jako algoritmicky nerozhodnutelný. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

10 / 68

Algoritmus

ˇ 9. Doplnkový problém P ˇ Doplnkový problém P k rozhodovacímu problému P . Pˇredstavuje takový problém, který má stejné vstupy jako P, ale výstupy jsou prohozeny. Vztahy mezi P a P: Definice1: Je -li P rozhodnutelný problém, pak je P také cˇ ásteˇcneˇ rozhodnutelný. Definice 2: Je -li P rozhodnutelný, pak je i P rozhodnutelný. Definice 3, negace (2): Je -li P nerozhodnutelný, pak je i P nerozhodnutelný. ˇ Postova veta: Je -li P cˇ ásteˇcneˇ rozhodnutelný a P cˇ ásteˇcneˇ rozhodnutelný, pak je P rozhodnutelný. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

11 / 68

Analýza efektivity algoritmu

10. Efektivita algoritmu Efektivita algoritmu je duležitou ˚ výkonnostní charakteristikou. Výkonnostní charakteristiky algoritmu˚ nelze ignorovat: cˇ asové a materiální úspory. ˇ Každý algoritmus má kritické místo (tzv. bottleneck ), které spotˇrebuje vetšinu výkonu ⇒ optimalizace. Efektivní algoritmus ˇreší problém s minimálními nároky na hardware v co nejrychlejším ˇ využití existujících prostˇredku˚ ⇒”Time Is Money”. cˇ ase, cílem je co neoptimálnejší ˇ ˇ ˇ Rychlost behu algoritmu ovlivnuje rychlost behu jeho nejpomalejší komponenty, pozor na zdánliveˇ nepodstatné detaily. Nejrychlejší vs. optimální rˇešení: Nejjednodušší ˇrešení zpravidla nejdéle trvá, ale je jednoduché na implementaci (nenároˇcné aplikace). Nejrychlejší ˇrešení bývá zpravidla velmi nároˇcné na implementaci (ˇcasoveˇ kritické aplikace), nemusí však být stabilní. Optimální ˇrešení bývá ˇrádoveˇ pomalejší než nejrychlejší varianta, avšak spolehlivé. Prumyslová ˚ implementace ˇ používáno optimální ˇrešení aneb v V prumyslové ˚ implementaci nejˇcasteji jednoduchosti je síla. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

12 / 68


11. Analýza efektivity algoritmu Efektivita algoritmu stanovena na základeˇ jeho analýzy. ˇ Analýzu algoritmu je možné provádet: ˇ Empiricky: srovnáním doby behu ruzných ˚ algoritmu. ˚ ˇ rují funkcionalitu algoritmu), data s Provádí se nad 3 množinami dat: náhodná data (oveˇ ˇ rují schopnost zpracovat libovolná data), skuteˇcná nevhodnou vstupní konfigurací (oveˇ data. ˇ s využitím matematické analýzy. Exaktne: Analýza ˇrad, hledání asymptotických funkcí. Cíle analýzy algoritmu: ˚ ˇ nejvhodnejšího ˇ Porovnání ruzných ˚ algoritmu˚ ˇrešící stejný problém: výber algoritmu (optimalizace volbou algoritmu). Odhad výkonnosti algoritmu: lze tento algoritmus použít pro zadaný problém a vstup? ˇ Nastavení parametru˚ algoritmu: jak nastavit vstupní parametry, aby algoritmus bežel co ˇ nejefektivneji? ˇ vhodných datových struktur (optimalizace volbou datové struktury) Výber ˇ Castou chybou je pouhé sledování výkonnostních charakteristik algoritmu. ˚ ˇ výkonoveˇ efektivnejšího ˇ Implementace a odladení algoritmu pro libovolný vstupní množinu ˇ je použít pomalejší, ale univerzálnejší ˇ algoritmus. muže ˚ být znaˇcneˇ složité ⇒ vhodnejší ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

13 / 68


Složitost algoritmu

12. Složitost algoritmu Jeden problém muže ˚ být ˇrešen sadou ruzných ˚ algoritmu. ˚ Kdyby poˇcítaˇc pracoval s nekoneˇcnou rychlostí, nezáleželo by na volbeˇ algoritmu. V praxi vykonání instrukce trvá urˇcitou dobu, nejrychlejší je pˇriˇrazení, nejpomalejší ˇ násobení/delení. Vyhýbat se mocninám a odmocninám, velmi pomalý výpoˇcet. ˇ ˇ Ruzné ˚ algoritmy se budou lišit dobou behu, a to mnohdy velmi významne. ˇ Jak exaktneˇ urˇcit, rychlost algoritmu a množství spotˇrebované pameti? Dveˇ kritéria: ˇ Casová složitost algoritmu (Time Complexity) Popisuje dobu zpracování vstupních dat D algoritmem A v cˇ ase T, vyjádˇrena cˇ asovou funkcí t T = t (A(D )) ˇ Pamet’ová složitost algoritmu (Space Complexity) ˇ Popisuje “pamet’ovou nároˇcnost algoritmu”. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

14 / 68



13. Posuzování složitosti algoritmu ˇ ˇ ˇ Doba behu algoritmu i pamet’ová nároˇcnost se mení, existují dva pˇrístupy vyjadˇrující ˇ dobu behu: A) V závislosti na velikosti vstupní množiny Složitost lze definovat jako funkcí velikosti vstupu n. ˇ Závislost doby behu na n lze hledat v exaktním tvaru (napˇr. 4n3 − 9n2 + 20n + 27), ˇ eˇ ve formeˇ odhadu (napˇr. O (n3 )). což není cˇ asté, nebo bežn B) V závislosti na vstupní množineˇ dat ˇ ˇ (napˇr. Pro vstupní množinu se stejnou velikostí n se doba behu muže ˚ výrazneˇ menit tˇrídící algoritmus se chová výrazneˇ jinak, pokud má na vstupu náhodnou, cˇ ásteˇcneˇ ˇ ˇ setˇrídenou nebo reverzneˇ setˇrídenou posloupnost dat). Složitost lze posuzovat: dle nejhoršího možného pˇrípadu (Worst Case). ˇ ˇ dle prum ˚ erné doby behu (Average Case). dle nejlepšího možného pˇrípadu (Best Case). ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

15 / 68



14. Worst/Average Case Nejhorší možný pˇrípad (Worst Case): ˇ Pro dané n je výsledkem maximum z dob behu algoritmu pro všechny vstupy velikosti n. TWORST = max(T1 (n), T2 (n), ..., Tn (n)) ˇ Zachycuje nejdelší možnou dobu behu algoritmu (napˇr. nevhodná konfigurace ˇ ˇrádu˚ vyšší než Average Case. vstupních dat), muže ˚ být o nekolik Algoritmus se bude ve všech pˇrípadech chovat “lépe” než pesimistický odhad. V praxi k takové situaci nemusí dojít (nebo jen ve velmi ˇrídkých pˇrípadech), vlastnosti algoritmu mohou být tímto odhadem zkresleny. ˇ ˇ Prum ˚ erná doby behu (Average Case): ˇ ˇ Prum ˚ erná doba výpoˇctu na (bežných) datech velikosti n. ˇ ˇrádu˚ lepší než Worst Case. Muže ˚ být o nekolik ˇ medián. Problematické urˇcení, nejˇcasteji TAVERAGE = ˜t (T1 (n), T2 (n), ..., Tn (n)) Nemusí reprezentovat skuteˇcná data, pouhý matematický konstrukt. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

16 / 68



15. Best Case Nejlepší možný pˇrípad (Best Case) ˇ Pro dané n je výsledkem minimum z dob behu algoritmu pro všechny vstupy velikosti n. TBEST = min(T1 (n), T2 (n), ..., Tn (n)) ˇ Zachycuje nejkratší možnou dobu behu algoritmu (pro ideální konfiguraci vstupních dat). Abychom se abstrahovali od závislosti na hardware, vytváˇríme model tzv. abstraktního ˇ ce, ˇ jehož parametry jsou odvozeny od skuteˇcného poˇcítaˇce. pocíta Pˇríkladem abstraktního matematického poˇcítaˇce muže ˚ být tzv. Turinguv ˚ stroj nebo tzv. RAM (Random Acces Machine). U dobˇre navržených algoritmu˚ rozdíl mezi Best Case a Worst Case malý. ˇ mezi Best Case a Worst Case. Optimalizace algoritmu: snížení rozpetí Pokud Best Case = Worst Case, nelze dále optimalizovat. ˇ Nekteré algoritmy nejsou z duvodu ˚ vysokého Worst Case používány pro cˇ asoveˇ kritické aplikace, napˇr. QuickSort: Average Case TAVER = n log n, ale Worst Case: TWORST = n2 !!!. Nahrazován HeapSortem, kde AC≈WC:TAVER = TWORST = n log n. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

17 / 68



16. Ukázka


18 / 68


Asymptotická složitost

17. Asymptotická složitost ˇ algoritmy je pˇresné (algebraické) vyjádˇrení složitosti algoritmu Pro složitejší matematicky nároˇcné. ˇ Ve vetšin eˇ pˇrípadu˚ postaˇcí nahrazení pˇresného vyjádˇrení cˇ asové složitosti jeho vhodným odhadem. Asymptotická složitost se pro n → ∞ limitneˇ blíží k algebraické hodnoteˇ složitosti. Zásady: 1) V matematických výrazech ignorujeme cˇ leny malých hodnot (ignorujeme aditivní a multiplikativní konstanty). 2) Do testování nezahrnujeme cˇ ásti algoritmu, ˚ které pˇrispívají k analyzovanému výkonu nepatrneˇ (tj. zanedbáme “rychlé” cˇ ásti algoritmu). 5 asymptotických odhadu˚ složitosti: 1) Asymptotický horní odhad cˇ asové složitosti: ostrý O (g (N )), neostrý o(g (N )). 2) Asymptotický dolní odhad cˇ asové složitosti: ostrý Ω(g (N )), neostrý ω(g (N )). 3) Asymptotický oboustranný odhad cˇ asové složitosti: Θ(g (N )).


19 / 68



18. Asymptotický horní odhad složitosti O (g (N )) ˇ Ilustruje nejhorší možný pˇrípad doby behu algoritmu. Pˇredpoklad 1: Zanedbání multiplikativní konstanty c Necht’ f (n) je libovolná funkce a c libovolná konstanta, c > 0. Pak funkce f (n) a c · f (n) jsou oznaˇcovány jako (asymptoticky) stejneˇ rychle rostoucí. Pˇredpoklad 2: Zanedbání aditivní konstanty d Necht’ f (n) je libovolná funkce a d libovolná konstanta, d > 0. Pak funkce f (n) a f (n) + d jsou oznaˇcovány jako (asymptoticky) stejneˇ rychle rostoucí. Dusledky ˚ obou pˇredpokladu: ˚ funkce f (n) a c · f (n) + d jsou stejneˇ rychle rostoucí. Napˇr. funkce 0.001n2 , 0.5n2 − 50, 100n2 + 90, 500000n2 + 100000 patˇrí do stejné tˇrídy (kvadratické funkce). ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

20 / 68



19. Definice O (g (N )) Pro libovolné funkce f , g: N → N platí: f (n) ∈ O (g (n)) ⇔ (∃k ∈ N )(∃n0 ∈ N )(∀n > n0 ): f (n) ≤ k · g (n). Komentáˇr k definici: Z definice plyne, že funkce f (n) roste ˇrádoveˇ nejvýše rychle jako g (n), g (n) je horním odhadem f (n). Z definice nevyplývá, že f (n) ≤ g (n). Jedná se o ˇrádový rust, ˚ zanedbáváme aditivní a multiplikativní konstanty. ˇ Z definice nevyplývá, že ∀n : f (n) ≤ g (n). Existuje nejaké (n0 ∈ N )(n0 > N ) od kterého vztah asymptoticky platí. Z definice vyplývá, že f (n) ∈ O (g (n) tehdy, pokud pro dostateˇcneˇ velkou konstantu k platí f (n) ≤ k · g (n), tj. existuje pouze koneˇcné množství výjimek. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

21 / 68



20. Ukázka asymptotického horního odhadu O (g (N ))

ˇ Pˇríklad: Platí, že 20n2 ∈ O (0.001n2 )?. Rešení: 20n2 ≤ k · 0.001n2 . 20 k ≥ 0.001 = 20000. Platí. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

22 / 68



21. Pravidla pro práci s O-notací

1) O (O (f (n)) → O (f (n)) 2) O (f (n)) + O (f (n)) → O (f (n)) 3) c · O (g (n)) → O (g (n)) 4) O (c · g (n)) → O (g (n)) 5) f (n) − g (n) = O (h(n)) → f (n) = g (n) + O (h(n)) 6) O (f (n)) · O (g (n)) → O (f (n) · g (n)) O (f (n)) f (n) 7) O (g (n) → O ( g (n) ) 8) nk · O (f (n)) → O (f (n) · nk ) 9) O (f (n) + g (n)) → O (max(f (n), g (n)))


23 / 68



22. Pˇríklady Pˇríklad 1, zjednodušení výrazu:

(O (n) + n)(n + O (lg(n)) + O (n) + 1) + O (50) (O (n) + n)(n + O (lg(n)) + O (n)) = O (n2 ) + n2 + O (n lg(n)) + O (n2 ) + O (n2 ) + O (n2 ) + O (n) + n + O (50). O (n2 ) + n2 + O (n lg(n)) + O (n2 ) + O (n2 ) + O (n2 ) + O (n) + n + O (50) = O (n2 ) + n2 . Pˇríklad 2, zjednodušení výrazu: n

n

(10 lg(n) + O (n) + 4n) n lg n + O (n)

(10 lg(n) + O (n) + 4n) 10 lg(n) + O (n) + 4n = n lg n + O (n) lg n + O (1) = 10 + O (

n logn

)+

4n log n

= O (n) + n.

. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

24 / 68



23. Další asymptotické odhady (1/2) Asymptotický horní odhad složitosti O (g (n)) (ostrý): Pro libovolné funkce f , g: N → N platí: f (n) ∈ O (g (n)) ⇔ (∃k ∈ N )(∃n0 ∈ N )(∀n > n0 ): f (n) ≤ k · g (n). Interpretace: f roste nejvýše tak rychle jako g.

Asymptotický dolní odhad složitosti Ω(g (n)) (ostrý): Pro libovolné funkce f , g: N → N platí: f (n) ∈ Ω(g (n)) ⇔ (∃k ∈ N )(∃n0 ∈ N )(∀n > n0 ): k · f (n) ≤ g (n). Interpretace: f roste nejméneˇ tak rychle jako g. Asymptotický horní odhad složitosti o(g (n)) (neostrý): Pro libovolné funkce f , g: N → N platí: f (n) ∈ o(g (n)) ⇔ (∃k ∈ N )(∃n0 ∈ N )(∀n > n0 ): f (n) < k · g (n). Interpretace: f roste pomaleji než g. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

25 / 68



24. Další asymptotické odhady (2/2) Asymptotický dolní odhad složitosti ω(g (n)) (neostrý): Pro libovolné funkce f , g: N → N platí: f (n) ∈ ω(g (n)) ⇔ (∃k ∈ N )(∃n0 ∈ N )(∀n > n0 ): k · f (n) < g (n). Interpretace: f roste rychleji než g. Asymptotický oboustranný (horní i dolní) odhad Θ(g (n)) : Pro libovolné funkce f , g: N → N platí: f (n) ∈ Θ(g (n)) ⇔ (∃k1 ∈ N )(∃k2 ∈ N )(∃n0 ∈ N )(∀n > n0 ): 0 ≤ k1 · g (n) ≤ f (n) ≤ k2 · g (n). Interpretace: Odhad stejné rychlosti rustu, ˚ f roste stejneˇ rychle jako g, tj. složitost algoritmu daného f (n) je asymptoticky stejná jako g (n). ˇ Popisuje oˇcekávanou složitost (tj. prum ˚ erný pˇrípad). Vztahy mezi O-notacemi jsou platné i pro ostatní asymptotické odhady Ω(g (n)), o(g (n)), ω(g (n)). ˇ používány asymptotické odhady O (g (n)), Ω(g (n)), V praxi jsou nejˇcasteji Θ(g (n)). ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

26 / 68



25. Ukázka asymptotického dolního odhadu Ω(g (N ))


27 / 68



26. Ukázka asymptotického oboustranného odhadu Θ(g (N ))


28 / 68



27. Pˇríklady Pˇr. 1: ˇ Který kód probehne rychleji?

int n = 100; int sum = 0; for (i = 0; i < n; i++){ for (j = 0; j < i; j++){ sum += i+j; } } int n = 50;int sum = 0; for (i = 0; i < n; i++){ for (j = 0; j < n; j++){ sum += i+j; } } ˇ cyklus 100x, vnitˇrní 0,1,2,...,99, celkem 50*99=4950x První kód: vnejší ˇ cyklus 50x, vnitˇrní cyklus 50, celkem 50*50=2500. Druhý kód: vnejší Druhý cyklus je rychlejší. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

29 / 68



28. Pˇríklady Pˇr. 2: Problém s dobou ˇrešení k · n2 je na ˇrešen pro n = 10000 na PC. Jak je možné ˇ zvetšit vstup, aby byla úloha na 10x rychlejším poˇcítaˇci vyˇrešena ve stejném cˇ ase? Staré PC: k · 100002 ,nové PC 10 · k · 100002 . √ 10 · k · 100002 = k · n2 ⇒ n = 100000 = 31623. 31623 . ˇ se zvetší ˇ Pomer = 3. 10000 Pˇr. 3: Algoritmus A1 pro ˇrešení úlohy použije 10000n + 40000 operací, algoritmus A2 pro ˇrešení úlohy použije 12n2 + 9 operací. Pro jakou množinu dat je ˇ použít A2 ? výhodnejší 12n2 + 9 ≤ 10000n + 40000 ⇒ 12n2 − 10000n − 39991 < 0 ˇ algoritmus A2 . n1 = −4, n2 = 837. Pro n < 837 je vhodnejší ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

30 / 68



29. Pˇríklady Pˇr. 4: Která tvrzení jsou pravdivá? 1) 20n ∈ O (n) 2) 60n2 − 100n + 249 ∈ O (n2 ) 3) n2 ∈ O (n log n) 4) log n ∈ O (n) 5) n log n ∈ O (n2 ) 6) n log n ∈ Ω(n) 7) n log n ∈ Ω(n2 ) 8) n ∈ Ω(n log n) ˇ Rešení: Ad 1) Patˇrí do stejné skupiny, pravdivé. Ad2) viz 1) Ad 3) n log n roste pomaleji než n2 , nepravdivé. Ad 4) n roste rychleji než log n, pravdivé. Ad 5) n2 roste rychleji než n log n, pravdivé. Ad 6) n roste pomaleji než n log n, pravdivé. Ad 7) n2 roste rychleji než n log n, nepravdivé. Ad 8) n log n roste rychleji než n, nepravdivé. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

31 / 68



30. Pˇríklady odhadu˚ složitosti Algoritmus 1: C1 = 1; pro n > 1 :Cn = Cn−1 + n: procházení n − 1 položek Cn

...

=

Cn−1 + n

=

Cn−2 + (n − 1) + n

=

Cn−3 + (n − 2) + (n − 1) + n

...

...

=

C1 + 2 + ... + (n − 2) + (n − 1) + n =

n(n + 1) 2

Algoritmus 2: C1 = 0; pro n > 1 :Cn = Cn/2 + 1, n = 2N : pulení ˚ vstupu Divide and Conquer. Cn = log2 (N ) Algoritmus 3: C1 = 0; pro n > 2 :Cn = Cn/2 + n, n = 2N : pulení ˚ vstupu + kontrola vstupní položky Cn = n ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

32 / 68



31. Charakteristika algoritmu˚ dle cˇ asové složitosti

Složitost

Vyjádˇrení

Charakteristika

Konstantní

1

ˇ Konstantní doba behu programu. Nezávisí na vstupních datech.

Logaritmická

log(n)

ˇ ˇ ˇ ˇ Doba behu se mírneˇ zvetšuje v závislosti na N. Rešení hledáno opakovaným delení vstupní

Lineární

n

ˇ Doba behu programu roste lineárneˇ s N. Zpracováván každý prvek, napˇr.cyklus.

n log(n)

n log(n)

množiny na menší množiny (hledání v binárním stromu).

ˇ ˇ r lineárne. ˇ Opakované delení ˇ Doba behu roste témeˇ vstupního problému na menší problémy, ˇ které jsou ˇrešeny nezávisle (Divide and Conquer, napˇr. tˇrídení).

Kvadratická

n2

ˇ Doba behu roste kvadraticky, vhodný pro menší množiny dat. Vnoˇrený cyklus.

Kubická

n3

ˇ Doba behu roste s tˇretí mocninou, dvojnásobneˇ vnoˇrený cyklus. V praxi snaha nahrazovat

Exponenciální

2n

ˇ Exponenciální doba behu. Použitelné pro množiny do n=30 Aplikace v kryptografii.

ˇ algoritmus pˇredchozími dvema kategoriemi (Greedy algoritmy)


33 / 68



32. Ukázka cˇ asové složitosti algoritmu˚ Vstupní množina n = 10, 100, 1000 prvku. ˚ Poˇcet operací nutných pro ˇrešení problému. Složitost

n = 10

n = 100

n = 1000

Logaritmická složitost

1

2

3

Lineární složitost

10

100

1000

Kvadratická složitost

100

10000

1.0 · 106

Kubická složitost

1000

1.0 · 106

Bikvadratická složitost

10000

Exponenciální složitost

1024

Faktoriální složitost

3.6 · 10

1.0 · 10

8

1.3 · 1030 6

9.3 · 10

157

1.0 · 109 1.0 · 1012 1.1 · 10301 4.0 · 102567


34 / 68



ˇ 33. Ukázka doby behu algoritmu˚ ˇ Ukázka doby behu algoritmu pro n = 109 . 6 9 12 CPU: Poˇcet operací/s 10s , 10s , 10s . 106 s

CPU

109 s

CPU

1012 s

Složitost

CPU

Logaritmická složitost

hodiny

vteˇriny

okamžiteˇ

Lineární složitost

hodiny

vteˇriny

okamžiteˇ

N log(N )

hodiny

vteˇriny

okamžiteˇ

Kvadratická složitost

nikdy

roky

týdny

Kubická složitost

nikdy

nikdy

ˇ mesíce

Bikvadratická složitost

nikdy

nikdy

roky

Exponenciální složitost

nikdy

nikdy

nikdy

Faktoriální složitost

nikdy

nikdy

nikdy

ˇ Nepostaˇcuje zakoupení výkonnejšího PC. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

35 / 68



ˇ algoritmu˚ dle cˇ asové složitosti 34. Grafické znázornení Vstupní množina: n ∈ (0, 20)


36 / 68


35. Složitost problému vs složitost algoritmu Dle výše uvedených postupu˚ lze urˇcit složitost algoritmu. Jak pˇrejít ke složitosti problému? Problém muže ˚ být ˇrešen ˇradou algoritmu˚ s ruznou ˚ složitostí: O (n3 ), O (n2 ), O (n log n)... Složitost problému odpovídá složitosti efektivního algoritmu, který problém ˇreší. ˇ o vztazích složitosti problému a algoritmu: Vety ˇ 1: Veta ˇ existuje algoritmus rˇešící ho v O (g (n)). Problém P má složitost O (g (n)), jestliže pro nej Interpretace: Pokud se podaˇrí nalézt algoritmus se složitostí O (g (n)), pak má problém i složitost O (g (n)). ˇ 2: Veta ˇ existuje algoritmus rˇešící ho v Ω(g (n)). Problém P má složitost Ω(g (n)), jestliže pro nej Interpretace: Neexistuje algoritmus, který by problém ˇrešil rychleji. Velmi obtížné matematické dukazy!!! ˚ ˇ 3: Veta ˇ existuje algoritmus rˇešící ho v Θ(g (n)). Problém P má složitost Θ(g (n)), jestliže pro nej Interpretace: 1)+2) Hledán algoritmus se složitostí O (g (n)) + dukaz, ˚ že neexistuje rychlejší algoritmus. Tyto algoritmy v konkrétním pˇrípadeˇ nemusejí být známy. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

37 / 68


36. Tˇrída složitosti algoritmu˚ ˇ pro (hierarchickou) kategorizaci problému˚ dle jejich složitosti. Zavádeny ˇ problému˚ do tˇríd téže složitosti umožnuje: ˇ Rozˇclenení ˇ 1) Odhalovat vzájemné podobnosti techto problému. ˚ ˇ 2) Rešení jednoho problému pˇrevodem na jiný problém, tj. pˇrevodu problému s neznámým ˇrešením na podobný problém s již známým ˇrešením. Problém se snažíme zaˇradit do tˇrídy s co nejnižší složitostí. ˇ Vetšina problému˚ má limitní hranici složitosti, po jejímž dosažení již algoritmus nelze urychlit. Definice: Pro funkci f : N → N oznaˇcujeme tˇrídou cˇ asové složitosti τ (f (n)) množinu problému˚ P, které lze rˇešit s cˇ asovou složitostí O (f ). P ∈ τ (n) ⊆ τ (n · log n) ⊆ τ (n2 ) ⊆ τ (n3 ) ⊆ τ (2n ).


38 / 68


37. Tˇrída složitosti PTIME Dveˇ základní tˇrídy složitosti: tˇrída složitosti PTIME (problémy rychle ˇrešitelné), tˇrída složitosti NPTIME (problémy rychle verifikovatelné). Tˇrída složitosti PTIME: Do této tˇrídy patˇrí problémy ˇrešitelné algoritmy s polynomiální složitostí: O (nc ). PTIME =

∞ [

τ (n c )

c =0

ˇ existuje polynomiální algoritmus, nazýváme výpoˇcetneˇ Problémy, pro než snadné, pˇredstavují prakticky zvládnutelné problémy. ˇ používány algoritmy se složitostí: V praxi nejˇcasteji O (n), O (n log(n), O (n2 ), O (n3 ). ˇ problémy tˇrídy PTIME: aritmetické operace, tˇrídení, ˇ Nejznámejší vyhledávání, ˇ nekteré grafové cˇ i geometrické algoritmy. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

39 / 68


38. Nedeterministické polynomiální algoritmy Nedeterministický algoritmus: pˇri opakovaném stejném vstupu dává ruzné ˚ výsledky (ke každé hodnoteˇ vstupu definována více variant výstupu, algoritmus se rozhoduje ˇ ˇ náhodne/pseudonáhodn e). Deterministický algoritmus: pˇri opakovaném stejném vstupu dává stejné výsledky (ke každé hodnoteˇ vstupu definována hodnota výstupu). c

Pro každou množinu vstupních dat existuje 2n potenciálních rˇešení, u každého z nich ˇ ANO/NE, vede opet ˇ k nutné zjistit, zda se jedná o skuteˇcné ˇrešení ⇒odpoved’ rozhodovacímu problému. Definice: Nedeterministický algoritmus A rozhoduje ANO/NE problém P, pokud: ˇ je odpoved’ ˇ “ANO” alesponˇ jeden výpoˇcet Pro problém, na nejž nedeterministického algoritmu A vydá ”ANO”. ˇ je odpoved’ ˇ “NE” každý výpoˇcet nedeterministického Pro problém, na nejž algoritmu A vydá ”NE”. Pˇrevoditelnost lze realizovat v polynomiálním cˇ ase. Je -li vstupní formule splnitelná, alesponˇ jeden opakovaný výpoˇcet tuto skuteˇcnost ˇ rí vydáním “ANO”. oveˇ ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

40 / 68


39. Tˇrída složitosti NPTIME ˇ Casová složitost nedeterministického algoritmu: ˇ Casovou složitostí nedeterministického algoritmu A pˇredstavuje funkce TA : N → N, kde TA (n) je délkou nejdelšího výpoˇctu algoritmu A pro vstup velikosti n TA (n) = max(TA ). Tˇrída NPTIME je tˇrídou všech problému, ˚ které jsou rozhodovány Nedeterministickými polynomiálními algoritmy v polynomiálním cˇ ase O (nc ), c > 0 . Existuje pro neˇ verifikaˇcní algoritmus pracující v polynomiálneˇ omezeném cˇ ase. Použití u tzv. optimalizaˇcních úloh ⇒ obslužné algoritmy: ˇ Jak optimalizovat poˇcet pokladen, aby fronta byla co nemenší a náklady zamestnavatele co nejnižší? Jak optimalizovat dopravní znaˇcení (semafory), aby se co nejvíce zmenšily fronty v ulicích? Vztah mezi PTIME a NPTIME: PTIME ⊆ NPTIME nebo PTIME = NPTIME


41 / 68


40. Pˇrevoditelnost problému Obtížnost problému˚ náležejících tˇrídy NP je stejná. ˇ Nalezení „rychlého“ algoritmu pro ˇrešení kterékoliv z techto úloh, by znamenalo nalezení „rychlého“ algoritmu pro všechny úlohy této tˇrídy (Cook, 1970). Pokud umíme efektivneˇ ˇrešit problém P2 , potom lze problém P1 mužeme ˚ efektivneˇ vyˇrešit tím pˇrevedením na P2 . Pˇrevedení musí být dostateˇcneˇ rychlé (tj. polynomiální). Polynomiální ANO/NE problém P1 je polynomiálneˇ pˇrevoditelný na problém P2 , jestliže existuje polynomiální algoritmus A: který pro libovolný vstup v problému P1 sestrojí vstup A(v ) problému P2 . ˇ na otázku problému P1 pro vstup v je ANO práveˇ tehdy, platí, že odpoved’ ˇ na otázku problému P2 pro vstup A(v ) je ANO. když odpoved’ ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

42 / 68


ˇ 41. NP-težký a NP-úplný problém ˇ NP-težký problém ˇ Problém Q nazýváme NP-težkým, pokud každý problém ve tˇrídeˇ NP lze na problém Q polynomiálneˇ pˇrevést. ˇ Interpretace: Pokud bychom nalezli nejaký polynomiální algoritmus ˇrešící problém Q, pak takový algoritmus musí existovat pro každý problém v NP: PTIME = NPTIME (zatím žádný takový algoritmus nebyl nalezen). ˇ rit v Není znám algoritmus ˇrešící problém v polynomiálním cˇ ase, ˇrešení lze oveˇ polynomiálním cˇ ase. NP-úplný problém ˇ Problém Q nazýváme NP-úplným, pokud je NP-težký, a náleží do tˇrídy NP. ˇ Jedná se o nejtežší úlohy z tˇrídy NP. Do této skupiny patˇrí ˇrada problému, ˚ u kterých není známo exaktní ˇrešení. Není znám algoritmus ˇrešící problém v polynomiálním cˇ ase avšak nelze prokázat, že takové ˇrešení neexistuje. Praktické použití: je cˇ íslo x prvoˇcíslo? Existují p, q 6= 1 tak, aby platilo x = pq? ˇ Není znám algoritmus provádející rozklad x na souˇcin prvoˇcísel (faktorizace)→(RSA). ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

43 / 68


42. Vztah mezi P, NP, NP-úplným problémem


44 / 68


43. Pˇríklady NP-úplných problému˚ V souˇcasné dobeˇ existuje pˇres 1000 NP-úplných problému, ˚ u kterých není znám polynomiální algoritmus. Jsou cˇ asto velmi podobné problémum, ˚ u kterých existuje polynomiální algoritmus. Pˇríklady NP-úplných problému: ˚ TSP problem (problém obchodního cestujícího): navštívení všech vrcholu˚ grafu práveˇ jednou, délka cesty nejkratší. Problém k barev: obarvení vrcholu˚ grafu tak, aby žádné dva sousední ˇ vrcholy nebyly obarveny dvema stejnými barvami. ˇ známého tvaru tak, Problém batohu: Jak naskládat do batohu pˇredmety aby zabíraly co nejméneˇ místa? ˇ Loupežnický problém: rozdelení množiny n dveˇ podmnožiny se stejným souˇctem. ˇ aproximaˇcní algoritmy. NP-úplné problémy lze ˇrešit pˇribližne: ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

45 / 68


44. Techniky návrhu algoritmu˚

ˇ dvema ˇ Návrh algoritmu prováden technikami: Návrh algoritmu “Shora dolu”, ˚ Návrh algoritmu “Zdola nahoru”. ˇ efektivity cˇ asto kombinujeme. V praxi obeˇ techniky z duvod ˚ u˚ vetší ˇ Pˇredstavují analogie postupu˚ používaný pˇri ˇrešení “bežných” problému. ˚


46 / 68


45. Návrh algoritmu “Shora dolu” ˚ Návrh algoritmu “Shora dolu” ˚ ˇ rˇeší složité úkoly v praxi. Odvozen z postupu, jakým cˇ lovek Problém rozkládáme na jednodušší kroky, tzv. dekompozice problému. ˇ Postup smerem od obecného ke konkrétnímu. ˇ ˇ eˇ snadno Postupneˇ tak dospejeme k elementárním krokum, ˚ které již zpravidla umíme pomern vyˇrešit. ˇ Návrh algoritmu metodou shora-dolu˚ je nejpoužívanejším pˇrístupem. Pˇríkladem využití návrhu shora dolu˚ muže ˚ být metoda Divide&Conquer. Návrh algoritmu “Zdola nahoru” Opaˇcný pˇrístup než “Shora dolu”. ˚ ˇ Elementární kroky se snažíme za použití abstrakce sdružovat do složitejších celku˚ ve snaze nalézt ˇrešení zadaného problému. ˇ Postup smerem od konkrétního k obecnému. Používán pˇrevážneˇ pˇri implementaci algoritmu: 1) Nejprve vytváˇríme nejjednodušší komponenty. ˇ komponenty. 2) Jednoduché komponenty spojujeme ve složitejší 3) Jako poslední vytváˇríme zpravidla hlavní program. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

47 / 68


46. Druhy algoritmu˚ ˇ Problémy ˇrešené v bežném životeˇ jsou ruznorodé. ˚ Pˇri návrhu algoritmu neexistuje univerzální technika vedoucí k nalezení ˇrešení. ˇ ˇ V nekterých pˇrípadech požadujeme pˇresné ˇrešení, nekdy postaˇcuje ˇrešení pˇribližné (pˇresné nemusí existovat, viz NP-úplné problémy ). Každá z technik je vhodná pro ˇrešení jiných skupin problému. V závislosti na typu problému je nutné zvolit vhodnou techniku k jeho ˇrešení. Pˇrehled technik návrhu algoritmu: ˚ Metoda hrubé síly (Brute Force Algorithm). Inkrementální algoritmy (Incremental Algorithms). ˇ a panuj (Divide and Conquer). Rozdel Heuristické algoritmy (Heuristic Algorithm). Aproximaˇcní algoritmy Randomizované algoritmy ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

48 / 68


47. Metoda hrubé síly Vyzkoušení všech variant ˇrešení problému, vybráno nejlepší z nich. Poˇcet operací nutných k nalezení ˇrešení roste nepolynomicky (exponenciálneˇ nc , faktoriálneˇ n!). Výhodou je jednoduchost implementace. Lze aplikovat pouze na malé datové soubory, pro rozsáhlé soubory nelze vyzkoušet všechny metody, nalezené ˇrešení nemusí být nejlepší. Postupy založené na hrubé síle bývají nazývány naivními algoritmy, neobsahují žádnou hlubší myšlenku. Využití napˇr. u NP problému. ˚ Lepších výsledku˚ pro tyto problémy dosahují heuristické algoritmy.


49 / 68


48. Inkrementální algoritmy ˇ jednoho prvku ze vstupní množiny resp. z existujícího Postupné pˇridávání resp. výber ˇrešení, po každém takovém kroku je ˇrešení aktualizováno. Druhy inkrementálních algoritmu: ˚ Inkrementální vkládání, Inkrementální konstrukce, ˇ Inkrementální výber. Vlastnosti: ˇ eˇ jednoduché, za pˇredpokladu, že pˇridání / Algoritmy implementaˇcneˇ pomern odebrání jednoho prvku pˇríliš neovlivní výsledné ˇrešení. Vhodné i pro znaˇcneˇ složité problémy. ˇ ˇrešení v závislosti na vstupní množineˇ dat. Snadno lze analyzovat zmeny Lze použít jako on-line algoritmy, po pˇridání vstupu vidíme výsledné ˇrešení nad podmnožinou zpracovaného data setu. ˇ používaných algoritmu˚ ve výpoˇcetní geometrii: konvexní obálky, Jedny z nejˇcasteji Voronoi Diagramy, Delauany triangulace. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

50 / 68


49. Inkrementální vkládání = Incremental Insertion Algoritmus inkrementálního vkládání konstruuje ˇrešení nad množinou M = {mi }ni=1 prvku˚ tak, −1 že nalezne ˇrešení pro množinu M = {mi }ni=1 prvku˚ a poté do této množiny pˇridá prvek mn (tj. updatuje stávající ˇrešení). −1 {mi }ni=1 = {mi }ni=1 ∩ mn

ˇ Celá vstupní množina dat nemusí být k dispozici po dobu behu algoritmu, data mohou být ˇ eˇ (tj. i v dobeˇ behu ˇ získávána prub ˚ ežn algoritmu). Data mohou být vybírána ze vstupní množiny bud’ randomizovaneˇ nebo dle urˇcitých pravidel. ˇ používaných postupu˚ ve výpoˇcetní geometrii. Jeden z nejˇcasteji ˇ udržováno vetšinou ˇ ˇ ˇ ˇrešení V pameti pouze výsledné ˇrešení, pro nekteré situace i prub ˚ ežná (DT). ˇ V takovém pˇrípadeˇ lze snadno analyzovat vliv dat na ˇrešené, tj. provést krok zpet. Pro první kroky ˇrešení (“malá” n) je nutno vstupní množinu doplnit vhodneˇ volenými daty a tato data po zpracování množiny n prvku˚ z ˇrešení dodateˇcneˇ odstranit. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

51 / 68


50. Inkrementální vkládání: konstrukce DT


52 / 68


51. Inkrementální konstrukce = Incremental Construction Algoritmus inkrementálního konstrukce generuje ˇrešení nad podmnožinou ˇ e, ˇ pˇridání dalšího vstupu zpravidla neovlivní dílˇcí ˇrešení. N ⊂ M prub ˚ ežn Data zpracovávána podle požadavku˚ algoritmu, nemohou být pˇridávána na ˇ vstup randomizovane. ˇ V dobeˇ behu algoritmu musí být k dispozici celá vstupní množina dat. ˇ Pro urychlení behu algoritmu je vhodné data pˇredzpracovat, napˇr. vhodneˇ setˇrídit. Algoritmus inkrementální konstrukce cˇ asto používán ve výpoˇcetní geometrii: Delaunay triangulace ˇ Vetšinou pomalejší než inkrementální vkládání. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

53 / 68


52. Inkrementální konstrukce: DT


54 / 68


53. Divide & Conquer ˇ Založena na opakovaném rozdelování problému na menší a jednodušší podproblémy, které jsou svým ˇrešením podobné puvodnímu ˚ problému. Dusledek ˚ návrhu algoritmu technikou “Shora dolu”. ˚ ˇ Hodí se pro dekomponovatelné úlohy, tj. úlohy rozdelitelné na podúlohy stejného nebo podobného typu. ˇ ˇ ˇ Delení provádeno dokud není ˇrešení podproblému triviální (tj. vetšinou pˇrímé). Takové ˇrešení umíme zpravidla nalézt bez složitých výpoˇctu. ˚ Podproblémy ˇrešeny nezávisle na sobeˇ a poté jejich ˇrešení spojena v celek, cˇ ímž získáme ˇrešení puvodního ˚ problému. Odhad složitosti: Θ(n log n) Techniky ˇrešení: Rekurze, iterace. Pˇríklady: tˇrídící algoritmy (Merge Sort, Quick Sort), významné pro úlohy výpoˇcetní geometrie (Convex Hull, Voronoi Diagram, Delaunay Triangulace...), kartografická generalizace (Douglas Peucker Algorithm) ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

55 / 68


54. Ukázka Douglas-Peuckerova algoritmu


56 / 68


55. Heuristické algoritmy Charakteristika heuristiky: Technika ˇrešení problému, ˚ vygenerováno velké množství potenciálních ˇrešení (na rozdíl od metody hrubé síly nikoliv všechny varianty), z nich hledáno nejlepší možné ˇrešení. Vygenerovaná množina nemusí obsahovat nejlepší možné ˇrešení. Heuristické algoritmy využívají heuristiku. Nehledají exaktní ˇrešení problému, ale tzv. pˇrípustné rˇešení, takové ˇrešení není nejlepší možné, ale zárovenˇ není špatné. ˇ ˇ Rešení nemusí být nalezeno v rychlém cˇ ase, nekteré heuristiky pracují ˇ eˇ dlouho. pomern ˇ ˇ rychle, jindy ne (závislost na Špatné urˇcování cˇ asové složitosti, nekdy beží vstupních datech). ˇ ˇrešení, kvalita ˇrešení Zvýšením poˇctu opakování lze dosáhnou pˇresnejšího ˇ zpravidla je zpravidla funkcí poˇctu iterací (odmocnina) nadmerné zvyšování iterací nemá proto smysl. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

57 / 68


56. Techniky heuristiky Základní techniky heuristiky: Iterativní algoritmy: Postupné hledání ˇrešení nad zmenšující se množinou možných ˇrešení, kvalita ˇrešení se v každém dalším kroku zlepšuje. Hladové algoritmy: V každém dílˇcím kroku hledáno optimální ˇrešení. Hledáním lokálního minima chceme nalézt globální minimum. Genetické algoritmy: Založeny na principech evoluˇcní biologie. Do dalšího kroku pˇrežívají pouze perspektivní ˇrešení, která jsou dále zlepšována drobnou modifikací (kˇrížením). Výhody a nevýhoda heuristiky: + Snadná implementace. ˇ + Casto jediné ˇrešení problému, ˚ u nichž neexistuje exaktní ˇrešení (NP problémy). - Obtížné stanovení cˇ asové složitosti, závislost na konfiguraci vstupních dat. ˇ - Rešení nelze dokázat. - V mezních situacích nemusí být nalezené ˇrešení vhodné. - Není zaruˇceno, že takové ˇrešení bude vždy nalezeno. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

58 / 68


57. Kvalita ˇrešení Cílem nalezení pˇrípustného ˇrešení, jak je nalezené ˇrešení dobré ?. Hodnocení kvality nalezeného ˇrešení: odchylka rˇešení mA nalezeného algoritmem A od optimálního rˇešení mopt ˇ ˇ Casto hodnoceno pomerem k , nalezené ˇrešení pˇredstavuje k% optima (napˇr. 90%). k =

mA mopt

Jako optimální ˇrešení muže ˚ být posuzováno dosud nejlepší nalezené ˇrešení. poˇcet kroku˚ vedoucích k nalezení rˇešení Snaha o co nejrychlejší konvergenci algoritmu. Duležitá ˚ volba podmínky ukonˇcující iteraci.


59 / 68


58. Hladový algoritmus = Greedy Algorithm. Hladový algoritmus se snaží z množiny M = {mi } vybrat podmnožinu PN ⊂ M takovou, která má minimální/maximální sumu ohodnocení w (N ) = N ⊂M w (mi ). Hodnotu w (mi ) nazýváme ohodnocením prvku mi , funkci w (N ) oznaˇcujeme jako úˇcelovou funkcí. Hladový algoritmus hledá v každém kroku lokální minimum/maximum úˇcelové funkce ve snaze nalézt globální minimum/maximum úˇcelové funkce. Tímto postupem však globální minimum nemusí být vždy nalezeno. Algoritmus v takovém pˇrípadeˇ vygeneruje pˇrípustné ˇrešení, které není výrazneˇ horší než optimální ˇrešení. Jako pˇrípustné ˇrešené oznaˇcíme libovolnou množinu N ⊂ M, jako optimální ˇrešení množinu N ⊂ M pro kterou platí w (N ) = min resp. w (N ) = max. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

60 / 68


59. Implementace hladového algoritmu Pˇri implementaci Greedy algoritmu˚ používány dynamické datové struktury, zejména prioritní fronta. Vstupní množina M, množina ˇrešení N. Postup: Všechny prvky mi množiny M setˇrídíme do posloupnosti vzestupneˇ resp. sestupneˇ dle hodnot wi v závislosti na tom, zda hledáme minimum/maximum. V každém kroku vybereme prvek mj s nejnižším resp. nejvyšším ohodnocením wj , ˇ ho pˇridáme k existující množineˇ prvku˚ Nj −1 . Pro novou množinu Nj urˇcíme “doˇcasne” w (Nj ). Pokud : w (Nj ) < min resp. w (Nj ) > max: Pˇridáním prvku mj se snížilo resp. zvýšilo ohodnocení množiny Nj −1 . Spoˇcteme nové minimum min = w (Nj ) resp. maximu max = w (Nj ) množiny Nj . Prvek mj pˇridáme do Nj −1 . Pak Nj = Nj −1 ∪ mj . ˇ V opaˇcném pˇrípadneˇ množinu Nj −1 ponecháme beze zmeny: Nj = Nj −1 . Body 2,3 opakujeme pro všechna m. ˇ Po prohledání všech m úˇcelová funkce w (Nj ) splnuje podmínku minimálního resp. maximálního ohodnocení. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

61 / 68


60. Heuristika: TSP, Nearest Neighbor

Ukázka konstrukce nejkratší cesty metodou Nearest Neighbor.


62 / 68


61. Heuristika: TSP, Best Insertion


63 / 68


62. Randomizované algoritmy ˇ do procesu ˇrešení nedeterministický prvek, tj. prvek náhodnosti. Algoritmy zavádejí Cílem zjednodušení implementace algoritmu pˇri zachování Worst Case. ˇ (jestliže není vybrán nevhodný prvek), beží ˇ algoritmus prum ˇ eˇ rychleji. Máme -li štestí ˚ ern ˇ eˇ ˇrešitelné. Tímto postupem lze ˇrešit úlohy, které nemusí být bežn Metody randomizace: ˇ prvku ze vstupních dat Náhodný (nedeterministický) výber Zpracování dat ze vstupní množiny v náhodném poˇradí, v každém okamžiku vybrán náhodný prvek. Náhodné stanovení prahové veliˇciny ˇ náhodného prvku u kterého oˇcekáváme požadované statistické parametry (napˇr. Výber medián). Nahrazuje pˇredzpracování ve formeˇ statistické analýzy dat. Výhody a nevýhody: + snadnost implementace, + vylepšení špatných vlastností algoritmu˚ (špatný Worst Case, dobrý Average Case), - nelze použít pro NP problémy, - v obecných pˇrípadech vede pˇrevod deterministického algoritmu na nedeterministický ke zhoršení výkonu. ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

64 / 68


63. Randomizované algoritmy ˇ Delení randomizovaných algoritmu: ˚ Randomizované inkrementální algoritmy: ˇ prvku ze vstupní množiny, použití napˇr. u Zpravidla náhodný výber triangulací. Randomizované Divide & Conquer algoritmy: ˇ prvku majícího pˇredpokládané statistické parametry. Náhodný výber Napˇr. QuickSort, náhodné stanovení mediánu. Vzorkování: ˇ Pˇred spuštením algoritmu obyˇcejneˇ provedena statistická analýza podmnožiny dat, statistické parametry následneˇ vztaženy na celý vstupní soubor. ˇ vzorku velmi duležitý, Výber ˚ požadavky: reprezentativnost (vzorek reprezentuje rozložení dat v celém souboru), ˇ rená velikost (krátká doba zpracování). pˇrimeˇ ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

65 / 68


64. Randomizované algoritmy Typy vzorkování: Jednoduché vzorkování ˇ Všechny prvky vstupní množiny mají stejnou pravdepodobnost pro zaˇrazení do vzorku. ˇ nemusí být rovnomern ˇ eˇ rozloženy. Položky vybrány náhodne, Systematické vzorkování ˇ každé n-té položky, první položka vybrána náhodne. ˇ Výber Výhodou lepší rozložení položek v souboru. Shlukové vzorkování Ze vstupní množiny vybrán náhodný / pˇredem daný poˇcet vzorku. ˚ Zpracovány všechny prvky každého vybraného vzorku. Použití: Tˇrídící algoritmy, konvexní obálky, triangulace, hledání pruseˇ ˚ cíku. ˚ ˇ Tomáš Bayer | [email protected] (Katedra aplikované geoinformatiky Problémy aa algoritmy kartografie. Pˇrírodovedecká fakulta UK.)

66 / 68


65. Randomizované zpracování bodu: ˚ body vybírány ze shluku˚ v náhodném poˇradí


67 / 68

Volba algoritmu a problém

66. Volba algoritmu Pˇri volbeˇ algoritmu nutno zohlednit: Jaké jsou požadavky na vstupní / výstupní data? Jaká je velikost vstupních / výstupních dat, tj. pro jaká n problém ˇreším? ˇ rit kvalitu pˇribližného ˇrešení? Požaduji exaktní / pˇribližné ˇrešení? Jak jsem schopen oveˇ Je problém ˇrešitelný pro libovolnou konfiguraci vstupních dat? Existují speciální pˇrípady, které musí být ˇrešeny zvlášt’ nebo je lze zanedbat? Lze problém efektivneˇ pˇrevést na jiný problém? Jak má být problém rychle vyˇrešen, tj. on-line, nebo mohu cˇ ekat sekundy, minuty, hodiny cˇ i dny? Jak dlouho má vývoj aplikace trvat, tj. kolik cˇ asu a financí je do ˇrešení problému možno investovat? O jaký typ problému se jedná, nepatˇrí mezi NP problémy? Lze urychlit / vylepšit ˇrešení volbou vhodných datových struktur? Lze urychlit / vylepšit ˇrešení pˇredzpracováním dat?


68 / 68

Problémy a algoritmy

Recommend Documents