Teorija Flashcards
Dvojiško Iskanje (Binary Search)
Iskanje elementa v tabeli
Deli in vladaj
O(log n)
n - dolžina tabele
Quicksort
Hitro urejanje
Deli in vladaj
O(n^2)
n - dolžina tabele
Heapsort
Urejanje s kopico
O(n log n)
n - dolžina tabele
Bubblesort
Urejanje z zamenjavami/mehurčki
O(n^2)
n - dolžina tabele
Topološko urejanje grafa
Urejanje acikličnega grafa tako, da manjše poimenovana vozlišča kažejo na večja.
O(n^2)
n - št. vozlišč |V|
FFT (Hitra Fourierjeva Transformacija)
Množenje polinomov
O(n log n)
n - stopnja polinomov
Strassen
Množenje matrik
O(n^2.81)
n - velikost matrike
Ford-Fulkersonov algoritem
Iskanje maksimalnega pretoka v grafu
O(m*n)
m - maksimalen pretok
n - št. povezav |A|
Bellman-Fordov algoritem
Iskanje najcenejše poti v grafu
O(n^3)
n - št. vozlišč
Floyd-Warshallov algoritem
Iskanje najcenejše poti v grafu med vsemi pari
O(n^3)
n - št. vozlišč
5 metod za razvijanje programov
Deli in vladaj, dinamično programiranje, rekurzivni razcep, sestopanje, požrešni algoritem, naivni algoritem
Definiraj urejanje zaporedij
Dani so a1, a2, a3, …, an in relacije popolne urejenosti ≺.
Cilj je poiskati tako ureditev, da velja a1 ≺ a2 ≺ … ≺ an
Naštej algoritme za notranje urejanje
Quicksort, Heapsort, Selection sort, Insertion sort, Mergesort, Bubble sort
Best, worst, avg case za heapsort
Ω(nlogn), Θ(nlogn), O(nlogn)
Best, worst, avg case za quicksort
Ω(nlogn), Θ(nlogn), O(n^2)
Kaj je načelo optimalnosti? Kje se uporablja?
Zaporedje odločitev D1, D2, …, Dn je optimalno, če nas privede do optimalne rešitve problema N.
Načelo optimalnosti se uporablja pri metodi dinamičnega programiranja za razvoj algoritmov. Dinamično programiranje sistematično preglejuje delne rešitve in sestavlja optimalno rešitev.
Kdaj rečemo, da ima algoritem psevdo-polinomsko časovno zahtevnost?
Kadar je časovna kompleksnost algoritma odvisna od numerične vrednosti vhoda in ne dolžine vhoda.
Naštej matrična mnnoženja in zapiši njihove časovne zahtevnosti.
Navadno množenje: O(n^3)
Deli in vladaj: O(n^3)
Strassen: O(n^2.81)
Kakšna je časovna zahtevnost navadnega in izboljšanega algoritma za iskanje k-tega elementa?
Navadna: O(nlogn)
Izboljšana: O(n) –> algoritem je asimptotično optimalen
V izboljšani verziji algoritma (Blum-Floyd-Pratt-Rivest-Tarjanov) se uporablja metoda Deli in vladaj.
Kaj je topološka ureditev grafa? Kdaj lahko graf topološko uredimo?
Graf je topološko urejen ko vsaka povezava poteka iz vozlišča z nižjo oznako v vozlišče z višjo.
Graf lahko topološko uredimo ko je acikličen.
Master theorem za Deli in Vladaj
a - št. podproblemov ki jih rešimo b - konstanta c - faktor delitve d - red velikosti zahtevnosti n - velikost problema
(zapisi oba sistema - aT(n/c) + bn^d in (c^d)/a)
DFT - zapisi definicijo n-tega primitivnega korena, matriko F in njen inverz, kaj delamo s to matriko v kerem cajtu.
- w^d = 1 in
- w^k != 1 za k = 1, …, d-1
V obsegu C (kompleksna mnozica) je w^(i*(2pi/d)), kjer je i imaginarna enota.
Matrika F je matrika d*d komponent w^(i,j) kjer je 0 <= i,j <= d-1.
Inverzna DFT F^-1 je reda dd, komponente so:
(1/d)w^(-i*j), kjer je 0 <= i,j <= d-1.
F*F^1 = I.
S pomočjo F predstavimo DFT, ki je linearna transformacija prostora V. Algoritem FFT v času O(n log n) pretvori koeficientno predstavitev polinoma v vrednostno.
Stroga definicija problema nahrbtnika
Množica R = {1, 2, 3, …, n} predstavlja predmete
Funkcija v: R -> N predmetu R(i) priredi vrednost v(i)
Funkcija t: R -> N predmetu R(i) priredi težo t(i)
Število b € N je nosilnost nahrbtnika
Cilj je poiskati podmnožico P⊆R, da velja:
- Σt(i) <= b
- Σv(i) je max (maksimiziramo vrednost plena)
Bellmanove enačbe. Kaj, kje, zakaj?
Bellmanove enačbe se uporabljajo pri dinamičnem programiranju za iskanje najcenejših poti s predpostavko, da v grafu G obstaja usmerjena pot do vsakega vozlišča in da G nima negativnih ciklov.
Najcenejše poti iz izbranega vozlišča:
U_i
if(i=1)
u_i = 0
else if(i >= 2)
min {u_k + c_k,i} (min k, (k, i) € A)
Najcenejše poti iz izhodišča v ackiličnem grafu
U_i
if(i = 1)
u_i = 0
else if(i >= 2)
min {u_k + c_k,i} (min k, k < i)
Najcenejše poti iz izhodišča v splošnem grafu (Bellman-Ford)
(u_i)^(p)
if(i = 1, vsi p)
u_i = 0
else if( i >1, p = 1)
c_i,j
else if(i > 1, p > 1)
min{(u_i)^(p-1), min {(u_k)^(p-1) + c_k,i}} (drugi min k, (k, i)€ A
Najcenejše poti med pari (Floyd-Warshall)
(u_i,j)^(m)
if(m = 0)
c_i,j
else if(1 <= m <= n)
min{(u[i][j]^(m-1), u[i][m]^(m-1) + u[m][j]^(m-1)}
Pogoj za zatesnitev temeljne poti
Temeljno pot zatisnemo natanko tedaj ko pretok povečamo za:
min{min{c_i,j - v_i,j}, min{v_i,j}} (prvi min v p+, drugi v p-=
Floyd-Warshall psevdokoda pls
VHOD: C - matrika cen
IZHOD: U - matrika najcenejših poti med pari
int, k, i, j;
U = C;
for(k = 1; k <= n; k++)
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
U[i][j] = min(U[i][j], U[i][k] + U[k][j]);
Bellman-Ford psevdokoda pls
for(int p = 1; p <= n-1; p++)
for(int i = 1; i <= n; i++)
u_i^(p) = min {u_i^(p-1), min{u_k^(p-1) + c_ki}}
Topološko urejanje grafa psevdokoda pls
G_t = G;
s = 0;
while (G_t vsebuje vsaj eno vozlišče s vhodno stopnjo 0) do {
v = izberi vozlišče s v.s. = 0 v G_t;
s++:
Ord(v) = s;
G_t = G_t - v;
end
if(G_t = prazna množica)
return "DA" in Ord(...);
else
return "NE"Dijkstra psevdokoda pls
P = {1};
T = {2,3,…,u};
u_1 = 0;
za vsak i > 1: u_i = c(1, i), ce je (1,i) v mnozici E sicer u_i = infinity
while T!= 0 do
poisci k element T, kjer u_k = min {u_i};
T = T - {k};
P = P U {k};
za v_j v mnozici T: u_j = min{u_j, u_k + c_kj}
