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? * Důkazy indukcí se systematickými technikami. * Ukázky netriviálních aritmetických algoritmů s důkazy. Petr Hliněný, Fl MU Brno, 2013 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, 2013 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 + 1 > 5, avšak nyní již Algoritmus 11.2 musí skončit po í — 1 < í dalších průchodech cyklu. nTo 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, 2013 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, a přesto jsou s programem implicitně nerozlučně svázány. 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, 2013 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, 2013 5/23 Fl: IB000: Pokročilé algoritmy Příklad 11.5. Dokažte, že následující algoritmus (viz dřívější 10.13) 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 f ibonacci (n) tak bude vždy nejen konečný, ale podle uvedené úvahy přímo striktně menší než 2n. □ Petr Hliněný, Fl MU Brno, 2013 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, 2013 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; res 0; while x>0 do res res + y; x -í— x-1; done output res; i Sledováním algoritmu zjistíme, že hodnota proměnné res bude narůstajícím součtem y + • • • + y, dokud se x nesníží na nulu. Poté odhadneme: Věta. Pro každé x,y G N Algoritmus 11.6 vypočítá hodnotu res = x ■ y. Jaký je vhodný postup k důkazu tohoto tvrzení indukcí? Je snadno vidět, že na hodnotě vstupu y vlastně nijak podstatně nezáleží (lze y fixovat) a důležité je sledovat x. Tato úvaha nás dovede k následujícímu: Petr Hliněný, Fl MU Brno, 2013 8/23 Fl: IB000: Pokročilé algoritmy while x > O do res res + y; x -í— x-1; done Důkaz: Budiž /i^sN libovolné ale pro další úvahy pevné. Dokážeme, že pro každý vst. x G N je výsledkem výpočtu hodnota ro + x ■ hy, kde hy byla hodnota vstupu y a ro byla hodnota v proměnné res na začátku uvažovaného výpočtu (pro potřeby indukce, ro = 0 na úplném začátku), c • Báze x = 0 znamená, že tělo cyklu ve výpočtu už ani jednou neproběhne a výsledkem bude počáteční ro. c • 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ží res <— res + y = r^ + hy = r\ ax-í— x — 1 = i. Začáteční hodnota vstupu y nyní (pro naše indukční úvahy) tudíž je ro + hy = r\ a podle indukčního předpokladu je výsledkem výpočtu hodnota ri + i ■ hy = (r0 + hy) + i ■ hy = r0 + (i + 1) • hy = r0 + x ■ hy . Důkaz matematickou indukcí je tímto ukončen. a Petr Hliněný, Fl MU Brno, 2013 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) +kombinační(m,n-l); 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ý, FI MU Brno, 2013 10/23 FI: IB000: Pokročilé algoritmy res -í— 1; if m>0 A n>0 then res kombinační(m-1,n) + kombinační(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. Zde však s výhodou využijeme tzv. „rozšírení báze" na všechny hraniční 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 rozšířené báze indukce dokončen. Petr Hliněný, FI MU Brno, 2013 11/23 FI: IB000: Pokročilé algoritmy res -í— 1; if m>0 A n>0 then res kombinační(m-1,n) +kombinační(m,n-l); fi • Indukční krok přechází na součet 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 + l)-prvkové množiny M' = M U {i + 1}? Pokud ze všech podmnožin odebereme prvek i + 1, 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). nA to je přesně rovno kombinační (m-1 ,n) + kombinační (m,n-l), jak jsme měli dokázat. □ Petr Hliněný, FI MU Brno, 2013 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ý, FI MU Brno, 2013 13/23 FI: 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, 2013 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á čísla 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. ab mod m, následujícím postupem. res 4— 1; while b > 0 do if b mod 2 > 0 then res (res-a) mod m ; b i— \b/2\ ; a (a-a) mod m ; done output res; i K důkazu správnosti algoritmu použijeme indukci podle délky í binárního zápisu čísla b. Věta. Algoritmus 11.10 skončí a správně vypočte hodnotu ab mod m. Petr Hliněný, Fl MU Brno, 2013 15/23 Fl: IB000: Pokročilé algoritmy res <— 1; while b > O do if 6 mod 2 > 0 then res <— (res-a) mod m ; b i— \b/2\ ; a (a-a) mod m ; done output res; 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 res = 1. Pro 6 = 1 se vykoná jen jedna iterace cyklu a výsledek je res = a mod m. Nechť tvrzení platí pro £q > 1 a uvažme £ = £q + 1. Pak zřejmě 6 > 2 a vykonají se alespoň dvě iterace cyklu, c Po první iteraci budou hodnoty proměnných po řadě ai = a2, 6i = [6/2J a res = rx = (ab mod 2) mod m .c 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 res = r\ • a^1 mod m = (ab mod 2 • a2^/2!) mod m = ab mod m. □ Petr Hliněný, Fl MU Brno, 2013 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 opět povedeme indukcí podle součtu i = p + q vstupních hodnot. (Jak jsme psali, je to přirozená volba v situaci, kdy každý průchod cyklem algoritmu sníží jedno z p,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, 2013 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 zase výhodné uvažovat rozšířenou bázi, která zahrnuje i případy, kdy jen jedno z p, q je nulové (což je ukončovací podmínka cyklu).c 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 nyní vstupní hodnoty p = /ip>0ag = /i?>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 proto bude dokončen následujícím Lematem 11.12. □ Petr Hliněný, Fl MU Brno, 2013 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, 2013 19/23 Fl: IB000: Pokročilé algoritmy Relatívne 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 [v^J ■' p i— x; res 0; while p > 0 do while (res + p)2 < x do res <— res + p; p <- Lp/2J ; done output res ; Petr Hliněný, Fl MU Brno, 2013 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]. i • Po N krocích úprav je výpočet hotov. Petr Hliněný, Fl MU Brno, 2013 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' ; foreach t <- 0, l,...,iV-l do foreach i <- 0,1,... , N - 1, j <- 0,1,..., N - 1 do d[i,j] <- min(d[i, j] , d [i ,t]+d [t, j] ); done done output 'Matice vzdáleností dvojic d[,] ' ; i Poznámka: V implementaci pro symbol oo použijeme velkou konst., třeba MAX_INT/2. Petr Hliněný, Fl MU Brno, 2013 22/23 Fl: IB000: Pokročilé algoritmy foreach t <- 0,1,...,N-1 do foreach i <- 0,1,..., N - 1, j <- 0,1,..., N - 1 do d[i,j] <- min(d[i,j]» d[i,t]+d[t, j] ); done done Věta 11.16. Algoritmus 11.15 v poli d[i, j] správně vypočte vzdálenost mezi každou dvojicí vrcholů V{, v j. Důkaz povedeme matematickou indukcí podle řídící proměnné t cyklu. Báze je snadná - na počátku kroku t = 0 udává d[i,j] vzdálenost mezi v\ a Vj po cestách, které nemají vnitřní vrcholy (tj. pouze případně existující hranu), c Přejdeme-li na krok í + 1, musíme určit nejkratší cestu P mezi v\ a Vj takovou, že P používá (mimo ví,vj) pouze vrcholy {vq,vi, ..., vt}. nTuto nejkratší cestu Psi hypoteticky představme: Pokud vt 0 V(P), pakd[i,j] již udává správnou vzdálenost. nJinak vt G V (P) a označíme P\ podcestu v P od počátku v\ do vt a obdobně P2 podcestu od vt do konce Vj. Podle indukčního předpokladu je pak délka P rovna d[i,t]+d[t, j]. c V kroku t = TV" jsme hotovi se všemi vrcholy. □ Petr Hliněný, Fl MU Brno, 2013 23/23 Fl: IB000: Pokročilé algoritmy