Algoritmy II

Zdroj: SOOM.cz [ISSN 1804-7270]
Autor: pr0ph3t
Datum: 21.3.2007
Hodnocení/Hlasovalo: 0/0

Dukaz vlastnosti algoritmu pomoci matematicke indukce.

Po vicemene uspesnem prvnim user textu o algoritmech, jsem se rozhodl napsat dalsi, tentokrat z trochu jineho soudku. Rec totiz nebude o zajimavych algoritmech, ale pouze o dvou vicemene obycejnych. Pokusim se rozebrat co delaji a proc to delaji. Take bych rad ukazal tem, kteri stale neveri ze matematika a informatika jsou uzce propojene, proc se hodi umet napriklad matematicke dukazy pokud porovnavame dva algoritmy. Ty budou stejne jako v minulem dile napsany v jazyce C. Predpokladam ze pro jejich jednoduchost s tim nebude mit nikdo problemy, ale pokud by se preci jen nekdo takovy nasel, tak na teto adrese najde oba priklady zapsane obecne, bez pouzii jakehokoliv urciteho jazyka (mozna trochu to zavani pascalem). http://www.fimuni.org/ib000-11-1-2007-doc-899/

Tento kratky uvod bych ukoncil tim, ze az po dopsani usertexu a pote, co jsem si ho po sobe precetl, jsem si uvedomil, ze je mozna dost slozity. Verim ze je tu spousta takovych, kteri uvazuji o studiu informatiky na vysoke skole. Proto bych rad, aby ti kteri treba vsemu neporozumi, ho brali jako ukazku toho s cim se mohou v budoucnosti setkat. Ode mne nezbyva nez slibit ze pripadny dalsi user text uz bude zase jednodussi ;)


Prvnim dnesnim algotimem jsou uplne jednoduche dva vnorene cykly for. Nas bude zajimat, co cely algoritmus provede, a hlavne kolikrat.

#include <stdio.h> int main(){ int a,b; int n; scanf("%d",&n); for (a=0;a<=n;a++){ for (b=1;b<=n;b++){ printf("x"); } } return 0; }

Na prvni pohled je zrejme, ze program nacte cislo n ze vstupu, a podle nej vypise urcity pocet pismen "x". Kolikrat to ale bude? Pro ty, kteri to nevidi hned, to trochu priblizim: prvni forcyklus probehne od 0 do n, tedy celkove (n+1) krat, druhy forcyklus probehne od 1 do n, tedy n-krat, a vypise znak x. Celkove tedy (n+1)*n=n^2 + n Ted si urcite rikate ze to je jasne, neni na tom co resis. Co kdyz ale vstup nebude n, ale n+1? Nebo n+15? Kolikrat bude potom vypsan znak "x". Je to (n+16)*(n+15)? A je to tak urcite?

Na tyto otazky odpovim pozdeji. Cely vypocet vzorce pro urceni poctu vytistenych znaku je totiz az do ted pouhym predpokladem, neco u ceho verime ze to tak je, ale nejaka jistota to urcite neni. Pokud se vam to zda hotove a pripada vam to zcela jasne, je tu druhy algotirmus, u ktereho uz to tak zrejme mozna nebude.

#include <stdio.h> int main(){ int a,b,c; int n; scanf("%d",&n); for (a=1;a<=2;a++){ for (b=1;b<=n;b++){ for (c=1;c<=b;c++){ printf("x"); } } } return 0; }

Jedna se uz o tri vnorene for cykly, navic uz nejsou tak primitivni jako u prvniho prikladu. Kolikrat tento algoritmus vypise znak "x"? Vicekrat nez ten predchozi? Nebo ne? Zkusime si jako u prvniho algoritmu odhadnout o co jde. Prvni for cyklus probehne celkove dvakrat. Treti forcyklus probehne presne tolikrat, kolik je prave b, tedy postupne jednou, dvakrat, trikrat, ctyrikrat az maximum b, coz je n. Tedy 1+2+3+...+n. Pokud tato cisla secteme, dostavame (podle vzorce pro soucet n clenu posloupnosti, viz http://cs.wikipedia.org/wiki/Aritmetick%C3%A1_posloupnost) (1+n)*n / 2. Celkove tedy 2*(1+n)*n / 2 a pokud vykratime nasobeni dvojkou a opetovne deleni, tak je to (1+n)*n. Presne stejne jako u prvniho algotimu. Bylo to i tady tak zrejme? A je to skutecne spravne? A znovu: co se stane pokud nebude n=n, ale treba n+1? Nebo treba n=16? Bude vzorec (1+n)*n platit?

Proto abychom mohli skutecne odpovedet na tyto otazky, musime provest nejaky dukaz, v tomto pripade dukaz matematickou indukci. Verim ze spousta z vas jej zna, nebo o nem alespon slysela.

Matematicka indukce

O co se jedna? Jde o to dokazat ze nejake tvrzeni, v nasem pripade ze program vypise urcity pocet znaku "x", dokaze postupne pro vsechna mozna n, v tomto pripade cisla od nuly do nekonecna. Cely postup se casto prirovnava ke kostkam domina. Predstavte si kostky domina vyskladane na stole za sebou tak, aby kdyz do prvni strcite prstem a spadne, opre se o druhou, shodi ji a ta se opre o treti, shodi ji, a ta se opre ctvrtou a tak dal az spadnou uplne vsechny. Stejne tak budeme postupovat i my.

Prvni algoritmus:
Shodime prvni kostku domina, spravne se tomu rika baze indukce. Na vstupu programu zadame nulu, tedy n=0. Co potom? Nic. Nic se nevytiskne. Vychazi nam to podle vzorce (n+1)*n? 1*0 = 0. Ano vychazi. Prvni kostka spadla.
Skvele, ted predpokladame ze domino pada a pada a pada. Rika se tomu indukcni predpoklad. Tedy ze pro vsechna n plati vzorec (n+1)*n. A ted si potrebujeme overit ze se domino nezastavi. Spadne i (n+1)-ni kostka?
Pokud je vstup o jedna vetsi nez ten predchozi, vytiskne se (n+1)n znaku podle indukcniho predpokladu(=IP), tedy vsechny kostky spadli az sem, resime tu dalsi. Ted se podivame na nas program. Prvni frocyklus probehl az po n podle IP, jen s tim rozdilem, ze pro kazde "a" bylo vytisteno o jeden znak vic, tim padem se nam vytisklo navic (n+1) znaku. V posledni iteraci prvniho forcyklu, ktera v pripade IP vubec neprobehla, se nam naposledy spusti i druhy forcyklus, a nim se vypise dalsich (n+1) znaku. Celkove tedy (n+1)*n + n+1 + n+1 = n^2 + 3n +2 Odpovida to nasemu vzorci? Pokud si v (n+1)*n zvetsime n o jedna, dostavame (n+1+1)*(n+1)=n^2+3n+2 Vyborne, vyslo to. V tomto okamziku muzeme rict, ze vzorec je spravny, a pro jakykoliv vstup vypise (n+1)*n znaku "x". Vsechny kostky domina padaji a nikdy se nezastavi (pokud jich mame opravdu nekonecno ;) )

Druhy algotimus:
Opet shodime prvni kostku: kdyz bude vstup 0, nevypise se zjevne nic. Odpovida to podle vzorce? 1*0=0. Ano. Prvni kostka spadla, baze indukce je dokazana.
Nasledne predpokladame ze padaji dalsi a dalsi kostky, a ze plati vzorec, ktery rika, ze pro vstup n se nam vypise (n+1)*n znaku. Co se stane pokud bude n o jedna vetsi, tedy n+1? Pro n, se vypise (n+1)*n znaku podle IP, a pro tu jednicku je situace takova, ze vnejsi for cyklus probehne dvakrat, tedy vsechno co je v nem se bude nasobit dvema. Cyklus b bude o jedna delsi a proto treti cyklus vypise navic (n+1) znaku. Celkove tedy (n+1)*n + 2 (n+1) = n^2+3n+2, coz je presne podle vzorce.

V tomto okamziku muzeme rict ze obe tvrzeni (Prvni i druhy algoritmus vypisuji presne (n+1)*n znaku '"x".) jsou formalne dokazane pomoci matematicke indukce. Podotykam ze tohoto postupu se vyuziva i u dalsich dukazu vlastnosti programu, napriklad dukazu konecnosti cyklu.

Doufam ze aspon nekdo vydrzel cist az sem, a ze mu to neco dalo. Minimalne ukazku toho jak to vypada s informatikou na vysoke skole, pripadne pocit ze ta matematika neni tak uplne zbytecna. A hlavne pokud to myslite s informatikou vazne, bez matematiky se neobejdete. Dekuji za pozornost, a verim ze me upozornite na pripadne chyby v komentarich, at uz logicke ci pravopisne.