Algoritmick´ a matematika 1 ˇ c´ ast 1 ˇ ´ Radim BELOHL AVEK Katedra informatiky Univerzita Palack´eho v Olomouci
Radim Bˇ elohl´ avek (UP)
Algoritmick´ a matematika 1
ZS
1 / 71
Z´ akladn´ı informace – webov´ e str´ anky – http://belohlavek.inf.upol.cz/vyuka/alm1-2015-16.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
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
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
4 / 71
Algoritmy z´ akladn´ı u ´vahy
Radim Bˇ elohl´ avek (UP)
Algoritmick´ a matematika 1
ZS
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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 . . . logaritmicko line´arn´ı (log-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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
71 / 71
