Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Ú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ý
Úvodní pˇrednáška
Úvod do programování
1/37
Základní informace Algoritmus Složitost Rekurze
Úvod do programování
2/37
Základní informace Algoritmus Složitost Rekurze
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. ˚
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
3/37
Úvod do programování
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
4/37
Základní informace Algoritmus Složitost Rekurze
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.
Michal Krátký, Jiˇrí Dvorský
c 2005
Základní informace Algoritmus Složitost Rekurze
Podmínky získání zápoˇctu II/III
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
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
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
6/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Obsah kurzu I/II
1
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
7/37
2
3
4
5
6
Úvodní pˇrednáška
Úvod do programování
8/37
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Základní informace Algoritmus Složitost Rekurze
Literatura 1
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
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
Michal Krátký, Jiˇrí Dvorský
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Algoritmus - pˇríklad
Úvod do programování
10/37
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
11/37
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
12/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
c 2005
13/37
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
14/37
Základní informace Algoritmus Složitost Rekurze
Úvod do programování
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
Základní informace Algoritmus Složitost Rekurze
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Složitost
Úvod do programování
16/37
Základní informace Algoritmus Složitost Rekurze
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
Úvod do programování
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.
Michal Krátký, Jiˇrí Dvorský
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Algoritmus - Jednoznaˇcnost
c 2005
Základní informace Algoritmus Složitost Rekurze
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
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
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
18/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
ˇ 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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
ˇ ˇ 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
Michal Krátký, Jiˇrí Dvorský
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Složitost - pˇríklad
Úvod do programování
20/37
Základní informace Algoritmus Složitost Rekurze
Složitost - pˇríklad
ˇ 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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
1s 1000 140 31 10 9
1min 6 · 103 4895 244 39 15
1hod 3, 6 · 106 2, 0 · 105 1897 153 21
Úvod do programování
21/37
Úvodní pˇrednáška
22/37
Základní informace Algoritmus Složitost Rekurze
ˇ 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.
Úvod do programování
Úvod do programování
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 .
Michal Krátký, Jiˇrí Dvorský
Michal Krátký, Jiˇrí Dvorský
Základní informace Algoritmus Složitost Rekurze
Složitost – horní, dolní odhad
c 2005
c 2005
23/37
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
24/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Θ(g(n))
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
Pˇríklad: O(log n), n = 107 , t = 7s.
25/37
c 2005
Michal Krátký, Jiˇrí Dvorský
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
Ω(g(n))
Úvod do programování
26/37
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
27/37
Základní informace Algoritmus Složitost Rekurze
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Pˇríklad
a) b) c) d) e) f)
c 2005
Úvod do programování
28/37
Základní informace Algoritmus Složitost Rekurze
Rekurze
3n n2 n en √ n log n
= = = = = =
c 2005
Michal Krátký, Jiˇrí Dvorský
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
Úvod do programování
29/37
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
30/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvodní pˇrednáška
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
Úvod do programování
31/37
int factorial(int n) { if (n == 0) { return 1; } else { return (n * factorial(n - 1)); } }
c 2005
Základní informace Algoritmus Složitost Rekurze
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Rekurze - volání funkcí
Úvod do programování
32/37
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Úvod do programování
33/37
Základní informace Algoritmus Složitost Rekurze
Úvod do programování
34/37
Základní informace Algoritmus Složitost Rekurze
Fibonacciho funkce – složitost
int fib(int n) { if (n == 0 || n == 1) { return n; } else { return fib(n - 1) + fib(n - 2); } }
Michal Krátký, Jiˇrí Dvorský
Michal Krátký, Jiˇrí Dvorský
Úvodní pˇrednáška
Fibonacciho funkce
c 2005
c 2005
Úvod do programování
Poˇcítání již spoˇcítaných hodnot – exponenciální složitost.
35/37
c 2005
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
36/37
Úvodní pˇrednáška
Základní informace Algoritmus Složitost Rekurze
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
Michal Krátký, Jiˇrí Dvorský
Úvod do programování
37/37