Algoritmi in računska zahtevnost (24 %) (doc. Zoran Bosnić) (8 %) (doc. Gašper Fijavž)
Pregled poskusa 1
Začeto dne | sreda, 3. november 2010, 22:24 |
---|---|
Dokončano dne | sreda, 3. november 2010, 22:59 |
Porabljeni čas | 34 min 56 s |
Točke | 18/24 |
Ocena | 7.5 od možne ocene 10 (75%) |
Kakšno časovno zahtevnost ima naslednja psevdokoda programa?
for(int i=n; i>0; i/=2)
for(int j=0; j<m; j++)
for(int k=0; k<m; k++)
// operacija zahtevnosti O(1)
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 22:26:31 dne 3/11/10 | 1 | 1 | |
2 | Zapri in oceni | 22:59:46 dne 3/11/10 | 1 | 1 |
Podana je psevdokoda naslednjega rekurzivnega algoritma:
procedura(int n, int m) {
if (n==0) return;
else {
for(int i=0; i<m; i++) /* operacija O(1) */
procedura(n-1, m);
}
}
Kakšna je časovna zahtevnost gornje procedure?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 22:28:06 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | ![]() | 22:59:46 dne 3/11/10 | 0 | 0 |
Denimo, da imamo podan neskončen
prostor stanj, ki vsebuje končno število končnih vozlišč. Pri katerem od
naslednjih preiskovalnih algoritmov obstaja nevarnost ciklanja pri
iskanju rešitve?
1.) iskanje v širino
2.) iskanje v globino
3.) iterativno poglabljanje
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | samo 2 | 22:29:05 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | samo 2 | 22:59:46 dne 3/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | iskanju najkrajše poti | 22:29:22 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | iskanju najkrajše poti | 22:59:46 dne 3/11/10 | 0 | 0 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | logična trditev | 22:29:41 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | logična trditev | 22:59:46 dne 3/11/10 | 0 | 0 |
Kruskalov algoritem gradi minimalni vpeti gozd tako, da na vsakem koraku algoritem združi dve minimalni vpeti drevesi v eno samo minimalno vpeto drevo. Pri tem ju združi z minimalno povezavo med poljubnima minimalnima vpetima drevesima. Algoritem konča, ko so vsa vpeta drevesa združena v eno minimalno vpeto drevo.
Kakšno strategijo uporablja opisani algoritem?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | požrešno metodo | 22:31:07 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | požrešno metodo | 22:59:46 dne 3/11/10 | 1 | 1 |
Za nek program smo ocenili, da ima kvadratično časovno zahtevnost reda
pri n=10 traja 400ms in
pri n=20 traja 1000ms.
Za napovedovanje časa izvajanja smo uporabili model n2+ 200
Kakšen bo čas izvajanja pri n=30?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 3600ms | 22:31:38 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | 3600ms | 22:59:46 dne 3/11/10 | 0 | 0 |
Podan je rekurziven algoritem, za katerega časovno zahtevnost ocenimo z rekurzivno enačbo:
2n
)
Ta algoritem ima pričakovano časovno zahtevnost reda
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Časovna zahtevnost iskanja optimalne rešitve | 22:33:43 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Časovna zahtevnost iskanja optimalne rešitve | 22:59:46 dne 3/11/10 | 0 | 0 |

V vseh primerih kot vhodni podatek dobiš graf
- I. Ali
G vsebuje pot dolžine vsajn .2
- II. Ali
G vsebuje cikel dolžine vsaj2n ? - III. Ali
G vsebuje vpeto drevo? - IV. Koliko različnih 3-barvanj točk dopušča graf
G ? - V. Ali je najkrajši cikel v grafu
G dolžine vsajn ?2
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | II, III in V. | 22:35:40 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | II, III in V. | 22:59:46 dne 3/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | navadne zamenjave (angl. bubble sort) | 22:36:04 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | navadne zamenjave (angl. bubble sort) | 22:59:46 dne 3/11/10 | 1 | 1 |
Podan je preprost algoritem za iskanje podnizov, ki sprejme krajši niz M dolžine m in išče njegove pojavitve v daljšem nizu N, ki je dolžine n. Algoritem deluje tako, da pri vsakem odmiku s preveri enakost M[1 ... m] == N[s+1 ... s+m].
Oceni red časovne zahtevnosti takšnega algoritma (predpostavi, da m in n nista fiksna).
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 22:37:22 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | ![]() | 22:59:46 dne 3/11/10 | 1 | 1 |
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | S prevedbo na problem pretoka v omrežjih. | 22:45:53 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | S prevedbo na problem pretoka v omrežjih. | 22:59:46 dne 3/11/10 | 1 | 1 |

# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Boyer-Mooreov algoritem | 22:46:22 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Boyer-Mooreov algoritem | 22:59:46 dne 3/11/10 | 1 | 1 |
Kruskalov algoritem se uporablja za iskanje minimalnega vpetega drevesa v grafu. Postopa tako, da na začetku vsako vozlišče obravnava kot samostojno drevo. Iterativno nadaljuje tako, da na vsakem koraku združi dve drevesi v eno minimalno vpeto drevo, tako da uporabi minimalno povezavo med njima. Ko so v drevesu vsa vozlišča grafa, se algoritem ustavi.
Denimo, da imamo v grafu n vozlišč in m povezav ter predpostavimo, da algoritem podatke o najkrajših povezavah hrani v prioritetni vrsti, implementirani s kopico. Kakšna je časovna zahtevnost algoritma?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | iskanje minimalnega vpetega drevesa | 22:48:28 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | iskanje minimalnega vpetega drevesa | 22:59:46 dne 3/11/10 | 1 | 1 |
Optimalno binarno iskalno drevo ima svoje elemente urejene tako, da je povprečni čas iskanja elementa v njem minimalen (drevo še vedno ohranja urejenost elementov: levo-manjši elementi, desno-večji). Gradnje optimalnega binarnega iskalnega drevesa se lotimo z algoritmom, ki končno drevo sestavlja postopoma: najprej preišče vse kombinacije vozlišč, ki vodijo do optimalnega drevesa višine 2, nato le-te uporabi za iskanje optimalnega drevesa višine 3 in tako naprej, dokler ne sestavi drevesa z vsemi potrebnimi vozlišči. Algoritem torej na vsakem koraku uporabi optimalno rešitev manjšega reda. Princip, na katerem je ta algoritem zasnovan se imenuje
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | dinamično programiranje | 22:50:49 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | dinamično programiranje | 22:59:46 dne 3/11/10 | 1 | 1 |
Implementirali smo algoritem, ki dela v odvisnosti od parametrov m)=log4m+n5+2n2
Kakšen je najbolj poenostavljen zapis reda te časovne zahtevnosti s funkcijo
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 22:51:33 dne 3/11/10 | 1 | 1 | |
2 | Zapri in oceni | 22:59:46 dne 3/11/10 | 1 | 1 |
Podan je rekurziven algoritem, za katerega časovno zahtevnost ocenimo z rekurzivno enačbo:
Ta algoritem ima pričakovano časovno zahtevnost reda
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Strassenova metoda za množenje matrik | 22:53:26 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Strassenova metoda za množenje matrik | 22:59:46 dne 3/11/10 | 1 | 1 |
Implementirati želimo algoritem, ki bo problem rešil tako, da bo preizkusil vse možne poti, ki bi lahko pripeljale do rešitve. Pri svojem izvajanju ta algoritem nadaljuje po neki poti, dokler ne izčrpa vsa možna nadaljevanja. Tedaj se vrne korak nazaj in nadaljuje iz prejšnjega koraka v drugi smeri. S takšnim izvajanjem nadaljuje, vse dokler ne pride do rešitve ali izčrpa vse možnosti. Kakšen princip iskanja rešitve uporablja algoritem?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | sestopanje | 22:56:50 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | sestopanje | 22:59:46 dne 3/11/10 | 1 | 1 |

V vseh primerih kot vhodni podatek dobiš graf
- I. Ali
G vsebuje kliko (poln podgraf) nan točkah.2
- II. Koliko Hamiltonovih ciklov vsebuje graf
G ? - III. Koliko vpetih dreves vsebuje graf
G ? - IV. Koliko različnih 2-barvanj točk dopušča graf
G ? - V. Koliko ciklov na
n točkah vsebuje graf2
G ?
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo III. | 22:58:34 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Samo III. | 22:59:46 dne 3/11/10 | 0 | 0 |
Kateri od naslednjih algoritmov za urejanje ima pričakovano časovno zahtevnost boljšo kot
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | urejanje s porazdelitvami (angl. partition sort): urejanje, ki tabelo števil razdeli glede na mejno vrednost in z rekurzivnim razcepom nadaljuje urejanje vsakega od obeh delov | 22:59:39 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | urejanje s porazdelitvami (angl. partition sort): urejanje, ki tabelo števil razdeli glede na mejno vrednost in z rekurzivnim razcepom nadaljuje urejanje vsakega od obeh delov | 22:59:46 dne 3/11/10 | 1 | 1 |