APS2 teorija

Question 1

Zapiši definicijo f(n) = O(g(n))

Answer 1

f(n) = O(g(n)): f(n) je omejena navzgor z g(n)

(∃c1, n0 > 0)(∀n ≥ n0) [0 ≤ f(n) ≤ c1*g(n))]

Question 2

Zapiši definicijo f(n) = Ω(h(n))

Answer 2

f(n) = Ω(h(n)): f(n) je omejena navzdol z h(n)

(∃c2, n1 > 0)(∀n ≥ n1) [c2*h(n)) ≤ f(n)]

Question 3

Zapiši definicijo f(n) = Θ(k(n))

Answer 3

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

Question 4

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

Answer 4

Θ(n^2*logn)

Question 5

Izpeljite asimptotično (Θ) zahtevnost funkcije f(n) = 8^(log2(n))

Answer 5

f(n) = 8^(log2(n)) = n^(log2(8)) = n^3 => Θ(n^3)

Question 6

Izpeljite asimptotično (Θ) zahtevnost funkcije f(n) = 4^(log2(n))

Answer 6

f(n) = 4^(log2(n)) = n^(log2(4)) = n^2 => Θ(n^2)

Question 7

Kaj hitreje narašča?
f(n) = e^n + n!
g(n) = n^(n+1)

Answer 7

f(n) (n -> ∞) = n!
g(n) (n -> ∞) = n^n

g(n) > f(n)
g(n) narašča hitreje

Question 8

Izpeljite asimptotično (Θ) zahtevnost za naslednji funkciji.
f(n) = n^2 + 3n
g(n) = n^2 - e^(-π/2)

Answer 8

T(n) = n^2 + 3n -> n^2 => Θ(n) = n^2
T(n) = n^2 - e^(-π/2) -> n^2 => Θ(n) = n^2

Question 9

Definiraj urejanje zaporedij

Answer 9

Dani so a1, a2 ,…, an in relacija popolne urejenosti ≼.

Cilj je poiskati tako razporeditev, da velja ai1 ≼ ai2 ≼ … ≼ ain.

Question 10

Naštejte 5 algoritmov za notranje urejanje.

Answer 10

(Č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)

Question 11

Najboljši, povprečen in najslabši case scenario časovne zahtevnosti za heapsort

Answer 11

Ω(n log n), Θ(n log n), O(n log n)

Question 12

Najboljši, povprečen in najslabši case scenario časovne zahtevnosti za quicksort

Answer 12

Ω(n log n), Θ(n log n), O(n2)

Question 13

Naštejte 5 metod za razvoj algoritmov

Answer 13

Dinamično programiranje, deli in vladaj, sestopanje, požrešni algoritmi, rekurzivni razcep

Question 14

Opiši razliko med dinamičnim programiranjem in deli in vladaj ter načelo optimalnosti

Answer 14

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.

Question 15

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

Answer 15

Časovna kompleksnost algoritma odvisna od numerične vrednosti vhoda, in ne od velikosti vhoda.

Question 16

Zapišite glavni izrek (Master Theorem) metode deli & vladaj. Pojasnite pomen uporabljenih oznak.

Answer 16

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

Question 17

Psevdokoda za navadno matrično množenje

Answer 17

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.

Question 18

Psevdokoda za Strassenovo matrično množenje

Answer 18

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

Question 19

Asimptotična zashtevnost za Strassenovo množenje

Answer 19

T(n) = Θ(n^(logc(a))) = Θ(n^(log2(7))) = Θ(n^2,80735)

Question 20

Zapišite definicijo n-tega primitivnega korena.

Answer 20

1. ω^d = 1 // ω je koren enote
2. ω^k ≠ 1 za k = 1, …, d-1 // ω je primitivni koren enote

V kompleksnem (C) obsegu je
ω = e^(i*(2π/d))

Question 21

Zapišite definicijo Fourierove matrike F

Answer 21

Fij = ω^(i*j), 0 ≤ i, j < d

Question 22

Kakšna je inverzna matrika F-1?

Answer 22

Fij^-1 = 1/d * ω^(-i*j), 0 ≤ i, j < d

Question 23

Napiši matriki F in inverzni F 4 X 4 za splošni ω pri DFT

Answer 23

Glej 2nd_theory… Stran 10

Question 24

Kakšna je časovna zahtevnost algoritma za Hitro Fourierovo Transformacijo (FFT)?

Answer 24

Polinoma stopnje n lahko zmnožimo v času Θ(n log n).

Question 25

Zapišite strogo (formalno) definicijo Problema nahrbtnika

Answer 25

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

Question 26

Ford-Fulkersonov algoritem

Answer 26

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.

Question 27

Za koliko povečamo pretok, ko pot zasitimo?

Answer 27

min{min((i,j)∈P+) {c i,j - v i,j}, min((i,j)∈P-) {v i,j}}

Question 28

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

Answer 28

ui = { 0, če i = 1; min (k (k, i)∈A) {uk + c k,i}, če i ≥ 2 }

Question 29

Kdaj pravimo, da je usmerjeni graf G({1, ..., m}, A) topološko urejen?

Answer 29

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.

Question 30

Topološko uredi dani graf.

Answer 30

Stran 14/23

Question 31

Katere grafe lahko topološko uredimo?

Answer 31

Aciklične

Question 32

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

Answer 32

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

Question 33

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?

Answer 33

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

Question 34

Napiši psevdokodo za Bellman-Fordov algoritem

Answer 34

``` 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/23 ```

Question 35

Zapiši psevdokodo za Floyd-Warshallov algoritem

Answer 35

``` 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 end ```

Question 36

Zapiši Bellmanovo enačbo za najcenejše poti iz izbranega izhodišča

Answer 36

stran 18/23 - 1

Question 37

Zapiši Bellmanovo enačbo za najcenejše poti iz izhodišča v acikličnem grafu

Answer 37

stran 18/23 - 2

Question 38

Zapiši Bellmanovo enačbo za najcenejše poti iz izhodišča v splošnem grafu (Bellmann-Ford)

Answer 38

stran 18/23 - 3

Question 39

Zapiši Bellmanovo enačbo za najcenejše poti med vsemi pari

Answer 39

stran 18/23 - 4

Question 40

Iskanje znakovnih podnizov

Answer 40

Č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.

Question 41

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.

Answer 41

a) iskanje elementa v urejeni tabeli, deli in vladaj b) O(log n) n ... dolžina tabele

Question 42

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.

Answer 42

a) hitro urejanje, deli in vladaj b) Ω(n log n), Θ(n log n), O(n2) n ... dolžina tabele

Question 43

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.

Answer 43

a) urejanje s kopico b) O(n log n) n ... dolžina tabele

Question 44

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.

Answer 44

a) urejanje z zamenjavami/mehurčki b) O(n2) n ... dolžina tabele

Question 45

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.

Answer 45

a) topološko uredimo aciklični graf b) O(|n|^2) n ... vozlišča

Question 46

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.

Answer 46

a) množenje polinoma b) O(n log n) n ... stopnja polinoma

Question 47

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.

Answer 47

a) množenje matrik b) O(n2,80) n ... velikost matrike

Question 48

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.

Answer 48

a) iskanje največjega pretoka v grafu, dinamično programiranje b) O(v∗|A|) v* ... največji pretok A ... povezave

Question 49

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.

Answer 49

a) iskanje najcenejše poti iz izhodišča v splošnem grafu, dinamično programiranje b) O(|V|^3) V ... vozlišča

Question 50

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.

Answer 50

a) iskanje najcenejše poti med vsemi pari v grafu, dinamično programiranje b) O(|V|^3) V ... vozlišča

Question 51

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.

Answer 51

a) Iskanje znakovnih podnizov b) O(n) n ... dolžina besedila

Question 52

Napiši psevdokodo za Djikstrov algoritem

Answer 52

``` 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. ```

Question 53

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.

Answer 53

a) Najcenejše poti iz izhodišca v grafu s pozitivnimi cenami b) O(|V|^2) V ... vozlišča

Question 54

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.

Answer 54

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]

Question 55

Algoritem FFT v psevdokodi

Answer 55

``` 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. ```