Naći niz edit operacija minimalne cene koji transformiše niz znakova
A = a1 a2 ... an
u niz znakova B = b1 b2 ... bm
pri čemu važi:
i
je c·i
(c = const.
)k
-tog znaka je cj
1
.Rešenje:
Problem svodimo na problem nalaženja najkraćih puteva iz datog čvora u posebnom grafu G
,
koji je određen nizovima A i B. Skup čvorova je
V = { (i, k) | 0 ≤ i ≤ n, 0 ≤ k ≤ m }
dok u čvor (i, k)
vode grane iz čvorova:
(i, k-1)
ako je 0 ≤ i ≤ n, 1 ≤ k ≤ m
(umetanje znaka ai
, cena c*i
);(i-1, k)
ako je 1 ≤ i ≤ n, 0 ≤ k ≤ m
(brisanje znaka bj
, cena c*j
);(i-1, k-1)
ako je 1 ≤ i ≤ n, 1 ≤ k ≤ m
(zamena znaka aᵢ
sa bj
, cena 0
ako aᵢ = bj
, 1
inače.Nalazimo najkraći put od (0, 0)
do svih ostalih čvorova i specijalno
do čvora (n, m)
i dobijamo rešenje.
Taj put odgovara nizu edit operacija najmanje cene koji niz A transformiše u niz B.
U datom grafu G = (V, E)
izdvojen je čvor v
i svakom čvoru w ∈ V
pridružena je cena c(w)
. Cena usmerenog puta v, x₁ , x₂, ..., xₖ, u
definiše se izrazom:
k
∑ c(xᵢ);
i = 1
specijalno, ako (v, u) ∈ E
, onda je cena puta v, u
nula.
Konstruisati efikasan algoritam za nalaženje puteva
minimalne cene od v
do ostalih čvorova u G
.
Rešenje:
Konstruišemo graf H
takav da svakom čvoru w
iz G
odgovaraju
dva čvora w₁ (završni), w₂ (polazni)
u H
, uz granu (w₁, w₂)
cene c(w)
.
Za svaku granu (w, u)
iz G
pravimo granu (w₂, u₁)
cene 0
u H
.
c(w)
w -------- u w₁ -------- w₂
c(w) c(u) | 0
u₁ -------- u₂
c(u)
Time smo problem sveli na problem određivanja svih najkraćih
puteva od v₂
do svih završnih čvorova u H
.
Gornje trougaona matrica je kvadratna matrica u kojoj su svi elementi
ispod glavne dijagonale jednaki nula. Dokazati da ako postoji algoritam
složenosti O(T(n))
za množenje dve n × n
gornje trougaone matrice,
onda postoji algoritam složenosti O(T(n) + n²)
za množenje dve proizvoljne
n × n
matrice. Može se koristiti pretpostavka da je T(cn) = O(T(n)), c=const
.
Rešenje:
A
, B
- dve proizvoljne kvadratne matrice reda n
.
Potrebno je svesti izračunavanje A · B
na izračunavanje
proizvoda nekih gornje-trougaonih matrica.
A
i B
možemo napisati u obliku zbira jedne donje i jedne
gornje trougaone matrice:
A = GA + DA
B = GB + DB
A · B = GA GB + (GA DB + DA GB) + DA DB
Ako algoritam za množenje dve gornje trougaone matrice primenimo na
⌈GA DA⌉ ⌈GB DB⌉ - gornje trougaone dimenzija 2n x 2n
⌊0 GA⌋ i ⌊0 GB⌋
Dobijamo prva tri sabirka:
⌈ GA DA ⌉ ⌈ GB DB ⌉ ⌈ GA GB GA DB + DA GB ⌉
| | x | | = | |
⌊ 0 GA ⌋ ⌊ 0 GB ⌋ ⌊ 0 GA GB ⌋
Poslednji sabirak računamo kao DA DB = ((DBᵀ) (DAᵀ))ᵀ
.
Dakle, algoritam za množenje gornje trougaonih matrica primenjujemo
jednom na 2n x 2n
matrice i jednom na n x n
matrice.
Pored toga, imamo 3
transponovanja i 2
sabiranja matrica reda n
.
Složenost je O(T(2n) + T(n) + n²) = Q(T(n) + n²)
Neka je S
skup od n
tačaka u ravni. Dijametar skupa S
je najveće
rastojanje nekih dveju tačaka iz S
. Označimo sa DM
problem
odredivanja dijametra skupa od n tačaka, a sa DS
problem utvrdjivanja
da li su disjunktna dva skupa A
i B
od ukupno n
realnih brojeva.
Dokazati da ako postoji algoritam koji problem DM
rešava za vreme
O(T(n))
, onda postoji algoritam složenosti O(T(n) + n)
za
rešavanje problema DS
.
Rešenje: