Algoritmicka matematika 1

cast 1

Radim BELOHLAVEK

Katedra informatikyUniverzita Palackeho v Olomouci

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 1 / 79

Zakladn informace

webove stranky http://belohlavek.inf.upol.cz/vyuka/alm1-2015-16.html

(predmet) http://belohlavek.inf.upol.cz/ (prednasejc) dals (cvicc, STAG, katedra informatiky)

studium prednasky (vede prednasejc) cvicen (vede a podmnky urcuje cvicc) konzultacn hodiny (vyuzvat) samostante studium (studium literatury, promyslen problemu,

prakticke u poctace)

absolvovan predmetu zapocet (udel cvicc, zskat alespon 60% bodu za zadanych ukolu: 1

psemny test, 1 program) zkouska (vypsane predtermny a termny)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 2 / 79

http://belohlavek.inf.upol.cz/vyuka/alm1-2015-16.htmlhttp://belohlavek.inf.upol.cz/

Charakteristika predmetu, doporucen

co je obsahem predmetu zakladn algoritmy a datove struktury v informatice navrh, analyza a implementace

charakter predmetu jeden z nejdulezitejsch predmetu pro informatiky vyzaduje schopnost kombinatorickeho uvazovan nen primarne predmetem o programovan, ale schopnost programovat

je potrebna k procvicovan nen typickym matematicky predmetem, ale presnost matematickeho

uvazovan je zde typicka souvisejc predmety: Paradigmata programovan 1, Uvod do

programovan 1

rady pro studium chodit na predasky a cvicen (setr cas studia, rozpozna dulezite od

mene duleziteho) implementovat probrane algoritmy (programovat, > 10 hod./tyden) snazit se veci pochopit do hloubky, neucit se zpameti (behem studia se

temata v obmenach opakuj, pochopen na zacatku studium usnadn) prprava na zkousku (individualn, 2 dny je malo, sps tyden)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 3 / 79

Dals informace

na katedre moznost zapojit se do studentskych soutez moznost zapojit se do vyzkumu moznost studentskych zahranicnch pobytu

chyby v tomto studijnm textu hlaste mi prosm osobne nebo e-mailem

bonus zkousku se znamkou vybornezska ten, kdo prokazatelne prispeje

originalnm vysledkem k rozvoji oblasti algoritmu (posuzujeprednasejc)

napr. novy algoritmus prinasejc zlepsen oproti soucasnemu stavu,novy vysledek o slozitosti algoritmu (teoreticky nebo experimentaln)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 4 / 79

Algoritmyzakladn uvahy

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 5 / 79

Co je to algoritmus?

Prvn priblzen (definice):Algoritmus je posloupnost instrukc pro resen problemu.

Tato definice je nepresna (tedy to vlastne nen definice):

Co je to problem?

Co je to instrukce?

Co to znamena resit problem?

Nazorne ale vystihuje podstatu pojmu algoritmus.

Existuje rada podobnych definic pojmu algoritmus, vce ci menerozsahlych a prp. pridavajcch dals omezen. Napr.

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, orperspicuity, and that sooner or later comes to an end.D. Berlinsky, The Advent of the Algorithm

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 6 / 79

Tedy, co je to problem, instrukce, resit problem?

ProblemV beznem zivote hovorme napr. o nasledujcch problemech:

1. Problem zaparkovan auta.

2. Problem vypoctu resen linearn rovnice (tj. rovnice tvaru ax + b = 0).

3. Problem zjisten, zda dane prirozene cslo n je prvocslo.

4. Izraelsko-palestinsky problem.

5. Problem jak zt smysluplny zivot.

1, 2, 3 jsou prklady problemu, o kterych se hovor v definici algoritmuuvedene drve a ktere nas budou v dalsm zajmat. Problemy 4 a 5 ne.

Problem (napr. problem 1, 2 nebo 3) je popsan (zadan, specifikovan):

mnozinou prpustnych zadan (vstupu),

prirazenm (predpisem, zobrazenm), ktery pro kazde prpustne zadan(vstup) rka, jake je odpovdajc (tj. spravne) resen (vystup).

Problem se nekdy prmo chape jako prirazen, ktere kazdemu prpustnemuvstupu prirazuje odpovdajc vystup.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 7 / 79

Takove pojet (problem = mnozina prpustnych vstupu a prirazen) davapomerne presne vymezen pojmu problem, ktere nam zatm stac.

Prklady:

1. Problem zaparkovan auta.Prpustnym vstupem je popis S pocatecn dopravn situace (zahrnujepolohu auta, ktere je treba zaparkovat, popis okoln situace vcetnemsta, kam je treba zaparkovat).Prirazen specifikuje pro kazdy S popis spravne koncove situace T (tj.ve ktere je auto spravne zaparkovano).(Popisy S a T mohou byt znacne komplikovane.)

2. Problem vypoctu resen linearn rovnice.Prpustne vstupy jsou dvojice a, b racionalnch csel a a b.Prirazen rka, ze vystupem odpovdajcm vstupu a, b je

cslo c , pro ktere ac + b = 0, pokud a 6= 0,text Kazde cslo je resenm, pokud a = 0 a b = 0.text Nema resen, pokud a = 0 a b 6= 0.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 8 / 79

3. Problem zjisten, zda dane prirozene cslo n je prvocslo.Prpustne vstupy jsou prirozena csla n.Prirazen rka, ze vystupem odpovdajcm vstupu n je

Ano, pokud n je prvocslo,Ne, pokud n nen prvocslo.

Problemy 2 a 3 jsou typicke prklady problemu, kterymi se budemezabyvat. Zkraceny popis problemu:

problem (nazev problemu)vstup: popis prpustneho vstupuvystup: popis odpovdajcho vystupu

Prklad:

problem (test prvocselnosti)vstup: prirozene cslo nvystup: Ano, pokud n je prvocslo; Ne, pokud n nen prvocslo.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 9 / 79

InstrukceInstrukce je jednoznacny srozumitelny pokyn jako napr.:

Seslapni brzdovy pedal.

Secti csla a a b. (aritmeticka instrukce)

Do promenne x uloz cslo 5. (instrukce prirazen)

Pokud je C > 0, pak zvys hodnotu b o 1. (podmnena instrukce)

Precti cslo, ktere je na vstupu. (vstupne/vystupn instrukce)

Vytiskni hodnotu promene x . (vstupne/vystupn instrukce)

Pro kazde i = 1, 2, 3, 4, 5 postupne proved: vytiskni hodnotu i2

(instrukce cyklu; v tele cyklu je vstupne/vystupn instrukce)

Pojem instrukce (opet nepresne definovany) vychaz z predstavy, ze existujenekdo, napr. clovek (nebo neco, napr. poctac), kdo (co) instrukcmrozum a je schopen je mechanicky, tj. bez dalsho premyslen, vykonavat.Tento vykonavatel instrukc je schopen vykonavat instrukce tak, jak jsoupredepsany algoritmem (tj. ve spravnem porad).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 10 / 79

Resen problemu algoritmem co to znamena?Algoritmus res dany problem, pokud pro kazdy prpustny vstup I danehoproblemu, jemuz odpovda vystup O (tj. O je spravny vystup pro vstup I )plat:Vykonavan instrukc podle algoritmu se vstupem I se po urcite dobe (pokonecnem poctu kroku) zastav a na vystupu je O.

Tj. vykonavanm instrukc podle algoritmu se od vstupu I po konecnempoctu kroku dobereme k O.

Rkame, ze algoritmus se pro vstup I zastav s vystupem O.

Pritom se predpoklada, ze vstup I je na zacatku vykonavan instrukczapsan na dohodnutem vstupnm zarzen (soubor na disku, je zadan zklavesnice apod.) a ze vystup se objev na dohodnutem vystupnm zarzen(soubor na disku, obrazovka apod.).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 11 / 79

Zpet k problemu vypoctu resen rovnice ax + b = 0

Posloupnost instrukc 1:Pokud a 6= 0, zapis na vystup cslo b/a.Pokud a = 0 a b = 0, zapis na vystup Kazde cslo je resenm.Pokud a = 0 a b 6= 0, zapis na vystup Nema resen.

Posloupnost instrukc 2:Pokud a 6= 0, zapis na vystup cslo b/a, jinak zapis cslo b/a.

Posloupnost instrukc 3:Dokud a 6= 0, provadej: zvys hodnotu b o 1.Pokud a = 0 a b 6= 0, zapis na vystup Nema resen.

Posloupnost 1 je algoritmus pro resen daneho problemu. (Velmijednoduchy algoritmus pro velmi jednoduchy problem. Dals budouslozitejs.)Posloupnosti 2 a 3 ne (2 nedava spravne vystupy, 3 se pro nektere vstupynezastav).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 12 / 79

Za algoritmy nelze povazovat ani nasledujc posloupnosti:

Posloupnost 4:Zkus odhadnout resen.Vyzkousej, zda je spravne.Pokud ano, zapis ho na vystup.Pokud ne, zpresni odhad a jdi dal.

Nen to algoritmus, protoze nen jasne, jak postupovat.

Posloupnost 5:Spust na PC program Mathematica.Vyres v nem rovnici.Vysledek zapis na vystup.

Nen to algoritmus, odvolava se na zarzen (jeho existence a dostupnost jecasove podmnena), ktere problem vyres.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 13 / 79

Existuje presna definice pojmu algoritmus a dalschpojmu?

Ano. Zabyva se tm informaticka disciplna zvana teorie vycslitelnosti(computability theory).

Poznamenejme, ze existuj ruzne nazory na to, co pojem algoritmus presneznamena, a tedy ruzne definice pojmu algoritmus. Temer vsechny definicelze vsak chapat jako zpresnen vyse uvedene nepresne definice.

Jeste jednou. Nase nepresna definice, ktera rka

Algoritmus je posloupnost instrukc pro resen problemu.

nen vlastne definic. Popisuje intuitivn predstavu o tom, co to jealgoritmus.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 14 / 79

Co rekli o algoritmech

Algorithmics is more than a branch of computer science. It is the core ofcomputer science, and, in all fairness, can be said to be relevant to mostof science, business, and technology.D. Harel, Algorithmics: The Spirit of Computing, 1992

Two ideas lie gleaming on the jewelers velvet. The first is the calculus, thesecond the algorithm. The calculus and the rich body of mathematicalanalysis to which it gave rise made modern science possible; but it hasbeen the algorithm that has made possible the modern world.D. Berlinski, The Advent of the Algorithm, 2000

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 15 / 79

Co rekli o pojmu algoritmus

A person well-trained in computer science knows how to deal withalgorithms: how to construct them, manipulate them, understand them,analyze them. This knowledge is preparation for much more than writinggood computer programs; it is a general-purpose mental tool that will be adefinite aid to understanding other subjects, whether they be chemistry,linguistics, or music, etc. The reason for this may be understood in thefollowing way: It has often been said that a person does not reallyunderstand something until after teaching it to someone else. Actually, aperson does not really understand something until after teaching it to acomputer, i.e., expressing it as an algorithm. . . . An attempt to formalizethings as algorithms leads to a much deeper understanding than if wesimply try to comprehend things in the traditional way.D. E. Knuth, Selected Papers on Computer Science, 1996

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 16 / 79

Donald E. Knuth

Professor Emeritus of The Art of Computer ProgrammingStanford Universityhttp://www-cs-faculty.stanford.edu/~uno/

jeden z nejvyznamnejsch informatikuautor nekolikasvazkoveho dlaThe Art of Computer Programmingautor systemu TEX

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 17 / 79

http://www-cs-faculty.stanford.edu/~uno/

Nekolik zasadnch fakt o algoritmech a problemech

... ke kterym se budeme v tomto predmetu i v dalsch predmetech vracet.

Je kazdy problem resitelny algoritmem?Ne, existuj prirozene problemy, ktere nelze resit zadnym algoritmem(algoritmicky neresitelene).

Ma smysl rkat, ze problemy jsou lehke a tezke, ze nektere problemyjsou lehc nez jine?Ano, zabyva se tm teorie vycslitelnosti.

Ma klasifikace problemu podle obtznosti nejaky prakticky vyznam?Ano, zakladn je delen algoritmicky resitelnych problemu na rychleresitelne a ty, pro ktere rychly algoritmus nen znam. Praktickyvyznamne jsou oba typy problemu.

Lze o algoritmech rkat, ze jeden je leps (efektivnejs) nez druhy?Ano, zabyva se tm teorie slozitosti a je to prakticky velmi dulezite.Budeme se tm zabyvat i v tomto predmetu.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 18 / 79

To vypada zajmave, ale asi to bude narocne nastudovat. Da se to abudu vsemu rozumet?Ano, da se to. Prosly tm stovky jinych. Ne vsemu je treba rozumetdo nejmensch detailu. Neco je treba pochopit hloubeji, nekde stacpochopit zakladn principy.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 19 / 79

Jak popsat (specifikovat) algoritmus?

Budeme se zabyvat zejm. algoritmy, ktere jsou urceny pro poctac (tj.instrukce vykonava poctac). Zakladn zpusoby popisu takovych algoritmujsou:

Prirozenym jazykem. To jsme uz videli.+: Snadno srozumitelne i laikum.: Muze byt nejednoznacne. Zdlouhave.

Programovacm jazykem. Budeme pouzvat jazyk C (ale je moznepouzt jakykoli programovac jazyk).

+: Jednoznacne.+: Vytvorit poctacovy program je pak snadne (temer ho mame). Rozum

tomu programatori.: Obsahuje i zbytecne (nepodstatne) detaily. Dlouhe.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 20 / 79

Pseudokodem. Pseudokod je jazyk blzky programovacmu jazyku, aleje uspornejs, protoze neobsahuje tolik podrobnost. Budeme pouzvatpseudokod z knihy Cormen et al.: Introduction to Algorithms, 2nd Ed.MIT Press, 2001.

+: Je snadno pochopitelny i pro ty, kter nemaj zkusenosti sprogramovanm a programovacmi jazyky. Je vytvoreny prmo prosrozumitelny a usporny popis algortmu. Umoznuje snadny prepis doprogramovacch jazyku.

: Snad to, ze pri implementaci algoritmu je treba ho prepsat doprogramovacho jazyka.

Dalsmi (polo)formalnmi prostredky (vyvojove diagramy, . . . ).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 21 / 79

Algoritmus sctan v destkove soustave

sctan prirozenych csel v destkove soustave (zakladn skola)

1 0 9 3+ 2 3 4 5

3 4 3 8

protoze:postupujeme zprava (od posledn cifry) doleva3 + 5 = 8 napseme 8 a prenasme 09 + 4 = 13 napseme 3 a prenasme 11 + 0 + 3 = 4 napseme 4 a prenasme 01 + 2 = 3 napseme 3 a prenasme 0

podobne

9 7 2 8+ 2 3 9 9

1 2 1 2 7,

1 0+ 2 5

3 5,

0 0 1 3+ 8 6 8 2

8 6 9 5

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 22 / 79

Popisme presne reseny problem.

problem (sctan v destkove soustave):vstup: an1an2 a1a0, bn1bn2 b1b0,kde ai , bi jsou cslice z mnoziny {0, 1, . . . , 9}vystup: cncn1 c1c0,(posloupnost), ktera je zapisem v destkove soustave csla A + B, kde A aB jsou csla jejichz zapisy jsou posloupnosti an1 a0 a bn1 b0Poznamky:

Prvky n-prvkove posloupnosti indexujeme pomoc 0, 1, . . . , n 1, a ne1, 2, . . . , n (byva to vyhodnejs, uvidme).

Msto ai take pseme a[i ] (tak se to pse v programovacch jazycch).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 23 / 79

Popis v prirozenem 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] naa[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.

Vidme, ze popis v prirozenem jazyku je tezkopadny a neprehledny.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 24 / 79

Jiny popis v prirozenem jazyku

1. Nastav t na 0.

2. Pro hodnoty i od 0 do n 1 provadej postupne: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.

Zaradili jsme konstrukci zvanou cyklus (Pro hodnoty i od . . . ). Stale tonen ono.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 25 / 79

Popis v pseudokodu

Scitani-Cisel-Desitkove(a[0..n 1], b[0..n 1])1 t 02 for i 0 to n 13 do c[i ] a[i ] + b[i ] + t mod 104 t b(a[i ] + b[i ] + t)/10c5 c[n] t

Poznamenejme:

amod n je zbytek po delen csla a cslem npr.: 5 mod 2 = 1, 12 mod 10 = 2, . . .

bac je nejvets cele cslo, ktere je ab0.5c = 0, b1.2c = 1, b1.0c = 1, . . .

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 26 / 79

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 prehledne (a srozumitelne) jako pseudokod.Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 27 / 79

Shrnut

Probrali jsme:

pojem algoritmus

pojmy problem, instrukce, resen problemu algoritmem

prklady problemu

prklady algoritmu

jak popsat algoritmus

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 28 / 79

Zakladn instrukce pouzvane v algoritmech

prirazen

aritmeticke instrukce a vyrazy

logicke instrukce a vyrazy

podmneny prkaz

cykly

dals

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 29 / 79

prirazen:

1 i 12 j i + 1

1 i 12 i i i

1 i 12 i i i

1 i 12 i i i3 i 5

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 30 / 79

aritmeticke instrukce a vyrazy:

+ (sctan), (odctan), (nasoben), / (delen),

x mod y (zbytek po delen csla x cslem y):5mod 2 = 1, 5mod 3 = 2, 6mod 2 = 0

prpadne dals

prklady:

1 p 72 q p p + 2 p 8

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 31 / 79

logicke instrukce a vyrazy:

and (konjunkce, logicke a),or (disjunkce, logicke nebo)

= (test na rovnost hodnot), nebo ! = (test na nerovnost hodnot),< (porovnan dle velikosti, napr. csel),

i = 5 (test na rovnost hodnoty promenne i a hodnoty 5, vysledkem jelogicka hodnota pravda, nebo nepravda)

2 < j , 2 j 6, apod.

(i = 5) and (j < 10)(ma hodnotu pravda, prave kdyz maj oba vyrazy i = 5 i j < 10 hodnotupravda)

(i = 5) or (j < 10)(ma hodnotu pravda, prave kdyz ma aspon jeden z vyrazu i = 5 a j < 10hodnotu pravda)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 32 / 79

podmneny prkaz:

if-then: prkaz se vykona, pokud je splnena podmnka:1 if i = 0 then print(Hodnota je 0.)

if-then-else: pokud podmnka nen splnena, vykona se prkaz za else1 if i = 0 then print(Hodnota je 0.)2 else print(Hodnota nen 0.)

1 if i = 0 then print(Hodnota je 0.)2 else if i = 1 then print(Hodnota je 1.)3 else print(Hodnota nen ani 0, ani 1.)

Odsazenm textu vyjadrujeme logickou strukturu programu:1 if i = 0 then print(Hodnota je 0.)2 print(Jeste jednou: hodnota je 0.)3 else print(Hodnota nen 0.)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 33 / 79

cyklus for:cyklus s rdic promennou (ctacem)

1 for i 0 to n do2 print(i)

1 for i 1 to 9 do2 for i 1 to 9 do3 print(i)4 print()5 print(j)6 print(=)7 print(i j)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 34 / 79

cyklus while-do:vykonava se, dokud plat podmnka za slovem while

1 i 12 while i < 10 do3 print(i i)4 i i + 1

1 nactiPole(a[0..9])2 i 03 while (a[i ] 0 and i < 10) do4 print(i)5 i i + 1

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 35 / 79

cyklus repeat-until:vykonava se, dokud nen splnena podmnka za slovem until(vykona se aspon jednou)

1 i 02 repeat3 i i + 13 print(i i)4 until i = 10

1 i 12 repeat3 read(i)4 if i mod 2 = 0 then print(Zadal jsi sude cslo.)5 else print(Zadal jsi liche cslo.)6 until i = 0

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 36 / 79

Zakladn otazky o algoritmech

Spravnost algoritmu:Je dan problem. Skonc navrzeny algoritmus pro kazdy prpustnyvstup problemu po konecnem poctu kroku a se spravnym vystupem?Tj. jde vubec o algoritmus pro dany problem?Pro kazdy navrzeny algoritmus je treba overit (dokazat), zda jespravny. Jinak muze hrozit vazne riziko (rzen slozitychsystemuelektrarna, ABS system u aut, . . . ).Zda je algoritmus spravny, je nekdy snadno videt, muze to ale bytnarocne.

Slozitost algoritmu:Jak dlouho trva vykonavan algoritmu (tj. jaka je jeho casovaslozitost)?Kolik pameti algoritmus potrebuje (tj. jaka je jeho pametovaslozitost)?Slozitost nam dava informaci o tom, jak je algoritmus kvalitn aumoznuje ho z tohoto pohledu porovnat s jinymi algoritmy.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 37 / 79

Optimalita algoritmu:Existuje leps algoritmus?Pro nektere algoritmy lze dokazat, ze leps neexistuj, tedy nemasmysl je hledat. (Co to ale znamena leps? Je treba rozebrat.)

Nyn vysvetlme intuitivne a na prkladech.Pozdeji se k tomu vratme a vysvetlme presne.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 38 / 79

Spravnost algoritmu prklad

Scitani-Cisel-Desitkove(a[0..n 1], b[0..n 1])1 t 02 for i 0 to n 13 do c[i ] a[i ] + b[i ] + t mod 104 t b(a[i ] + b[i ] + t)/10c5 c[n] t

Jak dokazeme spravnost naseho algoritmu?V tomto prpade je to snadne (nekdo by rekl zbytecne). Pro uplnost todokazme (kdyz se to na zaklad skole neudela, deti se uc algoritmusnazpamet bez pochopen).

Tvrzen Algoritmus Scitani-Cisel-Desitkove je spravny.

Dukaz Cslo A si predstavme jako A koralku. Zapisua[n 1]a[n 2] a[0] csla A v destkove soustave odpovda nasledujcusporadan koralku (usporadan se snadneji namaluje nez slovne popisuje).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 39 / 79

Krok 1: Koralky navlekame na nit po 10 (nit s 10 koralky svazeme arkame j svazek). Tak zskame nekolik svazku (kazdy ma 10 koralku) azbyde prave a[0] nenavlecenych koralku. (Udelejte si prklad, pro A = 123zskame 12 svazku a 3 koralky zbydou). Zbyle koralky dame stranou.

Krok 2: Postupujeme dal tak, ze k sobe svazujeme vzdy 10 svazkuzskanych v predchozm kroku. Tak zskame nekolik vetsch svazku (kazdyma 100 koralku) a zbyde prave a[1] nesvazanych svazku o 10 koralcch.(Pro A = 123 zskame 1 svazek o 100 koralcch a zbydou 2 svazky o 10koralcch). Zbyle svazky dame stranou.

Postupujeme dal, az dojdeme do kroku n, ve kterem zbyva mene nez 10svazku s 10n1 koralky. Pocet techto svazku je prave a[n 1]. (ProA = 123 tak dojdeme do kroku 3, ve kterem zbyva 1 svazek o 100koralcch.)

Tak si predstavme i cslo B.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 40 / 79

Svazky koralku a koralky, ktere jsme zskali z A koralku predstavujcchcslo A a B koralku predstavujcch cslo B dame k sobe. Zskame takC = A + B koralku. Abychom zskali usporadan techto koralku, ktereodpovda zapisu C v destkove soustave, musme je spravne usporadat.

Protoze koralky jiz jsou usporadane ve svazcch, dojdeme k pozadovanemuusporadan nasledovne.

Dame dohromady jednotlive koralky (je jich a[0] + b[0]). Je-li jich alespon10, vytvorme novy svazek o 10 koralcch. Koralky, ktere nejsou v novemsvazku, dame stranou, novy svazek ponechame. Je jasne, ze stranou damea[0] + b[0] mod 10 koralku a ze vznikne b(a[0] + b[0])/10c novych svazku(zadny nebo jeden). To jsou prave csla prirazena c[0] a t na radcch 3 a 4v kroku pro i = 0.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 41 / 79

V obecnem kroku pro i dame dohromady svazky s 10i koralky (je jicha[i ] + b[i ] + t, kde t je pocet novych svazku vytvorenych v predchozmkroku). Je-li jich alespon 10, vytvorme novy svazek o 10i+1 koralcch.Svazky o 10i koralcch, ktere nejsou v novem svazku, dame stranou, novysvazek ponechame. Je jasne, ze stranou dame a[i ] + b[i ] + t mod 10 svazkua ze vznikne b(a[i ] + b[i ] + t)/10c novych svazku (zadny nebo jeden). Tojsou prave csla prirazena c[i ] a t na radcch 3 a 4 v kroku pro i .

Tak dojdeme az k i = n, kdy opustme cyklus a kdy zbyvab(a[n 1] + b[n 1] + t)/10c svazku o 10n koralcch. To je spravnahodnota c[n] je to take hodnota prirazena c[n] na radku 5.

Dukaz je hotov.

Msto

Tvrzen Algoritmus Scitani-Cisel-Desitkove je spravny.

Dukaz . . .budeme psat jenDukaz spravnosti Scitani-Cisel-Desitkove . . .

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 42 / 79

Je dukaz spravnosti nutny?

Ano. U mnoha algoritmu je ale spravnost zrejma, takze dukaz odbydemeslovy Je zrejmy.

Dukazem spravnosti nen, kdyz ukazeme, ze algoritmus spravne funguje pronekolik zvolenych vstupu (nemus totiz spravne fungovat pro dals vstupy).

U jinych algoritmu je dukaz spravnosti komplikovany. Kdyz chcemealgoritmus jen pouzt, nemusme dukaz spravnosti cst, pokud algoritmusprevezmeme z duveryhodneho zdroje (napr. kniha o algoritmech).

V tomto predmetu se ale spravnost algoritmu budeme zabyvat.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 43 / 79

Dukaz spravnosti muze mt mnoho podob

Jina podoba dukazu spravnosti Scitani-Cisel-Desitkove (hutna verze,muzete preskocit):

Je A =n1

i=0 a[i ] 10i , B =n1

i=0 b[i ] 10i , tedy pro C = A + B a jehozapis C =

n1i=0 c[i ] 10i 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),

coz jsou prave hodnoty obdrzene nasm algoritmem.

Vzdy je treba najt vhodny kompromis mezi strucnost a srozumitelnost.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 44 / 79

Kdyz navrzeny algoritmus nen spravny

Co kdyz navrzeny algoritmus nen spravny? Jak to prokazu?

Musme najt prklad, pro ktery algoritmus skonc s nespravnym vystupem(tzv. protiprklad). Tj. najt prpustny vstup I , pro ktery je spravnymvystupem O, ale pro ktery algoritmus skonc s vystupem O 6= O neboneskonc vubec.

Prklad (nespravny algoritmus pro hledan nejkrats cesty)Je dana st mest, nektera jsou spojena silnic, jsou dana mesta Z (zacatek)a K (konec). Jak najt nejkrats cestu z Z do K?Prpustnym vstupem je tedy popis ste mest (napr. ve forme pouzite nze) advojice mest Z a K ; odpovdajcm vystupem je nejkrats cesta ze Z do K .

Navrh algoritmu: Zacnu v Z a jdu do nejblizsho mesta M1, ve kteremjsem jeste nebyl; v M1 postupuji stejne (jdu do nejblizsho mesta M2, vekterem jsem jeste nebyl), az dojdu do K .

Tento algoritmus je nespravny.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 45 / 79

Vstup 1: St

{({A,B}, 1), ({A,D}, 5), ({B,C}, 2), ({C ,D}, 1), ({D,E}, 2)},Z = A,K = E .({A,B}, 1) znamena, ze mezi A a B je silnice delky 2, atd. Algoritmusnajde cestu A,B,C ,D,E delky 6 (1 + 2 + 1 + 2). To je skutecne nejkratscesta.

ALEVstup 2: St

{({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 delky 8 (1 + 4 + 1 + 2). To nennejkrats cesta! Nejkrats je A,D,E , ma delku 7. Tedy vstup 2 jeprotiprklad (jeden z mnoha moznych), ktery ukazuje, ze navrzenyalgoritmus nen spravny.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 46 / 79

Nejvets spolecny delitel a Eukliduv algoritmus

problem (nejvets spolecny delitel, greatest common divisor)vstup: prirozena csla m, nvystup: gcd(m, n) (nejvets spolecny delitel m a n)

Pozn.: gcd(m, n) je nejvets prirozene cslo, ktere del m i n (se zbytem 0).Pr.: 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 mmod t 6= 0 or nmod t 6= 03 do t t 14 return t

Dukaz spravnosti gcd-naive(m, n): Zacna s t = min{m, n}, coz je cslo gcd(m, n). Dokud t nen delitelem obou m i n, hodnota t se snz o 1.Vracena hodnota t tedy je gcd(m, n). Vzdy se zastav, nejpozdeji prot = 1, protoze 1 del kazde m a n.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 47 / 79

Existuje ale leps algoritmus (pozdeji vysvetlme, v cem leps).

gcd-Euclid(m, n)1 while n 6= 02 do r mmod n3 m n4 n r5 return m

Jak algoritmus pracuje? Podvejme se nejdrve, jak pracuje pro(m, n) = (84, 24).

Pri prvnm testu podmnky na r. 1 je (m, n) = (84, 24), instrukce cyklu24 se provedou (r 12, nebot 12 = 84mod 24; m 24; n 12).Nasleduje druhy test podmnky na r. 1 s (m, n) = (24, 12), instrukce 24se provedou (r 0, nebot 0 = 24mod 12; m 12; n 0).Nasleduje tret test podmnky na r. 1 s (m, n) = (12, 0), podmnka n 6= 0nen splnena, prejde se k instrukci na r. 5 a vystupem je 12, coz jeskutecne gcd(84, 24).

Rozmyslete, co se stane, je-li na vstupu (m, n) a m < n.Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 48 / 79

Algoritmus prochaz dvojice(m, n), (n,mmod n), (mmod n,nmod (mmod n)), . . . ,dokud nen vytvorena dvojice (p, 0). Cslo p je pak vystupem algoritmu.

Dukaz spravnosti gcd-Euclid: Je treba ukazat, ze1. Kazde dve po sobe nasledujc dvojice v posloupnosti maj stejny gcd.2. gcd(p, 0) = p.3. Algoritmus skonc.

Ad 1: Zrejme stac ukazat, ze pro kazda m, n jegcd(m, n) = gcd(n,mmod n).

Pripomenme: k del m, prave kdyz existuje l tak, ze m = kl . Dale mmod nlze psat jako mmod n = m qn pro vhodne prirozene c. q. (zkuste naprkladech a pak zduvodnete).

gcd(m, n) = gcd(n,mmod n) dokazeme overenm, ze spolecny delitel kcsel m a n je i spolecnym delitelem csel n a mmod n a naopak, tj.spolecny delitel csel n a mmod n je i spolecnym delitelem csel m a n.(uvedomte si, proc to stac)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 49 / 79

Je-li k spolecnym delitelem m a n, pak m = kl1 a n = kl2 pro nejaka l1, l2.Pak tedy mmod n = m qn = kl1 qkl2 = k(l1 ql2), tj. k je delitelemcsla mmod n, a je tedy spolecnym delitelem csel n a mmod n.

Je-li k spolecnym delitelem n a mmod n, pak n = kl1 ammod n = m qn = kl2, pro nejaka q, l1, l2. Pak tedym = qn + kl2 = qkl1 + kl2 = k(ql1 + l2), tedy k del m a je spolecnymdelitelem csel m a n.

Ad 2: Plyne prmo z definice gcd.

Ad 3: Vzdy je mmod n < n (zduvodnete). Kdyz algoritmus zacne s dvojic(m, n), kde m > n, splnuje prpadna druha dvojice (n,mmod n) podmnkun > mmod n. Prvn prvek druhe a kazde dals dvojice je tedy mens nezprvn prvek predchoz dvojice a druhy prvek kazde dvojice je mens nez jejprvn prvek. Je zrejme, ze takova posloupnost dvojic mus byt konecna ajej posledn dvojice ma tvar (k , 0).

Kdyz zacne s dvojic (m, n), kde m = n, je dals dvojic (n, 0) a skonc.

Kdyz algoritmus zacne s dvojic (m, n), kde m < n, . . . (dokoncete sami).

Dukaz je hotov.Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 50 / 79

Proc je gcd-Euclid leps nez gcd-naive?

Protoze ma mens casovou slozitost.Co to znamena? Uvidme v dalsm.

Zatm zkusme rucne spoctat gcd(84,24).

1. Jak jsme videli, testuje gcd-Euclid(84, 24) dvojice (84, 24), (24, 12),(12, 0), pak skonc (zhruba receno po 3 krocch).

2. gcd-naive(84, 24) vsak mus snzit hodnotu t 12krat (zhruba receno tedyskonc az po 12 krocch).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 51 / 79

Slozitost algoritmu

Popisuje efektivitu algoritmu z hlediska zdroju, ktere potrebuje.

Casova slozitost

Popisuje, jak je algoritmus rychly, tj. kolik casu trva vypocet podlealgoritmu (od zahajen po ukoncen).

Tedy popisuje efektivitu algoritmu z hlediska casu jakoztovyuzvaneho zdroje.

Touto slozitost se budeme zejmena zabyvat.

Pametova (prostorova) slozitost

Popisuje, kolik pameti poctace je treba pro vypocet podle algoritmu.

Tedy popisuje efektivitu algoritmu z hlediska pameti jakoztovyuzvaneho zdroje.

Touto slozitost se budeme zabyvat okrajove. Vce bude v predmetuVycslitelnost a slozitost.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 52 / 79

Casova slozitost algoritmu

Projdeme uvahami, ktere nas dovedou ke spravnemu pojmu casovaslozitost algoritmu.

Otazka 1: Volba casove jednotky.Je rozumne merit trvan vypoctu podle algoritmu v sekundach?

+ Je to konkretn a kazdy tomu rozum. Viz:Vypocet podle algoritmu A1 pro vstup m = 3681 trval 2.15 sec.Vypocet podle algoritmu gcd-Euclid pro vstupn csla m = 3680,n = 260 trval 0.013 sec.

- Je to prlis zavisle na implementaci algoritmu (v jakemprogramovacm jazyku a jak kvalitne je naprogramovan, kvalitaprekladace) a na rychlosti poctace, na kterem vypocet probehl.Probehne-li vypocet, ktery na poctaci P1 trva 15.6 sec, na poctaciP2, ktery je 100krat rychlejs nez P1, pak na P2 tento vypocet trva0.156 sec. Z tohoto pohledu maj vyse uvedene vyroky slabouvypovdac hodnotu, zejmena pokud nam jde o porovnavan casoveslozitosti algoritmu.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 53 / 79

Jak tedy vhodne merit trvan vypoctu, ktery probha podle danehoalgoritmu?

trvan vypoctu = pocet elementarnch vypocetnch kroku vykonanychod zahajen do skoncen vypoctu

Elementarnm vypocetnm krokem je obvykle instrukce (instrukcepseudokodu nebo instrukce programovacho jazyka ve kterem je algoritmuszapsan).

+ Nen zavisle na rychlosti poctace. Je objektivnejs nez vyjadrit trvanv sekundach, zejm. jde-li o porovnan dvou algoritmu. Viz:Vypocet podle algoritmu A1 pro vstup m = 3681 trval 158 kroku.Vypocet podle algoritmu gcd-Euclid pro vstupn csla m = 84,n = 24 trval 10 kroku.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 54 / 79

- Nedava konkretn predstavu, jak dlouho budeme u poctace cekat, nezvypocet skonc. Proto se v praxi informace o slozitosti vyjadrene vpoctech kroku doplnuje o informaci o skutecnem trvan vypoctuvcetne toho, na jakem poctaci vypocet probhal.Pocet el. kroku (instrukc) zavis na tom, jaky psedokod neboprogramovac jazyk pouzvame. Napr. instrukci pseudokodu

swap(a,b),ktera zpusob vymenu hodnot promennych a a b, odpovda v jazyce Ctrojice instrukc

temp = a; a = b; b = temp;.

Uvedene dve nevyhody vsak nejsou velke, vyhody maj vets vahu.

Pozn.: Pro zjednodusen nekdy uvazujeme jen pocet dulezitych (proalgoritmus zakladnch) instrukc, tj. tech, ktere se pri vypoctu vykonavajcasto. Jde typicky o instrukce vykonavane opakovane, napr. uvnitr cyklu.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 55 / 79

Otazka 2: Je casova slozitost algoritmu doba trvan?(. . . at uz merme v sekundach nebo poctem vykonanych instrukc)

Ma napr. smysl rci:Casova slozitost algoritmu je 162 casovych jednotek (sec, kroku).?

Ne.

Ma smysl rci Vypocet podle algoritmu A1 pro vstup m = 3681 trval 2.15sec., ale predchoz vyrok smysl nema. Proc?

Protoze pro ruzne vstupy ma vypocet obvykle ruzna trvan. Trvan obvyklezavis na tzv. velikosti vstupu (Co to je, vysvetlme pozdeji. Pro predstavu:Cm vets jsou sctana csla, tm dels je trvan vypoctu pro jejich secten.).

Rozumnejs je tedy chapat pojem casova slozitost algoritmu jako funkci(zobrazen) T , jejz argumenty n jsou prirozena csla vyjadrujc velikostvstupu daneho algoritmu a jejz hodnotou T (n) pro n je trvan algoritmuve zvolenych casovych jednotkach (pocet instrukc, sekundy).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 56 / 79

Dals navrh tedy: Casova slozitost algoritmu je funkce T : N N, jejzhodnoty interpretujeme nasledovne:T (n) je doba trvan vypoctu podle daneho algoritmu pro vstup velikosti n.

Je to ted jasne? Ma to smysl?

Jeste ne zcela.

Vstupu stejne velikosti (velikosti n) je obvykle velke mnozstv. Ktery mamena mysli, mluvme-li o dobe trvan pro vstup velikosti n?

Pojem casova slozitost musme tedy dale upresnit. To nas privad kedvema dulezitym pojmum:

Casova slozitost v nejhorsm prpade:T (n) je nejvets trvan vypoctu podle algoritmu pro vstupy delky n.

Casova slozitost v prumernem prpade:T (n) je prumerne trvan vypoctu podle algoritmu pro vstupy delky n.

Lze uvazovat i casovou slozitost v nejlepsm prpade a tzv. amortizovanoucasovou slozitost. Nebudeme se jimi zabyvat.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 57 / 79

Ted presne. Je dan problem P, jeho vstupy oznacujeme I , algoritmus Apro dany problem. Oznacme:

tA(I ) . . . trvan vypoctu podle algoritmu A pro vstup I (ve vhodnychjednotkach).

|I | . . . velikost vstupu I .Napr. pocet cifer vstupnch csel u problemu sctan csel v destkovesoustave; pocet mest u problemu hledan nejkrats cesty mezi mesty vsti mest; pocet prvku pole, ktere je treba setrdit (pozdeji detailne)atd.Obecne |I | vhodnym zpusobem vyjadruje rozsahlost vstupu I . Muzeexistovat vce prirozenych zpusobu, jak merit rozsahlost vstupu (napr.u problemu hledan v sti mest to muze byt pocet mest, nebo jinak:pocet spojnic mezi mesty). Zamer: chceme, aby tA(I ) prirozenezaviselo na |I | (napr. tA(I ) = 2 |I |+ 3).Tedy velikost vstupu je funkce | | : Vst N (Vst je mnozinaprpustnych vstupu problemu P).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 58 / 79

DefiniceCasova slozitost algoritmu A v nejhorsm prpadeje funkce T : N N definovana takto:

T (n) = max{tA(I ) | I je vstup problemu P a |I | = n}.

Casova slozitost algoritmu A v prumernem prpadeje funkce T : N N definovana takto:

T (n) =tA(I1) + + tA(Im)

m,

kde I1, . . . , Im jsou vsechny vstupy problemu P, ktere maj delku n.

Uvidme mnoho prkladu, zejm. slozitosti v nejhorsm prpade.(Ktera slozitost je dulezitejs?)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 59 / 79

Prklad: slozitost algoritmu sctan v des. soustave

Scitani-Cisel-Desitkove(a[0..n 1], b[0..n 1])1 t 02 for i 0 to n 13 do c[i ] a[i ] + b[i ] + t mod 104 t b(a[i ] + b[i ] + t)/10c5 c[n] tPripomenme: vstupem I je dvojice csel zapsanych v destkove soustave,zapis kazdeho z nich obsahuje n pozic.

1. Co je velikost vstupu |I |, tj. |a[0..n 1], b[0..n 1]|?Polozme |a[0..n 1], b[0..n 1]| = n.(Mohli bychom ale vzt i |a[0..n 1], b[0..n 1]| = 2n, zkuste take.)2. Co je tA(I ), tj. tA(a[0..n 1], b[0..n 1])?Predpokladejme, ze za elementarn instrukce povazujeme instrukce nasehopseudokodu a ze za trvan vypoctu povazujeme pocet vykonanychelementarnch instrukc. Behem vypoctu pro vstup a[0..n 1], b[0..n 1]se provede:

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 60 / 79

1 radek 1: 1 instrukce prirazen,n radky 24: 1 instrukce na r. 2 (prirazen nove hodnoty promenne i), 4instrukce na r. 3 (2x instrukce +, 1x mod, 1x prirazen), 5 instrukc na r. 4(2x instrukce +, 1x /, 1x b c, 1x prirazen), celkem 10n instrukc,1 radek 5: 1 instrukce prirazen.Celkem se tedy provede 10n + 2 instrukc. TedytA(I ) = tA(a[0..n 1], b[0..n 1]) = 10n + 2.Je zrejme, ze tA(I ) = 10n + 2 pro kazdy vstup I velikosti n.(U jinych algoritmu ale muze pro dva vstupy I1, I2 se stejnou velikost byttA(I1) 6= tA(I2). Pomyslete napr. na gcd-Euclid.)

Casova slozitost v nejhorsm prpade je tedy T (n) = 10n + 2.Casova slozitost v prumernem prpade je take T (n) = 10n + 2.

Co se zmen, pokud proveden r. 3 budeme povazovat za proveden 1instrukce?Co se zmen, pokud i proveden r. 4 budeme povazovat za proveden 1instrukce?

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 61 / 79

Poznamka: velikost csla coby vstupu

U problemu sctan csel v destkove soustave je vstup tvoren dveman-ticemi csel. Prvn je an1 . . . a0 reprezentovana v poli a[0..n 1] (tj.a[0] = a0, . . . , a[n 1] = an1), druha je bn1 . . . b0 reprezentovana v polib[0..n 1] (tj. b[0] = b0, . . . , b[n 1] = bn1). Vstupem tedy nejsou cslaA =

ni=01ai 10i a B =

ni=01bi 10i reprezentovana csly ai a bi .

Proto jsme za velikost vstupu volili n (ale mohli bychom zvolit i 2n).

Casto se objevuje situace, kdy vstupem problemu je prirozene cslo N.Prirozeny zpusob jak merit velikost vstupu pak je:

|N| = pocet bitu potrebnych pro zapis csla N, tedy|N| = pocet mst zapisu csla N ve dvojkove soustave, tedy|N| = blog2Nc+ 1

Prklady: |1| = 1 (protoze (1)2 = 1), |2| = 2 ((3)2 = 10), |3| = 2((3)2 = 11), |4| = 3 ((4)2 = 100), |5| = 3 ((5)2 = 101), . . .

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 62 / 79

Zduvodnen:

Kazde cslo N je nekterym z csel 2k1, 2k1 + 1, . . . , 2k 1 pro vhodne k.

To jsou prave csla, jejichz binarn zapis ma k mst.

Prave pro tato csla platblog2 2k1c = k 1, blog2 2k1 + 1c = k 1, . . . , blog2 2k 1c = k 1.(Pro N < 2k1 je blog2 Nc < k 1, pro N > 2k 1 je blog2 Nc > k 1.)

Tedy pro kazde M {2k1, 2k1 + 1, . . . , 2k 1} plat blog2 Mc+ 1 = k.

Tedy specialne i pro N plat

blog2 Nc+ 1 = k

Prklady k procvicen:1. Jaky je pocet mst zapisu csla N v destkove soustave (obecneji, vsoustave o zakladu b)?2. Oznacme-li |N|b pocet mst zapisu csla N v soustave o zakladu b, jakyje vztah mezi |N|10 a |N|2? (Pouzijte loga N = loga b logb N.)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 63 / 79

Casto se vyskytujc slozitosti

Analyza slozitosti a odvozen vztahu T (n) = 10n + 2 bylo v tomto prpadevelmi jednoduche. U jinych algoritmu to je obtznejs, ale v principu stejne.

Pri analyze slozitosti algoritmu se casto vyskytuj nektere funkce. Jednou znich je 10n + 2. Dalsmi jsou.

c . . . konstantalogb n . . . logaritmus o zakladu b (msto log2 n pseme take lg n)n . . . linearn (obecneji an + b)n log n . . . logaritmicko linearn (log-linearn)n2 . . . kvadratickan3 . . . kubicka (obecneji an3 + bn2 + cn + d nebo polynomy vyssch radu)2n . . . exponencialnn! . . . faktorial

Proc jsou uvedeny v tomto porad? Prozkoumejte jejich chovan (napr. jakrychle rostou). Vratme se k tomu.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 64 / 79

Slozitost T (n) jako nositel dulezite informace

O cem nas informuje zprava, ze T (n) = 10n + 2, popr. T (n) = n2, popr.T (n) = 2n?

Strucne receno, algoritmus se slozitost T (n) = 10n + 2, popr. T (n) = n2

je prakticky pouzitelny.Algoritmus se slozitost T (n) = 2n je prakticky nepouzitelny.

Provedme ale zatm jednoduchou uvahu.

Uvaha 1 Uvazujme dva ruzne algoritmy, A1 a A2, pro resen problemu(napr. problem setrdit n-prvkovou posloupnost csel). Predpokladejme, zejejich sloztosti jsouT1(n) = n

2 a T2(n) = 20n log2 n.

Algoritmy jsou vykonavany na poctacch C1 a C2. C1 je rychly, vykona1010 instrukc/sekundu, C2 jen 10

7 instrukc/sekundu.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 65 / 79

Chceme vyresit pro vstup I velikosti 10,000,000 (10 milionu), tj. |I | = 107.S pomoc A1 na poc. C1 tva vypocet

(107)2

1010= 104sec = 166min40sec = 2hod46min40sec .

S pomoc A2 na poc. C2 tva vypocet

20 107 log 107

107 465sec = 7min35sec .

S A2 na 1000krat pomalejsm poctaci je vypocet cca 21.5 krat rychlejs.

Zaver: Slozitost algoritmu je skutecne dulezita. Zvysenm rychlostipoctace ji neobejdeme.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 66 / 79

Uvaha 2 Jak dlouho trva vypocet? (Priblizne) hodnoty nekterych funkc.n log2 n n n log2 n n

2 n3 2n n!

10 3.3 10 33 100 1000 1024 3628800100 6.6 100 660 104 106 1.27 1030 9.33 10157103 10 103 104 106 109 1.07 10301 4.02 102567104 13 104 1.3 105 108 1012 1.99 103010 2.85 1035659105 17 105 1.7 106 1010 1015106 20 106 2 107 1012 1018

Probha-li vypocet na velmi rychlem poctaci, ktery provad 1015 operac zasekundu (rychly asi jako nejrychlejs poctac v soucasne dobe), jsou dobyvypoctu v sekundach nasledujc (zaokrouhleno).n log2 n n n log2 n n

2 n3 2n n!

10 0 0 0 0 0 0 0100 0 0 0 0 0 1.27 1015 9.33 10142103 0 0 0 0 0 1.07 10186 4.02 102552104 0 0 0 0 0.001 1.99 102995 2.85 1035644105 0 0 0 105 1106 0 0 0 0.001 1000

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 67 / 79

Je to pro algoritmy se slozitost 2n a n! tak hrozne?

Jak dlouho je napr. 2.85 1035644 sec? (trvan pro n = 104 pri slozitosti n!)Rok ma prumerne 31,556,926 sekund. Je to tedy2.85 1035644/31556926 9 1035636 let!

Doba existence planety Zeme 4.54 109 let. Tedy vypocet je cca2 1035627krat dels nez doba existence nas planety!

Vysledku vypoctu se nikdy nedockame!

Co prvn vyznamne (nenulove) trvan pro slozitosti 2n a n!?

Pro n = 100 a T (n) = 2n je doba vypoctu 4 107 let, tj. 40 milionu let(pred 65 mil. lety vyhynuli dinosauri).

Ani v tomto prpade se vysledku nikdy nedockame.

Tomuto jevu se rka curse of exponential complexity (prokletexponencialn slozitosti, R. Bellman pouzil podobny pojem curse ofdimensionality).

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 68 / 79

Poctace vcera, dnes a ztra

VCERA prvn poctac:ENIAC (Electronic Numerical Integrator And Computer)

1946

prvn obecne programovatelny poctac vypocetne ekvivalentn tzv.Turingovu stroji (obecne programovatelny)

Univ. Pennsylvania, USA (US Army projekt, $6 mil. v dnesn hodnote)

27 tun, plocha 63 m2, prkon 150kW

380 operac nasoben za sekundu

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 69 / 79

DNES - nejrychlejs poctac na sveteJak se mer rychlost?

v jednotkach FLOPS (FLoating point Operations Per Second, tj.pocet operac s plovouc radovou carkou za sekundu)

mer se specialnm testem zahrnujcm vypocet tzv. LU rozkladu velkematice

TF TFLOPS (teraFLOPS) = 1012 FLOPS, PFLOPS (petaFLOPS) =1015 FLOPS, EFLOPS (exaFLOPS) = 1018 FLOPS

od r. 1993 existuje seznam TOP500 (aktualizovan 2x rocne, pri Int.Supercomputing Conference a ACM/IEEE SupercomputingConference)

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 70 / 79

nejrychlejs poctac (cerven 2017):Sunway TaihuLight, National Supercomputing Center, Wuxi (Cna), 93PFLOPS

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 71 / 79

ZITRA Mooruv zakon

G. E. Moore, *1929, spoluzakladatel Inteluzakon popisujc trend ve vyvoji hardware:pocet soucast integrovanych obvodu sezdvojjnasob kazde dva roky;plat priblizne i pro rychlost poctacu, pamet apod.

Tedy: Parametry hardware se zlepsuj velmi rychle.

Pozor na predpovedi. Ukazuj nase permanentn podcenovan vyvoje.

It would appear that we have reached the limits of what its possible toachieve with computer technology, although one should be careful withsuch statements, as they tend to sound pretty silly in five years.John von Neumann, 1949

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 72 / 79

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 withthe best people, and I can assure you that data processing is a fad thatwont 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 apractical proposition.Dennis Gabor, 1962 (laureat 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 Belohlavek (UP) Algoritmicka matematika 1 ZS 73 / 79

Jak by mohl vypadat domac poctac v roce 2004 (predstava v roce 1954)?

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 74 / 79

Cvicen Udaje v radcch udavaj cas t, ktery mame k dispozici. Funkcef (n) ve sloupcch udavaj dobu vypoctu v milisekundach potrebnou prozpracovan vstupu o velikosti n. Do kazdeho polcka (daneho casem t afunkc f (n)) doplnte udaj, ktery udava maximaln velikost n vstupu, kteryje mozne zpracovat v case t pri dobe vypoctu dane f (n).Napr. pro t =1 sec a f (n) = n je maximaln velikost vstupu 1000, protozetakovy vyposet trva f (1000) = 1000 msec = 1 sec.

cas log2 n n n log2 n n2 n3 2n n!

1 sec 1000

1 min

1 hod

1 den

1 mes.

1 rok

1 stolet

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 75 / 79

Uvaha 3 Pomuze technologicky pokrok?Jak se zvets velikost vstupu, ktery jsme za danou dobu (kterou muzemecekat) schopni algoritmem zpracovat, zvysuje-li se rychlost poctacukazdym rokem dvojnasobne?

Ze se rychlost poctacu zvysuje kazdym rokem dvojnasobne (to odpovdaMooreovu zakonu), znamena, ze Cas potrebny k proveden jedne instrukcev roce r + 1 je 2krat mens nez v roce r (jinymi slovy, za danou casovoujednotku poctac vykona v roce r + 1 je 2krat vce instrukc nez v roce r).

Oznacmetmax . . . doba, kterou muzeme cekat (napr. 5 min, 2 hod, 10 ms)nmax(r) . . . max. velikost vstupu, ktery jsme schopni zpracovat (v roce r)f (n) . . . casova slozitost algoritmu (pocet instrukc).

Jak velky vstup jsme schopni zpracovat v roce r + 1, tj. jaky je nmax(r)?Uvazme pro f (n) = n (linearn) a f (n) = 2n (exponencialn).

Doba vypoctu pro vstup velikosti n je f (n) cr , kde cr je cas potrebny kproveden jedne instrukce v roce r .

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 76 / 79

f(n) = n: nmax(r + 1) = 2nmax(r), tedy po roce budeme schopnizpracovat dvakrat vets vstup (dvakrat vce dat).

Proc? nmax(r) je nejvets n, pro ktere n cr tmax. Hledame nmax(r + 1),tj. nejvets n, pro ktere n cr+1 tmax, tedy (protoze cr+1 = 12cr ) pro kteren 12cr tmax. Je jasne, ze tm je 2nmax(r), tj. nmax(r + 1) = 2nmax(r).Snadno take vidme, ze nmax(r + k) = 2

knmax(r), tj. po k letech sevelikost zpracovatelneho vstupu zvys 2kkrat.

f(n) = 2n: nmax(r + 1) = nmax(r) + 1, tedy po roce budeme schopnizpracovat jen o jednotku velikosti vets vstup.

Proc? Stejnou uvahou dojdeme k tomu, ze nmax(r + 1) je nejvets n, proktere je 2n 12cr tmax, a tm je nmax(r) + 1.Snadno take vidme, ze nmax(r + k) = nmax(r) + k , tj. po k letech sevelikost zpracovatelneho vstupu zvys o k , kazdy rok jsme schopnizpracovat data vets jen o jednu polozku!

U algoritmu s exponencialn slozitost technologicky pokrok nepomuze.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 77 / 79

Cvicen (predchoz uvaha obecneji) Jak se zvets velikost vstupu, kteryjsme za danou dobu tmax schopni algoritmem zpracovat, zvets-li serychlost poctacu za obdob od roku r do roku r d-nasobne?

V roce r je nejvets velikost zpracovatelneho vstupu nmax(r), coz je tedynejvets n, pro ktere f (n) cr tmax. Dale je cr+1 = 1d cr .nmax(r

) je nejvets n, pro ktere f (n) cr tmax, tj. f (n) 1d cr tmax.

Predpokladejme pro jednoduchost, ze f (nmax(r)) cr = tmax a ze f mainverzn funkci f 1.Pak nmax(r

) je nejvets n, pro ktere f (n) d f (nmax(r)), tedyn f 1(d f (nmax(r))).

Pro f (n) = 2n:n lg(d 2nmax(r)) = lg d + nmax(r), tj. nmax(r ) = blg d + nmax(r)c.

Pro f (n) = np:n p

d nmax(r)p = p

d nmax(r), tj. nmax(r ) = b p

d nmax(r)c.

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 78 / 79

Predpokladejme opet f (nmax(r)) cr = tmax. Doplnte hodnoty nmax(r ) donasledujc tabulky.

d log2 n n n log2 n n2 n3 2n n!

1

2

4

10

100

1000

106

10p

2p

Radim Belohlavek (UP) Algoritmicka matematika 1 ZS 79 / 79