Algoritmick´
a matematika 1
ˇ
c´
ast 1
ZS 2013/14
ˇ
´
Radim BELOHL
AVEK
Katedra informatiky
Univerzita Palack´eho v Olomouci
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
1 / 71
Z´
akladn´ı informace
– webov´
e str´
anky
– http://belohlavek.inf.upol.cz/vyuka/alm1-2014-15.html
(pˇredmˇet)
– http://belohlavek.inf.upol.cz/ (pˇredn´aˇsej´ıc´ı)
– dalˇs´ı (cviˇc´ıc´ı, STAG, katedra informatiky)
– studium
–
–
–
–
pˇredn´aˇsky (vede pˇredn´aˇsej´ıc´ı)
cviˇcen´ı (vede a podm´ınky urˇcuje cviˇc´ıc´ı)
konzultaˇcn´ı hodiny (vyuˇz´ıvat)
samostant´e studium (studium literatury, prom´yˇslen´ı probl´em˚
u,
praktick´e u poˇc´ıtaˇce)
– absolvov´
an´ı pˇredmˇ
etu
– z´apoˇcet (udˇel´ı cviˇc´ıc´ı, z´ıskat alespoˇ
n 60% bod˚
u za zadan´ych u
´kol˚
u: 1
p´ısemn´y test, 1 program)
– zkouˇska (vypsan´e pˇredterm´ıny a term´ıny)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
2 / 71
Charakteristika pˇredmˇ
etu, doporuˇ
cen´ı
– co je obsahem pˇredmˇetu
– z´akladn´ı algoritmy a datov´e struktury v informatice
– n´avrh, anal´yza a implementace
– charakter pˇredmˇetu
– jeden z nejd˚
uleˇzitˇejˇs´ıch pˇredmˇet˚
u pro informatiky
– vyˇzaduje schopnost kombinatorick´eho uvaˇzov´an´ı
– nen´ı prim´arnˇe pˇredmˇetem o programov´an´ı, ale schopnost programovat
je potˇrebn´a k procviˇcov´an´ı
– nen´ı typick´ym matematick´y pˇredmˇetem, ale pˇresnost matematick´eho
uvaˇzov´an´ı je zde typick´a
´
– souvisej´ıc´ı pˇredmˇety: Paradigmata programov´an´ı 1, Uvod
do
programov´an´ı 1
– rady pro studium
– chodit na pˇred´aˇsky a cviˇcen´ı (ˇsetˇr´ı ˇcas studia, rozpozn´a d˚
uleˇzit´e od
m´enˇe d˚
uleˇzit´eho)
– implementovat prob´ıran´e algoritmy (programovat, > 10 hod./t´yden)
– snaˇzit se vˇeci pochopit do hloubky, neuˇcit se zpamˇeti (bˇehem studia se
t´emata v obmˇen´ach opakuj´ı, pochopen´ı na zaˇc´atku studium usnadn´ı)
– pˇr´ıprava na zkouˇsku (individu´aln´ı, 2 dny je m´alo, sp´ıˇs t´yden)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
3 / 71
Dalˇs´ı informace
– na katedˇre
– moˇznost zapojit se do studentsk´ych soutˇeˇz´ı
– moˇznost zapojit se do v´yzkumu
– moˇznost studentsk´ych zahraniˇcn´ıch pobyt˚
u
– chyby v tomto studijn´ım textu
– hlaste mi pros´ım osobnˇe nebo e-mailem
– bonus
– zkouˇsku se zn´amkou ”v´ybornˇe”z´ısk´a ten, kdo prokazatelnˇe pˇrispˇeje
origin´aln´ım v´ysledkem k rozvoji oblasti algoritm˚
u (posuzuje
pˇredn´aˇsej´ıc´ı)
– napˇr. nov´y algoritmus pˇrin´aˇsej´ıc´ı zlepˇsen´ı oproti souˇcasn´emu stavu,
nov´y v´ysledek o sloˇzitosti algoritmu (teoretick´y nebo experiment´aln´ı)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
4 / 71
Algoritmy
z´
akladn´ı u
´vahy
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
5 / 71
Co je to algoritmus?
Prvn´ı pˇribl´ıˇzen´ı (“definice”):
Algoritmus je posloupnost instrukc´ı pro ˇreˇsen´ı probl´
emu.
Tato “definice” je nepˇresn´a (tedy to vlastnˇe nen´ı definice):
– Co je to probl´em?
– Co je to instrukce?
– Co to znamen´a ˇreˇsit probl´em?
N´azornˇe ale vystihuje podstatu pojmu algoritmus.
Existuje ˇrada podobn´ych “definic” pojmu algoritmus, v´ıce ˇci m´enˇe
rozs´ahl´ych a pˇr´ıp. pˇrid´avaj´ıc´ıch dalˇs´ı omezen´ı. Napˇr.
“an algorithm is a finite procedure, written in a fixed symbolic vocabulary,
governed by precise instructions, moving in discrete steps, 1, 2, 3, . . . ,
whose execution requires no insight, cleverness, intuition, intelligence, or
perspicuity, and that sooner or later comes to an end.”
–D. Berlinsky, The Advent of the Algorithm
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
6 / 71
Tedy, co je to probl´
em, instrukce, ˇreˇsit probl´
em?
Probl´
em
V bˇeˇzn´em ˇzivotˇe hovoˇr´ıme napˇr. o n´asleduj´ıc´ıch probl´emech:
1. Probl´em zaparkov´an´ı auta.
2. Probl´em v´ypoˇctu ˇreˇsen´ı line´arn´ı rovnice (tj. rovnice tvaru ax + b = 0).
3. Probl´em zjiˇstˇen´ı, zda dan´e pˇrirozen´e ˇc´ıslo n je prvoˇc´ıslo.
4. Izraelsko-palestinsk´y probl´em.
5. Probl´em jak ˇz´ıt smyslupln´y ˇzivot.
1, 2, 3 jsou pˇr´ıklady probl´em˚
u, o kter´ych se hovoˇr´ı v definici algoritmu
uveden´e dˇr´ıve a kter´e n´as budou v dalˇs´ım zaj´ımat. Probl´emy 4 a 5 ne.
Probl´em (napˇr. probl´em 1, 2 nebo 3) je pops´an (zad´an, specifikov´an):
– mnoˇzinou pˇr´ıpustn´ych zad´an´ı (vstup˚
u),
– pˇriˇrazen´ım (pˇredpisem, zobrazen´ım), kter´y pro kaˇzd´e pˇr´ıpustn´e zad´an´ı
(vstup) ˇr´ık´a, jak´e je odpov´ıdaj´ıc´ı (tj. spr´avn´e) ˇreˇsen´ı (v´ystup).
Probl´em se nˇekdy pˇr´ımo ch´ape jako pˇriˇrazen´ı, kter´e kaˇzd´emu pˇr´ıpustn´emu
vstupu pˇriˇrazuje odpov´ıdaj´ıc´ı v´ystup.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
7 / 71
Takov´e pojet´ı (probl´em = mnoˇzina pˇr´ıpustn´ych vstup˚
u a pˇriˇrazen´ı) d´av´a
pomˇernˇe pˇresn´e vymezen´ı pojmu probl´em, kter´e n´am zat´ım staˇc´ı.
Pˇr´ıklady:
1. Probl´em zaparkov´an´ı auta.
Pˇr´ıpustn´ym vstupem je popis S poˇc´ateˇcn´ı dopravn´ı situace (zahrnuje
polohu auta, kter´e je tˇreba zaparkovat, popis okoln´ı situace vˇcetnˇe
m´ısta, kam je tˇreba zaparkovat).
Pˇriˇrazen´ı specifikuje pro kaˇzd´y S popis spr´avn´e koncov´e situace T (tj.
ve kter´e je auto spr´avnˇe zaparkov´ano).
(Popisy S a T mohou b´yt znaˇcnˇe komplikovan´e.)
2. Probl´em v´ypoˇctu ˇreˇsen´ı line´arn´ı rovnice.
Pˇr´ıpustn´e vstupy jsou dvojice ha, bi racion´aln´ıch ˇc´ısel a a b.
Pˇriˇrazen´ı ˇr´ık´a, ˇze v´ystupem odpov´ıdaj´ıc´ım vstupu ha, bi je
ˇc´ıslo c, pro kter´e ac + b = 0, pokud a 6= 0,
text “Kaˇzd´e ˇc´ıslo je ˇreˇsen´ım”, pokud a = 0 a b = 0.
text “Nem´a ˇreˇsen´ı”, pokud a = 0 a b 6= 0.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
8 / 71
3. Probl´em zjiˇstˇen´ı, zda dan´e pˇrirozen´e ˇc´ıslo n je prvoˇc´ıslo.
Pˇr´ıpustn´e vstupy jsou pˇrirozen´a ˇc´ısla n.
Pˇriˇrazen´ı ˇr´ık´a, ˇze v´ystupem odpov´ıdaj´ıc´ım vstupu n je
“Ano”, pokud n je prvoˇc´ıslo,
“Ne”, pokud n nen´ı prvoˇc´ıslo.
Probl´emy 2 a 3 jsou typick´e pˇr´ıklady probl´em˚
u, kter´ymi se budeme
zab´yvat. Zkr´acen´y popis probl´emu:
probl´em (n´azev probl´emu)
vstup: popis pˇr´ıpustn´eho vstupu
v´ystup: popis odpov´ıdaj´ıc´ıho v´ystupu
Pˇr´ıklad:
probl´em (test prvoˇc´ıselnosti)
vstup: pˇrirozen´e ˇc´ıslo n
v´ystup: “Ano”, pokud n je prvoˇc´ıslo; “Ne”, pokud n nen´ı prvoˇc´ıslo.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
9 / 71
Instrukce
Instrukce je jednoznaˇcn´y srozumiteln´y pokyn jako napˇr.:
–
–
–
–
–
–
–
Seˇsl´apni brzdov´y ped´al.
Seˇcti ˇc´ısla a a b. (aritmetick´a instrukce)
Do promˇenn´e x uloˇz ˇc´ıslo 5. (instrukce pˇriˇrazen´ı)
Pokud je C > 0, pak zvyˇs hodnotu b o 1. (podm´ınˇen´a instrukce)
Pˇreˇcti ˇc´ıslo, kter´e je na vstupu. (vstupnˇe/v´ystupn´ı instrukce)
Vytiskni hodnotu promˇen´e x. (vstupnˇe/v´ystupn´ı instrukce)
Pro kaˇzd´e i = 1, 2, 3, 4, 5 postupnˇe proved’: vytiskni hodnotu i 2
(instrukce cyklu; v tˇele cyklu je vstupnˇe/v´ystupn´ı instrukce)
Pojem instrukce (opˇet nepˇresnˇe definovan´y) vych´az´ı z pˇredstavy, ˇze existuje
nˇekdo, napˇr. ˇclovˇek (nebo nˇeco, napˇr. poˇc´ıtaˇc), kdo (co) instrukc´ım
rozum´ı a je schopen je mechanicky, tj. bez dalˇs´ıho pˇrem´yˇslen´ı, vykon´avat.
Tento vykonavatel instrukc´ı je schopen vykon´avat instrukce tak, jak jsou
pˇredeps´any algoritmem (tj. ve spr´avn´em poˇrad´ı).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
10 / 71
ˇ sen´ı probl´
Reˇ
emu algoritmem — co to znamen´
a?
Algoritmus ˇreˇs´ı dan´y probl´em, pokud pro kaˇzd´y pˇr´ıpustn´y vstup I dan´eho
probl´emu, jemuˇz odpov´ıd´a v´ystup O (tj. O je spr´avn´y v´ystup pro vstup I )
plat´ı:
Vykon´av´an´ı instrukc´ı podle algoritmu se vstupem I se po urˇcit´e dobˇe (po
koneˇcn´em poˇctu krok˚
u) zastav´ı a na v´ystupu je O.
Tj. vykon´av´an´ım instrukc´ı podle algoritmu se od vstupu I po koneˇcn´em
poˇctu krok˚
u dobereme k O.
ˇ ık´ame, ˇze algoritmus se pro vstup I zastav´ı s v´ystupem O.
R´
Pˇritom se pˇredpokl´ad´a, ˇze vstup I je na zaˇc´atku vykon´av´an´ı instrukc´ı
zaps´an na dohodnut´em vstupn´ım zaˇr´ızen´ı (soubor na disku, je zad´an z
kl´avesnice apod.) a ˇze v´ystup se objev´ı na dohodnut´em v´ystupn´ım zaˇr´ızen´ı
(soubor na disku, obrazovka apod.).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
11 / 71
Zpˇ
et k probl´
emu v´
ypoˇ
ctu ˇreˇsen´ı rovnice ax + b = 0
Posloupnost instrukc´ı 1:
Pokud a 6= 0, zapiˇs na v´ystup ˇc´ıslo −b/a.
Pokud a = 0 a b = 0, zapiˇs na v´ystup “Kaˇzd´e ˇc´ıslo je ˇreˇsen´ım”.
Pokud a = 0 a b 6= 0, zapiˇs na v´ystup “Nem´a ˇreˇsen´ı”.
Posloupnost instrukc´ı 2:
Pokud a 6= 0, zapiˇs na v´ystup ˇc´ıslo −b/a, jinak zapiˇs ˇc´ıslo b/a.
Posloupnost instrukc´ı 3:
Dokud a 6= 0, prov´adˇej: zvyˇs hodnotu b o 1.
Pokud a = 0 a b 6= 0, zapiˇs na v´ystup “Nem´a ˇreˇsen´ı”.
Posloupnost 1 je algoritmus pro ˇreˇsen´ı dan´eho probl´emu. (Velmi
jednoduch´y algoritmus pro velmi jednoduch´y probl´em. Dalˇs´ı budou
sloˇzitˇejˇs´ı.)
Posloupnosti 2 a 3 ne (2 ned´av´a spr´avn´e v´ystupy, 3 se pro nˇekter´e vstupy
nezastav´ı).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
12 / 71
Za algoritmy nelze povaˇzovat ani n´asleduj´ıc´ı posloupnosti:
Posloupnost 4:
Zkus odhadnout ˇreˇsen´ı.
Vyzkouˇsej, zda je spr´avn´e.
Pokud ano, zapiˇs ho na v´ystup.
Pokud ne, zpˇresni odhad a jdi d´al.
Nen´ı to algoritmus, protoˇze nen´ı jasn´e, jak postupovat.
Posloupnost 5:
Spust’ na PC program Mathematica.
Vyˇreˇs v nˇem rovnici.
V´ysledek zapiˇs na v´ystup.
Nen´ı to algoritmus, odvol´av´a se na zaˇr´ızen´ı (jeho existence a dostupnost je
ˇcasovˇe podm´ınˇena), kter´e probl´em vyˇreˇs´ı.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
13 / 71
Existuje pˇresn´
a definice pojmu algoritmus a dalˇs´ıch
pojm˚
u?
Ano. Zab´yv´a se t´ım informatick´a discipl´ına zvan´a teorie vyˇc´ıslitelnosti
(computability theory).
Poznamenejme, ˇze existuj´ı r˚
uzn´e n´azory na to, co pojem algoritmus pˇresnˇe
znamen´a, a tedy r˚
uzn´e definice pojmu algoritmus. T´emˇeˇr vˇsechny definice
lze vˇsak ch´apat jako zpˇresnˇen´ı v´yˇse uveden´e nepˇresn´e definice.
Jeˇstˇe jednou. Naˇse nepˇresn´a definice, kter´a ˇr´ık´a
“Algoritmus je posloupnost instrukc´ı pro ˇreˇsen´ı probl´emu.”
nen´ı vlastnˇe definic´ı. Popisuje intuitivn´ı pˇredstavu o tom, co to je
algoritmus.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
14 / 71
Co ˇrekli o pojmu algoritmus
Algorithmics is more than a branch of computer science. It is the core of
computer science, and, in all fairness, can be said to be relevant to most
of science, business, and technology.
—D. Harel, Algorithmics: The Spirit of Computing, 1992
Two ideas lie gleaming on the jeweler’s velvet. The first is the calculus, the
second the algorithm. The calculus and the rich body of mathematical
analysis to which it gave rise made modern science possible; but it has
been the algorithm that has made possible the modern world.
—D. Berlinski, The Advent of the Algorithm, 2000
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
15 / 71
Co ˇrekli o pojmu algoritmus
A person well-trained in computer science knows how to deal with
algorithms: how to contruct them, manipulate them, understand them,
analyze them. This knowledge is preparation for much more than writing
good computer programs; it is a general-purpose mental tool that will be a
definite aid to understanding other subjects, whether they be chemistry,
linguistics, or music, etc. The reason for this may be understood in the
following way: It has often been said that a person does not really
understand something until after teaching it to someone else. Actually, a
person does not really understand something until after teaching it to a
computer, i.e., expressing it as an algorithm. . . . An attempt to formalize
things as algorithms leads to a much deeper understanding than if we
simply try to comprehend things in the traditional way.
—D. E. Knuth, Selected Papers on Computer Science, 1996
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
16 / 71
Donald E. Knuth
Professor Emeritus of The Art of Computer Programming
Stanford University
http://www-cs-faculty.stanford.edu/~uno/
jeden z nejv´yznamnˇejˇs´ıch informatik˚
u
autor nˇekolikasvazkov´eho d´ıla
“The Art of Computer Programming”
autor syst´emu TEX
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
17 / 71
Nˇ
ekolik z´
asadn´ıch fakt o algoritmech a probl´
emech
... ke kter´ym se budeme v tomto pˇredmˇetu i v dalˇs´ıch pˇredmˇetech vracet.
– Je kaˇzd´y probl´em ˇreˇsiteln´y algoritmem?
Ne, existuj´ı pˇrirozen´e probl´emy, kter´e nelze ˇreˇsit ˇz´adn´ym algoritmem
(algoritmicky neˇreˇsitelen´e).
– M´a smysl ˇr´ıkat, ˇze probl´emy jsou lehk´e a tˇeˇzk´e, ˇze nˇekter´e probl´emy
jsou lehˇc´ı neˇz jin´e?
Ano, zab´yv´a se t´ım teorie vyˇc´ıslitelnosti.
– M´a klasifikace probl´em˚
u podle obt´ıˇznosti nˇejak´y praktick´y v´yznam?
Ano, z´akladn´ı je dˇelen´ı algoritmicky ˇreˇsiteln´ych probl´em˚
u na rychle
ˇreˇsiteln´e a ty, pro kter´e rychl´y algoritmus nen´ı zn´am. Prakticky
v´yznamn´e jsou oba typy probl´em˚
u.
– Lze o algoritmech ˇr´ıkat, ˇze jeden je lepˇs´ı (efektivnˇejˇs´ı) neˇz druh´y?
Ano, zab´yv´a se t´ım teorie sloˇzitosti a je to prakticky velmi d˚
uleˇzit´e.
Budeme se t´ım zab´yvat i v tomto pˇredmˇetu.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
18 / 71
– To vypad´a zaj´ımavˇe, ale asi to bude n´aroˇcn´e nastudovat. D´a se to a
budu vˇsemu rozumˇet?
Ano, d´a se to. Proˇsly t´ım stovky jin´ych. Ne vˇsemu je tˇreba rozumˇet
do nejmenˇs´ıch detail˚
u. Nˇeco je tˇreba pochopit hloubˇeji, nˇekde staˇc´ı
pochopit z´akladn´ı principy.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
19 / 71
Jak popsat (specifikovat) algoritmus?
Budeme se zab´yvat zejm. algoritmy, kter´e jsou urˇceny pro poˇc´ıtaˇc (tj.
instrukce vykon´av´a poˇc´ıtaˇc). Z´akladn´ı zp˚
usoby popisu takov´ych algoritm˚
u
jsou:
– Pˇrirozen´ym jazykem. To jsme uˇz vidˇeli.
+: Snadno srozumiteln´e i laik˚
um.
−: M˚
uˇze b´yt nejednoznaˇcn´e. Zdlouhav´e.
– Programovac´ım jazykem. Budeme pouˇz´ıvat jazyk C (ale je moˇzn´e
pouˇz´ıt jak´ykoli programovac´ı jazyk).
+: Jednoznaˇcn´e.
+: Vytvoˇrit poˇc´ıtaˇcov´y program je pak snadn´e (t´emˇeˇr ho m´ame). Rozum´ı
tomu program´atoˇri.
−: Obsahuje i zbyteˇcn´e (nepodstatn´e) detaily. Dlouh´e.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
20 / 71
– Pseudok´odem. Pseudok´
od je jazyk bl´ızk´y programovac´ımu jazyku, ale
je u
´spornˇejˇs´ı, protoˇze neobsahuje tolik podrobnost´ı. Budeme pouˇz´ıvat
pseudok´od z knihy Cormen et al.: Introduction to Algorithms, 2nd Ed.
MIT Press, 2001.
+: Je snadno pochopiteln´y i pro ty, kteˇr´ı nemaj´ı zkuˇsenosti s
programov´an´ım a programovac´ımi jazyky. Je vytvoˇren´y pˇr´ımo pro
srozumiteln´y a u
´sporn´y popis algortm˚
u. Umoˇzn
ˇuje snadn´y pˇrepis do
programovac´ıch jazyk˚
u.
−: Snad to, ˇze pˇri implementaci algoritmu je tˇreba ho pˇrepsat do
programovac´ıho jazyka.
– Dalˇs´ımi (polo)form´aln´ımi prostˇredky (v´yvojov´e diagramy, . . . ).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
21 / 71
Algoritmus sˇ
c´ıt´
an´ı v des´ıtkov´
e soustavˇ
e
sˇc´ıt´an´ı pˇrirozen´ych ˇc´ısel v des´ıtkov´e soustavˇe (z´akladn´ı ˇskola)
1 0 9 3
+ 2 3 4 5
3 4 3 8
protoˇze:
postupujeme zprava (od posledn´ı cifry) doleva
3 + 5 = 8 ⇒ nap´ıˇseme 8 a pˇren´aˇs´ıme 0
9 + 4 = 13 ⇒ nap´ıˇseme 3 a pˇren´aˇs´ıme 1
1 + 0 + 3 = 4 ⇒ nap´ıˇseme 4 a pˇren´aˇs´ıme 0
1 + 2 = 3 ⇒ nap´ıˇseme 3 a pˇren´aˇs´ıme 0
podobnˇe
9 7 2 8
+ 2 3 9 9 ,
1 2 1 2 7
Radim Bˇ
elohl´
avek (UP)
1 0
+ 2 5 ,
3 5
Algoritmick´
a matematika 1
0 0 1 3
+ 8 6 8 2
8 6 9 5
ZS 2014/15
22 / 71
Popiˇsme pˇresnˇe ˇreˇsen´y probl´em.
probl´
em (sˇ
c´ıt´
an´ı v des´ıtkov´
e soustavˇ
e):
vstup: an−1 an−2 · · · a1 a0 , bn−1 bn−2 · · · b1 b0 ,
kde ai , bi jsou ˇc´ıslice z mnoˇziny {0, 1, . . . , 9}
v´
ystup: cn cn−1 · · · c1 c0 ,
(posloupnost), kter´a je z´apisem v des´ıtkov´e soustavˇe ˇc´ısla A + B, kde A a
B jsou ˇc´ısla jejichˇz z´apisy jsou posloupnosti an−1 · · · a0 a bn−1 · · · b0
Pozn´amky:
– Prvky n-prvkov´e posloupnosti indexujeme pomoc´ı 0, 1, . . . , n − 1, a ne
1, 2, . . . , n (b´yv´a to v´yhodnˇejˇs´ı, uvid´ıme).
– M´ısto ai tak´e p´ıˇseme a[i] (tak se to p´ıˇse v programovac´ıch jazyc´ıch).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
23 / 71
Popis v pˇrirozen´
em jazyku
1. Je-li a[0] + b[0] < 10, nastav hodnoty c[0] na a[0] + b[0] a t na 0;
jinak nastav c[0] na a[0] + b[0] − 10 a t na 1;
2. Je-li a[1] + b[1] + t < 10, nastav c[1] na a[1] + b[1] + t a t na 0;
jinak nastav c[1] na a[1] + b[1] + t − 10 a t na 1;
...
n. Je-li a[n − 1] + b[n − 1] + t < 10, nastav c[n − 1] na
a[n − 1] + b[n − 1] + t a t na 0;
jinak nastav c[n − 1] na a[n − 1] + b[n − 1] + t − 10 a t na 1;
n+1. nastav c[n] na t.
Vid´ıme, ˇze popis v pˇrirozen´em jazyku je tˇeˇzkop´adn´y a nepˇrehledn´y.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
24 / 71
Jin´
y popis v pˇrirozen´
em jazyku
1. Nastav t na 0.
2. Pro hodnoty i od 0 do n − 1 prov´adˇej postupnˇe:
Je-li a[i] + b[i] + t < 10, nastav c[i] na a[i] + b[i] + t a t na 0;
jinak nastav c[i] na a[i] + b[i] + t − 10 a t na 1;
3. nastav c[n] na t.
Zaˇradili jsme konstrukci zvanou cyklus (“Pro hodnoty i od . . . ”). St´ale to
nen´ı ono.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
25 / 71
Popis v pseudok´
odu
Scitani-Cisel-Desitkove(a[0..n − 1], b[0..n − 1])
1 t←0
2 for i ← 0 to n − 1
3
do c[i] ← a[i] + b[i] + t mod 10
4
t ← b(a[i] + b[i] + t)/10c
5 c[n] ← t
Poznamenejme:
– a mod n je zbytek po dˇelen´ı ˇc´ısla a ˇc´ıslem n
pˇr.: 5 mod 2 = 1, 12 mod 10 = 2, . . .
– bac je nejvˇetˇs´ı cel´e ˇc´ıslo, kter´e je ≤ a
b0.5c = 0, b1.2c = 1, b1.0c = 1, . . .
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
26 / 71
Popis v programovac´ı jazyku C
int ScitaniCiselDesitkove (int *a, int *b, int *c)
{
int i,t;
t=0;
for (i = 2; i < n; i++){
c[i] = (a[i] + b[i] + t) % 10;
t = (a[i] + b[i] + t) / 10;
}
c[n]=t;
return 0;
}
Nen´ı tak pˇrehledn´e (a srozumiteln´e) jako pseudok´
od.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
27 / 71
Shrnut´ı
Probrali jsme:
– pojem algoritmus
– pojmy probl´em, instrukce, ˇreˇsen´ı probl´emu algoritmem
– pˇr´ıklady probl´em˚
u
– pˇr´ıklady algoritm˚
u
– jak popsat algoritmus
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
28 / 71
Z´
akladn´ı ot´
azky o algoritmech
– Spr´
avnost algoritmu:
Je d´an probl´em. Skonˇc´ı navrˇzen´y algoritmus pro kaˇzd´y pˇr´ıpustn´y
vstup probl´emu po koneˇcn´em poˇctu krok˚
u a se spr´avn´ym v´ystupem?
Tj. jde v˚
ubec o algoritmus pro dan´y probl´em?
Pro kaˇzd´y navrˇzen´y algoritmus je tˇreba ovˇeˇrit (dok´azat), zda je
spr´avn´y. Jinak m˚
uˇze hrozit v´aˇzn´e riziko (ˇr´ızen´ı sloˇzit´ych
syst´em˚
u—elektr´arna, ABS syst´em u aut, . . . ).
Zda je algoritmus spr´avn´y, je nˇekdy snadno vidˇet, m˚
uˇze to ale b´yt
n´aroˇcn´e.
– Sloˇ
zitost algoritmu:
Jak dlouho trv´a vykon´av´an´ı algoritmu (tj. jak´a je jeho ˇcasov´a
sloˇzitost)?
Kolik pamˇeti algoritmus potˇrebuje (tj. jak´a je jeho pamˇet’ov´a
sloˇzitost)?
Sloˇzitost n´am d´av´a informaci o tom, jak je algoritmus kvalitn´ı a
umoˇzn
ˇuje ho z tohoto pohledu porovnat s jin´ymi algoritmy.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
29 / 71
– Optimalita algoritmu:
Existuje lepˇs´ı algoritmus?
Pro nˇekter´e algoritmy lze dok´azat, ˇze lepˇs´ı neexistuj´ı, tedy nem´a
smysl je hledat. (Co to ale znamen´a “lepˇs´ı”? Je tˇreba rozebrat.)
Nyn´ı vysvˇetl´ıme intuitivnˇe a na pˇr´ıkladech.
Pozdˇeji se k tomu vr´at´ıme a vysvˇetl´ıme pˇresnˇe.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
30 / 71
Spr´
avnost algoritmu – pˇr´ıklad
Scitani-Cisel-Desitkove(a[0..n − 1], b[0..n − 1])
1 t←0
2 for i ← 0 to n − 1
3
do c[i] ← a[i] + b[i] + t mod 10
4
t ← b(a[i] + b[i] + t)/10c
5 c[n] ← t
Jak dok´aˇzeme spr´avnost naˇseho algoritmu?
V tomto pˇr´ıpadˇe je to snadn´e (nˇekdo by ˇrekl zbyteˇcn´e). Pro u
´plnost to
dokaˇzme (kdyˇz se to na z´aklad´ı ˇskole neudˇel´a, dˇeti se uˇc´ı algoritmus
nazpamˇet’ bez pochopen´ı).
Tvrzen´ı Algoritmus Scitani-Cisel-Desitkove je spr´avn´y.
ˇ ıslo A si pˇredstav´ıme jako A kor´alk˚
D˚
ukaz C´
u. Z´apisu
a[n − 1]a[n − 2] · · · a[0] ˇc´ısla A v des´ıtkov´e soustavˇe odpov´ıd´a n´asleduj´ıc´ı
uspoˇr´ad´an´ı kor´alk˚
u (uspoˇr´ad´an´ı se snadnˇeji namaluje neˇz slovnˇe popisuje).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
31 / 71
Krok 1: Kor´alky navl´ek´ame na nit po 10 (nit s 10 kor´alky sv´aˇzeme a
ˇr´ık´ame j´ı svazek). Tak z´ısk´ame nˇekolik svazk˚
u (kaˇzd´y m´a 10 kor´alk˚
u) a
zbyde pr´avˇe a[0] nenavleˇcen´ych kor´alk˚
u. (Udˇelejte si pˇr´ıklad, pro A = 123
z´ısk´ame 12 svazk˚
u a 3 kor´alky zbydou). Zbyl´e kor´alky d´ame stranou.
Krok 2: Postupujeme d´al tak, ˇze k sobˇe svazujeme vˇzdy 10 svazk˚
u
z´ıskan´ych v pˇredchoz´ım kroku. Tak z´ısk´ame nˇekolik vˇetˇs´ıch svazk˚
u (kaˇzd´y
m´a 100 kor´alk˚
u) a zbyde pr´avˇe a[1] nesv´azan´ych svazk˚
u o 10 kor´alc´ıch.
(Pro A = 123 z´ısk´ame 1 svazek o 100 kor´alc´ıch a zbydou 2 svazky o 10
kor´alc´ıch). Zbyl´e svazky d´ame stranou.
Postupujeme d´al, aˇz dojdeme do kroku n, ve kter´em zb´yv´a m´enˇe neˇz 10
svazk˚
u s 10n−1 kor´alky. Poˇcet tˇechto svazk˚
u je pr´avˇe a[n − 1]. (Pro
A = 123 tak dojdeme do kroku 3, ve kter´em zb´yv´a 1 svazek o 100
kor´alc´ıch.)
Tak si pˇredstav´ıme i ˇc´ıslo B.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
32 / 71
Svazky kor´alk˚
u a kor´alky, kter´e jsme z´ıskali z A kor´alk˚
u pˇredstavuj´ıc´ıch
ˇc´ıslo A a B kor´alk˚
u pˇredstavuj´ıc´ıch ˇc´ıslo B d´ame k sobˇe. Z´ısk´ame tak
C = A + B kor´alk˚
u. Abychom z´ıskali uspoˇr´ad´an´ı tˇechto kor´alk˚
u, kter´e
odpov´ıd´a z´apisu C v des´ıtkov´e soustavˇe, mus´ıme je spr´avnˇe uspoˇr´adat.
Protoˇze kor´alky jiˇz jsou uspoˇr´adan´e ve svazc´ıch, dojdeme k poˇzadovan´emu
uspoˇr´ad´an´ı n´asledovnˇe.
D´ame dohromady jednotliv´e kor´alky (je jich a[0] + b[0]). Je-li jich alespoˇ
n
10, vytvoˇr´ıme nov´y svazek o 10 kor´alc´ıch. Kor´alky, kter´e nejsou v nov´em
svazku, d´ame stranou, nov´y svazek ponech´ame. Je jasn´e, ˇze stranou d´ame
a[0] + b[0] mod 10 kor´alk˚
u a ˇze vznikne b(a[0] + b[0])/10c nov´ych svazk˚
u
(ˇz´adn´y nebo jeden). To jsou pr´avˇe ˇc´ısla pˇriˇrazen´a c[0] a t na ˇr´adc´ıch 3 a 4
v kroku pro i = 0.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
33 / 71
V obecn´em kroku pro i d´ame dohromady svazky s 10i kor´alky (je jich
a[i] + b[i] + t, kde t je poˇcet nov´ych svazk˚
u vytvoˇren´ych v pˇredchoz´ım
kroku). Je-li jich alespoˇ
n 10, vytvoˇr´ıme nov´y svazek o 10i+1 kor´alc´ıch.
Svazky o 10i kor´alc´ıch, kter´e nejsou v nov´em svazku, d´ame stranou, nov´y
svazek ponech´ame. Je jasn´e, ˇze stranou d´ame a[i] + b[i] + t mod 10 svazk˚
u
a ˇze vznikne b(a[i] + b[i] + t)/10c nov´ych svazk˚
u (ˇz´adn´y nebo jeden). To
jsou pr´avˇe ˇc´ısla pˇriˇrazen´a c[i] a t na ˇr´adc´ıch 3 a 4 v kroku pro i.
Tak dojdeme aˇz k i = n, kdy opust´ıme cyklus a kdy zb´yv´a
b(a[n − 1] + b[n − 1] + t)/10c svazk˚
u o 10n kor´alc´ıch. To je spr´avn´a
hodnota c[n] je to tak´e hodnota pˇriˇrazen´a c[n] na ˇr´adku 5.
D˚
ukaz je hotov.
M´ısto
Tvrzen´ı Algoritmus Scitani-Cisel-Desitkove je spr´avn´y.
D˚
ukaz . . .
budeme ps´at jen
D˚
ukaz spr´
avnosti Scitani-Cisel-Desitkove . . .
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
34 / 71
Je d˚
ukaz spr´
avnosti nutn´
y?
Ano. U mnoha algoritm˚
u je ale spr´avnost zˇrejm´a, takˇze d˚
ukaz odbydeme
slovy “Je zˇrejm´y”.
D˚
ukazem spr´avnosti nen´ı, kdyˇz uk´aˇzeme, ˇze algoritmus spr´avnˇe funguje pro
nˇekolik zvolen´ych vstup˚
u (nemus´ı totiˇz spr´avnˇe fungovat pro dalˇs´ı vstupy).
U jin´ych algoritm˚
u je d˚
ukaz spr´avnosti komplikovan´y. Kdyˇz chceme
algoritmus “jen” pouˇz´ıt, nemus´ıme d˚
ukaz spr´avnosti ˇc´ıst, pokud algoritmus
pˇrevezmeme z d˚
uvˇeryhodn´eho zdroje (napˇr. kniha o algoritmech).
V tomto pˇredmˇetu se ale spr´avnost´ı algoritm˚
u budeme zab´yvat.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
35 / 71
D˚
ukaz spr´
avnosti m˚
uˇ
ze m´ıt mnoho podob
Jin´a podoba d˚
ukazu spr´avnosti Scitani-Cisel-Desitkove (hutn´a verze,
m˚
uˇzete pˇreskoˇcit):
Pn−1
P
i, B =
i
a[i]
∗
10
Je A = n−1
i=0
i=0 b[i] ∗ 10 , tedy pro C = A + B a jeho
Pn−1
i
z´apis C = i=0 c[i] ∗ 10 mus´ı platit:
c[0] = (a[0] + b[0]) mod 10,
c[1] = (a[1] + b[1] + b(a[0] + b[0])/10c) mod 10,
...
c[n − 1] = (a[n − 1] + b[n − 1] + b(a[n − 2] + b[n − 2] +
b(a[n − 3] + b[n − 3] + · · · )/10c))/10c) mod 10,
c[n] = b(a[n − 1] + b[n − 1] + b(a[n − 2] + b[n − 2] + · · · )/10c))/10c
coˇz jsou pr´avˇe hodnoty obdrˇzen´e naˇs´ım algoritmem.
Vˇzdy je tˇreba naj´ıt vhodn´y kompromis mezi struˇcnost´ı a srozumitelnost´ı.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
36 / 71
Kdyˇ
z navrˇ
zen´
y algoritmus nen´ı spr´
avn´
y
Co kdyˇz navrˇzen´y algoritmus nen´ı spr´avn´y? Jak to prok´aˇzu?
Mus´ıme naj´ıt pˇr´ıklad, pro kter´y algoritmus skonˇc´ı s nespr´avn´ym v´ystupem
(tzv. protipˇr´ıklad). Tj. naj´ıt pˇr´ıpustn´y vstup I , pro kter´y je spr´avn´ym
v´ystupem O, ale pro kter´y algoritmus skonˇc´ı s v´ystupem O 0 6= O nebo
neskonˇc´ı v˚
ubec.
Pˇr´ıklad (nespr´avn´y algoritmus pro hled´an´ı nejkratˇs´ı cesty)
Je d´ana s´ıt’ mˇest, nˇekter´a jsou spojena silnic´ı, jsou d´ana mˇesta Z (zaˇc´atek)
a K (konec). Jak naj´ıt nejkratˇs´ı cestu z Z do K ?
Pˇr´ıpustn´ym vstupem je tedy popis s´ıtˇe mˇest (napˇr. ve formˇe pouˇzit´e n´ıˇze) a
dvojice mˇest Z a K ; odpov´ıdaj´ıc´ım v´ystupem je nejkratˇs´ı cesta ze Z do K .
N´avrh algoritmu: Zaˇcnu v Z a jdu do nejbliˇzˇs´ıho mˇesta M1 , ve kter´em
jsem jeˇstˇe nebyl; v M1 postupuji stejnˇe (jdu do nejbliˇzˇs´ıho mˇesta M2 , ve
kter´em jsem jeˇstˇe nebyl), aˇz dojdu do K .
Tento algoritmus je nespr´avn´y.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
37 / 71
Vstup 1: S´ıt’
{({A, B}, 1), ({A, D}, 5), ({B, C }, 2), ({C , D}, 1), ({D, E }, 2)},
Z = A, K = E .
({A, B}, 1) znamen´a, ˇze mezi A a B je silnice d´elky 2, atd. Algoritmus
najde cestu A, B, C , D, E d´elky 6 (1 + 2 + 1 + 2). To je skuteˇcnˇe nejkratˇs´ı
cesta.
ALE
Vstup 2: S´ıt’
{({A, B}, 1), ({A, D}, 5), ({B, C }, 4), ({C , D}, 1), ({D, E }, 2)},
Z = A, K = E .
Algoritmus najde cestu A, B, C , D, E d´elky 8 (1 + 4 + 1 + 2). To nen´ı
nejkratˇs´ı cesta! Nejkratˇs´ı je A, D, E , m´a d´elku 7. Tedy vstup 2 je
protipˇr´ıklad (jeden z mnoha moˇzn´ych), kter´y ukazuje, ˇze navrˇzen´y
algoritmus nen´ı spr´avn´y.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
38 / 71
Nejvˇ
etˇs´ı spoleˇ
cn´
y dˇ
elitel a Euklid˚
uv algoritmus
probl´em (nejvˇetˇs´ı spoleˇcn´y dˇelitel, greatest common divisor)
vstup: pˇrirozen´a ˇc´ısla m, n
v´ystup: gcd(m, n) (nejvˇetˇs´ı spoleˇcn´y dˇelitel m a n)
Pozn.: gcd(m, n) je nejvˇetˇs´ı pˇrirozen´e ˇc´ıslo, kter´e dˇel´ı m i n (se zbytem 0).
Pˇr.: gcd(3, 5) = 1, gcd(3, 6) = 3, gcd(12, 18) = 6, atd.
Prvn´ı algoritmus (naivn´ı):
gcd-naive(m, n)
1 t ← min{m, n}
2 while m mod t 6= 0 or n mod t 6= 0
3
do t ← t − 1
4 return t
D˚
ukaz spr´
avnosti gcd-naive(m, n): Zaˇc´ın´a s t = min{m, n}, coˇz je ˇc´ıslo
≥ gcd(m, n). Dokud t nen´ı dˇelitelem obou m i n, hodnota t se sn´ıˇz´ı o 1.
Vr´acen´a hodnota t tedy je gcd(m, n). Vˇzdy se zastav´ı, nejpozdˇeji pro
t = 1, protoˇze 1 dˇel´ı kaˇzd´e m a n.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
39 / 71
Existuje ale lepˇs´ı algoritmus (pozdˇeji vysvˇetl´ıme, v ˇcem “lepˇs´ı”).
gcd-Euclid(m, n)
1 while n 6= 0
2
do r ← m mod n
3
m←n
4
n←r
5 return m
Jak algoritmus pracuje? Pod´ıvejme se nejdˇr´ıve, jak pracuje pro
(m, n) = (84, 24).
Pˇri prvn´ım testu podm´ınky na ˇr. 1 je (m, n) = (84, 24), instrukce cyklu
2–4 se provedou (r ← 12, nebot’ 12 = 84 mod 24; m ← 24; n ← 12).
N´asleduje druh´y test podm´ınky na ˇr. 1 s (m, n) = (24, 12), instrukce 2–4
se provedou (r ← 0, nebot’ 0 = 24 mod 12; m ← 12; n ← 0).
N´asleduje tˇret´ı test podm´ınky na ˇr. 1 s (m, n) = (12, 0), podm´ınka n 6= 0
nen´ı splnˇena, pˇrejde se k instrukci na ˇr. 5 a v´ystupem je 12, coˇz je
skuteˇcnˇe gcd(84, 24).
Rozmyslete, co se stane, je-li na vstupu (m, n) a m < n.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
40 / 71
Algoritmus proch´az´ı dvojice
(m, n), (n, m mod n), (m mod n,n mod (m mod n)), . . . ,
ˇ ıslo p je pak v´ystupem algoritmu.
dokud nen´ı vytvoˇrena dvojice (p, 0). C´
D˚
ukaz spr´
avnosti gcd-Euclid: Je tˇreba uk´azat, ˇze
1. Kaˇzd´e dvˇe po sobˇe n´asleduj´ıc´ı dvojice v posloupnosti maj´ı stejn´y gcd.
2. gcd(p, 0) = p.
3. Algoritmus skonˇc´ı.
Ad 1: Zˇrejmˇe staˇc´ı uk´azat, ˇze pro kaˇzd´a m, n je
gcd(m, n) = gcd(n, m mod n).
Pˇripomeˇ
nme: k dˇel´ı m, pr´avˇe kdyˇz existuje l tak, ˇze m = kl. D´ale m mod n
lze ps´at jako m mod n = m − qn pro vhodn´e pˇrirozen´e ˇc. q. (zkuste na
pˇr´ıkladech a pak zd˚
uvodnˇete).
gcd(m, n) = gcd(n, m mod n) dok´aˇzeme ovˇeˇren´ım, ˇze spoleˇcn´y dˇelitel k
ˇc´ısel m a n je i spoleˇcn´ym dˇelitelem ˇc´ısel n a m mod n a naopak, tj.
spoleˇcn´y dˇelitel ˇc´ısel n a m mod n je i spoleˇcn´ym dˇelitelem ˇc´ısel m a n.
(uvˇedomte si, proˇc to staˇc´ı)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
41 / 71
Je-li k spoleˇcn´ym dˇelitelem m a n, pak m = kl1 a n = kl2 pro nˇejak´a l1 , l2 .
Pak tedy m mod n = m − qn = kl1 − qkl2 = k(l1 − ql2 ), tj. k je dˇelitelem
ˇc´ısla m mod n, a je tedy spoleˇcn´ym dˇelitelem ˇc´ısel n a m mod n.
Je-li k spoleˇcn´ym dˇelitelem n a m mod n, pak n = kl1 a
m mod n = m − qn = kl2 , pro nˇejak´a q, l1 , l2 . Pak tedy
m = qn + kl2 = qkl1 + kl2 = k(ql1 + l2 ), tedy k dˇel´ı m a je spoleˇcn´ym
dˇelitelem ˇc´ısel m a n.
Ad 2: Plyne pˇr´ımo z definice gcd.
Ad 3: Vˇzdy je m mod n < n (zd˚
uvodnˇete). Kdyˇz algoritmus zaˇcne s dvojic´ı
(m, n), kde m > n, splˇ
nuje pˇr´ıpadn´a druh´a dvojice (n, m mod n) podm´ınku
n > m mod n. Prvn´ı prvek druh´e a kaˇzd´e dalˇs´ı dvojice je tedy menˇs´ı neˇz
prvn´ı prvek pˇredchoz´ı dvojice a druh´y prvek kaˇzd´e dvojice je menˇs´ı neˇz jej´ı
prvn´ı prvek. Je zˇrejm´e, ˇze takov´a posloupnost dvojic mus´ı b´yt koneˇcn´a a
jej´ı posledn´ı dvojice m´a tvar (k, 0).
Kdyˇz zaˇcne s dvojic´ı (m, n), kde m = n, je dalˇs´ı dvojic´ı (n, 0) a skonˇc´ı.
Kdyˇz algoritmus zaˇcne s dvojic´ı (m, n), kde m < n, . . . (dokonˇcete sami).
D˚
ukaz je hotov.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
42 / 71
Proˇ
c je gcd-Euclid lepˇs´ı neˇ
z gcd-naive?
Protoˇze m´a menˇs´ı ˇcasovou sloˇzitost.
Co to znamen´a? Uvid´ıme v dalˇs´ım.
Zat´ım zkusme ruˇcnˇe spoˇc´ıtat gcd(84,24).
1. Jak jsme vidˇeli, testuje gcd-Euclid(84, 24) dvojice (84, 24), (24, 12),
(12, 0), pak skonˇc´ı (zhruba ˇreˇceno po 3 kroc´ıch).
2. gcd-naive(84, 24) vˇsak mus´ı sn´ıˇzit hodnotu t 12kr´at (zhruba ˇreˇceno tedy
skonˇc´ı aˇz po 12 kroc´ıch).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
43 / 71
Sloˇ
zitost algoritmu
Popisuje efektivitu algoritmu z hlediska zdroj˚
u, kter´e potˇrebuje.
ˇ
Casov´
a sloˇ
zitost
– Popisuje, jak je algoritmus “rychl´y”, tj. kolik ˇcasu trv´a v´ypoˇcet podle
algoritmu (od zah´ajen´ı po ukonˇcen´ı).
– Tedy popisuje efektivitu algoritmu z hlediska ˇcasu jakoˇzto
vyuˇz´ıvan´eho zdroje.
– Touto sloˇzitost´ı se budeme zejm´ena zab´yvat.
Pamˇ
et’ov´
a (prostorov´
a) sloˇ
zitost
– Popisuje, kolik pamˇeti poˇc´ıtaˇce je tˇreba pro v´ypoˇcet podle algoritmu.
– Tedy popisuje efektivitu algoritmu z hlediska pamˇeti jakoˇzto
vyuˇz´ıvan´eho zdroje.
– Touto sloˇzitost´ı se budeme zab´yvat okrajovˇe. V´ıce bude v pˇredmˇetu
Vyˇc´ıslitelnost a sloˇzitost.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
44 / 71
ˇ
Casov´
a sloˇ
zitost algoritmu
Projdeme u
´vahami, kter´e n´as dovedou ke spr´avn´emu pojmu “ˇcasov´a
sloˇzitost algoritmu”.
Ot´
azka 1: Volba ˇ
casov´
e jednotky.
Je rozumn´e mˇeˇrit trv´an´ı v´ypoˇctu podle algoritmu v sekund´ach?
+ Je to konkr´etn´ı a kaˇzd´y tomu rozum´ı. Viz:
“V´ypoˇcet podle algoritmu A1 pro vstup m = 3681 trval 2.15 sec.”
“V´ypoˇcet podle algoritmu gcd-Euclid pro vstupn´ı ˇc´ısla m = 3680,
n = 260 trval 0.013 sec.”
- Je to pˇr´ıliˇs z´avisl´e na implementaci algoritmu (v jak´em
programovac´ım jazyku a jak kvalitnˇe je naprogramov´an, kvalita
pˇrekladaˇce) a na rychlosti poˇc´ıtaˇce, na kter´em v´ypoˇcet probˇehl.
Probˇehne-li v´ypoˇcet, kter´y na poˇc´ıtaˇci P1 trv´a 15.6 sec, na poˇc´ıtaˇci
P2, kter´y je 100kr´at rychlejˇs´ı neˇz P1, pak na P2 tento v´ypoˇcet trv´a
0.156 sec. Z tohoto pohledu maj´ı v´yˇse uveden´e v´yroky slabou
vypov´ıdac´ı hodnotu, zejm´ena pokud n´am jde o porovn´av´an´ı ˇcasov´e
sloˇzitosti algoritm˚
u.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
45 / 71
Jak tedy vhodnˇe mˇeˇrit trv´an´ı v´ypoˇctu, kter´y prob´ıh´a podle dan´eho
algoritmu?
trv´
an´ı v´
ypoˇ
ctu = poˇ
cet element´
arn´ıch v´
ypoˇ
cetn´ıch krok˚
u vykonan´ych
od zah´ajen´ı do skonˇcen´ı v´ypoˇctu
Element´arn´ım v´ypoˇcetn´ım krokem je obvykle instrukce (instrukce
pseudok´odu nebo instrukce programovac´ıho jazyka ve kter´em je algoritmus
zaps´an).
+ Nen´ı z´avisl´e na rychlosti poˇc´ıtaˇce. Je objektivnˇejˇs´ı neˇz vyj´adˇrit trv´an´ı
v sekund´ach, zejm. jde-li o porovn´an´ı dvou algoritm˚
u. Viz:
“V´ypoˇcet podle algoritmu A1 pro vstup m = 3681 trval 158 krok˚
u.”
“V´ypoˇcet podle algoritmu gcd-Euclid pro vstupn´ı ˇc´ısla m = 84,
n = 24 trval 10 krok˚
u.”
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
46 / 71
- Ned´av´a konkr´etn´ı pˇredstavu, jak dlouho budeme u poˇc´ıtaˇce ˇcekat, neˇz
v´ypoˇcet skonˇc´ı. Proto se v praxi informace o sloˇzitosti vyj´adˇren´e v
poˇctech krok˚
u doplˇ
nuje o informaci o skuteˇcn´em trv´an´ı v´ypoˇctu
vˇcetnˇe toho, na jak´em poˇc´ıtaˇci v´ypoˇcet prob´ıhal.
Poˇcet el. krok˚
u (instrukc´ı) z´avis´ı na tom, jak´y psedok´od nebo
programovac´ı jazyk pouˇz´ıv´ame. Napˇr. instrukci pseudok´odu
swap(a,b),
kter´a zp˚
usob´ı v´ymˇenu hodnot promˇenn´ych a a b, odpov´ıd´a v jazyce C
trojice instrukc´ı
temp = a; a = b; b = temp;.
Uveden´e dvˇe nev´yhody vˇsak nejsou velk´e, v´yhody maj´ı vˇetˇs´ı v´ahu.
Pozn.: Pro zjednoduˇsen´ı nˇekdy uvaˇzujeme jen poˇcet “d˚
uleˇzit´ych” (pro
algoritmus z´akladn´ıch) instrukc´ı, tj. tˇech, kter´e se pˇri v´ypoˇctu vykon´avaj´ı
ˇcasto. Jde typicky o instrukce vykon´avan´e opakovanˇe, napˇr. uvnitˇr cyklu.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
47 / 71
Ot´
azka 2: Je ˇ
casov´
a sloˇ
zitost algoritmu doba trv´
an´ı?
(. . . at’ uˇz mˇeˇr´ıme v sekund´ach nebo poˇctem vykonan´ych instrukc´ı)
M´a napˇr. smysl ˇr´ıci:
ˇ
“Casov´
a sloˇzitost algoritmu je 162 ˇcasov´ych jednotek (sec, krok˚
u).”?
Ne.
M´a smysl ˇr´ıci “V´ypoˇcet podle algoritmu A1 pro vstup m = 3681 trval 2.15
sec.”, ale pˇredchoz´ı v´yrok smysl nem´a. Proˇc?
Protoˇze pro r˚
uzn´e vstupy m´a v´ypoˇcet obvykle r˚
uzn´a trv´an´ı. Trv´an´ı obvykle
z´avis´ı na tzv. velikosti vstupu (Co to je, vysvˇetl´ıme pozdˇeji. Pro pˇredstavu:
ˇ ım vˇetˇs´ı jsou sˇc´ıtan´a ˇc´ısla, t´ım delˇs´ı je trv´an´ı v´ypoˇctu pro jejich seˇcten´ı.).
C´
Rozumnˇejˇs´ı je tedy ch´apat pojem ˇcasov´a sloˇzitost algoritmu jako funkci
(zobrazen´ı) T , jej´ıˇz argumenty n jsou pˇrirozen´a ˇc´ısla vyjadˇruj´ıc´ı velikost
vstupu dan´eho algoritmu a jej´ıˇz hodnotou T (n) pro n je trv´an´ı algoritmu
ve zvolen´ych ˇcasov´ych jednotk´ach (poˇcet instrukc´ı, sekundy).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
48 / 71
ˇ
Dalˇs´ı n´avrh tedy: Casov´
a sloˇzitost algoritmu je funkce T : N → N, jej´ıˇz
hodnoty interpretujeme n´asledovnˇe:
T (n) je doba trv´an´ı v´ypoˇctu podle dan´eho algoritmu pro vstup velikosti n.
Je to ted’ jasn´e? M´a to smysl?
Jeˇstˇe ne zcela.
Vstup˚
u stejn´e velikosti (velikosti n) je obvykle velk´e mnoˇzstv´ı. Kter´y m´ame
na mysli, mluv´ıme-li o dobˇe trv´an´ı pro vstup velikosti n?
Pojem ˇcasov´a sloˇzitost mus´ıme tedy d´ale upˇresnit. To n´as pˇriv´ad´ı ke
dvˇema d˚
uleˇzit´ym pojm˚
um:
ˇ
– Casov´a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe:
T (n) je nejvˇetˇs´ı trv´an´ı v´ypoˇctu podle algoritmu pro vstupy d´elky n.
ˇ
– Casov´
a sloˇzitost v pr˚
umˇern´em pˇr´ıpadˇe:
T (n) je pr˚
umˇern´e trv´an´ı v´ypoˇctu podle algoritmu pro vstupy d´elky n.
Lze uvaˇzovat i ˇcasovou sloˇzitost v nejlepˇs´ım pˇr´ıpadˇe a tzv. amortizovanou
ˇcasovou sloˇzitost. Nebudeme se jimi zab´yvat.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
49 / 71
Ted’ pˇresnˇe. Je d´an probl´em P, jeho vstupy oznaˇcujeme I , algoritmus A
pro dan´y probl´em. Oznaˇcme:
– tA (I ) . . . trv´an´ı v´ypoˇctu podle algoritmu A pro vstup I (ve vhodn´ych
jednotk´ach).
– |I | . . . velikost vstupu I .
Napˇr. poˇcet cifer vstupn´ıch ˇc´ısel u probl´emu sˇc´ıt´an´ı ˇc´ısel v des´ıtkov´e
soustavˇe; poˇcet mˇest u probl´emu hled´an´ı nejkratˇs´ı cesty mezi mˇesty v
s´ıti mˇest; poˇcet prvk˚
u pole, kter´e je tˇreba setˇr´ıdit (pozdˇeji detailnˇe)
atd.
Obecnˇe |I | vhodn´ym zp˚
usobem vyjadˇruje “rozs´ahlost” vstupu I . M˚
uˇze
existovat v´ıce pˇrirozen´ych zp˚
usob˚
u, jak mˇeˇrit rozs´ahlost vstupu (napˇr.
u probl´emu hled´an´ı v s´ıti mˇest to m˚
uˇze b´yt poˇcet mˇest, nebo jinak:
poˇcet spojnic mezi mˇesty). Z´amˇer: chceme, aby tA (I ) pˇrirozenˇe
z´aviselo na |I | (napˇr. tA (I ) = 2 ∗ |I | + 3).
Tedy velikost vstupu je funkce | | : Vst → N (Vst je mnoˇzina
pˇr´ıpustn´ych vstup˚
u probl´emu P).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
50 / 71
Definice
ˇ
Casov´
a sloˇzitost algoritmu A v nejhorˇs´ım pˇr´ıpadˇe
je funkce T : N → N definovan´a takto:
T (n) = max{tA (I ) | I je vstup probl´emu P a |I | = n}.
ˇ
Casov´
a sloˇzitost algoritmu A v pr˚
umˇern´em pˇr´ıpadˇe
je funkce T : N → N definovan´a takto:
T (n) =
tA (I1 ) + · · · + tA (Im )
,
m
kde I1 , . . . , Im jsou vˇsechny vstupy probl´emu P, kter´e maj´ı d´elku n.
Uvid´ıme mnoho pˇr´ıklad˚
u, zejm. sloˇzitosti v nejhorˇs´ım pˇr´ıpadˇe.
(Kter´a sloˇzitost je d˚
uleˇzitˇejˇs´ı?)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
51 / 71
Pˇr´ıklad: sloˇ
zitost algoritmu sˇ
c´ıt´
an´ı v des. soustavˇ
e
Scitani-Cisel-Desitkove(a[0..n − 1], b[0..n − 1])
1 t←0
2 for i ← 0 to n − 1
3
do c[i] ← a[i] + b[i] + t mod 10
4
t ← b(a[i] + b[i] + t)/10c
5 c[n] ← t
Pˇripomeˇ
nme: vstupem I je dvojice ˇc´ısel zapsan´ych v des´ıtkov´e soustavˇe,
z´apis kaˇzd´eho z nich obsahuje n pozic.
1. Co je velikost vstupu |I |, tj. |a[0..n − 1], b[0..n − 1]|?
Poloˇzme |a[0..n − 1], b[0..n − 1]| = n.
(Mohli bychom ale vz´ıt i |a[0..n − 1], b[0..n − 1]| = 2n, zkuste tak´e.)
2. Co je tA (I ), tj. tA (a[0..n − 1], b[0..n − 1])?
Pˇredpokl´adejme, ˇze za element´arn´ı instrukce povaˇzujeme instrukce naˇseho
pseudok´odu a ˇze za trv´an´ı v´ypoˇctu povaˇzujeme poˇcet vykonan´ych
element´arn´ıch instrukc´ı. Bˇehem v´ypoˇctu pro vstup a[0..n − 1], b[0..n − 1]
se provede:
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
52 / 71
1× ˇr´adek 1: 1 instrukce pˇriˇrazen´ı,
n× ˇr´adky 2–4: 1 instrukce na ˇr. 2 (pˇriˇrazen´ı nov´e hodnoty promˇenn´e i), 4
instrukce na ˇr. 3 (2x instrukce +, 1x mod, 1x pˇriˇrazen´ı), 5 instrukc´ı na ˇr. 4
(2x instrukce +, 1x /, 1x b c, 1x pˇriˇrazen´ı), celkem 10n instrukc´ı,
1× ˇr´adek 5: 1 instrukce pˇriˇrazen´ı.
Celkem se tedy provede 10n + 2 instrukc´ı. Tedy
tA (I ) = tA (a[0..n − 1], b[0..n − 1]) = 10n + 2.
Je zˇrejm´e, ˇze tA (I ) = 10n + 2 pro kaˇzd´y vstup I velikosti n.
(U jin´ych algoritm˚
u ale m˚
uˇze pro dva vstupy I1 , I2 se stejnou velikost´ı b´yt
tA (I1 ) 6= tA (I2 ). Pomyslete napˇr. na gcd-Euclid.)
ˇ
Casov´
a sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe je tedy T (n) = 10n + 2.
ˇ
Casov´a sloˇzitost v pr˚
umˇern´em pˇr´ıpadˇe je tak´e T (n) = 10n + 2.
Co se zmˇen´ı, pokud proveden´ı ˇr. 3 budeme povaˇzovat za proveden´ı 1
instrukce?
Co se zmˇen´ı, pokud i proveden´ı ˇr. 4 budeme povaˇzovat za proveden´ı 1
instrukce?
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
53 / 71
Pozn´
amka: velikost ˇ
c´ısla coby vstupu
U probl´emu sˇc´ıt´an´ı ˇc´ısel v des´ıtkov´e soustavˇe je vstup tvoˇren dvˇema
n-ticemi ˇc´ısel. Prvn´ı je an−1 . . . a0 reprezentovan´a v poli a[0..n − 1] (tj.
a[0] = a0 , . . . , a[n − 1] = an−1 ), druh´a je bn−1 . . . b0 reprezentovan´a v poli
b[0..nP− 1] (tj. b[0] = b0 , . . . P
, b[n − 1] = bn−1 ). Vstupem tedy nejsou ˇc´ısla
n
i
A = i=0 −1ai ∗ 10 a B = ni=0 −1bi ∗ 10i reprezentovan´a ˇc´ısly ai a bi .
Proto jsme za velikost vstupu volili n (ale mohli bychom zvolit i 2n).
ˇ
Casto
se objevuje situace, kdy vstupem probl´emu je pˇrirozen´e ˇc´ıslo N.
Pˇrirozen´y zp˚
usob jak mˇeˇrit velikost vstupu pak je:
|N| = poˇcet bit˚
u potˇrebn´ych pro z´apis ˇc´ısla N, tedy
|N| = poˇcet m´ıst z´apisu ˇc´ısla N ve dvojkov´e soustavˇe, tedy
|N| = blog2 Nc + 1
Pˇr´ıklady: |1| = 1 (protoˇze (1)2 = 1), |2| = 2 ((3)2 = 10), |3| = 2
((3)2 = 11), |4| = 3 ((4)2 = 100), |5| = 3 ((5)2 = 101), . . .
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
54 / 71
Zd˚
uvodnˇen´ı:
Kaˇzd´e ˇc´ıslo N je nˇekter´ym z ˇc´ısel 2k−1 , 2k−1 + 1, . . . , 2k − 1 pro vhodn´e k.
To jsou pr´avˇe ˇc´ısla, jejichˇz bin´arn´ı z´apis m´a k m´ıst.
Pr´avˇe pro tato ˇc´ısla plat´ı
blog2 2k−1 c = k − 1, blog2 2k−1 + 1c = k − 1, . . . , blog2 2k − 1c = k − 1.
(Pro N < 2k−1 je blog2 Nc < k − 1, pro N > 2k − 1 je blog2 Nc > k − 1.)
Tedy pro kaˇzd´e M ∈ {2k−1 , 2k−1 + 1, . . . , 2k − 1} plat´ı blog2 Mc + 1 = k.
Tedy speci´alnˇe i pro N plat´ı
blog2 Nc + 1 = k
Pˇr´ıklady k procviˇcen´ı:
1. Jak´y je poˇcet m´ıst z´apisu ˇc´ısla N v des´ıtkov´e soustavˇe (obecnˇeji, v
soustavˇe o z´akladu b)?
2. Oznaˇc´ıme-li |N|b poˇcet m´ıst z´apisu ˇc´ısla N v soustavˇe o z´akladu b, jak´y
je vztah mezi |N|10 a |N|2 ? (Pouˇzijte loga N = loga b · logb N.)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
55 / 71
ˇ
Casto
se vyskytuj´ıc´ı sloˇ
zitosti
Anal´yza sloˇzitosti a odvozen´ı vztahu T (n) = 10n + 2 bylo v tomto pˇr´ıpadˇe
velmi jednoduch´e. U jin´ych algoritm˚
u to je obt´ıˇznˇejˇs´ı, ale v principu stejn´e.
Pˇri anal´yze sloˇzitosti algoritm˚
u se ˇcasto vyskytuj´ı nˇekter´e funkce. Jednou z
nich je 10n + 2. Dalˇs´ımi jsou.
c . . . konstanta
logb n . . . logaritmus o z´akladu b (m´ısto log2 n p´ıˇseme tak´e lg n)
n . . . line´arn´ı (obecnˇeji an + b)
n log n . . . line´arn´ı
n2 . . . kvadratick´a
n3 . . . kubick´a (obecnˇeji an3 + bn2 + cn + d nebo polynomy vyˇsˇs´ıch ˇr´ad˚
u)
n
2 . . . exponenci´aln´ı
n! . . . faktori´al
Proˇc jsou uvedeny v tomto poˇrad´ı? Prozkoumejte jejich chov´an´ı (napˇr. jak
rychle rostou). Vr´at´ıme se k tomu.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
56 / 71
Sloˇ
zitost T (n) jako nositel d˚
uleˇ
zit´
e informace
O ˇcem n´as informuje zpr´ava, ˇze T (n) = 10n + 2, popˇr. T (n) = n2 , popˇr.
T (n) = 2n ?
Struˇcnˇe ˇreˇceno, algoritmus se sloˇzitost´ı T (n) = 10n + 2, popˇr. T (n) = n2
je prakticky pouˇziteln´y.
Algoritmus se sloˇzitost´ı T (n) = 2n je prakticky nepouˇziteln´y.
Proved’me ale zat´ım jednoduchou u
´vahu.
´
Uvaha
1 Uvaˇzujme dva r˚
uzn´e algoritmy, A1 a A2 , pro ˇreˇsen´ı probl´emu
(napˇr. probl´em setˇr´ıdit n-prvkovou posloupnost ˇc´ısel). Pˇredpokl´adejme, ˇze
jejich sloˇztosti jsou
T1 (n) = n2 a T2 (n) = 20n log2 n.
Algoritmy jsou vykon´av´any na poˇc´ıtaˇc´ıch C1 a C2 . C1 je rychl´y, vykon´a
1010 instrukc´ı/sekundu, C2 jen 107 instrukc´ı/sekundu.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
57 / 71
Chceme vyˇreˇsit pro vstup I velikosti 10,000,000 (10 milion˚
u), tj. |I | = 107 .
S pomoc´ı A1 na poˇc. C1 tv´a v´ypoˇcet
(107 )2
= 104 sec = 166min40sec = 2hod46min40sec.
1010
S pomoc´ı A2 na poˇc. C2 tv´a v´ypoˇcet
20 · 107 · log 107
≈ 465sec = 7min35sec.
107
S A2 na 1000kr´at pomalejˇs´ım poˇc´ıtaˇci je v´ypoˇcet cca 21.5 kr´at rychlejˇs´ı.
Z´avˇer: Sloˇzitost algoritmu je skuteˇcnˇe d˚
uleˇzit´a. Zv´yˇsen´ım rychlosti
poˇc´ıtaˇce ji neobejdeme.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
58 / 71
´
Uvaha
2 Jak dlouho trv´a v´ypoˇcet? (Pˇribliˇzn´e) hodnoty nˇekter´ych funkc´ı.
n
log2 n n
n log2 n n2
n3
2n
n!
10
3.3
10
33
100 1000 1024
3628800
100 6.6
100 660
104
106
1.27 · 1030
9.33 · 10157
103 104
106
109
1.07 · 10301
4.02 · 102567
103 10
4
4
5
8
12
3010
10
13
10
1.3 · 10
10
10
1.99 · 10
2.85 · 1035659
105 1.7 · 106 1010 1015
105 17
6
10
20
106 2 · 107
1012 1018
Prob´ıh´a-li v´ypoˇcet na velmi rychl´em poˇc´ıtaˇci, kter´y prov´ad´ı 1015 operac´ı za
sekundu (rychl´y asi jako nejrychlejˇs´ı poˇc´ıtaˇc v souˇcasn´e dobˇe), jsou doby
v´ypoˇct˚
u v sekund´ach n´asleduj´ıc´ı (zaokrouhleno).
n
log2 n n n log2 n n2
n3
2n
n!
10
0
0 0
0
0
0
0
15
100 0
0 0
0
0
1.27 · 10
9.33 · 10142
3
186
10
0
0 0
0
0
1.07 · 10
4.02 · 102552
4
2995
10
0
0 0
0
0.001 1.99 · 10
2.85 · 1035644
105 0
0 0
10−5 1
6
10
0
0 0
0.001 1000
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
59 / 71
Je to pro algoritmy se sloˇzitost´ı 2n a n! tak hrozn´e?
Jak dlouho je napˇr. 2.85 · 1035644 sec? (trv´an´ı pro n = 104 pˇri sloˇzitosti n!)
Rok m´a pr˚
umˇernˇe 31,556,926 sekund. Je to tedy
2.85 · 1035644 /31556926 ≈ 9 · 1035636 let!
Doba existence planety Zemˇe 4.54 · 109 let. Tedy v´ypoˇcet je cca
2 · 1035627 kr´at delˇs´ı neˇz doba existence naˇs´ı planety!
V´ysledku v´ypoˇctu se nikdy nedoˇck´ame!
Co prvn´ı v´yznamn´e (nenulov´e) trv´an´ı pro sloˇzitosti 2n a n!?
Pro n = 100 a T (n) = 2n je doba v´ypoˇctu 4 · 107 let, tj. 40 mili´on˚
u let
(pˇred 65 mil. lety vyhynuli dinosauˇri).
Ani v tomto pˇr´ıpadˇe se v´ysledku nikdy nedoˇck´ame.
Tomuto jevu se ˇr´ık´a “curse of exponential complexity” (proklet´ı
exponenci´aln´ı sloˇzitosti, R. Bellman pouˇzil podobn´y pojem “curse of
dimensionality”).
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
60 / 71
Poˇ
c´ıtaˇ
ce vˇ
cera, dnes a z´ıtra
ˇ
VCERA
– prvn´ı poˇ
c´ıtaˇ
c:
ENIAC (Electronic Numerical Integrator And Computer)
– 1946
– prvn´ı obecnˇe programnovateln´y poˇc´ıtaˇc v´ypoˇcetnˇe ekvivalentn´ı tzv.
Turingovu stroji (obecnˇe programovateln´y)
– Univ. Pennsylvania, USA (US Army projekt, $6 mil. v dneˇsn´ı hodnotˇe)
– 27 tun, plocha 63 m2 , pˇr´ıkon 150kW
– 380 operac´ı n´asoben´ı za sekundu
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
61 / 71
DNES - nejrychlejˇs´ı poˇ
c´ıtaˇ
c na svˇ
etˇ
e
Jak se mˇeˇr´ı rychlost?
– v jednotk´ach FLOPS (FLoating point Operations Per Second, tj.
poˇcet operac´ı s plovouc´ı ˇr´adovou ˇc´arkou za sekundu)
– mˇeˇr´ı se speci´aln´ım testem zahrnuj´ıc´ım v´ypoˇcet tzv. LU rozkladu velk´e
matice
– TF TFLOPS (teraFLOPS) = 1012 FLOPS, PFLOPS (petaFLOPS) =
1015 FLOPS, EFLOPS (exaFLOPS) = 1018 FLOPS
– od r. 1993 existuje seznam TOP500 (aktualizov´an 2x roˇcnˇe, pˇri Int.
Supercomputing Conference a ACM/IEEE Supercomputing
Conference)
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
62 / 71
nejrychlejˇs´ı poˇc´ıtaˇc (ˇcerven 2010):
Jaguar (v´
yrobce Cray), Oak Ridge Ntnl. Lab., USA, 1.759 PFLOPS
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
63 / 71
Z´ITRA – Moor˚
uv z´
akon
G. E. Moore, *1929, spoluzakladatel Intelu
z´akon popisuj´ıc´ı trend ve v´yvoji hardware:
“poˇcet souˇc´ast´ı integrovan´ych obvod˚
u se
zdvojjn´asob´ı kaˇzd´e dva roky”;
plat´ı pˇribliˇznˇe i pro rychlost poˇc´ıtaˇc˚
u, pamˇet’ apod.
Tedy: Parametry hardware se zlepˇsuj´ı velmi rychle.
Pozor na pˇredpovˇedi. Ukazuj´ı naˇse permanentn´ı podceˇ
nov´an´ı v´yvoje.
“It would appear that we have reached the limits of what it’s possible to
achieve with computer technology, although one should be careful with
such statements, as they tend to sound pretty silly in five years.”
—John von Neumann, 1949
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
64 / 71
“I think there is a world market for maybe five computers.”
—Thomas J Watson, President of IBM, 1943
“Computers in the future will weigh no more than 1.5 tons.”
—Popular Mechanics, 1949
“I have travelled the length and breadth of this country and talked with
the best people, and I can assure you that data processing is a fad that
won’t last out the year.”
—Editor in charge of business books, Prentice Hall, 1957
“Transmission of documents via telephone wires is possible in principle,
but the apparatus required is so expensive that it will never become a
practical proposition.”
—Dennis Gabor, 1962 (laure´at Nobelovy ceny za holografii)
“There is no reason for any individual to have a computer in his home.”
—Ken Olsen, co-founder of Digital Equipment Corporation, 1977
“640kB should be enough for anyone.”
—Bill Gates, 1981
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
65 / 71
Jak by mohl vypadat dom´ac´ı poˇc´ıtaˇc v roce 2004 (pˇredstava v roce 1954)?
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
66 / 71
´
Cviˇ
cen´ı Udaje
v ˇr´adc´ıch ud´avaj´ı ˇcas t, kter´y m´ame k dispozici. Funkce
f (n) ve sloupc´ıch ud´avaj´ı dobu v´ypoˇctu v milisekund´ach potˇrebnou pro
zpracov´an´ı vstupu o velikosti n. Do kaˇzd´eho pol´ıˇcka (dan´eho ˇcasem t a
funkc´ı f (n)) doplˇ
nte u
´daj, kter´y ud´av´a maxim´aln´ı velikost n vstupu, kter´y
je moˇzn´e zpracovat v ˇcase t pˇri dobˇe v´ypoˇctu dan´e f (n).
Napˇr. pro t =1 sec a f (n) = n je maxim´aln´ı velikost vstupu 1000, protoˇze
takov´y v´ypoˇset trv´a f (1000) = 1000 msec = 1 sec.
ˇcas
1 sec
1 min
1 hod
1 den
1 mˇes.
1 rok
1 stolet´ı
log2 n
Radim Bˇ
elohl´
avek (UP)
n
1000
n log2 n
n2
n3
Algoritmick´
a matematika 1
2n
n!
ZS 2014/15
67 / 71
´
Uvaha
3 Pom˚
uˇze technologick´y pokrok?
Jak se zvˇetˇs´ı velikost vstupu, kter´y jsme za danou dobu (kterou m˚
uˇzeme
ˇcekat) schopni algoritmem zpracovat, zvyˇsuje-li se rychlost poˇc´ıtaˇc˚
u
kaˇzd´ym rokem dvojn´asobnˇe?
ˇ se rychlost poˇc´ıtaˇc˚
Ze
u zvyˇsuje kaˇzd´ym rokem dvojn´asobnˇe (to odpov´ıd´a
ˇ potˇrebn´y k proveden´ı jedn´e instrukce
Mooreovu z´akonu), znamen´a, ˇze Cas
v roce r + 1 je 2kr´at menˇs´ı neˇz v roce r (jin´ymi slovy, za danou ˇcasovou
jednotku poˇc´ıtaˇc vykon´a v roce r + 1 je 2kr´at v´ıce instrukc´ı neˇz v roce r ).
Oznaˇcme
tmax . . . doba, kterou m˚
uˇzeme ˇcekat (napˇr. 5 min, 2 hod, 10 ms)
nmax (r ) . . . max. velikost vstupu, kter´y jsme schopni zpracovat (v roce r )
f (n) . . . ˇcasov´a sloˇzitost algoritmu (poˇcet instrukc´ı).
Jak velk´y vstup jsme schopni zpracovat v roce r + 1, tj. jak´y je nmax (r )?
Uvaˇzme pro f (n) = n (line´arn´ı) a f (n) = 2n (exponenci´aln´ı).
Doba v´ypoˇctu pro vstup velikosti n je f (n) · cr , kde cr je ˇcas potˇrebn´y k
proveden´ı jedn´e instrukce v roce r .
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
68 / 71
f(n) = n: nmax (r + 1) = 2nmax (r ), tedy po roce budeme schopni
zpracovat dvakr´at vˇetˇs´ı vstup (“dvakr´at v´ıce dat”).
Proˇc? nmax (r ) je nejvˇetˇs´ı n, pro kter´e n · cr ≤ tmax . Hled´ame nmax (r + 1),
tj. nejvˇetˇs´ı n, pro kter´e n · cr +1 ≤ tmax , tedy (protoˇze cr +1 = 21 cr ) pro kter´e
n · 21 cr ≤ tmax . Je jasn´e, ˇze t´ım je 2nmax (r ), tj. nmax (r + 1) = 2nmax (r ).
Snadno tak´e vid´ıme, ˇze nmax (r + k) = 2k nmax (r ), tj. po k letech se
velikost zpracovateln´eho vstupu zv´yˇs´ı 2k kr´at.
f(n) = 2n : nmax (r + 1) = nmax (r ) + 1, tedy po roce budeme schopni
zpracovat jen o jednotku velikosti vˇetˇs´ı vstup.
Proˇc? Stejnou u
´vahou dojdeme k tomu, ˇze nmax (r + 1) je nejvˇetˇs´ı n, pro
kter´e je 2n · 12 cr ≤ tmax , a t´ım je nmax (r ) + 1.
Snadno tak´e vid´ıme, ˇze nmax (r + k) = nmax (r ) + k, tj. po k letech se
velikost zpracovateln´eho vstupu zv´yˇs´ı o k, kaˇzd´y rok jsme schopni
zpracovat data vˇetˇs´ı jen o jednu poloˇzku!
⇒ U algoritm˚
u s exponenci´aln´ı sloˇzitost´ı technologick´y pokrok nepom˚
uˇze.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
69 / 71
Cviˇ
cen´ı (pˇredchoz´ı u
´vaha obecnˇeji) Jak se zvˇetˇs´ı velikost vstupu, kter´y
jsme za danou dobu tmax schopni algoritmem zpracovat, zvˇetˇs´ı-li se
rychlost poˇc´ıtaˇc˚
u za obdob´ı od roku r do roku r 0 d-n´asobnˇe?
V roce r je nejvˇetˇs´ı velikost zpracovateln´eho vstupu nmax (r ), coˇz je tedy
nejvˇetˇs´ı n, pro kter´e f (n) · cr ≤ tmax . D´ale je cr +1 = d1 · cr .
nmax (r 0 ) je nejvˇetˇs´ı n, pro kter´e f (n) · cr 0 ≤ tmax , tj. f (n) · d1 · cr ≤ tmax .
Pˇredpokl´adejme pro jednoduchost, ˇze f (nmax (r )) · cr = tmax a ˇze f m´a
inverzn´ı funkci f −1 .
Pak nmax (r 0 ) je nejvˇetˇs´ı n, pro kter´e f (n) ≤ d · f (nmax (r )), tedy
n ≤ f −1 (d · f (nmax (r ))).
Pro f (n) = 2n :
n ≤ lg(d · 2nmax (r ) ) = lg d + nmax (r ), tj. nmax (r 0 ) = blg d + nmax (r )c.
Pro fp
(n) = np :
√
√
p
n ≤ d · nmax (r )p = p d · nmax (r ), tj. nmax (r 0 ) = b p d · nmax (r )c.
Radim Bˇ
elohl´
avek (UP)
Algoritmick´
a matematika 1
ZS 2014/15
70 / 71
Pˇredpokl´adejme opˇet f (nmax (r )) · cr = tmax . Doplˇ
nte hodnoty nmax (r 0 ) do
n´asleduj´ıc´ı tabulky.
d
1
2
4
10
100
1000
106
10p
2p
log2 n
n
Radim Bˇ
elohl´
avek (UP)
n log2 n
n2
n3
2n
Algoritmick´
a matematika 1
n!
ZS 2014/15
71 / 71
Download

Algoritmická matematika 1 - Radim Belohlavek