Teorija

Question 1

Dvojiško Iskanje (Binary Search)

Answer 1

Iskanje elementa v tabeli
Deli in vladaj
O(log n)
n - dolžina tabele

Question 2

Quicksort

Answer 2

Hitro urejanje
Deli in vladaj
O(n^2)
n - dolžina tabele

Question 3

Heapsort

Answer 3

Urejanje s kopico
O(n log n)
n - dolžina tabele

Question 4

Bubblesort

Answer 4

Urejanje z zamenjavami/mehurčki
O(n^2)
n - dolžina tabele

Question 5

Topološko urejanje grafa

Answer 5

Urejanje acikličnega grafa tako, da manjše poimenovana vozlišča kažejo na večja.
O(n^2)
n - št. vozlišč |V|

Question 6

FFT (Hitra Fourierjeva Transformacija)

Answer 6

Množenje polinomov
O(n log n)
n - stopnja polinomov

Question 7

Strassen

Answer 7

Množenje matrik
O(n^2.81)
n - velikost matrike

Question 8

Ford-Fulkersonov algoritem

Answer 8

Iskanje maksimalnega pretoka v grafu
O(m*n)
m - maksimalen pretok
n - št. povezav |A|

Question 9

Bellman-Fordov algoritem

Answer 9

Iskanje najcenejše poti v grafu
O(n^3)
n - št. vozlišč

Question 10

Floyd-Warshallov algoritem

Answer 10

Iskanje najcenejše poti v grafu med vsemi pari
O(n^3)
n - št. vozlišč

Question 11

5 metod za razvijanje programov

Answer 11

Deli in vladaj, dinamično programiranje, rekurzivni razcep, sestopanje, požrešni algoritem, naivni algoritem

Question 12

Definiraj urejanje zaporedij

Answer 12

Dani so a1, a2, a3, …, an in relacije popolne urejenosti ≺.
Cilj je poiskati tako ureditev, da velja a1 ≺ a2 ≺ … ≺ an

Question 13

Naštej algoritme za notranje urejanje

Answer 13

Quicksort, Heapsort, Selection sort, Insertion sort, Mergesort, Bubble sort

Question 14

Best, worst, avg case za heapsort

Answer 14

Ω(nlogn), Θ(nlogn), O(nlogn)

Question 15

Best, worst, avg case za quicksort

Answer 15

Ω(nlogn), Θ(nlogn), O(n^2)

Question 16

Kaj je načelo optimalnosti? Kje se uporablja?

Answer 16

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.

Question 17

Kdaj rečemo, da ima algoritem psevdo-polinomsko časovno zahtevnost?

Answer 17

Kadar je časovna kompleksnost algoritma odvisna od numerične vrednosti vhoda in ne dolžine vhoda.

Question 18

Naštej matrična mnnoženja in zapiši njihove časovne zahtevnosti.

Answer 18

Navadno množenje: O(n^3)
Deli in vladaj: O(n^3)
Strassen: O(n^2.81)

Question 19

Kakšna je časovna zahtevnost navadnega in izboljšanega algoritma za iskanje k-tega elementa?

Answer 19

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.

Question 20

Kaj je topološka ureditev grafa? Kdaj lahko graf topološko uredimo?

Answer 20

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.

Question 21

Master theorem za Deli in Vladaj

Answer 21

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)

Question 22

DFT - zapisi definicijo n-tega primitivnega korena, matriko F in njen inverz, kaj delamo s to matriko v kerem cajtu.

Answer 22

1. w^d = 1 in
2. 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.

Question 23

Stroga definicija problema nahrbtnika

Answer 23

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:

1. Σt(i) <= b
2. Σv(i) je max (maksimiziramo vrednost plena)

Question 24

Bellmanove enačbe. Kaj, kje, zakaj?

Answer 24

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)}

Question 25

Pogoj za zatesnitev temeljne poti

Answer 25

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-=

Question 26

Floyd-Warshall psevdokoda pls

Answer 26

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]);

Question 27

Bellman-Ford psevdokoda pls

Answer 27

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}}

Question 28

Topološko urejanje grafa psevdokoda pls

Answer 28

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"

Question 29

Dijkstra psevdokoda pls

Answer 29

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}