11 Pokročilé dokazování nad algoritmy Pokračujíce v látce předchozí Lekce 10 se budeme věnovat ukázkám důkazů správné funkce krátkých, ale ne zas tak jednoduchých, algoritmů. YOU WANT PROOF? I'LL GIVE ¥OU PROOF) Stručný přehled lekce * Zastaví se náš algoritmus a jak to dokázat? * Ukázky netriviálních aritmetických algoritmů s důkazy. * Důkazy indukcí s pokročilými technikami. Petr Hliněný, Fl MU Brno, 2012 1/23 Fl: IB000: Pokročilé algoritmy 11.1 Dokazování konečnosti algoritmu • Co bývá snad ještě horší, než chybný výsledek algoritmu? Je to situace, kdy spuštěný algoritmus běží „do nekonečna" a vůbec se nezastaví, c Všimněte si, že jsme se zatím v důkazech Lekce 10 vůbec nezamýšleli nad tím, zda naše algoritmy vůbec skončí. (To není samozřejmé a důkaz konečnosti je nutno v obecnosti podávat!:) Prozatím jsme však ukazovali algoritmy využívající jen foreach cykly, přitom podle naší konvence obsahuje foreach cyklus předem danou konečnou množinu hodnot pro řídící proměnnou, neboli náš foreach cyklus vždy musí skončit. Ale už v příštím algoritmu využijeme while cyklus, u kterého vůbec není jasné kdy a jestli skončí, a tudíž bude potřebný i důkaz konečnosti, c • Právě nad takovou situací a její možnou prevencí se v tomto oddíle zamyslíme. Předesíláme, že další podnětná látka k témuž tématu se nachází ještě v Lekci 12. Petr Hliněný, Fl MU Brno, 2012 2/23 Fl: IB000: Pokročilé algoritmy Příklad 11.1. Zastaví se vždy výpočet následujícího primitivního algoritmu? Algoritmus 11.2. input x; while x>5 do x ^— x+1; done output x : Odpověď je samozřejmě NE, jak každý vidí pro jakýkoliv vstup x větší než 5. Jak však tuto negativní odpověď matematicky dokázat? c To není zcela jednoduché, a proto si pomůžeme následujícím trikem: • Předpokládejme pro spor, že Algoritmus 11.2 někdy skončí pro x > 5. Nechť přirozené n > 5 je zvoleno tak, že Algoritmus 11.2 skončí pro x = n po nejmenším možném počtu í průchodů cyklem while. c Pak jistě í > 0, neboť na začátku je podmínka x>5 splněna z definice n. Po prvním průchodu pak x = n + l, avšak nyní již Algoritmus 11.2 musí skončit po l — 1 < i dalších průchodech cyklu. To je spor s volbou x = n coby vstupní hodnoty s nejmenším možným počtem průchodů. □ Petr Hliněný, Fl MU Brno, 2012 3/23 Fl: IB000: Pokročilé algoritmy Když algoritmus vždy končí Na rozdíl od předchozí ukázky se budeme dále věnovat pozitivním případům, kdy algoritmy poslušně končí své výpočty. Metoda 11.3. Jednoduchý důkaz konečnosti. Máme-li za úkol dokázat, že algoritmus skončí, vhodný postup je následující: • Sledujeme zvolený celočíselný a zdola ohraničený parametr algoritmu (třeba přirozené číslo) a dokážeme, že se jeho hodnota v průběhu algoritmu neustále ostře zmenšuje, c • Případně předchozí přístup rozšíříme na zvolenou k-tici přirozených parametrů a dokážeme, že se jejich hodnoty v průběhu algoritmu lexikograficky ostře zmenšují. Jedná se zde vlastně o vhodné (a zjednodušené pro daný účel) využití principu matematické indukce. Pozor, naše „parametry" vůbec nemusejí být proměnnými v programu. Například pro rekurzivní funkci factorial (x) z Příkladu 10.12 přímo využijeme parametr x, který se ostře zmenšuje, pro snadný důkaz ukončenosti. Petr Hliněný, Fl MU Brno, 2012 4/23 Fl: IB000: Pokročilé algoritmy Příklad 11.4. Dokažte, že násl. alg. vždy skončí pro jakýkoliv přirozený vstup x. Algoritmus . input x; while x<100 do y ^— 0; x ^— x+1; while y 0 a v každém průchodu vnějšího i vnitřního cyklu se p(x,y) ostře zmenší. □ Petr Hliněný, Fl MU Brno, 2012 5/23 Fl: IB000: Pokročilé algoritmy Příklad 11.5. Dokažte, že následující algoritmus vždy skončí pro jakýkoliv přirozený vstup x. Algoritmus. Rekurzivní výpočet funkce f ibonacci (x) pro přirozené x. if x < 2 then t <— x; else t i— fibonacci(x-l)+fibonacci(x-2); return t : Nyní je na první pohled přirozené sledovat přímo parametr x. Indukcí podle něj pak snadno odvodíme, že výpočet f ibonacci (x) vždy skončí. .. : V čem je tedy možný nedostatek tohoto přímého přístupu? V zásadě pouze jediný; nezískáme z něj žádný rozumný horní odhad počtu kroků algoritmu. Na druhou stranu při trikové volbě parametru p(x) = 2X pro Metodu 11.3 v každé iteraci rekurzivního volání f ibonacci (x) pro x > 2 nastane p(x - 1) + p(x - 2) = 2X-X + 2X-2 < 2 • 2X-1 -1<2X a počet iterací výpočtu fibonacci(n) tak bude vždy nejen konečný, ale přímo striktně menší než 2n. □ Petr Hliněný, Fl MU Brno, 2012 6/23 Fl: IB000: Pokročilé algoritmy 11.2 Přehled technik důkazu indukcí • Doposud zde byla matematická indukce představována ve své přímočaré formě, kdy dokazované tvrzení obvykle přímo nabízelo celočíselný parametr, podle nějž bylo potřebné indukci vést. c • Indukční krok pak prostě zpracoval přechod „n —> n + 1". c • To však u dokazování správnosti algoritmů typicky neplatí a našim cílem zde je ukázat možné techniky, jak správně indukci na dokazování algoritmů aplikovat, c • Uvidíme, jak si z nabízejících se parametrů správně vybrat a jak je případně kombinovat. Petr Hliněný, Fl MU Brno, 2012 7/23 Fl: IB000: Pokročilé algoritmy Technika fixace parametru Příklad 11.6. Mějme následující algoritmus. Co je jeho výsledkem výpočtu? Algoritmus . input x, y; z <- 0; while x>0 do z <— z+y; x <— x-1; done output z; Sledováním algoritmu zjistíme, že hodnota z bude součtem z = y + • • • + y, dokud x se nesníží na nulu. Poté odhadneme: Věta. Pro každé .ijgN Algoritmus 11.6 vypočítá hodnotu z = x - y. Petr Hliněný, Fl MU Brno, 2012 8/23 Fl: IB000: Pokročilé alRoritm; while x > O do z <— z+y; x <— x-1; done Důkaz: Budiž b G N libovolné ale pro další úvahy pevné. Dokážeme, že pro každé x G N je výsledkem algoritmu hodnota z = zq + x-b, kde b je hodnota vstupu y a zq je hodnota v proměnné z na začátku uvažovaného výpočtu (pro potřeby indukce), c • Báze x = 0 znamená, že tělo cyklu ani jednou neproběhne a výsledkem bude počáteční z = zq (nula na úplném začátku). • Indukční krok. Nechť je tvrzení známo pro x = i a uvažujme nyní vstup x = i + 1 > 0. Prvním průchodem cyklem se uloží z <— z + y = zo + ba x <— x — 1 = i. Začáteční hodnota vstupu y nyní (pro naše úvahy) je zq + b a podle indukčního předpokladu je výsledkem algoritmu hodnota (z0 + b) +i-b = z0 + (i + l)-b = z0+x-b. Důkaz matematickou indukcí je tímto ukončen. a Petr Hliněný, Fl MU Brno, 2012 9/23 Fl: IB000: Pokročilé algoritmy Indukce k součtu parametrů Příklad 11.7. Je dán následující rekurentní algoritmus. Algoritmus. Funkce kombinační (m,n) pro přirozená m, n. res 4— 1; if m>0 A n>0 then res = kombinační(m-1,n)+kombinacni(m,n-1); fi return res; i Výše uvedený vzorec (a ostatně i název funkce) naznačuje, že funkce má co společného s kombinačními čísly a Pascalovým trojúhelníkem je však třeba správně „nastavit" význam parametrů a,b. .. c Věta. Pro každé parametry m,n G N je výsledkem výpočtu funkce kombinační (m,n) hodnota r = (m,^n) (kombinační číslo) - počet všech m-prvkových podmnožin (m + n)-prvkové množiny. Petr Hliněný, Fl MU Brno, 2012 10/23 Fl: IB000: Pokročilé algoritmy if m>0 A n>0 then res = kombinační(m-1,n)+kombinacni(m,n-l); fi Důkaz indukcí vzhledem k součtu parametrů i = m + n: c • Báze i = m + n = 0 pro m, n G N znamená, že m = n = 0. Opět však s výhodou využijeme rozšíření báze na případy m = 0 nebo n = 0 (zvlášť). V obou rozšířených případech daná podmínka algoritmu není splněna, a proto výsledek výpočtu bude iniciální res = 1. Je toto platná odpověď? c * Kolik je prázdných podmnožin (m = 0) jakékoliv množiny? Jedna, 0. Kolik je m-prvkových podmnožin (n = 0) m-prvkové množiny? Zase jedna, ta množina samotná. Tím je důkaz báze indukce dokončen. Petr Hliněný, FI MU Brno, 2012 11/23 FI: IB000: Pokročilé algoritmy res -í— 1; if m>0 A n>0 then res = kombinační(m-1,n)+kombinacni(m,n-1); fi • Indukční krok je i + 1 = m + n pro m, n > 0. Nyní je podmínka algoritmu splněna a vykonají se rekurentní volání kombinační(m-1,n) + kombinační(m,n-l).c Rekurentní volání se vztahují k výběru podmnožin m—l+n = m+n—1 = i -prvkové množiny, například M = {1,2,... Výsledkem tedy je, podle indukčního předpokladu pro součet i, počet (m — l)-prvkových plus m-prvkových podmnožin množiny M. c Kolik nyní je m-prvkových podmnožin (i + 1)-prvkové množiny M' = MU {i+l}l Pokud ze všech podmnožin odebereme prvek dostaneme právě m-prvkové podmnožiny (z těch neobsahujících i + 1) plus (m — l)-prvkové podmnožiny (z těch původně obsahujících i + 1). To je přesně rovno kombinační (m-1 ,n) + kombinační (m,n-1), jak jsme měli dokázat. Petr Hliněný, FI MU Brno, 2012 12/23 FI: IB000: Pokročilé algoritmy Zesílení dokazovaného tvrzení Příklad 11.8. Zjistěte, kolik znaků 'z' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 11.9. st ^"z"; foreach i<—l,2,3,...,n-l,n do vytiskni řetězec st; st 4— st . st ; (zřetězení dvou kopií st za sebou) done Zkusíme-li si výpočet simulovat pro n = 0,1, 2, 3,4 ... , postupně dostaneme počty 'z' jako 0,1, 3, 7,15 ... . Na základě toho již není obtížné „uhodnout", že počet 'z' bude (asi) obecně určen vztahem 2n — 1. Toto je však třeba dokázat! c Jak záhy zjistíme, matematická indukce na naše tvrzení přímo „nezabírá", ale mnohem lépe se nám povede s následujícím přirozeným zesílením dokazovaného tvrzení: Petr Hliněný, Fl MU Brno, 2012 13/23 Fl: IB000: Pokročilé algoritmy Algoritmus . st ^"z"; foreach i<—l,2,3,...,n-l,n do vytiskni řetězec st; st -í— st . st ; (zřetězení dvou kopií st za sebou) done Věta. Pro každé přirozené n Algoritmus 11.9 vypíše právě 2n —1 znaků 'z' a proměnná st bude na konci obsahovat řetězec 2n znaků 'z' x Důkaz: Postupujeme indukcí podle n. Báze pro n = 0 je zřejmá, neprovede se ani jedna iterace cyklu a tudíž bude vytištěno 0 = 2° — 1 znaků 'z', což bylo třeba dokázat. Mimo to proměnná st iniciálně obsahuje 1 = 2° znak 'z' x Nechť tedy tvrzení platí pro jakékoliv uq a položme n = uq + 1. Podle indukčního předpokladu po prvních uq iteracích bude vytištěno 2n° — 1 znaků 'z' a proměnná st bude obsahovat řetězec 2n° znaků 'z'. V poslední iteraci cyklu (pro i 4— n=no+l) vytiskneme dalších 2n° znaků 'z' (z proměnné st) a dále řetězec st „zdvojnásobíme", c Proto po n iteracích bude vytištěno celkem 2n° - 1 + 2n° = 2no+1 - 1 = 2n - 1 znaků 'z' a v st bude uloženo 2 • 2n° = 2n°+1 = 2n znaků 'z'. n Petr Hliněný, Fl MU Brno, 2012 14/23 Fl: IB000: Pokročilé algoritmy 11.3 Zajímavé algoritmy aritmetiky Například umocňování na velmi vysoké exponenty je podkladem RSA šifry: Algoritmus 11.10. Binární postup umocňování. Pro daná číslo a, b vypočteme jejich celočíselnou mocninu (omezenou na zbytkové třídy modulo m kvůli prevenci přetečení rozsahu celých čísel v počítači), tj. c = ab mod m. c ^— 1; while b > 0 do if b mod 2 > 0 then c -í— (c-a) mod m ; b i— \b/2\ ; a (a-a) mod m ; done výsledek c ; i Zde použijeme k důkazu správnosti algoritmu indukci podle délky í binárního zápisu čísla b. Věta. Algoritmus 11.10 skončia správně vypočte hodnotu c = ab mod m. Petr Hliněný, Fl MU Brno, 2012 15/23 Fl: IB000: Pokročilé algoritmy c ^— 1; while b > O do if 6 mod 2 > 0 then c -í— (c-a) mod m ; b i— \b/2\ ; a (a-a) mod m ; done výsledek c ; Důkaz: Báze indukce je pro £ = 1, kdy 6 = 0 nebo 6 = 1. Přitom pro 6 = 0 se cyklus vůbec nevykoná a výsledek je c = 1. Pro 6 = 1 se vykoná jen jedna iterace cyklu a výsledek je c = a mod m. c Nechť tvrzení platí pro £q > 1 a uvažme £ = £q + 1. Pak zřejmě 6 > 2 a vykonají se alespoň dvě iterace cyklu. Po první iteraci bude a' = a2, b' = [b/2\ a d = (a6 mod 2) mod m. Tudíž délka binárního zápisu b' bude jen £q a podle indukčního předpokladu zbylé iterace algoritmu skončí s výsledkem c = c' • a'h' mod m = (ab mod 2 • a2L6/2J) mod m = ah mod m. Petr Hliněný, Fl MU Brno, 2012 16/23 Fl: IB000: Pokročilé algoritmy Euklidův algoritmus Algoritmus 11.11. Euklidův pro největšího společného dělitele. input p, q; while p>0 A q>0 do if p>q then p -í— p-q; else q -í— q-p; done output p+q; i Věta. Pro každé p, q G N na vstupu algoritmus vrátí hodnotu největšího společného dělitele čísel p a q, nebo 0 pro p = q = Ox Důkaz povedeme indukcí podle součtu i = p + q vstupních hodnot. (Je to přirozená volba v situaci, kdy každý průchod cyklem algoritmu sníží jedno zp,q, avšak není jasné, které z nich.) c • Báze indukce pro i=p + q = 0]e zřejmá; cyklus algoritmu neproběhne a výsledek ihned bude 0. Petr Hliněný, Fl MU Brno, 2012 17/23 Fl: IB000: Pokročilé algoritmy while p>0 A q>0 do if p>q then p -í— p-q; else q -í— q-p; done • Ve skutečnosti je výhodné uvažovat „rozšířenou bázi", která zahrnuje i případy, kdy jedno z p, q je nulové. Pak výsledek p + q bude roven tomu nenulovému z obou sčítanců, což je v tomto případě zároveň jejich největší společný dělitel, c • Indukční krok. Mějme tedy nyní vstupní hodnoty p = hp > 0 a q = hq > 0 - tehdy dojde k prvnímu průchodu tělem cyklu našeho algoritmu, c * Předp. hp > hq\ poté po prvním průchodu tělem cyklu budou hodnoty p = hp — hq a q = hq, přičemž nyní p + q = hp < hp + hq = i. Podle indukčního předpokladu tudíž výsledkem algoritmu pro vstupy p = hp — hq a q = hq bude největší společný dělitel NSD(hp — hq, hq).c * Symetricky pro hp < hq algoritmus vrátí NSD(hp, hq — hp). Důkaz tak bude dokončen následujícím Lematem 11.12. □ Petr Hliněný, Fl MU Brno, 2012 18/23 Fl: IB000: Pokročilé algoritmy Největší společný dělitel Lema 11.12. NSD(a, b) = NSD{a -b,b) = NSD(a, b - a). Všimněte si, že dělitelnost je dobře definována i na záporných celých číslech. Důkaz: Ověříme, že c = NSD(a — b, b) je také největší společný dělitel čísel a a b (druhá část je pak symetrická), c • Jelikož číslo c dělí čísla a —b a b, dělí i jejich součet (a — b) + b = a. Potom c je společným dělitelem a a b. c • Naopak nechť d nějaký společný dělitel čísel a a b. Pak d dělí také rozdíl a — b. Tedy d je společný dělitel čísel a — bab. Jelikož c je největší společný dělitel těchto dvou čísel, nutně d dělí c a závěr platí. Petr Hliněný, Fl MU Brno, 2012 19/23 Fl: IB000: Pokročilé algoritmy Relativně rychlé odmocnění Na závěr oddílu si ukážeme jeden netradiční krátký algoritmus a jeho analýzu a důkaz ponecháme zde otevřené. Dokážete popsat, na čem je algoritmus založen? Algoritmus 11.13. Celočíselná odmocnina. Pro dané přir. číslo x vypočteme dolní celou část jeho odmocniny r = [v^J ■ p i— x; r i— 0; while p > 0 do while (r+p)2 < x do r -í— r+p ; p <- Lp/2J ; done výsledek r ; Petr Hliněný, Fl MU Brno, 2012 20/23 Fl: IB000: Pokročilé algoritmy 11.4 Dynamický algoritmus Klíčovou myšlenkou dynamických algoritmu je rozklad problému na podproblémy, jejichž řešení jsou postupně ukládána pro další možné použití. Metoda je obzvláště vhodná v případech, kdy rozložené podúlohy si jsou podobné a mohou se opakovat. Metoda 11.14. Dynamický výpočet všech nejkratších cest mezi vrcholy v grafu G na množině vrcholů V(G) = {vq,vi, ..., vn-i}- • Na počátku nechť d[i,j] udává 1 (případně váhu-délku hrany {ví,vj}), nebo oo pokud hrana mezi i, j není. c • Po kroku t > 0 nechť platí, že d[i, j] udává délku nej kratší cesty mezi ví,vj, který užívá pouze vnitřní vrcholy z množiny {vq, v±, ..., vt-i}.£ • Při přechodu z kroku t na následující krok t + 1 upravujeme vzdálenost pro každou dvojici vrcholů ví,vj - jsou vždy pouhé dvě možnosti: Bud' je cesta délky d [i, j ] z předchozího kroku t stále nej lepší (tj. nově povolený vrchol vt nám nepomůže), * nebo cestu vylepšíme spojením přes nově povolený vrchol vt, čímž získáme menší vzdálenost d[i,t]+d[t, j] —>d[i, j]. • Po iV krocích úprav je výpočet hotov. Petr Hliněný, Fl MU Brno, 2012 21/23 Fl: IB000: Pokročilé algoritmy Výpočet nejkratších cest Alternativně si zapíšeme postup této metody až překvapivě krátkým symbolickým algoritmem: Algoritmus 11.15. Výpočet všech nejkratších cest; Floyd-Warshall input 'Pole d[,] délek hran (nebo oo) grafu G' ; for (t=0; t