III

Úvodní pˇrednáška

Základní informace Algoritmus Složitost Rekurze



Michal Krátký

Úvod do programování tel.: +420 596 993 239 místnost: A1004 Michal Krátký1 , Jiˇrí Dvorský1

mail: [email protected] web: http://www.cs.vsb.cz/kratky

1 Katedra

informatiky VŠB–Technická univerzita Ostrava

web udp: http://www.cs.vsb.cz/kratky/courses/2004-05/udp/

Úvod do programování, 2004/2005

c 2005

Michal Krátký, Jiˇrí Dvorský


Úvod do programování

1/37



2/37


Podmínky získání zápoˇctu I/III

V rámci kurzu Úvod do programování budou studenti vypracovávat dva semestrální projekty. První projekt bude ˇ rení zda je student schopen implementovat a sloužit pro oveˇ ladit jednoduchý algoritmus. Tento projekt je hodnocen maximálním poˇctem bodu˚ 10. Zadání si studenti mohou vybrat od prvního cviˇcení, termín odevzdání je konec 5. týdne, tedy 27.3.2005 ve 24:00.

Cílem kurzu je seznámit studenty se základy algoritmizace. ˇ Kromeˇ základních pojmu˚ budou prezentovány algoritmy tˇrídení a vyhledávání, lineární i nelineární datové struktury, vyhledávání v textu a komprimace dat. Na cviˇcení budou ˇ rí v studenti algoritmy implementovat a své znalosti si proveˇ rámci semestrálních projektu. ˚




3/37





4/37


Podmínky získání zápoˇctu III/III

Problémy implementované v rámci 2. projektu budou ˇ a od studentu˚ se bude požadovat jejich komplikovanejší implementaˇcní i algoritmické zvládnutí. Projekt bude ˇ umožnovat rozumné vstupy (napˇr. stadartní vstup) a výstupy (napˇr. standartní výstup). Tento projekt je hodnocen maximálním poˇctem bodu˚ 30. Zadání si studenti mohou vybrat od 6. cviˇcení, termín odevzdání je pˇredposlední týden v semestru, tedy 22.5.2005 ve 24:00.


c 2005


Podmínky získání zápoˇctu II/III

c 2005



Cíl kurzu

c 2005

c 2005

Podmínkou pro získání zápoˇctu je odevzdání obou projektu˚ a zisku minimálního poˇctu bodu˚ 21 (ze 40 možných). Pˇrípadný ˇ zápoˇcet bude udelen po ústní konzultaci 2. projektu, která bude probíhat v zápoˇctovém týdnu.

5/37

c 2005



6/37




Obsah kurzu I/II

1


Obsah kurzu II/II

Úvodní pˇrednáška. Pojem algoritmu. Složitost, O(f ) notace. Dopad na efektivitu programu. ˚ Rekurze.

2

Lineární datové struktury. Pole, zásobník, fronta, seznam.

3

Obecná definice tˇrídícího problému. Adresní metody ˇ ˇ ˇ pˇrímým vkládáním, pˇrímým tˇrídení. Tˇrídení. Tˇrídení ˇ výberem. Bubble sort, Quick sort, Heap sort.

1

Binární stromy. Vyhledávání, vkládání, rušení uzlu. ˚ Pruchody ˚ stromem.

2

Vyvážené stromy, Splay stromy. B-stromy.

3

Moderní stromové datové struktury. Indexování prostorových dat.

4

Vyhledávání. Sekvenˇcní, binární vyhledávání.

4

Vyhledávání v textu, pattern matching.

5

Hashování, hashovací funkce, ˇrešení kolizí. Separate chaining, Linear probing.

5

Komprimace dat.

c 2005




7/37

2

3

4

5

6



8/37


Algoritmus

ˇ D. Duráková, J. Dvorský, O. Ochodková: Základy algoritmizace, Ostrava, 2002, sylaby pˇrednášek, http://www.cs.vsb.cz/ochodkova/courses/za/algor_dist.zip. Alfred V. Aho: Data Structures and Algorithms. Addison-Wesley Series in Computer Science and Information, 1983. N. Wirth: Algoritmy a štruktúry údajov, Alfa, Bratislava, 1989. R. Szturc: Java technologie. http://www.cs.vsb.cz/java/index.html. B. Eckel: Thinking in Java, http://www.mindview.net/Books/TIJ. B. Eckel: Thinking in C++, http://www.mindview.net/Books/TICPP. c 2005



Literatura 1

c 2005




Název algoritmus pochází ze zaˇcátku devátého století z Arábie. V letech 800 až 825 napsal arabský matematik Muhammad ibn Músá al Chwárizmí dveˇ knihy, z nichž jedna se v latinském pˇrekladu jmenovala Algoritmi dicit, cˇ esky Tak praví al Chwárizmí. Byla to kniha postupu˚ pro poˇcítání s cˇ ísly.

9/37

c 2005




Algoritmus - pˇríklad


10/37


Algoritmus Algoritmus je pˇredpis, který se skládá z kroku˚ a který zabezpeˇcí, že na základeˇ vstupních dat jsou poskytnuta požadovaná data výstupní. Navíc každý algoritmus musí mít následující vlastnosti:

ˇ jako pˇredpisu pro ˇrešení nejakého ˇ Algoritmu mužeme ˚ rozumet ˇ ˇ množiny celých cˇ ísel. problému. Jako pˇríklad vezmeme tˇrídení Pokud rozebereme ˇrešení takové úlohy do dusledku, ˚ musí ˇ obsahovat tˇri veci:

ˇ Konecnost,

1

hodnoty vstupních dat (množina celých cˇ ísel),

Hromadnost,

2

pˇredpis pro ˇrešení,

ˇ Jednoznacnost,

3

ˇ požadovaný výsledek, tj. výstupní data (setˇrídená cˇ ísla).

Opakovatelnost, Rezultativnost.

c 2005



11/37

c 2005



12/37




Algoritmus - Koneˇcnost

Algoritmus - Hromadnost

Vstupní data nejsou v popisu algoritmu reprezentována konkrétními hodnotami, ale spíše množinami, ze kterých lze ˇ celých cˇ ísel bude vstupem data vybrat (napˇr. pˇri ˇrešení tˇrídení M ⊂ Z). Pˇri popisu algoritmu v programovacím jazyce se to projeví tím, že vstupy do algoritmu jsou oznaˇceny symbolickými jmény.

Požadovaný výsledek musí být poskytnut v rozumném cˇ ase (pokud by výpoˇcet trval na nejrychlejším poˇcítaˇci napˇr. jeden ˇ milion let, težko bychom mohli hovoˇrit o algoritmu ˇrešení, nemluveˇ o výpoˇctu, který by neskonˇcil vubec). ˚ Za rozumný lze ˇ cemu bude. považovat cˇ as, kdy nám výsledek výpoˇctu k neˇ

c 2005




c 2005

13/37



14/37



Opakovatelnost Pˇri použití stejných vstupních údaju˚ musí algoritmus ˇ vždy k témuž výsledku. dospet Rezultativnost Algoritmus vede ke správnému výsledku.

c 2005

15/37




Složitost


16/37


Složitost - pˇríklad

ˇ Mejme databázi 10mil. záznamu˚ o klientech bankovního ústavu. Našim úkolem je napsat algoritmus pro vyhledání ˇ nejakého klienta (napˇr. František Novák). Porovnání jednoho záznamu trvá 1s.

ˇ ˇ rit "kvalitu" algoritmu? Mužeme Mužeme ˚ nejak meˇ ˚ tedy ˇríci, zda daný algoritmus je "lepší" než jiný? ˇ Má smysl vymýšlet "lepší" algoritmy pro ˇrešení nejakého problému?

1

2

c 2005


Algoritmus - Opakovatelnost, Rezultativnost

Každý pˇredpis je složen z kroku, ˚ které na sebe navazují. Každý krok mužeme ˚ charakterizovat jako pˇrechod z jednoho stavu algoritmu do jiného, pˇriˇcemž každý stav je urˇcen zpracovávanými daty. Tím, jak data v jednotlivých stavech algoritmu vypadají, musí být jednoznaˇcneˇ urˇceno, který krok následuje.




Algoritmus - Jednoznaˇcnost

c 2005




17/37

O(n) - provedeme 107 porovnání. Vyhledání záznamu by ˇ trvalo necelé 4 mesíce. O(log n) - provedeme log(107 ) = 7 porovnání. Vyhledání záznamu by tedy trvalo 7s.

c 2005



18/37





ˇ Složitost cˇ asová a pamet’ová

Složitost

ˇ Složitost casová – cˇ asovou složitostí rozumíme funkci, která každé množineˇ vstupních dat pˇriˇrazuje poˇcet operací vykonaných pˇri výpoˇctu podle daného algoritmu.

Pˇri praktické realizaci každé výpoˇcetní metody jsme omezeni ˇ poˇcet registru˚ prostˇredky, které máme k dispozici – cˇ as, pamet’, atd. Duležitým ˚ parametrem každé výpoˇcetní metody je její složitost, kterou mužeme ˚ chápat jako vztah dané metody k daným prostˇredkum. ˚ ˇ ˇ Vezmeme v úvahu tˇrídení. Aˇckoliv je zvolena adekvátní metoda ˇ a metoda je odladena ˇ tˇrídení na vzorových datech, poˇrád je ješteˇ možné, že pro urˇcitá konkrétní data se výpoˇcet protáhne ˇ na hranici únosnosti nebo výpoˇcet ztroskotá na pˇreplnení ˇ poˇcítaˇce. operaˇcní pameti

c 2005




ˇ ˇ Složitost pamet’ová – pamet’ovou složitost definujeme ˇ jako závislost pamet’ových nároku˚ algoritmu na vstupních datech. ˇ Casová složitost výpoˇcetních metod zpravidla vzbuzuje menší respekt než složitost prostorová. Pˇríklad: O(n), n = 107 . Pˇrepsáním cˇ ásti kódu do assembleru jsme snížili cˇ as operace na 0.25 s. Nalezení záznamu tedy ˇ bude trvat necelý mesíc. O(log n), n = 107 , t = 7s. 19/37

c 2005






20/37



ˇ ruzných Pˇredpokládejme nyní, že pet ˚ programu˚ P1 , P2 , P3 , P4 , P5 má cˇ asovou složitost danou funkcemi: t1 (n) = n, t2 (n) = n × log n, t3 (n) = n2 , t4 (n) = n3 , t5 (n) = 2n . Elementární operace vykonávané programy trvají 1ms, rozsah dat zpracovaných programy: program t1 (n) t2 (n) t3 (n) t4 (n) t5 (n) c 2005

složitost n n × log n n2 n3 2n



1s 1000 140 31 10 9

1min 6 · 103 4895 244 39 15

1hod 3, 6 · 106 2, 0 · 105 1897 153 21


21/37


22/37


ˇ Podaˇrí-li se vyjádˇrit cˇ asovou cˇ i pamet’ovou složitost algoritmu jako funkci rozsahu vstupních dat, pak pro hodnocení efektivity algoritmu je duležité ˚ zejména to, jak roste složitost v závislosti na rustu ˚ rozsahu vstupních dat. Jinak ˇreˇceno, zajímá nás limitní chování složitosti tzv. asymptotická složitost.

Definice: ˇ Ríkáme, že problém T má cˇ asovou složitost alesponˇ f , jestliže existuje program P pro T takový, že tP (n) ≥ f (n) pro všechna ˇ n. V tomto pˇrípadeˇ je f dolním odhadem casové složitosti.



Složitostní míry

Definice: ˇ Necht’ f je libovolná funkce v oboru pˇrirozených cˇ ísel. Ríkáme, že problém T má cˇ asovou složitost nejvýše f , jestliže existuje algoritmus A pro T takový, že složitost všech ostatních algoritmu˚ je menší nebo rovna složitosti algoritmu A. Funkce f se nazývá horním odhadem cˇ asové složitosti problému T .




Složitost – horní, dolní odhad

c 2005

c 2005

23/37

c 2005



24/37




Θ(g(n))


O(g(n))

Pro každou funkci g(n), oznaˇcíme zápisem Θ(g(n)) množinu funkcí Θ(g(n)) = {f (n) : takových, že existují kladné konstanty c1 , c2 a n0 tak, že 0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n) pro všechna n ≥ n0 }.

Θ-znaˇcení omezuje asymptoticky funkci zdola a shora. Jestliže budeme chtít omezit funkci jen shora použijeme O(g(n)). Pro každou funkci g(n), oznaˇcíme zápisem O(g(n)) množinu funkcí O(g(n)) = {f (n) : takových, že existují kladné konstanty c a n0 tak, že 0 ≤ f (n) ≤ cg(n) pro všechna n ≥ n0 }.

Funkce f (n) patˇrí do množiny Θ(g(n)) jestliže existují kladné konstanty c1 a c2 takové, že tato funkce nabývá hodnot mezi c1 g(n) a c2 g(n). ˇ Skuteˇcnost, že f (n) splnuje pˇredcházející vlastnost zapisujeme f (n) = Θ(g(n)). Tento zápis znamená f (n) ∈ Θ(g(n)). c 2005




Pˇríklad: O(log n), n = 107 , t = 7s.

25/37

c 2005




Ω(g(n))


26/37


o(g(n)), ω(g(n))

Pro každou funkci g(n), oznaˇcíme zápisem Ω(g(n)) množinu funkcí Ω(g(n)) = {f (n) : takových, že existují kladné konstanty c a n0 tak, že 0 ≤ cg(n) ≤ f (n) pro všechna n ≥ n0 }.

o(g(n)) Pro každou funkci g(n), oznaˇcíme zápisem o(g(n)) množinu funkcí o(g(n)) = {f (n) : takových, že pro každou kladnou konstantu c existuje konstanta n0 taková, že 0 ≤ f (n) < cg(n) pro všechna n ≥ n0 }. ω(g(n)) Pro každou funkci g(n), oznaˇcíme zápisem ω(g(n)) množinu funkcí ω(g(n)) = {f (n) : takových, že pro každou kladnou konstantu c existuje konstanta n0 taková, že 0 ≤ cg(n) < f (n) pro všechna n ≥ n0 }.

c 2005




27/37




Pˇríklad

a) b) c) d) e) f)

c 2005


28/37


Rekurze

3n n2 n en √ n log n

= = = = = =

c 2005


V programování je rekurze pˇredstavována funkcí nebo ˇ funkce nebo procedury obsahuje procedurou, která uvnitˇr tela ˇ volání téže funkce nebo procedury. Ríkáme, že funkce nebo procedura volá samu sebe.

O(n) O(n) O(n2 ) O(n4 ) O(log n) O(n)

Princip rekurze si ukážeme na výpoˇctu faktoriálu cˇ ísla n. Funkce faktoriál je definována 1 pro n = 0 f (n) = f (n ∗ f (n − 1)) pro n ≥ 1


29/37

c 2005



30/37




Rekurze - faktoriál

Rekurze - faktoriál

f (n) = f (n ∗ f (n − 1)) = f (n ∗ f ((n − 1) ∗ f ((n − 2)))) = · · · = = f (n ∗ f ((n − 1) ∗ f ((n − 2) ∗ · · · ∗ f (1 ∗ f (0)) . . . )) což vede ke známému vyjádˇrení n! = n∗(n−1)! = n∗(n−1)(n−2)! = · · · = n∗(n−1)∗(n−2)∗· · ·∗1∗0!

c 2005





31/37

int factorial(int n) { if (n == 0) { return 1; } else { return (n * factorial(n - 1)); } }

c 2005




Rekurze - volání funkcí


32/37


Efektivita rekurze

Pˇredpis Fibonacciho funkce: ⎧ pro n = 0 ⎨ 0 1 pro n = 1 fib(n) = ⎩ fib(n − 1) + fib(n − 2) pro n > 1 ˇ Rada Fibonacciho cˇ ísel vypadá následovneˇ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .

c 2005




33/37



34/37


Fibonacciho funkce – složitost

int fib(int n) { if (n == 0 || n == 1) { return n; } else { return fib(n - 1) + fib(n - 2); } }




Fibonacciho funkce

c 2005

c 2005


Poˇcítání již spoˇcítaných hodnot – exponenciální složitost.

35/37

c 2005



36/37



Fibonacciho funkce – lineární algoritmus int fibi(int n) { int f[3], i; f[0] = 0; f[1] = 1; for (i = 2; i <= n; i++) { f[i % 3] = f[(i - 1) % 3] + f[(i - 2) % 3]; } return f[(i - 1) % 3]; } V pomocném poli jsou uloženy spoˇcítané hodnoty – lineární složitost. c 2005



37/37

III

Recommend Documents