APS2 teorija Flashcards
Zapiši definicijo f(n) = O(g(n))
f(n) = O(g(n)): f(n) je omejena navzgor z g(n)
(∃c1, n0 > 0)(∀n ≥ n0) [0 ≤ f(n) ≤ c1*g(n))]
Zapiši definicijo f(n) = Ω(h(n))
f(n) = Ω(h(n)): f(n) je omejena navzdol z h(n)
(∃c2, n1 > 0)(∀n ≥ n1) [c2*h(n)) ≤ f(n)]
Zapiši definicijo f(n) = Θ(k(n))
f(n) = Θ(k(n)): f(n) je enaka funkciji k(n) (f je od zgoraj in spodaj omejena z k)
(∃c1, c2, n2 > 0)(∀n ≥ n2) [c1k(n) ≤ f(n) ≤ c2k(n)]
Kakšni sta asimptotični zahtevnosti funkcij f(n) in g(n), kjer je
f(n) = 2n^2logn + 2n^2loglogn in
g(n) = n^2logn + 10n^2loglogn
Θ(n^2*logn)
Izpeljite asimptotično (Θ) zahtevnost funkcije f(n) = 8^(log2(n))
f(n) = 8^(log2(n)) = n^(log2(8)) = n^3 => Θ(n^3)
Izpeljite asimptotično (Θ) zahtevnost funkcije f(n) = 4^(log2(n))
f(n) = 4^(log2(n)) = n^(log2(4)) = n^2 => Θ(n^2)
Kaj hitreje narašča?
f(n) = e^n + n!
g(n) = n^(n+1)
f(n) (n -> ∞) = n!
g(n) (n -> ∞) = n^n
g(n) > f(n)
g(n) narašča hitreje
Izpeljite asimptotično (Θ) zahtevnost za naslednji funkciji.
f(n) = n^2 + 3n
g(n) = n^2 - e^(-π/2)
T(n) = n^2 + 3n -> n^2 => Θ(n) = n^2 T(n) = n^2 - e^(-π/2) -> n^2 => Θ(n) = n^2
Definiraj urejanje zaporedij
Dani so a1, a2 ,…, an in relacija popolne urejenosti ≼.
Cilj je poiskati tako razporeditev, da velja ai1 ≼ ai2 ≼ … ≼ ain.
Naštejte 5 algoritmov za notranje urejanje.
(Če je n takšno število, da so vsi elementi v glavnem pomnilniku v neki tabeli.)
urejanje z izbiranjem (Selection sort), urejanje z zamenjavami (Bubble sort), urejanje z zamenjavami (Bubble sort), urejanje s kopico (Heap sort), hitro urejanje (Quick sort) in zlivanje (Merge sort)
Najboljši, povprečen in najslabši case scenario časovne zahtevnosti za heapsort
Ω(n log n), Θ(n log n), O(n log n)
Najboljši, povprečen in najslabši case scenario časovne zahtevnosti za quicksort
Ω(n log n), Θ(n log n), O(n2)
Naštejte 5 metod za razvoj algoritmov
Dinamično programiranje, deli in vladaj, sestopanje, požrešni algoritmi, rekurzivni razcep
Opiši razliko med dinamičnim programiranjem in deli in vladaj ter načelo optimalnosti
Dinamično programiranje temelji na pravilu optimalnosti, kjer sistematično pregleduje delne rešitve in
sestavlja optimalno rešitev. Če v danem koraku ugotovimo, da delna rešitev ne pripelje do optimalne, jo
zavržemo. Vsaka naloga ima svojo Bellmanovo enačbo.
Primer: nahrbtnik
Pri Deli in vladaj problem najprej razdelimo na manjše podprobleme, le-te rešimo z uporabo rekurzije in iz
njihovih rešitev sestavimo rešitev problema.
Primer: QuickSort (urejanje podtabele t1 in urejanje podtabele t2 ∪ t3)
Zaporedje odločitev D1, D2, . . . , Dm (ki jih sprejmemo med računanjem rešitve naloge N) je optimalno, če
nas privede do optimalne rešitve naloge N.
Načelo optimalnosti: Vsako podzaporedje optimalnega zaporedja odločitev je tudi optimalno.
Kdaj rečemo, da ima algoritem psevdo-polinomsko časovno zahtevnost?
Časovna kompleksnost algoritma odvisna od numerične vrednosti vhoda, in ne od velikosti vhoda.
Zapišite glavni izrek (Master Theorem) metode deli & vladaj. Pojasnite pomen uporabljenih oznak.
T(n) =
b, če n = 1;
aT(n/c) + b*n^d, če n > 0;
kjer so a ≥ 1, b > 0, c ≥ 2 in d ≥ 0, velja naslednje:
T(n) =
Θ(n^d), če c^d/a > 1;
Θ(n^d log n) če c^d/a = 1;
Θ(n^(logc(a))) če c^d/a < 1;
a = število podnalog b = konstanta brez bistvenega pomena c = faktor delitve naloge d = red velikosti zahtevnosti pri delitvi in združevanju n = velikost naloge
Psevdokoda za navadno matrično množenje
procedure MatProdukt(A,B,C);
begin
C := 0;
for i = 1 to n do
for j = 1 to n do
for k = 1 to n do
C[i,j] := C[i,j] + A[i,k]*B[k,j]
end.Psevdokoda za Strassenovo matrično množenje
procedure Strassen(A,B) return C;
begin
if n=1 then
C := AB
else
begin
P_11 := Strassen(A_11 + A_22, B_11 + B_22)
...
C_11 := P_11 + P_12 - P_13 - P14
...
C := (C_11,C_12,C_21,C_22)
end
end.
P11 = (A11 + A22)(B11 + B22) P21 = (A22 + A11)(B22 + B11) P12 = (A12 - A22)(B21 + B22) P22 = (A21 - A11)(B12 + B11) P13 = (A11 + A12)B22 P23 = (A22 + A21)B11 P14 = A22(B11 - B21) P24 = A11(B22 - B12)
C11 = P11 + P12 - P13 - P14 C12 = P13 - P24 C21 = P23 - P14 C22 = P21 + P22 - P23 - P24
Asimptotična zashtevnost za Strassenovo množenje
T(n) = Θ(n^(logc(a))) = Θ(n^(log2(7))) = Θ(n^2,80735)
Zapišite definicijo n-tega primitivnega korena.
- ω^d = 1 // ω je koren enote
- ω^k ≠ 1 za k = 1, …, d-1 // ω je primitivni koren enote
V kompleksnem (C) obsegu je ω = e^(i*(2π/d))
Zapišite definicijo Fourierove matrike F
Fij = ω^(i*j), 0 ≤ i, j < d
Kakšna je inverzna matrika F-1?
Fij^-1 = 1/d * ω^(-i*j), 0 ≤ i, j < d
Napiši matriki F in inverzni F 4 X 4 za splošni ω pri DFT
Glej 2nd_theory… Stran 10
Kakšna je časovna zahtevnost algoritma za Hitro Fourierovo Transformacijo (FFT)?
Polinoma stopnje n lahko zmnožimo v času Θ(n log n).
Zapišite strogo (formalno) definicijo Problema nahrbtnika
- množica R = {1, 2, . . . , n} z elementi, ki predstavljajo predmete
- funkcija v : R → N, ki vsakemu predmetu i priredi vrednost v(i)
- funkcija t : R → N, ki vsakemu predmetu i priredi težo t(i)
- število b ∈ N, ki predstavlja nosilnost nahrbtnika
Poiskati moramo podmnožico P ⊆ R, imenovano plen, za katero bo veljalo
• plen ni pretežek: Σ(i ∈ P) t(i) ≤ b
• maksimizira vsoto (plen je najvrednejši): Σ(i ∈ P) v(i)
Ford-Fulkersonov algoritem
Temeljna pot P je pot iz izvora v ponor, ki nima ciklov in na kateri zanemarimo smeri povezav.
Povezava (i, j):
• pozitivna (P+): kaže v smeri od izvora proti ponoru
• negativna (P-): kaže v smeri od ponora proti izvoru
• P+ je zasičena: vi,j = ci,j
• P− je zasičena: vi, j = 0
P je zasičena, če vsebuje vsaj eno zasičeno povezavo (pretoka čez njo ne moremo več povečati).
P ni zasičena, če za vsako (i, j) ∈ P+ velja vi,j < ci,j in če za vsako (i, j) ∈ P− velja vi, j > 0.
Za koliko povečamo pretok, ko pot zasitimo?
min{min((i,j)∈P+) {c i,j - v i,j}, min((i,j)∈P-) {v i,j}}
Naj bo G splošen graf z n vozlišči in cenami povezav ci,j. Zapišite splošne Bellmanove enačbe za
računanje vrednosti ui, kjer je ui cena najcenejše poti iz vozlišča 1 v vozlišče i
ui = {
0, če i = 1;
min (k (k, i)∈A) {uk + c k,i}, če i ≥ 2
}
Kdaj pravimo, da je usmerjeni graf G({1, …, m}, A) topološko urejen?
Naj bo G(V, A) graf z množico vozlišč V = {1, 2, . . . , m}.
Če za graf G(V, A) obstaja bijektivna funkcija τ : V → V, ki vsakemu i ∈ V priredi novo ime τ(i) ∈ V tako,
da velja (i, j) ∈ A ⇒ τ(i) < τ(j), rečemo, da τ topološko ureja G(V, A) oz. da je G(V, A) z njo topološko
urejen.
Topološko uredi dani graf.
Stran 14/23
Katere grafe lahko topološko uredimo?
Aciklične
V psevdokodi napišite algoritem za topološko urejanje grafa G(V, E).
V psevdokodi zapišite algoritem za odločanje, ali je dani graf G(V, A) acikličen.
Časovna zahtevnost naj bo polinomska glede na |V|.
Topološko urejanje(G)
G’ = G
s = 0
while ima vozlišče z vhodno stopnjo 0(G')
i = izberi vozlišče z vhodno stopnjo 0(G')
s++
tau(i) = s
G’ = G’-i
if prazen graf(G')
return(G je aciklicen; topološko urejen s tau)
else
return(G je cikličen)
Časovna zahtevnost: O(|V|^2)
Naj bo G splošen graf z n vozlišči in cenami povezav cij. Naj bo ui^(p) ≡ cena najcenejše poti iz 1 v i, ki
ima kvečjemu p povezav.
Zapišite Bellmanove enačbe, po katerih deluje Bellman-Fordov algoritem (za računanje najmanjših
cen poti iz 1 do vseh vozlišč grafa G).
Obrazloži oznake. Kdaj ne deluje? Kdaj pot ni enolično določena?
Ne deluje, če iz izhodišča do nekega vozlišča ni usmerjene poti in če obstajajo negativni cikli v grafu.
Oznake
• i … indeks vozlišča
• c … cena
• k … vozlišče, ki je sosed vozlišča z indeksom i
• A … množica usmerjenih povezav med vozlišči
• p … povezava
• ui^(p)… cena najcenejše poti iz 1 v i, ki ima kvečjemu p povezav
• ck,i .. cena najcenejše povezave med k in i
• c1, i … cena najcenejše poti iz 1 v i v grafu
ui^(p) = {
0 če i = 1, vsi p;
c1,i če i > 1, p = 1;
min {ui^(p-1), min (k (k, i)∈A) {uk^(p-1) + c k,i}}, če i > 1, p>1.
} --> stran 16/23
Napiši psevdokodo za Bellman-Fordov algoritem
Bellman Fordov algoritem(G(V, A, c))
for p = 1 to n - 1
u1(p) = 0
for i = 2 to n
ui(1) = c1,i
for p = 2 to n - 1
for i = 2 to n
ui^(p) = min{...} -->stran 16/23Zapiši psevdokodo za Floyd-Warshallov algoritem
Floyd-Warshallov algoritem(G(V,A,c))
for i = 1 to n
for j = 1 to n
U[i,j] = C[i,j]
for m = 1 to n
for i = 1 to n
for j = 1 to n
U[i,j] = min{U[i,j], U[i,m] + U[m,j}]}
endfor
endfor
endfor
endZapiši Bellmanovo enačbo za najcenejše poti iz izbranega izhodišča
stran 18/23 - 1
Zapiši Bellmanovo enačbo za najcenejše poti iz izhodišča v acikličnem grafu
stran 18/23 - 2
Zapiši Bellmanovo enačbo za najcenejše poti iz izhodišča v splošnem grafu (Bellmann-Ford)
stran 18/23 - 3
Zapiši Bellmanovo enačbo za najcenejše poti med vsemi pari
stran 18/23 - 4
Iskanje znakovnih podnizov
Časovna zahtevnost v najslabšem primeru
V najslabšem primeru ima naivni algoritem časovno zahtevnost O(n^2).
Izboljšani algoritem KMP pa ima linearno časovno zahtevnost tudi v najslabšem primeru.
Za Dvojiško iskanje povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) iskanje elementa v urejeni tabeli, deli in vladaj
b) O(log n)
n … dolžina tabele
Za Quicksort povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima (vse)?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) hitro urejanje, deli in vladaj
b) Ω(n log n), Θ(n log n), O(n2)
n … dolžina tabele
Za Heapsort povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) urejanje s kopico
b) O(n log n)
n … dolžina tabele
Za Bubblesort povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) urejanje z zamenjavami/mehurčki
b) O(n2)
n … dolžina tabele
Za Topološko urejanje grafa povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) topološko uredimo aciklični graf
b) O(|n|^2)
n … vozlišča
Za FFT povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) množenje polinoma
b) O(n log n)
n … stopnja polinoma
Za Strassenovo množenje povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) množenje matrik
b) O(n2,80)
n … velikost matrike
Za Ford-Fulkersonov algoritem povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) iskanje največjega pretoka v grafu, dinamično programiranje
b) O(v∗|A|)
v* … največji pretok
A … povezave
Za Bellman-Fordov algoritem povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) iskanje najcenejše poti iz izhodišča v splošnem grafu, dinamično programiranje
b) O(|V|^3)
V … vozlišča
Za Floyd-Warshallov algoritem povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) iskanje najcenejše poti med vsemi pari v grafu, dinamično programiranje
b) O(|V|^3)
V … vozlišča
Za KMP povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) Iskanje znakovnih podnizov
b) O(n)
n … dolžina besedila
Napiši psevdokodo za Djikstrov algoritem
procedure Dijkstrov_Algoritem(G(V,A,c));
begin
u_1 := 1;
for i := 2 to n do
u_i := c_1,i; // 1
D := {1}; Z := {2,3,...,n};
while NiPrazna(Z) then
u_k := min_{j \in Z}{u_j}; // 2
D := D + {k}; Z := Z - {k};
IF NiPrazna(Z) then
forall j \in Z do u_j := min{u_j, u_k + c_k,j}; // 3
endwhile
end.Za Djikstrov algoritem povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) Najcenejše poti iz izhodišca v grafu s pozitivnimi cenami
b) O(|V|^2)
V … vozlišča
Za 01-nahrbtnik povejte:
a) Kakšen problem rešuje?
b) Kakšne časovne zahtevnosti O(f(n)) ima?
Pri vsakem odgovoru povejte, kaj pomeni n.
a) Optimizacijski problem, kako vzeti čim dražje stvari, omejene z maksimalno težo
b) O(nV) ali O(n2^d)
n … število predmetov
V … velikost vhodnih podatkov d = [log V]
Algoritem FFT v psevdokodi
procedure FFT(a,d);
begin
if d=1 then return a else
begin
Pripravi \omega;
Razdeli(a,a_S,a_L);
p_S := FFT(a_S,d/2);
p_L := FFT(a_L,d/2);
p := Sestavi(p_S,p_L);
end
end.
