ALGORITMY V této části si přiblížíme jeden ze základních pojmů informatiky, a to pojem algoritmus. Vyhneme se přesné definici, vystačíme s intuitivní definicí pojmu algoritmus tak, že se konstatujeme, že algoritmus je přesný, úplný a jednoznačný návod jak řešit daný problém. Každý algoritmus je tedy spojen s řešením nějakého konkrétního problému. Řešit algoritmicky nějakou úlohu znamená, že zadané vstupní hodnoty (přípustného tvaru) jsou nějakým způsobem zpracovávány a po konečném počtu kroků jsou získány nějaké výstupní hodnoty (v požadovaném tvaru). Základní požadavek na algoritmus je jeho jednoznačnost, což znamená, že ze stejných vstupních hodnot jsou vždy získány stejné výstupy. Postup, který vybere náhodně jednu z číslic {0, 1, 2, 3, 4} není (v přísně exatní definici algoritmu) algoritmem. Pro zjednodušení a praktičnost se často „náhodný výběr” považuje za přijatelný algoritmický krok. Euklidův algoritmus Slovo „algoritmus” je odvozeno od jména perského matematika, který žil v 9. století a který se jmenoval Muhammad al – Khwarizmí. Latinský přepis jeho jména je Algoritmus. Tento matematik se zabýval především pravidly pro operace s čísly. Algoritmické postupy byly známy dlouho před životem tohoto matematika. Jeden ze známých algoritmů, tzv. Euklidův algoritmus pro výpočet nějvětšího společného dělitele dvou přirozených čísel, pochází dokonce ze 4. století před naším letopočtem. Je to nejstarší známý netriviální algoritmus, který je připisován právě řeckému matematikovi Euklidovi (žil 365 – 300 před n.l.). Ukažme si, jak pracuje tento Euklidův postup pro výpočet největšího společného dělitele N D(a, b) dvou přirozených čísel a, b, kde a > b. Předem připomeňme, že jsouli m, n přirozená čísla (tj. m, n ∈ N), pak existují jednoznačně určená přirozená čísla s, r(m, n) ∈ N ∪ {0}, tak, že je m = n · s + r(m, n) a r(m, n) < n. Číslo r(m, n)je zbytek při dělení m n. 0. krok (inicializace algoritmu): položme a0 = a, b0 = b. 1. krok: Určíme zbytek r0 (a0 , b0 ) při dělení ab00 . Jestliže je r0 (a0 , b0 ) = 0, je N D(a, b) = b0 . Je–li r0 (a0 , b0 ) 6= 0, položme a1 = b0 a b1 = r(a0 , b0 ). 2. krok: určíme zbytek r1 (a1 , b1 ) při dělení ab11 . Je–li r1 (a1 , b1 ) = 0, je N D(a, b) = b1 . Je–li r1 (a1 , b1 ) 6= 0, položme a2 = b1 a b2 = r(a1 , b1 ). Takto pokračujeme tak dlouho, až postup skončí, tj. postup skončí v okamžiku, kdy je ri (ai , bi ) = 0. Potom je N D(a, b) = bi . Zmíněný postup si nyní ilustrujme na konkrétním příkladě. Získané hodnoty jsou uvedeny v následující tabulce. i
1
2
3
4
5
ai
23100
357
252
105
42
bi
357
252
105
42
21
ri (ai , bi )
252
105
42
21
0
Vidíme, že výpočet skončil v 5. kroku a je N D(23100, 357) = 21. Při tomto postupu jsme potřebovali pouze schopnost „dělit dvě přirozená čísla se zbytkem”. Kdybychom neuměli dělit, musel by být algoritmus formulován jinak. Krok „urči zbytek r(m, n) při
2
dělení m n dvou přirozených čísel m, n, m > n by bylo možno nahradit například tímto algoritmem: 0. krok (inicializace algoritmu): položme x0 = m. 1. krok: Určíme rozdíl x1 = x0 − n. Jestliže je x1 < n, je r(m, n) = x1 Není–li x1 < n, položme x2 = x1 . 2. krok: Určíme rozdíl x2 = x1 − n. Jestliže je x2 < n, je r(m, n) = x2 Není–li x2 < n, položme x3 = x2 . Takto pokračujeme tak dlouho, až postup skončí, tj. postup skončí v okamžiku, kdy je xi < n. Potom je r(m, n) = xi . Poznamenejme na tomto místě, že původní Euklidův algoritmus byl založen právě na tomto postupu „postupného odečítání menšího čísla od většího”. Hornerovo schema Dalším klasickým algoritmickým postupem je postup pro výpočet hodnot polynomu, který je znám v literatuře jako Hornerovo schema. Mějme polynom n– tého stupně P (x) = a0 · xn + a1 · xn−1 + · · · + an−1 · x + an . Naším úkolem je nyní určit hodnotu tohoto polynomu v daném bodě c, tj. máme určit P (c) = a0 · cn + a1 · cn−1 + · · · + an−1 · c + an . Vstupními údaji pro výpočet P (c) jsou údaje: a0 , a1 , . . . , an−1 , an a c. Hornerovo schema je založeno na postupném výpočtu nových hodnot b0 , b1 , . . . , bn−1 , bn podle předpisu: b0 = a0 , b1 = a1 + b0 · c, . . . , bi = ai + bi−1 · c, . . . bn = an + bn−1 · c. Závěr výpočtu je bn = P (c). Při konkrétním výpočtu si hodnoty zapisujeme do tabulky a0 c
a1
a2
·········
an
b0 · c
b1 · c
·········
bn−1 · c
b1
b2
·········
bn = P (c)
b0
Ukažme si jeden konkrétní příklad. Určeme pomocí Hornerova schematu hodnotu polynomu P (x) = 2 · x4 + 3 · x3 − x2 + x − 7 v bodě x = 2. Mezivýpočty budeme zapisovat přímo do tabulky. 2 2 2
3
−1
1
−7
4
14
26
54
7
13
27
47
Hodnota polynomu P (x) = 2 · x4 + 3 · x3 − x2 + x − 7 v bodě x = 2 je 47. Nyní si ukažme správnost Hornerova schematu. To je poměrně velmi jednoduché. Polynom P (x) = a0 ·xn +a1 ·xn−1 +· · ·+an−1 ·x+an je možno vyjádřit také následujícími způsoby: P (x) = (a0 · x + a1 ) · xn−1 + a2 · xn−2 + · · · + an−1 · x + an P (x) = ((a0 · x + a1 ) · x + a2 ) · xn−2 + · · · + an−1 · x + an P (x) = (((a0 · x + a1 ) · x + a2 ) · x + a3 ) · xn−3 + · · · + an−1 · x + an . .. .
3
P (x) = (· · · ((((a0 · x + a1 ) · x + a2 ) · x + a3 ) · x + a4 ) · x + · · · + an−1 ) · x + an
Hodnota polynomu v bodě x = c je
P (c) = (· · · ((((a0 · c + a1 ) · c + a2 ) · c + a3 ) · c + a4 ) · c + · · · + an−1 ) · c + an P (c) = (· · · (((b1 · c + a2 ) · c + a3 ) · c + a4 ) · c + · · · + an−1 ) · c + an P (c) = (· · · ((b2 · c + a3 ) · c + a4 ) · c + · · · + an−1 ) · c + an P (c) = (· · · (b3 · c + a4 ) · c + · · · + an−1 ) · c + an .. . P (c) = bn−1 · c + an P (c) = bn
Koeficienty b0 , b1 , . . . , bn−1 jsou koeficienty polynomu Q(x), který dostaneme při dělení polynomu P (x) polynomem x − c se zbytkem. Platí totiž, že P (x) = (x − c) · Q(x) + m, kde Q(x) je nějaký polynom stupně n−1. Skutečně, je–li polynom Q(x) zadán předpisem Q(x) = d0 · xn−1 + d1 · xn−2 + · · · + dn−2 · x + dn−1 , pak musí platit rovnosti ( které dostaneme porovnáním koeficientů u jednotlivých mocnin): a0 = d0 , a1 = d1 − c · a0 , a2 = d2 − c · d1 , . . . , an = m − c · dn−1 , nebo–li d0 = a0 , d1 = a1 + c · d0 , d2 = a2 + c · d1 , . . . , dn−1 = an−1 + c · dn−2 , m = an + c · dn−1 . Koeficenty d0 , d1 , . . . , dn−1 jsou stejné jako čísla b0 , b1 , . . . , bn−1 a m = P (c). Hornerovo schema je tedy možno použít pro dělení polynomů polynomem x − c. Další zajímavý důsledkek je to, že hodnota derivace polynomu P (x) je rovna Q(c). Je–li totiž P (x) = (x−c)·Q(x)+m, pak je P 0 (x) = Q(x)+(x−c)·Q0 (x) a následně je P 0 (c) = Q(c). Budeme–li pokračovat ve stejné úvaze dále, dostaneme, že Q(x) = (x − a) · R(x) + s pro nějaký polynom R(x) a nějaké číslo s. Určeme dále druhou derivaci polynomu P (x). Je P 00 (x) = (Q(x) + (x − c) · Q0 (x))0 = Q0 (x) + Q0 (x) + (x − c) · Q00 (x). Odsud dostaneme 00 P 00 (c) = 2 · Q0 (c) = 2 · R(c), tj. R(c) = P 2(c) . Hornerovo schema je možno tedy použít i pro výpočet hodnot derivací všech řádů polynomu P (x) v bodě c. Ukažme si to na příkladě. Máme polynom P (x) = 2x4 + 3x3 − 5x2 + 7x − 9. Pomocí Hornerova schematu určeme P (2), P 0 (2), P 00 (2), P 000 (2) a P (4) (2).
4
2
3
−5
7
−9
4
14
18
50
7
9
25
41 = P (2)
4
22
62
11
31
4
30
2 2 2 2 2 2
15
2
61 =
87 =
P 0 (2) 1!
P 00 (2) 2!
4 2
19 =
P 000 (2) 3!
2 2=
P (4) (2) 4!
Z tabulky vidíme, že je P (2) = 4, P 0 (2) = 1! · 87 = 87, P 00 (2) = 2! · 61 = 122, P 000 (2) = 3! · 19 = 114 a P (4) (2) = 4! · 2 = 48. Požadavky na algoritmus Algoritmus musí být vždy přesný, úplný a jednoznačný návod, jak daný problém řešit v konečně mnoha krocích s použitím prostředků, které jsou k dispozici. Základní požadavky kladené na každý algoritmus jsou: 1. Správnost algoritmu. Nejzákladnějším požadavkem kladeným na každý algoritmus je jeho správnost. U každého algoritmu by měla být dokázána jeho správnost podobně jako v matematice jsou dokazována tvrzení, věty a vzorce. Nestačí nahradit důkaz správnosti tím, že v testovacím provozu dává správné výsledky. 2. Konečnost algoritmu. Každý algoritmus musí skončit v konečném počtu kroků. Tento počet kroků může být libovolně velký (podle rozsahu a hodnot vstupních údajů), ale vždy musí být konečný. 3. Determinovanost (jednoznačnost) algoritmu. Každý krok algoritmu musí být jednoznačně a přesně definován. V každé z možných situací musí být naprosto jednoznačně určeno jak má provádění algoritmu pokračovat. 4. Obecnost algoritmu. Algoritmus má řešit „obecný problém”, ne tedy pouze jednu jedinou úlohu s jedinými možnými vstupy. Algoritmus musí být použitelný pro řešení celé třídy obdobných problémů. 5. Resultativnost algoritmu. Každý algoritmus zpracovává nějaké vstupní údaje, tj. nějaké veličiny které mu jsou předány před započetím jeho provádění, a po jejich zpracování dává výstupní údaje (alespoň jeden), které tvoří odpověď na problém algoritmem řešený. Jako ukázku si ukažme, že tyto vlastnosti má výše uvedený Euklidův algoritmus. Důkaz správnosti algoritmu je založen na evidentním poznatku, že pro každá dvě přirozená čísla
5
m a n, m > n platí: je–li m = n · s + r(m, n) pro nějaké s ∈ N a r(m, n) < n, pak je N D(m, n) = n v případě, že je r(m, n) = 0 a N D(m, n) = N (n, r(m, n)) v případě, že není r(m, n) = 0. V našem algoritmu proto v každém kroku platí: je–li ri (ai , bi ) = 0, je N D(a, b) = bi a je–li ri (ai , bi ) 6= 0, je N D(a, b) = N D(ai , bi ) = N D(bi , r(ai , bi )) = N D(ai+1 , bi+1 ). Euklidův algoritmus musí skončit po konečně mnoha krocích, protože posloupnost čísel bi je klesající a, tj. je b1 > b2 > · · · > bi ≥ 1. V každém kroku algoritmu mohou nastat pouze dvě možnosti a v obou je jasné, jak pokračovat. Je–li ri (ai , bi ) = 0, algoritmus končí a je N D(a, b) = bi . Je–li ri (ai , bi ) 6= 0, pokračuje algoritmus s hodnotami ai+1 = bi a bi+1 = r(ai , bi ). Algoritmus je plně obecný, platný a použitelný pro každou dvojici přirozených čísel m a n, m > n. Výstupem algoritmu je jedno jednoznačně určené přirozené číslo N D(m, n), což je největší společný dělitel přirozených čísel m a n. Složitost algoritmu Pro řešení konkrétních algorotmicky řešitelných úloh je možno nalézt více správných algoritmů, které problém řeší. Tím přichází další problém výběru algoritmu, a to problém určit který z nich je pro danou potřebu vhodný. Proto jednou z velmi důležitýchch vlastností jakéhokoliv algoritmu je jeho složitost. Pod pojmem složitost není myšlena kvalita či způsob jeho formulace, ale doba jeho trvání či jeho náročnost na paměť resp. množství uchovávaných mezivýsledků. Složitost algoritmu je možno posuzovat ze dvou základních hledisek. Jsou to hlediska „jak dlouho algoritmus běží” nebo „jaké množství údajů si algoritmus ponechává pro další použití”. V prvním případě hovoříme o časové složitosti algoritmu, ve druhém případě o prostorové složitosti algoritmu. Složitost algoritmu závisí na velikosti vstupních dat a je proto dobré odhadnout poté co si ověříme jeho správnost. Jistě v konkrétních příkladech také doba trvání algoritmického výpočtu závisí na kvalitě počítačů a kompilátoru, které jsou pro realizaci algoritmu použity. Časovou složitostí algoritmu se proto rozumí počet nutných elementárních operací, které je nutno vykonat pro zpracování n vstupních údajů. Nebude nás zajímat ale skutečný počet těchto operací, ale spíše nějaký jejich odhad. Bude–li například časová složitost algoritmu dána vzorcem T (n) = a · n + b, pak budeme spokojeni s konstatováním, že časová složitost algoritmu je lineární a nebudou nás příliš zajímat velikosti konstant a, b. Otázky týkající se složitosti algoritmu jsou velmi složité, je možno kromě horního odhadu (tj. složitost v nejhorším případě) studovat i složitosti v nějakém normálním (statisticky průměrném) případě. všemi těmito otázkami se nebudeme zabývat, v dalším vystačíme s horním odhadem časové složitosti algoritmu. Definice. Nechť g(n) je nějaká funkce proměnné n ∈ N. Řekneme, že funkce T (n) je složitosti O(g(n)), což budeme zapisovat vztahem T (n) ∈ O(g(n)), jestliže existuje přirozené číslo n0 a reálné číslo k tak, že pro každé n ∈ N, n ≥ n0 je T (n) ≤ k · g(n). Například je–li T (n) = a·n+b, pak je T (n) = a·n+b ≤ (a+|b|)·n. Je tedy T (n) ∈ O(n). Je–li T (n) = a · n2 + b · n + c, pak je obdobně T (n) = a · n2 + b · n + c ≤ (|a| + |b| + |c|) · n2 a platí tedy: T (n) ∈ O(n2 ). Zcela anologicky lze ukázat, že pro každou funkci T (n), která je dána předpisem T (n) = a0 · nk + a1 · nk−1 + · · · + ak−1 · n + ak pro nějaké ai ∈ R, je T (n) = O(nk ). Poznámka. Složitost funkce, tak jak jsme ji definovali má v sobě jistou volnost. Protože je n2 ≤ n3 ≤ n4 ≤ · · · , je každá funkce, která je složitosti O(n2 ) je také složitosti O(n3 ), O(n4 ) atd. Proto se zavádí pro hodnocení složitosti algoritmů přesnější symbol, a to symbol θ.
6
Definice. Nechť g(n) je nějaká funkce proměnné n ∈ N. Řekneme, že funkce T (n) je složitosti θ(g(n)), což budeme zapisovat T (n) ∈ θ(g(n)), jestliže je T (n) ∈ O(g(n)) a zároveň je g(n) ∈ O(T (n)). Je–li T (n) ∈ θ(g(n)), říkáme, že funkce g(n) a T (n) si jsou asymptoticky rovny. Funkce T (n) = n2 + 7n + 6 je, jak již víme, složitosti O(n2 ) . Protože též platí, že n ≤ n2 + 7n + 6, je n2 ∈ O(T (n)), a tedy funkce T (n) a n2 si jsou asymptonicky rovny. Platí tedy, že je T (n) ∈ θ(n2 ) což je mnohem silnější informace než informace T (n) ∈ O(n2 ). Ukažte, že není T (n) ∈ θ(n3 ). Přesto, že symbol θ vyjadřuje složitost algoritmu lépe, my v dalším vystačíme s horním odhadem pomocí symbolu O. Budeme se ale snažit, aby tento odhad byl co nejlepší. I když je možno uměle konstruovat algoritmy s různými časovými složitostmi, my v dalším většinou vystačíme s následujícími časovými složitostmi algoritmů: O(log n), O(n), O(n · log n), O(n2 ), O(n2 · log n), O(n3 ), O(2n ) a O(n!). Algoritmům, které mají složitost O(n), O(n2 ) a O(n3 ), říkáme postupně lineární, kvadratické a kubické algoritmy. Souhrně algoritmy, které mají složitost O(nk ), nazýváme polynomiální algoritmy. Algoritmy, které mají složitost O(2n ) se nazývají exponenciální algoritmy. Mezi polynomiální algoritmy se počítají též algoritmy se složitosí O(n · log n), O(n2 · log n) apod., a to proto, že je log n < n. Uvvďme si některé základní vlastnosti funkce O. Jsou to vlastnosti: 2
k · O(f (n) = O(f (n)) O(f (n)) + O(f (n)) = O(f (n)) O(O(f (n))) = O(f (n)) O(f (n)) · O(g(n)) = O(f (n) · g(n)) O(f (n) · g(n)) = f (n) · O(g(n)) Všimněme si, že hovoříme–li o tom, že je nějaký algoritmus „logaritmické” složitosti, x není nutno uvádět základ logaritmu. Platí totiž log a x = ln ln a . Odsud lze ihned odvodit známý převodní vztah (platný pro libovolné základy logaritmů a, b ∈ (0, 1) ∪ (1, ∞))
log a x =
ln b · log b x. ln a
Podle prvního pravidla jsou si logaritmické funkce f (n) = log a (n) a g(n) = log b (n) asymptoticky rovny. Poznámka. I když se zdá, že otázky složitosti počítačů jsou v dnešní době zanedbatelné z důvodu existence vysoce rychlých a kapacitně bohatých výpočetních prostředků, není to zcela pravda. Jisté je, že v případě malého počtu zpracovávaných dat je celkem jedno, jakým algoritmem jsou zpracovávána. Nemusí to být pravda, a to zejména při používání algoritmů nepolynomiální složitosti. V následující tabulce jsou uvedeny časy potřebné ke zpracování n vstupních dat při použití algoritmu složitosti T (n) a to za předpokladu, že je za 1 sec. zpracován 1 milion operací.
7
T (n)
10
20
30
40
50
n
10 µs
20 µs
30 µs
40 µs
50 µs
n2
0, 1 ms
0, 4 ms
0, 9 ms
1, 6 ms
2, 5 ms
n3
1 ms
8 ms
27 ms
64 ms
125 ms
2n
1 ms
1s
17, 9 min
12, 7 dne
35, 7 let
n!
3, 6 s
77 tis. let
8, 4 · 1018 let
2, 5 · 1034 let
9, 6 · 1050 let
Jako příklad si uveďme následující problém. Víme, že heslo pro vstup do nějaké aplikace se skládá přesně z 10 číslic 0, 1, 2, 3, 4, 5, 6, 7, 8 a 9 a desíti písmen A,B,C,D,E,F,G,H, I a J a žádný ze symbolů se neopakuje. Máme tedy přesně 20! možností pro toto heslo. Pokud za 1 sec. vyzkoušíme 1 milion hesel, máme zaručenu úspěšnost proniknutí do aplikace až po cca 77 000 letech. Jiným příkladem by mohl být algoritmus výpočtu determinantu čtvercové matice založený na definici determinantu. Připomeňme si tuto definici a definice dalších potřebných pojmů. Permutací množiny {1, 2, . . . , n} rozumíme každé prosté zobrazení této množiny na sebe. Takovýchto zobrazení existuje přesně n! (n faktoriál). Je-li π permutace množiny {1, 2, . . . , n}, pak její obraz lze vyjádřit posloupností π(1), π(2), . . . , π(n). Pro vyjádření permutace se také často používá následující zápis µ ¶ 1 2 ... n π= . π(1) π(2) . . . π(n) Množinu všech permutací množiny {1, 2, . . . , n} označíme symbolem Πn . Inverzí v permutaci π rozumíme každou dvojici i, j přirozených čísel z {1, 2 . . . , n} takovou, že platí: i < j a π(i) > π(j). Permutaci nazýváme lichou nebo sudou podle toho, zda její počet inverzí je číslo liché nebo sudé. Znaménkem permutace π budeme rozumět číslo zn π = (−1)k , kde k je počet inverzí v permutaci π. Příkladem sudé permutace je třeba permutace identická (k = 0) nebo první z níže uvedených permutací (k = 10); příkladem liché permutace je druhá z uvedených permutací (k = 1). µ ¶ µ ¶ 1 2 3 4 5 1 2 3 4 5 π1 = , π2 = . 5 4 3 2 1 1 2 3 5 4 Nyní již můžeme přistoupit k definici determinantu čtvercové matice. Definice. Determinantem čtvercové matice a11 a12 a21 a22 A= .. ... . an1 řádu n rozumíme reálné číslo det A =
X π∈Πn
an2
... ... ...
a1n a2n .. . ann
zn π · a1π(1) · a2π(2) · · · anπ(n) .
8
Algoritmus výpočtu determinantu čtvercové matice řádu n založený na definici by vyžadoval určit všechny permutace množiny {1, 2, . . . , n}, určit jejich znaménka, vypočítat součiny zn π · a1π(1) · a2π(2) · · · anπ(n) a všechny takto získané sčítance sečíst. Protože se jedná o n! sčítanců, trval by výpočet až nereálně dlouho. Existují i jednoduše formulované algoritmy jejichž složitost nelze v některých případech omezit žádným horním odhadem závislým na počtu vstupních veličin. Jako příklad si vezměme Euklidův algoritmus v modifikaci „postupného odečítání čísel”. Tak k určení zbytku při dělení čísla 1025 číslem 2 budeme potřebovat 512 kroků. Samozřejmě lze ke každému přirozenému číslu n číslo (např. 2n + 3) které bude vyžadovat při určování zbytku při dělení číslem 2 (metodou odečítání čísla 2) více než n kroků. Zejména v takovýchto případech je velmi důležité jakým algoritmem úlohu řešíme a každé zjednodušení je velice cenné. Mnohá zjednodušení využívají (a musí využívat) i hluboké teoretické výsledky z disciplín, kterých se algoritmus týká. Například při výpočtu determinantů čtvercových matic lze využít následující větu týkající se „úprav s řádky matice”. Věta. Nechť A je čtvercová matice. Platí: 1) jestliže matice B vznikne z matice A záměnou přesně dvou řádků matice A, pak det B = −det A; 2) jestliže matice B vznikne z matice A vynásobením některého řádku matice A číslem r, pak det B = r · det A; 3) jestliže matice B vznikne z matice A přičtením r–násobku nějakého řádku matice A k jinému řádku matice A, pak det B = det A; 4) má-li matice A pod hlavní diagonálou samé nuly, pak det A je roven součinu prvků na diagonále; 5) jestliže matice A obsahuje řádek nebo sloupec složený ze samých nul, je det A = 0. Výběrové a třídící algoritmy Ukažme si, na několika příkladech jednoduchých algoritmů, jak určovat složitost algoritmů. Ukážeme si to na příkladě výběrového algoritmu a na příkladech tzv. třídících algoritmů. Výběrové a třídící algoritmy patří mezi velmi aplikovatelné algoritmy. V podstatě jde o velmi přirozený požadavek z daných objektů vybrat objekt s nějakou extrémní hodnotou resp. danou množinu objektů uspořádat vzestupně (resp. sestupně) podle nějakého parametru vzhledem k nějakému úplnému uspořádání. Například je potřeba vybrat nebo setřídit výrobky podle ceny, váhy, data výroby apod. Jestliže abecedně (nebo jinak) seřazeným výrobkům přiřadíme jejich ceny, dostaneme „seznam” jejich cen, což nemusí být množina protože ceny různých výrobků mohou být stejné. Naším úkolem je tento soubor dat přetvořit v „uspořádaný seznam”. V seznamech záleží na pořadí jednotlivých prvků (na rozdíl od množin, které jsou zadány výčtem prvků) a připouští se i opakovaný výskyt stejné hodnoty (což se nepřipouští v množinovém výčtu). Pro jednoduchost bedeme dále předpokládat, že máme seznam n přirozených čísel A = {a1 , a2 , . . . , an }. Naším úkolem je tento seznam přetvořit v uspořádaný seznam B = {b1 , b2 , . . . , bn }, kde pro každé i je bi ∈ A a bi ≤ bi+1 . Výběr nejmenšího prvku Řešit algoritmicky úlohu „vybrat” z daného seznamu A = {a1 , a2 , . . . , an } prvek s nejmenší (nebo největší) hodnotou je velice jednoduché. Je možno postupovat například podle tohoto návodu (algoritmu). Výsledek algorimu bude prvek b jednoprvkové množiny Bn = {b}, kterou budeme tvořit v každém kroku následujícím způsobem:
9
1. krok: položíme b1 = a1 , je tedy B1 = {a1 }; 2. krok: porovnáme prvky a2 a b. Je–li a2 ≥ b, ponecháme množinu B1 = {b1 } beze změny, bude B2 = B1 . Je–li ale a2 < b, nahradíme prvek b1 prvkem a2 . Bude tedy B2 = {a2 }; i – tý krok: v tomto kroku porovnáme prvky ai a bi−1 . Je–li ai ≥ bi−1 , ponecháme množinu Bi−1 = {bi−1 } beze změny, bude Bi = {bi−1 . Je–li ale ai < bi−1 , nahradíme prvek bi−1 prvkem ai . Bude tedy Bi = {ai }; n – tý krok: v tomto kroku porovnáme prvky an a bn−1 . Je–li an ≥ bn−1 , ponecháme množinu Bn−1 = {bn−1 } beze změny, bude Bn = {bn−1 . Je–li ale an < b, nahradíme prvek bn−1 prvkem an . Bude tedy Bn = {an }. Toto je poslední krok algoritmu a jeho výstupem je prvek bn ∈ Bn . Poznámka. Samozřejmě, že není nutno „indexovat” množinu B = {b}, to děláme pro větší srozumitelnost. Ukažme si tuto metodu na jednom příkladě. Mějme dánu množinu A = {8, 5, 4, 2, 7, 5, 1, 9}. V následující tabulce je uvedeno, jak se mění výstupní hodnota po provedení i – tého kroku. krok A B
1 8 8
2 5 5
3 4 4
4 2 2
5 7 2
6 5 2
7 1 1
8 9 1
Hledaná nejmenší hodnota je 1. Protože pro provedení algoritmu bylo potřeba n kroků (při n vstupních hodnotách), je časová složitost algoritmu O(n), přesněji θ(n). Třídění přímým vkládáním Nejjednodušší metoda třídění kterou běžně používáme je tzv. metoda přímého vkládání. Metoda spočívá v tom, že vytváříme uspořádaný seznam objektů tak, že postupně zařazujeme objekty mezi již uspořádané tak, aby byla zachováno uspořádání. Algoritmus je možno formulovat takto: (inicializace algoritmu) máme A0 = {a1 , a2 , . . . , an } a B = ∅. 1. krok: první číslo seznamu A0 = {a1 , a2 , . . . , an } vyjmeme a zařadíme na první místo vytvářeného seznamu B1 , tj. určíme, že je b1 = a1 . Po provedení tohoto kroku budeme mít dva seznamy, a to A1 = {a2 , . . . , an } a B1 = {b1 }. 2. krok: první číslo seznamu A1 = {a2 , . . . , an } vyjmeme a porovnáme ho s číslem b1 . Je–li a2 ≤ b1 , dáme ho na první místo seznamu B a dosavadní první prvek seznamu B1 dáme na místo druhé. Bude tedy B2 = {a2 , a1 }. Je–li a2 > b1 , zařadíme prvek a2 na druhé místo seznamu B2 . V tomto případě bude tedy B2 = {a1 , a2 }. Po provedení tohoto kroku bude A2 = {a3 , . . . , an } a B2 = {b1 , b2 }. i – tý krok: první číslo seznamu Ai−1 = {ai , . . . , an } vyjmeme a porovnáme ho postupně (od prvního) se všemi čísly seznamu Bi−1 . Je–li j první (tj. nejmenší) číslo takové, že je ai ≤ bj , dáme ho na j – té místo seznamu B a prvky {bj , bj+1 , . . . } seznamu B posuneme o jedno místo dozadu. Bude tedy Bi = {b1 . . . , bj−1 , ai , bj , . . . }. Je–li prvek ai větší než všechny prvky seznamu B, zařadíme prvek ai na poslední místo seznamu B. V tomto případě bude tedy B = {b1 , b2 , . . . , bi , ai }. Po provedení tohoto kroku bude Ai = {ai+1 , . . . , an } a B = {b1 , b2 , . . . bi }.
10
n – tý krok (konec algoritmu): algoritmus končí po n krocích, A = ∅ a Bn je hledaný uspořádaný seznam. Pokud za elementární úkon algoritmu vezmeme porovnávání dvou čísel, musíme provést těchto elementárních úkonů (v nejhorším případě) celkem N = 0 + 1 + 2 + · · · + n − 1 = n2 · (0 + n − 1) = 12 · n2 − 12 · n. Popsaný algoritmus je časové složitosti O(n2 ), přesněji θ(n2 ). Ukažme si ještě algoritmus „třídění přímým vkládáním” na konkrétním příkladě. Jako výchozí seznam mějme seznam přirozených čísel {3, 5, 7, 1, 2, 8, 12, 16, 3, 2, 9}. V následující tabulce jsou v řádcích uvedeny výsledky algoritmu po jednotlivých krocích. A0 A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11
3, 5, 7, 1, 2, 8, 12, 16, 3, 2, 9 5, 7, 1, 2, 8, 12, 16, 3, 2, 9 7, 1, 2, 8, 12, 16, 3, 2, 9 1, 2, 8, 12, 16, 3, 2, 9 2, 8, 12, 16, 3, 2, 9 8, 12, 16, 3, 2, 9 12, 16, 3, 2, 9 16, 3, 2, 9 3, 2, 9 2, 9 9 ∅
B0 B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11
∅ 3 3, 5 3, 5, 7 1, 3, 5, 7 1, 2, 3, 5, 7 1, 2, 3, 5, 7, 8 1, 2, 3, 5, 7, 8, 12 1, 2, 3, 5, 7, 8, 12, 16 1, 2, 3, 3, 5, 7, 8, 12, 16 1, 2, 2, 3, 3, 5, 7, 8, 12, 16 1, 2, 2, 3, 3, 5, 7, 8, 9, 12, 16
Poznámka. při určování složitosti algoritmu není nutno elementární kroky počítat zcela přesně, někdy je to velmi obtížné. V našem případě to bylo jednoduché, mohli jsme použít vzorec pro výpočet součtu prních n členů aritmetické posloupnosti. Obvykle lze vystačit se zjednodušenými úvahami typu: je nutno provést nejvýše n kroků, při každém kroku je nutno provést maximálně n elementárních úkonů a tedy k výpočtu je nutno provést maximálně n · n elementárních úkonů. Algoritmus je tedy časové složitosti maximálně O(n2 ). Při takto zjednodušených úvahách ovšem hrozí nebezpečí, že neodhadneme dobře „minimální složitost”. Při určování složitosti funkcí T (n) můžeme využít i jiné prostředky matematiky. Ukažme si jeden příklad. Mějme funkci T (n) = 12 +22 +32 +· · ·+n2 . Protože je evidentně 12 ≤ n2 , 22 ≤ n2 , 32 ≤ n2 , . . . , n2 ≤ n2 , je také T (n) = 12 +22 +32 +· · ·+n2 ≤ n·n2 = n3 . Proto platí: T 9n) ∈ O(n3 ). Zůstává ale otázka, zda toto zařazení funkce T (n) do třídy O(n3 ) nelze zlepšit, tj. zda také platí T (n) ∈ θ(n3 ). Provedeme tuto úvahu: pro x ∈ h0, 1i R1 R1 je 0 ≤ x ≤ 1, a proto je následně x2 dx ≤ 12 dx = 12 . Obdobně je pro x ∈ h1, 2i je 1 ≤ x ≤ 2, a tedy i Rn n−1
Rn
2
x dx ≤
R2
x2 dx ≤
1 2
R2
0
0
22 dx = 22 ; obdobně je
1
R3 2
x2 dx ≤
R3
32 dx = 32 , až
2
2
n dx = 3 . Sečtením všech nerovnic dostaneme nerovnici
n−1
Rn 2 x dx ≤ 12 + 22 + 32 + · · · + n2 = T (n). h 0 3 in Rn 2 3 3 = n3 , dostáváme, že je n3 ≤ T (n). To dává, spolu s již Protože je x dx = x3 0
0 3
známým vztahem T (n) ≤ n , platnost vztahu T (n) ∈ θ(n3 ).
11
Třídění sléváním Základní myšlenka algoritmu, který je nazýván třídění sléváním (nebo slučováním – anglicky mergesort) je velmi jednoduchá. Je založena na tom, že 1. jednoprvkový seznam je uspořádaný; 2. jsou–li A = {a1 , . . . , ak ) a B = {b1 , . . . , bk ) uspořádané seznamy, pak lze snadno vytvořit uspořádaný seznam A ∪ B tak, že neustále porovnáváme první dva prvky seznamů A a B a menší z nich (v případě rovnosti třeba ten z A) přidáme na poslední místo vytvářeného seznamu A ∪ B. Máme–li tady za úkol setřídit prvky daného seznamu M , pak seznam rozdělíme na jednoprvkové seznamy. Z jednoprvkových seznamů vytvoříme uspořádané dvouprvkové seznamy (např. tak, že spojujeme první dva seznamy, druhé dva seznamy atd.). Je–li počet prvků seznamu M lichý, ponecháme poslední seznam jednoprvkový. Dále z dvouprvkových seznamů vytváříme čtyřprvkové uspořádané seznamy, poslední seznam může mít i méně prvků. Takto postupujeme až dostaneme požadovaný uspořádaný seznam. Ukažme si postup na příkladě seznamu M = {6, 5, 8, 2, 4, 1, 3, 7}. V prvním řádku tabulky je seznam, ve druhém řádku je seznam rozdělen na jednoprvkové (již nerozdělitelné) části. Ve třetím řádku jsou uspořádané dvouprvkové seznamy, v čtvrtém řádku jsou čtyřprkové seznamy a v pátém řádku jsou spojeny dva čtyřprkové seznamy; tím je získán požadovaný uspořádaný seznam, který je uveden v posledním řádku. seznam jednoprvkové seznamy dvouprvkové uspořádané seznamy čtyřprvkové uspořádané seznamy osmiprvkový uspořádaný seznam uspořádaný seznam
6 5 2 1
{6, 5 6 5 2 {1,
5, 8, 2, 8 2 2 8 6 8 3 4 2, 3, 4,
4, 1, 4 1 1 5 5, 6,
3, 7} 1 3 4 3 3 4 6 7 7, 8}
7 7 7 8
Pro úplnost si ukažme, jak vzniká osmiprvkový uspořádaný seznam C (předposlední řádek) sléváním dvou čtyřprvkových uspořádaných seznamů A a B, které jsou v předcházejícím řádku. A0 A1 A2 A3 A4 A5 A6 A7 A7
2, 5, 6, 8 2, 5, 6, 8 5, 6, 8 5, 6, 8 5, 6, 8 6, 8 8 8
B0 B1 B2 B3 B4 B5 B6 B7 B7
1, 3, 4, 7 3, 4, 7 3, 4, 7 4, 7 7 7 7
C0 C1 C2 C3 C4 C5 C6 C7 C7
1 1, 2 1, 2, 3 1, 2, 3, 4 1, 2, 3, 4, 5 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6, 7 1, 2, 3, 4, 5, 6, 7, 8
A jaká je složitost uvedeného algoritmu? Nechť má pro jednoduchost výchozí seznam M přesně n = 2m prvků. Ke spojení dvou k prvkových seznamů je třeba provést přesně 2 · k kroků. Celkem je tedy potřeby provést při spojování seznamů 2m−1 · 21 (je 2m−1 dvojic jednoprvkových seznamů) plus 2m−2 · 22 (je 2m−2 dvojic dvouprvkových seznamů) atd. až plus 2 · 2m−1 (jsou dva 2m−1 prvkové seznamy) kroků. Pro spojování seznamů je tedy potřeba (m − 1) · 2m kroků. Celkem při algoritmu je potřeba provést maximálně
12
m + 1 + (m − 1)2m kroků. Pro počet potřebných kroků T (n) je T (n) ≤ m · 2m . Protože je n = 2m , je m = log 2 n a tedy pro časová náročnost algoritmu je T (n) ∈ O(n · log 2 n). Ukažte, že je i T (n) ∈ θ(n · log 2 n). Třídění haldou Velmi populárnímm algoritmem pro vytváření uspořádaného seznamu čísel z daného seznamu je tzv. metoda třídění haldou. Nejprve si řekněmě co se rozumí pod pojmem halda (anglicky heap). Můžeme si představit, že je to uspořádaná množina s největším prvkem a každý prvek má nějakou číselnou hodnotu. Prvky množiny jsou situovány v k hladinách a splňují následující podmínky: 1. v první hladině je jediný prvek; 2. v i – té hladině, 1 ≤ k, je 2i−1 prvků; 3. v k – té hladině je maximálně 2k−1 prvků a prvky v hladině jsou umístěny co nejvíce „vlevo”; 4. každý prvek v i – té hladině, 2 ≤ k je pokrýván právě jedním prvkem z hladiny i − 1, a to tak, že pokud prvek patří mezi první dva prvky z i – té hladiny, je pokrývány prvním prvkem hladiny i − 1, pokud prvek patří mezi druhé dva prvky z i – té hladiny je pokrývány druhým prvkem hladiny i − 1 atd. 5. je–li prvek a pokrýván prvkem b, pak hodnota prvku a je větší nebo rovna hodnotě prvku b. Každý prvek haldy, která má k hladin, je možno jednoznačně charakterizovat dvojicí čísel (h, p) (1 ≤ h ≤ k, 1 ≤ p ≤ 2k−1 ) která uvádí, že prvek leží v h – té hladině na p – tém místě. Každý prvek z h – té hladiny (h > 1)je pokrýván právě jedním prvkem z hladiny h−1 (prvkem (h−1, j), jedná–li se o prvek (h, 2j−1) nebo (h, 2j) a každý prvek (i, j) z i – té hladiny pokrývá nejvýše dva prvky, a to prvky (i+1, 2j −1) (i+1, 2j) (poslední hladina nemusí být obsazena plně). Každý prvek haldy má tedy přesně jednoho „předchůdce” (nebo též „otce”) a nejvýše dva „následníky” (nebo též „syny”). Hodnota „následníka” je větší nebo rovna hodnotě „předchůdce”. Prvek v první hladině se nazývá „kořen” haldy. Plně obsazená halda, která má k hladin, má přesně 1 + 21 + 22 + · · · + 2k−1 = 2k − 1 prvků. Na následujícím obrázku jsou zobrazeny příklady hald. 2 2
2
2
5
5
9
8
10
5
9
9 7 3
7
8
7
11 40
20
8
30
10
15
11
18
ˇ´iklady hald Obr. 1: Pr Jak je možno z daného seznamu vytvářet haldu? Stačí dodržovat následující dvě pravidla pro přidávání nových prvků do haldy. 1. vytvoříme nový uzel tak, že ho přidáme do poslední hladiny, a to „co nejvíce vlevo”; 2. kontrolujeme, zda je splněno pravidlo „hodnota následníka je větší nebo rovna hodnotě předchůdce”. Pokud tomu tak není, vyměníme mezi sebou předchůdce a následníka.
13
V této kontrole pokračuje tak dlouho, až bude mít nově vkládaný prvek hodnotu větší nebo rovnu hodnotě předchůdce nebo až se dostane do kořene haldy. Uvědomme si, že tímto postupen vždy vznikne halda. Vyměníme–li totiž mezi sebou předchůdce P a následníka N1 , nic to nemění na požadované relaci mezi případným druhým následníkem N2 uzlu P a „novým” předchůdcem uzlu N2 . Hodnota uzlu N2 byla větší nebo rovna hodnotě uzlu P a hodnota uzlu P je větší než hodnotu uzlu N1 , tedy určitě je hodnota uzlu N2 větší než hodnota uzlu N1 . Postup tvorby haldy je ilustrován na následujícím obrázku. 5
5
3
2
2
2
3
5 3
5
5
2
5
1
1
5
1
2 3
3
3
1 2 3 5
3 5
7
Obr. 1: Tvorba haldy Určeme složitost algoritmu vytváření haldy. Vložíme–li nový prvek do i – té hladiny haldy, musíme provést v nejhorším případě i−1 výměn mezi následníkem a předchůdcem. Mějme senam, který má n prvků. Potom existuje číslo k takové, že je n = 2k−1 + m, kde 0 ≤ m < 2k , tj. halda je tvořena k plně obsazenými hladinami a v poslední hladině je m prvků. Vložení případného prvku do poslední hladiny a následné výměny mezi následníkem a předchůdcem vyžaduje maximálně k kroků. Protože je 2k ≤ 2 · n ≤ n2 (pro n ≥ 2), je k ≤ log 2 n2 = 2 · log 2 n. Vkládaní prvků do i – té hladiny (s následnými výměnami mezi následníkem a předchůdcem) pro i ≤ k vyžaduje méně kroků. Pro počet T (n) případných výměn mezi následníkem a předchůdcem pro vytvoření haldy platí: T (n) ≤ n · k ≤ 2 · n · log 2 n. Algoritmus vytváření haldy je časové složitosti O(n · log n). Nyní si ukažme, jak z haldy vytvořit uspořádaný seznam. Důležité je, že umíme ihned vybrat nejmenší prvek (přesněji jeden z prvků s nejmenší hodnotou). Jedná se vždy o prvek umístěný v kořenu haldy (jediný prvek v první hladině). Haldu budeme „rozebírat následujícím algoritmickým postupem: 1. odebereme prvek z kořenu (první hladiny)haldy; 2. poslední prvek haldy, tj. poslední (zleva do prava) prvek z poslední obsazené hladiny přemístíme do kořenu (první hladiny) haldy; 3. zajistíme, aby halda splňovala podmínku, že hadnota následníka je větší nebo rovna hodnotě předchůdce. Začneme od kořene a budeme porovnávat hodnoty s následníky. Je–li hodnota následníků větší nebo rovna hodnotě předchůdce, je halda v pořádku. V opačném případě zaměníme hodnotu předchůdce s menší z hodnot následníků; jsou–li hodnoty obou následníků stejné, provedeme výměnu s následníkem „vlevo”. 4. kroky 1. až 3. opakujeme tak dlouho, až „rozebereme” celou haldu. Z odebíraných prvků vytváříme uspořádaný seznam tak, že prvky vkládáme do vytvářeného uspořádaného seznamu vždy na konec. Je zřejmé, že algoritmus „rozebírání” halda je opět algoritmem časové složitosti O(n · log n). Stejné třídy bude tedy i algoritmus „třídění haldou”, kterým daný seznam prvků přetvoříme na uspořádaný seznam prvků ve dvou krocích: 1. z daného seznamu vytvoříme haldu; 2. haldu „rozebereme” a vytvoříme uspořádaný seznam.
14
Celý postup, tj. oba kroky si ukážeme na jednom příkladě. Výsledky budeme psát do tabulek tak, tak že v řádku tabulky budou stav po provedení příslušného kroku. V řádcích tabulek budou prvky uváděny po hladinách a v hladinách ve stejném pořadí zleva do prava jako v haldě. Zkontrolujte postup pomocí „obrázků” hald. Máme z daného seznamu {3, 5, 2, 1, 7, 10, 9, 5, 4, 2, 6} vytvořit uspořádaný seznam. 1. Z daného seznamu vytvoříme haldu. Halda bude mít 4 hladiny, poslední není plně obsazena.
hladina pořadí 1. krok 2. krok 3. krok 4. krok 5. krok 6. krok 7. krok 8. krok 9. krok 10. krok 11. krok 12. krok 13. krok 14. krok 15. krok 16. krok
1 1 3 3 3 2 2 2 1 1 1 1 1 1 1 1 1 1
2 1
2 2
3 1
5 5 5 5 1 2 2 2 2 2 2 2 2 2 2
2 3 3 3 3 3 3 3 3 3 3 3 3 3
1 5 5 5 5 5 5 5 4 4 4 4
3 2
3 3
3 4
4 1
4 2
4 3
4 4
4 5
4 6
vloženo 3 5 2 1
7 7 7 7 7 7 7 2 2
10 10 10 10 10 10 10 10
9 9 9 9 9 9 9
5 5 5 5 5 5
7 10 9 5 4
4 5 5 5 5
2 7 7
2 6
6
Získaná halda je zobrazena na následujícím obrázku.
1
2
3
4
2 10
5
5
7
6
´ halda Obr. 3: Z´iskana
9
15
2. Získanou haldu postupně rozebereme. hladina pořadí halda 1. krok 2. krok 3. krok 4. krok 5. krok 6. krok 7. krok 8. krok 9. krok 10. krok 11. krok 12. krok 13. krok 14. krok 15. krok 16. krok 17. krok 18. krok 19. krok 19. krok 20. krok 21. krok 22. krok 23. krok 24. krok 24. krok
1 1 1 6 2 2 7 2 2 2 5 3 7 4 4 9 5 5 10 5 9 6 6 9 7 10 9 10
2 1 2 2 6 2 2 7 4 4 4 4 4 7 5 5 9 6 6 6 6 9 7 7 9 9 10
2 2 3 3 3 3 3 3 3 3 3 5 5 5 5 5 5 5 5 10 10 10 10 10 10
3 1 4 4 4 4 4 4 7 5 5 5 5 5 7 7 7 7 7 7 7 7 9
3 2 2 2 2 6 6 6 6 6 6 6 6 6 6 6 6 9 9 9
3 3 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10
3 4 9 9 9 9 9 9 9 9 9 9 9 9 9
4 1 5 5 5 5 5 5 5 7 7 7
4 2 5 5 5 5 5 5 5 5
4 3 7 7 7 7
4 4 6
4 5
4 6
odebráno 1
2
2 3
4
5 5
6 7 9 10
Uspořádaný seznam v pořadí odebraných prvků je {1, 2, 2, 3, 4, 5, 5, 6, 7, 9, 10}. Prvočísla Ukažme si další příklady algoritmů, tentokrát z oblasti elementární teorie čísel. Přirozené číslo p se nazývá prvočíslem jesliže čísla 1 a p jsou jediná přirozená čísla, kterými lze dělit číslo p beze zbytku. Přirozené číslo 1 je považováno za prvočíslo. Úloha zní: rozhodněte, zda dané přirozené číslo n je prvočíslo. První a nejjednodušší algoritmus je založen na testování zda je číslo n dělitelné číslem m, m ≤ n. Algoritmus je možno formulovat takto: 1. zkusíme, zda je 2 < n. Je–li 2 = n algoritmus končí a n je prvočíslo. Je–li 2 < n, testujeme zda je n dělitelné číslem 2. Jestliže ano, n není prvočíslo a algoritmus končí; jestliže ne, přejdeme k dalšímu kroku. 2. zkusíme, zda je 3 < n. Je–li 3 = n algoritmus končí a n je prvočíslo. Je–li 3 < n, testujeme zda je n dělitelné číslem 3. Jestliže ano, n není prvočíslo a algoritmus končí; jestliže ne, přejdeme k dalšímu kroku.
16
3. takto pokračujeme dále. Algoritmus skončí nejpozději v n-1 krocích. A jak lze tento algoritmus zjednodušit? a) Stačí si například uvědomit, že test zda je n dělitelné číslem i stačí provádět pro i = 2 a dále pouze pro lichá čísla i. b) Další možnost zjednodušení je založena na tom, že pokud je přirozené číslo n dělitelné beze zbytku číslem k 6∈ {1, n}, pak existuje přirozené číslo m 6∈ {1, n}, pro které platí √ n = k · m. Předpokládejme, že je k ≤ m. Potom je k · k ≤ k · m = n. Tedy je√k ≤ n. Algoritmus tak může být ukončen mnohem dříve a to testem, zda je i > n. Je–li √ i > n, algoritmus končí konstatováním, že n je prvočíslo. c) Další teoretický výsledek týkající se testování, zda dané číslo je či není prvočíslo, √ spočívá ve skutečnosti, že pokud n není prvočíslo, pak existuje prvočíslo m, m ≤ n, kterým je číslo n dělitelné beze zbytku. √ Stačí tedy testovat dělitelnost pouze prvočísly, která jsou menší nebo rovna číslu n. To by ovšem znamenalo značnou komplikaci při úloze formulované „rozhodněte, zda dané přirozené číslo n je prvočíslo”. Zlepšení by to ale přineslo při úloze formulované takto: nalezněte všechna prvočísla, která jsou menší nebo rovna danému číslu n případně při úloze: nalezněte prvních n prvočísel. Samozřejmě tento menší počet nutných testů je komplikován nutností uchovávat již známá prvočísla. Snižuje se časová náročnost algoritmu za cenu zvýšení prostorové náročnosti algoritmu. Poznámka. Pro nalezení všech prvočísel, která jsou menší nebo rovna předem zadanému přirozenému číslu M , existuje jednoduchý algoritmus, který je pojmenován po řeckém matematikovi Eratosthenovi z Kyrény (žil v letech 276194 před n. l.). Algoritmus je v literatuře uváděn jako Eratosthenovo síto. Algoritmus je možno formulovat takto: 0. krok (inicializace algoritmu): vytvoříme množinu všech přirozených čísela dále množinu B = {1}; 1. krok: vezmeme první číslo množiny A, což je číslo 2. Toto číslo a přesuneme do množiny B a z množiny A odstraníme všechna čísla, která jsou jeho násobkem. Množina A bude obsahovat všechna lichá čísla (A = {3, 5, · · · }), která jsou menší nebo rovna číslu M a bude B = {1, 2}. i–tý krok: vezmeme první číslo množiny A. Toto číslo a přesuneme do množiny B a z množiny A odstraníme všechna čísla, která jsou jeho násobkem. Algoritmus končí, jakmile je A = ∅ a množina B obsahuje právě všechna prvočísla menší nebo rovna číslu M . V každém kroku je skutečně první číslo množiny A prvočíslem (protože by jinak bylo již odstraněno jako nějaký násobek čísla menšího). √ Algoritmus by bylo možno také ukončit testem „je první číslo množiny A větší než M ? Pokud ano, pak jsou již všechna čísla z množiny A prvočísla a je možno je přesunout do množiny B. Ukažme si Eratosthenovo síto na konkrétním příkladě. Nalezněme všechna prvočísla menší nebo rovna číslu 25. 0. krok (inicializace algoritmu): A = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25} B = {1}; √ 1. krok: 2 ≤ 5 = 25, A = {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25} B = {1, 2};
17
√ 2. krok: 3 ≤ 5 = 25, A = {5, 7, 11, 13, 17, 19, 23, 25} B = {1, 2,√3}; 3. krok: 5 ≤ 5 = 25 A = {7, 11, 13, 17, 19, 23} B = {1, 2, 3, 5}; √ 4. krok: protože je 7 > 5 = 25, je A=∅ B = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23}; Všechna prvočísla, která jsou menší nebo rovna číslu 25 jsou: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23. Zápis algoritmu je možno modifikovat tak, že si vytvoříme tabulku všech čísel menších nebo rovno číslu M . Z tabulky postupně odstraňujeme násobky čísel 2, 3, 5, 7, . . . . Tento zápis více připomíná „síto”. V následujících tabulkách je uveden postup pro hledání všech prvočísel větších rovno 2 √ a menších než 100. Postupně jsou odstraňovány násobky prvočísel menších než 10 = 100, tj. násobky prvočísel 2, 3, 5, 7. V tabulkách jsou označeny tučně. Všechna prvočísla větší než 1, jsou v poslední tabulce. 1 21 41 61 81
2 22 42 62 82
3 23 43 63 83
4 24 44 64 84
5 25 45 65 85
6 26 46 66 86
7 27 47 67 87
8 28 48 68 88
9 29 49 69 89
10 30 50 70 90
11 31 51 71 91
12 32 52 72 92
13 33 53 73 93
14 34 54 74 94
15 35 55 75 95
16 36 56 76 96
17 37 57 77 97
18 38 58 78 98
19 39 59 79 99
1 21 41 61 81
2 ∗ ∗ ∗ ∗
3 23 43 63 83
∗ ∗ ∗ ∗ ∗
5 25 45 65 85
∗ ∗ ∗ ∗ ∗
7 27 47 67 87
∗ ∗ ∗ ∗ ∗
9 29 49 69 89
∗ ∗ ∗ ∗ ∗
11 31 51 71 91
∗ ∗ ∗ ∗ ∗
13 33 53 73 93
∗ ∗ ∗ ∗ ∗
15 35 55 75 95
∗ ∗ ∗ ∗ ∗
17 37 57 77 97
∗ ∗ ∗ ∗ ∗
19 39 59 79 99
∗ ∗ ∗ ∗ ∗
1 ∗ 41 61 ∗
2 ∗ ∗ ∗ ∗
3 23 43 ∗ 83
∗ ∗ ∗ ∗ ∗
5 25 ∗ 65 85
∗ ∗ ∗ ∗ ∗
7 ∗ 47 67 ∗
∗ ∗ ∗ ∗ ∗
∗ 29 49 ∗ 89
∗ ∗ ∗ ∗ ∗
11 31 ∗ 71 91
∗ ∗ ∗ ∗ ∗
13 ∗ 53 73 ∗
∗ ∗ ∗ ∗ ∗
∗ 35 55 ∗ 95
∗ ∗ ∗ ∗ ∗
17 37 ∗ 77 97
∗ ∗ ∗ ∗ ∗
19 ∗ 59 79 ∗
∗ ∗ ∗ ∗ ∗
1 ∗ 41 61 ∗
2 ∗ ∗ ∗ ∗
3 23 43 ∗ 83
∗ ∗ ∗ ∗ ∗
5 ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
7 ∗ 47 67 ∗
∗ ∗ ∗ ∗ ∗
∗ 29 49 ∗ 89
∗ ∗ ∗ ∗ ∗
11 31 ∗ 71 91
∗ ∗ ∗ ∗ ∗
13 ∗ 53 73 ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
17 37 ∗ 77 97
∗ ∗ ∗ ∗ ∗
19 ∗ 59 79 ∗
∗ ∗ ∗ ∗ ∗
1 ∗ 41 61 ∗
2 ∗ ∗ ∗ ∗
3 23 43 ∗ 83
∗ ∗ ∗ ∗ ∗
5 ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
7 ∗ 47 67 ∗
∗ ∗ ∗ ∗ ∗
∗ 29 ∗ ∗ 89
∗ ∗ ∗ ∗ ∗
11 31 ∗ 71 ∗
∗ ∗ ∗ ∗ ∗
13 ∗ 53 73 ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
∗ ∗ ∗ ∗ ∗
17 37 ∗ ∗ 97
∗ ∗ ∗ ∗ ∗
19 ∗ 59 79 ∗
∗ ∗ ∗ ∗ ∗
20 40 60 80 100
18
Příklady k procvičení 1) Dokažte, že pro funkci f (n) = a0 · nk + a1 · nk−1 + · · · + a1 · n + ak , kde a0 6= 0, je f (n) = θ(nk ). 2) Která z následujících tvrzení jsou platná a která ne. Jednotlivá tvrzení dokažte nebo nalezněte protipříklad. a) je–li T (n) = n5 + n3 + n, je T (n) ∈ O(n9 ); b) je–li T (n) = n5 + n3 + n, je T (n) ∈ θ(n3 ); c) je–li T (n) = 3n+2 , je T (n) ∈ O(n3 ); d) je–li T (n) = 32n , je T (n) ∈ O(3n ); e) je–li T (n) = 32n , je T (n) ∈ O(9n ); f) je–li T (n) = n · 3n , je T (n) ∈ O(3n ); e) je–li T (n) = 32n , je T (n) ∈ O(4n ); 3) Určete typ časové složitosti pro funkci T (n), je–li a) T (n) = 3 + 6 + 9 + · · · + 3n; b) T (n) = 13 + 23 + 33 + · · · + n3 ; d) T (n) = 1 + 3 + 32 + · · · + 3n ; d) T (n) = 1 · 3 + 2 · 32 + · · · + n · 3n ; d) T (n) = n · (1 + 211 + 212 + 213 + · · · + 21n ); 4) Danou množinu {6, 8, 2, 5, 4, 7, 1, 9} přetvořte na uspořádanou množinu metodou: a) přímého vkládání; b) třídění sléváním; d) třídění haldou. Uvádějte všechny elementární kroky. 5) Bez rozkladu na prvočinitele nalezněte největší společné dělitele dvojic čísel: a) 255, 459; b) 323, 459; c) 323, 629; d) 1653, 3219; e) 385, 1435; f) 847, 3157; e) 360, 135135; f) 440,10395. 6) Pomocí Hornerova schematu nalezněte zbytek při dělení polynomu f (x) polynomem x − a, je–li: a) f (x) = x5 + 3x4 + x3 + 2x2 + 3x + 5, a = 3; b) f (x) = x5 + 3x4 + x3 + 2x2 + 3x + 5, a = −2; c) f (x) = 2x5 + x4 + 2x3 − 2x2 + 3x − 5, a = 5; d) f (x) = 2x5 + x4 + 2x3 − 2x2 + 3x − 5, a = 2; e) f (x) = x5 + x4 − 2x3 + 3x2 + 5x + 7, a = −1; f) f (x) = x5 + x4 − 2x3 + 3x2 + 5x + 7, a = 5; g) f (x) = 3x5 + 2x4 + 2x3 + 3x2 + 5x + 7, a = 1; h) f (x) = x5 + x4 − 2x3 + 3x2 + 5x + 7, a = 3. 7) Pomocí Hornerova schematu nalezněte hodnoty polynomu f (x) a hodnoty všech derivací polynomu f (x)(až do řádu rovnému stupni polynomu) v daném bodě a, je–li: a) f (x) = 2x5 + 3x4 − 2x2 + 3x − 5, a = 1; b) f (x) = 2x5 + 3x4 − 2x2 + 3x − 5, a = −1; c) f (x) = 2x5 + 3x4 − 2x2 + 3x − 5, a = 2; d) f (x) = x4 − x3 + 3x2 + 5x − 2, a = 1;
19
e) f (x) = x4 − x3 + 3x2 + 5x − 2, a = 2; f) f (x) = x4 − x3 + 3x2 + 5x − 2, a = 3. Výsledky 5) Výsledky jsou uvedeny v tabulce. a) 51
b) 17
c) 1
d) 51
e) 35
f) 77
d) 89
e) 7
f) 3607
g) 45
h) 55
6) Výsledky jsou uvedeny v tabulce. a) 538
b) 15
c) 7085
g) 22
h) 994
7) Výsledky jsou uvedeny v tabulce. a) b) c) d) e) e)
a 1 −1 2 1 2 3
f (a) 1 −9 105 6 28 94
f 0 (a) 21 5 251 12 37 104
f 00 (a) 72 −8 460 12 42 96
f 000 (a) 192 48 624 18 42 66
f (4) (a) 312 −168 552 24 24 24
f (5) (a) 240 240 240
