Zadaci u ovom poglavlju za teorijsku podlogu imaju rezultate predstavljene na IX i X dvocasu predavanja i izlozene u knjizi "Algoritmika" u poglavlju 8!!! Pre njihove izrade NEOPHODNO je poznavanje prikazanih rezultata.
A1 Navesti primer izračunavanja nk (k > 10) sa manjim brojem množenja nego u algoritmu Stepen_kvadriranjem (n, k) u glavi 8.2. |
PODSECANJE NA REZULTAT IZLOZEN NA PREDAVANJIMA: I algoritam: Algoritam Stepen (n,k) (glava 8.2) nk=n*nk-1=> O(k)
II algoritam: Algoritam Stepen_kvadriranjem (n,k) (glava 8.2) | nk=(nk/2)2 , k jeparan broj |
nk=n*(n(k-1)/2)2 , k je neparan broj | |
T(k)=T(k/2) + 1 => a=1, b=2, O(k0 log k), tj. O(log k) |
Broj množenja ne zavisi od n (zavisi od k). REŠENJE:
Pogledajmo primer najmanjeg k koje ispunjava uslov iz formulacije k > 10 i k=2m-1,tj. m=4, k=15: Stepen_kvadriranjem (n, k) za k=15: n15= n* (n7)2=n* (n*n6)2= . . . = n* ( n* (n*n2)2) 2 => šest množenja REŠENJE:
Na primer: 18 = 13 + 5 (2 sabirka, dok log2 18 > 2)
a) Dokaz principom matematičke indukcije: baza: n=3 F(1)=F(2)=1, F(3)=2, F(4)=3 => n=F(4) && 1<log2 3 Dokaz: Po (IH) za broj (n-F(k))potrebno je <= log2 (n-F(k)) razl. Fibonač. brojeva b) Algoritam Predstava (n)
REŠENJE: Algoritam vrsta * kolona zahteva n3množenja,Vinogradov algoritam n3/2 + n2 množenja.
Brute-force tehnika: izvrsiti proveru svih troclanih podskupova skupa cvorova.
Algoritam NZD (a0, a1)
{ Na primer: 57*x + 33*y = 3
Ako se više puta pojavljuje drugi slučaj nk=n*(n(k-1)/2)2,k je neparan broj, onda ukupan broj množenja je veći, a najgori slučaj je za k=2m-1 (tj. česta pojava drugog slučaja).
Ali, na primer n15=( ( (n2 ) 2 * n)3 => pet množenja
A2
Fibonačijevi brojevi su definisani sledećom diferencnom jednačinom:
F( n ) = F( n-1 ) + F( n-2 ), ( n > 2 )
F(1) = F(2) = 1
Dokazati da se svaki prirodan broj n > 2 može predstaviti u obliku zbira najviše log2 n različitih Fibonačijevih brojeva.
b) Konstruisati algoritam za određivanje takve predstave datog broja n.
induktivna hipoteza: Za sve brojeve k manje od n važi
(IH) prirodan broj k > 2 može se predstaviti u obliku zbira najviše log2k-1 Fibonačijevih brojeva
Dakle,postoji k: F(k)<=n<F(k+1) =>F(k) > n/2
/* supr. pretp. F(k)<=n/2. Kako je F(k-1) < F(k) za k>2, onda je F(k-1) < n/2
Odatle, F(k+1)=F(k)+F(k-1) < n/2 + n/2 =n što je kontradikcija sa n< F(k+1) */
Kako je n-F(k)< F(k), /* jer iz gore dokaznog svojstva F(k) > n/2 => 2*F(k)>n => F(k) > n-F(k)) */
onda F(k) ne učestvuje u reprezentaciji broja n-F(k) Fibonačijevim brojevima, te se za broj n= F(k) + (n-F(k))
koristi <= 1 + log2 (n-F(k)) razl. Fibonač. brojeva.
Kako 1+ log2 (n-F(k))=log22 + log2(n-F(k))=log2(2n - 2 F(k)) = log2(n + ( n- 2F(k))< log2n (jer n-2F(k) <0 po gore dokazanom)
input: n /* n>2 */
output: reprezentacija broja n kao sume Fibonačijevihbrojeva*/
{
f1=1; f2=1;
while (f2 <= n) {d=f1+f2; f1=f2; f2=d;} /* naci k: f(k)<=n < f(k+1) */
while (n>0) { if (n-f1>=0) { stampaj f1; n=n-f1;} d=f2-f1; f2=f1; f1=d;}
}
A3
Pokazati kako se kvadrat kvadratne matrice reda dva može izračunati pomoću pet množenja.
Za n=2 to je 8 množenja. Štrasen je otkrio da je potrebno sedam množenja elemenata da bi se izračunao proizvod ma koje dve matrice reda dva. (obavezno pogledati poglavlje 8.5.2)
Ako se radi o množenju dve iste matrice reda dva,tj. kvadriranju, onda je dovoljno izračunati pet proizvoda:
=
A4
Dat je neusmereni povezani graf G=(V,E) sa n cvorova.
Potrebno je ustanoviti da li u G postoji trougao (tj. takva tri cvora
da između svaka dva od njih postoji grana).
Konstruisati algoritam slozenosti O(nlog2 7)
koji daje odgovor na ovo pitanje.
Podskupova ima n(n-1)(n-2)/6, a kako se za svaki od njih moze proveriti za konstantno vreme da li jeste ili nije trougao, vremenska slozenost ovog algoritma je O(n3).
Dakle, slozenost je veca od one koje se trazi u zadatku!!! Moze li drukcije?
A5
Euklidov algoritam određuje najveći zajednički delilac za prirodne brojeve a0, a1. Na osnovu ideje Euklidovog algoritma, konstruisati algoritam koji pronalazi bar jedno celobrojno rešenje jednačine a0*x+ a1*y = NZD(a0,a1).
input: a[0], a[1]
output: x, y
i=0; x[i]=1; y[i]=0;
i=1; x[i]=0; y[i]=1;
while ( a[i-1] % a[i] != 0)
{ q=a[i-1] / a[i];
a[i+1]= a[i-1]- q* a[i];
x[i+1]= x[i-1]- q* x[i];
y[i+1]= y[i-1]- q* y[i];
i++;
}
stampaj x[i], y[i]
}
i | a[i] | x[i] | y[i] |
0 | 57 | 1 | 0 |
1 | 33 | 0 | 1 |
2 | 24 | 1 | -1 |
3 | 9 | -1 | 2 |
4 | 6 | 3 | -5 |
5 | 3 | -4 | 7 |
Dakle, x=-4, y=7
Da li je za svako i>=0 ispunjeno a[0]*x[i] + a[1]*y[i]=a[i] ?
DZ
i=0 => a[0]*x[0] + a[1]*y[0]=a[0]*1+0=a[0]
i=1 => a[0]*x[1] + a[1]*y[1]=0+a[1]*1=a[1]
IH: pretp. da važi za i-1, i, i>=2
Po algoritmu: x[i+1]= x[i-1] - q* x[i];
y[i+1]= y[i-1] - q* y[i];
Dakle, a[0]*x[i+1] + a[1]*y[i+1]= a[0] * (x[i-1] - q* x[i]) + a[1] * (y[i-1] - q* y[i]) =
a[0]*x[i-1] +a[1]*y[i-1] -
- q * (a[0]*x[i] + a[1]*y[i]) = a[i-1] -q* a[i] = (po IH) a[i+1] => Q.E.D.
M1
Dokazati da ako postoji algoritam složenosti O(T(n)) za množenje kvadratne n×n donje trougaone matrice kvadratnom n×n gornje trougaonom matricom, onda postoji algoritam složenosti O(T(n)+n2) za množenje dve proizvoljne n×n matrice. Pretpostaviti da T(cn)=O(T(n)) za proizvoljnu konstantu c > 0.
REŠENJE:
Neka su A i B dve proizvoljne kvadratne matrice reda n .
Svaka od njih se moze predstaviti kao zbir po jedne gornje
i po donje trougaone matrice (TA, BA, TB, BB, redom):
A= T A + B A
B= T B + B B
Dalje je : AB=( T A + B A ) ( T B + B B )=T AT B + B AB B + B AT B + T AB B
Ako se upotrebi algoritam iz formulacije zadataka mogu\ce je izracunati proizvod :
BA 0
T A BA |
× |
TB BB
0 TB |
= |
B AT B BABB T AT B B AT B + T AB B |
Kao rezultat dobija se matrica koja sadrzi blokove: B AB B , T AT B , B AT B + T AB B
Ovi blokovi ucestvuju u izracunavanju proizvoda A × B.
Na taj nacin se problem izracunavanja proizvoda dve proizvoljne matrice svodi na problem izracunavanja proizvoda kvadratne donje trougaone matrice kvadratnom gornjom trougaonom matricom.
Ukupno vreme izvršavanja : O(T(2n)+n2 )=O(T(n)+n2)
M2 Ako je dat algoritam za mnozenje dve n * n donje trougaone matrice čije vreme izvrsavanja je O(T(n)), dokazati da postoji algoritam za mnozenje dve proizvoljne n *n matrice cije vreme izvrsavanja je O(T(n)+n2 ). (Moze se pretpostaviti da je T(cn)=O(T(n)) za svaku konstantu c)
REŠENJE: Neka su A i B dve proizvoljne kvadratne matrice reda n .
A= T A + B A
B= T B + B B
Dalje je : AB=( T A + B A ) ( T B + B B )=T AT B + B AB B + B AT B + T AB B
Ako se upotrebi algoritam iz formulacije zadataka mogu\ce je izracunati proizvod :
BA 0
T A BA |
× |
BB 0
TB BB |
= |
B AB B 0 T AB B+B AT B B AB B |
Kao rezultat dobija se matrica koja sadrzi blokove: B AB B , T AT B , B AT B + T AB B
Ovi blokovi ucestvuju u izracunavanju proizvoda A × B.
Matrice ( TA )T i ( TB )T su donje trougaone matrice, te se upotrebom datog algoritma moze izracunati
blok T A T B na sledeci nacin:
T A T B = ( ( TB )T
( TA )T )T
Ukupno vreme izvršavanja je O(T(2n)+n2)= O(T(n)+n2).
Na taj nacin se problem izracunavanja proizvoda proizvoljne dve matrice svodi na problem izracunavanja proizvoda
dve kvadratne donje trougaone matrice.
M3 - samo za radoznale
Formirati algoritam koji za dve reči dužine n (prva reč), m
(druga reč) nad azbukom slova i cifara pronalazi
niz operacija editovanja najmanje cene kojim se prva reč transformiše u drugu reč.
Dozvoljene su tri vrste operacija editovanja i svaka ima cenu jedan:
insert = umetanje jednog karaktera
delete = brisanje 1 karaktera
replace = zamena jednog karaktera drugim karakterom
A(1)=amaak /*insert a*/
A(2)=amaa /*delete k */
CENA: 1+1=2
A(1)=aak /*delete m*/
A(2)=amak /*insert m */
A(3)=amaa
/*replace k slovom a */
CENA: 1+1+1=3
Koristi se u aplikacijama u kojima je potrebno znati koliko su slične dve niske, npr.
spell checker-i (provera pravopisa)
Spell checkeri porede reč sa ulaza sa jedinicom rečnika.Ako reč nije pronađena u rečniku, smatra se da nije korektno uneta i izlistavaju se moguće rečiiz rečnika, počev od onih sa najmanjom Levenshtein udaljenosti od ulazne reči.aplikacije molekularne biologije (DNK analiza; što je veći stepen sličnosti dve sekvence, bilo DNK, RNK ili amino-kiselina, to im je sličnija i funkcija ili struktura, npr. kod multiplskleroze koja to bakterijska ili virusna sekvenca iz ranije infekcije je slična sekvenci proteinske mijelinske ovojnice )
detekcija plagijata
prepoznavanje govora
Što je Levenštajnovo rastojanje dve niske veće, to se one više razlikuju među sobom.
Procena sličnosti dve niske može se utvrditi na osnovu Levenštajnovog rastojanja ili LCS algoritmom koji pronalazi najduužu zajedničku podsekvencu (podsekvenca se dobija iz niske brisanjem 0 ili više karaktera). Oba algoritma će biti navedena kao ilustracija tehnike dinamičkog programiranja.
Inače, današnje softverske alatke koriste više metrika, a često i njihovu kombinaciju. Neke metrike su pogodnije za oblast molekularne biologije, neke za oblast text mining-a. Više o metrikama nad niskama može se pogledati u lekciji Metrike nad niskama.
Oznake: Neka je A(k) niz koji se sastoji od prvih k elemenata niza A.Neka je B(k) niz koji se sastoji od prvih k elemenata niza B.
pseudo-jezik: Algoritam NajjeftinijeEditovanje (a, b, n, m)
ulaz: a, n, b, m
izlaz: Cena /* tabela (n+1)*(m+1) */
{
/* i, j su lokalne promenljive i imaju ulogu brojača u petljama
Potez je matrica koju pregledamo unazad (počev od Potez[n,m]), ne bi li dobili konačan niz operacija editovanja.
Potez[i,j]
poslednja operacija (delete ili insert ili replace) editovanja koja se obavlja da bi Cena[i,j] bila minimalna
c1 - slučaj prethodnog delete a[i]
c2 - slučaj prethodnog insert b[j]
c3 - slučaj prethodnog replace a[i] sa b[j]
*/
/* transformacija prefiksa A(i) u praznu nisku B(0) */
for (i=0; i <= n; i++)
{
Cena[i,0]=i;
Potez[i,0]= delete;
}
/* transformacija praznog prefiksa A(0) u prefiks B(j) */
for (j=0; j <= m; j++)
{
Cena[0,j]=j;
Potez[0,j]= insert;
}
/* i!=0, j!=0 i najjeftinija transformacija A(i) u B(j) */
for (i=1; i <= n; i++)
for (j=1; j <= m; j++)
{
c1= Cena[i-1,j]+1;
c2= Cena[i,j-1]+1;
if (a[i]==b[j])
c3= Cena[i-1,j-1];
else
c3= Cena[i-1,j-1]+1;
Cena[i,j]=Min_3_broja (c1, c2, c3);
Potez[i,j] = izabrana_operacija_editovanja_u_Min_3_broja;
} /*for */
} /*KRAJ*/
Svaki element matrice Cena se i izračunava za konstantno vreme, pa je vremenska složenost algoritma O(mn), dok je i prostorna složenost O(mn). Može se postići prostorna složenost reda O(m), ali ako se matrica Cena popunjava po vrstama (jer jedna vrsta zavisi samo od prethodne vrste).
Primer formiranja matrice cena za niske "SAMBA" i "SIMBAD".
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 |
|
|
|
|
|
I | 2 |
|
|
|
|
|
M | 3 |
|
|
|
|
|
B | 4 |
|
|
|
|
|
A | 5 |
|
|
|
|
|
D | 6 |
|
|
|
|
|
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 | 0 |
|
|
|
|
I | 2 | 1 |
|
|
|
|
M | 3 | 2 |
|
|
|
|
B | 4 | 3 |
|
|
|
|
A | 5 | 4 |
|
|
|
|
D | 6 | 5 |
|
|
|
|
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 | 0 | 1 |
|
|
|
I | 2 | 1 | 1 |
|
|
|
M | 3 | 2 | 2 |
|
|
|
B | 4 | 3 | 3 |
|
|
|
A | 5 | 4 | 4 |
|
|
|
D | 6 | 5 | 5 |
|
|
|
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 | 0 | 1 | 2 |
|
|
I | 2 | 1 | 1 | 2 |
|
|
M | 3 | 2 | 2 | 1 |
|
|
B | 4 | 3 | 3 | 2 |
|
|
A | 5 | 4 | 4 | 3 |
|
|
D | 6 | 5 | 5 | 4 |
|
|
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 | 0 | 1 | 2 | 3 |
|
I | 2 | 1 | 1 | 2 | 3 |
|
M | 3 | 2 | 2 | 1 | 2 |
|
B | 4 | 3 | 3 | 2 | 1 |
|
A | 5 | 4 | 4 | 3 | 2 |
|
D | 6 | 5 | 5 | 4 | 3 |
|
|
| S | A | M | B | A |
| 0 | 1 | 2 | 3 | 4 | 5 |
S | 1 | 0 | 1 | 2 | 3 | 4 |
I | 2 | 1 | 1 | 2 | 3 | 4 |
M | 3 | 2 | 2 | 1 | 2 | 3 |
B | 4 | 3 | 3 | 2 | 1 | 2 |
A | 5 | 4 | 4 | 3 | 2 | 1 |
D | 6 | 5 | 5 | 4 | 3 | 2 |
Rastojanje je u donjoj desnoj ćeliji, tj. 2, što odgovara i inuitivnoj realizaciji da se niska "SAMBA" može transformisati u nisku "SIMBAD" zamenom slova "A" slovom "I" i dodavanjem slova "D" (1 zamena i 1 umetanje = 2 operacije ).