Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer science > APS2 teorija > Flashcards

APS2 teorija Flashcards

1
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

Θ(n^2*logn)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A 
T(n) = n^2 + 3n -> n^2 => Θ(n) = n^2
T(n) = n^2 - e^(-π/2) -> n^2 => Θ(n) = n^2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Definiraj urejanje zaporedij

A

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Naštejte 5 algoritmov za notranje urejanje.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Naštejte 5 metod za razvoj algoritmov

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

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

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Psevdokoda za navadno matrično množenje

A 
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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Psevdokoda za Strassenovo matrično množenje

A 
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Asimptotična zashtevnost za Strassenovo množenje

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Zapišite definicijo n-tega primitivnega korena.

A
  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))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Zapišite definicijo Fourierove matrike F

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Kakšna je inverzna matrika F-1?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

Glej 2nd_theory… Stran 10

24
Q

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

A

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

25
Q

Zapišite strogo (formalno) definicijo Problema nahrbtnika

A
  • 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)

26
Q

Ford-Fulkersonov algoritem

A

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.

27
Q

Za koliko povečamo pretok, ko pot zasitimo?

A

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

28
Q

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

A

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

29
Q

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

A

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.

30
Q

Topološko uredi dani graf.

A

Stran 14/23

31
Q

Katere grafe lahko topološko uredimo?

A

Aciklične

32
Q

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

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

33
Q

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?

A

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
34
Q

Napiši psevdokodo za Bellman-Fordov algoritem

A 
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
35
Q

Zapiši psevdokodo za Floyd-Warshallov algoritem

A 
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
36
Q

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

A

stran 18/23 - 1

37
Q

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

A

stran 18/23 - 2

38
Q

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

A

stran 18/23 - 3

39
Q

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

A

stran 18/23 - 4

40
Q

Iskanje znakovnih podnizov

A

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

41
Q

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

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

42
Q

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

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

43
Q

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

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

44
Q

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

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

45
Q

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

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

46
Q

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

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

47
Q

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

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

48
Q

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

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

49
Q

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

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

50
Q

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

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

51
Q

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

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

52
Q

Napiši psevdokodo za Djikstrov algoritem

A 
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.
53
Q

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

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

54
Q

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

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]

55
Q

Algoritem FFT v psevdokodi

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

Computer science (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions