|
|
1. Dokazati da je za svaki prirodan broj n: 1 - 1/2 + 1/3 - ... + 1/(2n-1) - 1/(2n) = 1/(n+1) + 1/(n+2) + ... + 1/(2n) Rešenje za n=1: 1 - 1/2 = 1/2
IH: Pretpostavimo da je tvrđenje tačno za neki prirodan broj n i dokažimo da važi za n+1: 1 - 1/2 + 1/3 - ... + 1/(2n-1) - 1/(2n) + 1/ (2n+1) - 1/(2n+2) = 1/(n+1) + 1/(n+2) + ... + 1/(2n) + 1/ (2n+1) - 1/(2n+2) = 1/(n+2) + ... + 1/(2n) + 1/ (2n+1) + 1/(2n+2)
2. Dokazati da članovi Fibonačijevog niza (F1=F2=1, Fn=Fn-1 +Fn-2 za n >= 3) zadovoljavaju nejednakost Fn <= φn-1 gde φ je broj (1+√5)/2 Rešenje Za n=1: F1=1=φ0 =φn-1, pa je baza indukcije dokazana (tj. da tvrdnja važi za n=1) Za n=2: F2=1<1.6<φ1 =φ2-1 Sada pretpostavimo (tj.postavimo IH) da je tvrđenje tačno za 1,2,...n i važi n>1. To znači da tvrđenje važi i za n-1 tj. (i)Fn-1<=φ n-2 i važi za n, tj. (ii) Fn<=φn-1. Kako za članove Fibonačijevog niza važi (iii) Fn+1=Fn-1 +Fn <=φ n-2 +φ n-1=φ n-2(1+φ ) . Sada interveniše sledece svojstvo broja φ. Naime, neposredno se proveri da je φ2=φ +1 Stavljajući to u (iii) daje Fn+1<=φn , pa je dokazano da je tvrdjenje tacno za n+1 Verovatno se secate da ako zelimo da dokazemo da tvrdjenje P(n) je tačno za sve prirodne brojeve n onda postoje dva ključna poddokaza: 1)dokazati da je tacno P(1) 2)Ako je tacno P(1),P(2),...P(n) dokazati da je tacno P(n+1) U našem zadatku obavljen je 1). Ali pre koraka 2, pokazali smo direktnom proverom
da je tvrdjenje tacno za n=2. Da li je to suvišno? Fn-1=F1-1=F0, a ne možemo referisati na član F0, jer taj član ne figuriše u formulaciji zadatka. Za razmišljanje: Koji je odnos Fn i φn-2. 3. (jun 2001/02) Dati su za n >=2 prir.brojevi d1, d2,...,dn takvi da im je zbir 2n-2. Da li postoji stablo sa n čvorova čiji su stepeni brojevi d1,d2,...,dn ? Rešenje Odgovor je postoji. Dokažimo to. Stepen čvora je broj grana koje su mu susedne. U mnogim zadacima se koristi cinjenica da sabiranje stepena cvorova d1+...+dn je isto sto i brojanje grana, pri cemu se svaka grana broji tacno dva puta. Dakle, u ovom zadatku se radi nad stablom (ne mora da je binarno) i dokaz se izvodi indukcijom po n (broju čvorova) Baza: Ako n=2 je d1+d2=2 =>d1=d2=1 i postoji ovakvo stablo, jer dva cvora povezana granom jesu upravo stablo koje ima 2 cvora i to oba stepena 1 IH: Pretpostavimo da je tvrđenje tačno za n-1 brojeva i neka je dato n>=3 prirodnih brojeva d1,d2,...,dn ciji je zbir d1+...+dn=2n-2. Tada postoje bar jedno i (1<=i<=n), bar jedno j(1<=j<=n) tako da di=1, dj>1. Zašto? SP: Za svako i<=n da su di≠1. Tada ne može biti d1+...+dn=2n-2 (IH) Slično za dj se
pretpostavi suprotno: za svako j <=n je dj
<=1 . Izbacimo iz skupa di i umanjimo dj za jedan i dobice se skup za koga po IH postoji stablo sa tim stepenima. Zatim na to stablo dodamo novi
cvor, zapravo list stepena di=1 prikacenog za cvor
stepena dj-1>=1 i dobija se stablo iz f-lacije
zadtaka, tj. stablo sa n čvorova stepena d1,d2,....dn
.
4.(Oprez sa indukcijom)
Šta je pogrešno u sledećem "dokazu"
kojim se želi dokazati tvrđenje: "Dokaz" : n=1 =>an-1 =a1-1=1 IH:Pretpostavimo da je to tačno za 1,2,...,n
Rešenje Problem je što nismo smeli pretpostaviti
da je tvrđenje tačno za n=2. |
|
|
1. Problem Pn sa parametrom n (n je prir.broj) algoritam A rešava za T(n )vremenskih jedinica.
Ako se zna da za svaki prir.broj n vazi T(n+2)=3T(n+1)-2T(n), gde je T(1)=3, T(2)=5 odredi koliko vremenskih jedinica utrosi algoritam A za ulaznu vrednost n
Rešenje
Karakteristična j-na ove rek.j-ne je: t2-3t+2=0
<=> (t-1)(t-2)=0 =>t1=1, t2=2.
Tada
je rešenje oblika T(n)=C1*t1n
+C2*t2n
Iz početnih
uslova: za n=1: 3=T(1)=C1*1+C2*2
Za n=2: 5=T(2)=C1*1+C2*22 =>C1=1, C2=1
Pa je T(n)=2n +1
2.
Isto kao 1. Ali rekurentna jednačina glasi T(n+2)=4T(n+1)-4T(n), T(1)=6, T(2)=20
Zbog dvostrukog korena se ovaj zadatak razlikuje od prethodnog.
Karakteristična j-na ove rek.j-ne je: t2-4t+4=0 <=>(t-2)2=0
Tada se rešenje traži u obliku T(n)=C1*t1n +C2*n*t1n
Dakle za t1=2 rešenje je oblika T(n)=C1 2n +C2 n 2n
Iz početnih uslova: za n=1: 6=T(1)=C1*2+C2*2
Za n=2: 20=T(2)=C1*4+C2*8 =>C1=1, C2=2
Pa je T(n)=2n + 2n *2n
3. Često na ispitu zadatak u zadatku je:
Rešiti jednačinu tipa full history
T(n)=n+T(1)+T(2)+...+T(n-1), sa početnim uslovom T(1)=1
4. Sledeća rekurentna veza pojavljuje se u algoritmu tipa "zavadi pa vladaj" (algoritmi zasnovani na dekompoziciji ulaza na nejednake sastavne delove):
T(n)=∑ i=1..k ai T(n/bi) +cn, gde za konstante ai , bi važi ∑i=1..k ai/bi <1
Pronaći asimptotsko ponašanje ove rekurentne veze.
Copyright © 2002, Jelena Grmusa
Poslednja
izmena: oktobar 2002.
URL:
http://www.matf.bg.ac.yu/~jelenagr/pr/