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, 2015 1/23 Fl: IB000: Pokročilé algoritmy 11.1 Dokazování konečnosti algoritmu a programu * Co bývá snad ještě horší, než chybný výsledek algoritmu/programu? Je to situace, kdy spuštěný program běží „do nekonečna" a vůbec se nezastavíx Minule jsme problém zastavení algoritmu jednoduše obešli Konvencí 10.1, která vyžaduje, aby posloupnost kroků algoritmu byla konečná, c * Co když však, v důsledku použití řídících konstrukcí v zápise algoritmu, bude podmínka konečnosti porušena? c * V příkladech Lekce 10 to naštěstí nemůže nastat, neboť jsme dosud využívali jen f oreach cykly - přitom podle naší konvence f oreach cyklus obsahuje předem danou konečnou množinu hodnot dosazovaných do řídící proměnné a tudíž musí skončit. * Avšak už v příštím algoritmu využijeme while cyklus, u kterého nemusí být obecně jasné kdy a jestli skončí, a tudíž pro formálně korektní návrh algoritmu bude potřebný i důkaz konečnosti. Petr Hliněný, Fl MU Brno, 2015 2/23 Fl: IB000: Pokročilé algoritmy Příklad 11.1. Zastaví se vždy výpočet následujícího primitivního programu? Algoritmus 11.2. input x; while x>5 do x ^— x+1; done output x . i 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, 2015 3/23 Fl: IB000: Pokročilé algoritmy Když algoritmus vždy končí Na rozdíl od Příkladu 11.1 se budeme nadále věnovat pouze algoritmům, které poslušně končí své výpočty v souladu s naší Konvencí 10.1. Metoda 11.3. Jednoduchý důkaz konečnosti. Máme-li za úkol dokázat, že algoritmus skončí, lze doporučit následující postup: • 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 s každým voláním. Petr Hliněný, Fl MU Brno, 2015 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, 2015 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. function fibonacci(x ) : if x < 2 then t<—x; else t i— fibonacci(x-l)+fibonacci(x-2); return t . i 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 v každé iteraci rekurzivního volání f ibonacci (x) pro x > 2 v součtu nastane p(x - 1) + p(x - 2) = 2X-X + 2X~2 < 2 • 2X-X -1<2X. Počet iterací výpočtu fibonacci(n) tak bude vždy nejen konečný, ale podle uvedené úvahy přímo striktně menší než p(n) = 2n. □ Petr Hliněný, Fl MU Brno, 2015 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 = i —> n = i + 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, 2015 7/23 Fl: IB000: Pokročilé algoritmy Technika fixace parametru Příklad 11.7. 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ůstat jako součet y + • • • + y, dokud se x nesníží na nulu. Poté odhadneme: Věta. Pro každé x,y G N Algoritmus 11.7 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, 2015 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 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. Počáteční hodnota res nyní (pro naše indukční úvahy) tudíž je ro + hy = r\ a podle indukčního předpokladu je pak 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, 2015 9/23 Fl: IB000: Pokročilé algoritmy Indukce k součtu parametrů Příklad 11.8. Co je výsledkem následujícího rekurzivního výpočtu? Algoritmus . function kombinační(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 /a + 1\ / a \ / a\ Ui) = UJ + U)' 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 res = (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, 2015 10/23 Fl: 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 ? (m+n\ res = \ m ) 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, 2015 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 je m-prvkových podmn. (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). c A to je v součtu rovno kombinační (m-1 ,n) + kombinační (m,n-l), jak jsme měli dokázat. □ Petr Hliněný, FI MU Brno, 2015 12/23 FI: IB000: Pokročilé algoritmy Zesílení dokazovaného tvrzení Příklad 11.9. 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.10. 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, 2015 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.10 vypíše právě 2n — 1 znaků 'z' a proměnná st bude na konci obsahovat řetězec 2n znaků 'z'. 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, 2015 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.11. 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. input a,b, m ; 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 použijeme indukci podle délky í binárního zápisu čísla b. Věta. Algoritmus 11.11 skončí a správně vypočte hodnotu ab mod m. Petr Hliněný, Fl MU Brno, 2015 15/23 Fl: IB000: Pokročilé algoritmy r res <— 1; while b > 0 do if 6 mod 2 > 0 then res (res-a) mod m ; b \i>/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 i = Í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 = (a6 mod 2) mod m .c Tudíž délka binárního zápisu b\ bude jen 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, 2015 16/23 Fl: IB000: Pokročilé algoritmy Euklidův algoritmus Algoritmus 11.12. 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,g 6 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, 2015 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, přičemž hp + hq = i + 1. 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 — 1 = 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.13. □ Petr Hliněný, Fl MU Brno, 2015 18/23 Fl: IB000: Pokročilé algoritmy Největší společný dělitel Lema 11.13. 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, 2015 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.14. Celočíselná odmocnina. Pro dané přir. číslo x vypočteme dolní celou část jeho odmocniny [v^J ■' input x; p i— x; res 0; while p > 0 do while (res+p)2 < x do res 4— res + p; p <- Lp/2J ; done output res . Petr Hliněný, Fl MU Brno, 2015 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 11.15. Dynamický výpočet všech nejkratších cest mezi vrcholy v grafu G na množině vrcholů V(G) = {vq,vi, ..., v^-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, 2015 21/23 Fl: IB000: Pokročilé algoritmy Výpočet všech nejkratších cest Alternativně si zapíšeme postup této metody až překvapivě krátkým symbolickým algoritmem: Algoritmus 11.16. Výpočet všech nejkratších cest; Floyd-Warshall input 'Pole d[,] délek hran (nebo oo) grafu G' ; foreach t <- 0,1,... , iV - 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 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, 2015 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.17. Algoritmus 11.16 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]. 1 V kroku t = TV" jsme hotovi se všemi vrcholy. □ Petr Hliněný, Fl MU Brno, 2015 23/23 Fl: IB000: Pokročilé algoritmy