To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.
If the math symbols print as black boxes, turn off image alpha channels
using the Options pane of the jsMath control panel.

jsMath

Algoritmi in računska zahtevnost (24 %) (doc. Zoran Bosnić) (8 %) (doc. Gašper Fijavž)

Pregled poskusa 1

Začeto dnesreda, 3. november 2010, 22:24
Dokončano dnesreda, 3. november 2010, 22:59
Porabljeni čas34 min 56 s
Točke18/24
Ocena7.5 od možne ocene 10 (75%)
Question 1
Točke: 1/1

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)

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(m2logn)22:26:31 dne 3/11/1011
2Zapri in oceniO(m2logn)22:59:46 dne 3/11/1011
Question 2
Točke: 0/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?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(mn)22:28:06 dne 3/11/1000
2Zapri in oceniO(mn)22:59:46 dne 3/11/1000
Question 3
Točke: 1/1

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

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenasamo 222:29:05 dne 3/11/1011
2Zapri in ocenisamo 222:59:46 dne 3/11/1011
Question 4
Točke: 0/1
Dijkstrov algoritem, ki ga izvajamo na usmerjenih grafih z nenegativnimi cenami povezav je namenjen:
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaiskanju najkrajše poti22:29:22 dne 3/11/1000
2Zapri in oceniiskanju najkrajše poti22:59:46 dne 3/11/1000
Question 5
Točke: 0/1
Kateri od naslednjih pojmov je najmanj (oziroma ni) povezan s postopkom formalnega dokazovanja pravilnosti programov?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenalogična trditev22:29:41 dne 3/11/1000
2Zapri in ocenilogična trditev22:59:46 dne 3/11/1000
Question 6
Točke: 1/1

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?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenapožrešno metodo22:31:07 dne 3/11/1011
2Zapri in ocenipožrešno metodo22:59:46 dne 3/11/1011
Question 7
Točke: 0/1

Za nek program smo ocenili, da ima kvadratično časovno zahtevnost reda O(n2). Izmerili smo, da izvajanje podatkov:
pri n=10 traja 400ms in
pri n=20 traja 1000ms.
Za napovedovanje časa izvajanja smo uporabili model T(n)=an2+ 200  (model smo delno določili iz meritev, konstanto a je potrebno še izračunati).

Kakšen bo čas izvajanja pri n=30?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocena3600ms22:31:38 dne 3/11/1000
2Zapri in oceni3600ms22:59:46 dne 3/11/1000
Question 8
Točke: 1/1

Podan je rekurziven algoritem, za katerega časovno zahtevnost ocenimo z rekurzivno enačbo:

T(n)=6n+T(2n)
T(1)=1

Ta algoritem ima pričakovano časovno zahtevnost reda

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(logn) 22:32:51 dne 3/11/1000
2OcenaO(n)22:33:06 dne 3/11/1011
3Zapri in oceniO(n)22:59:46 dne 3/11/1011
Question 9
Točke: 0/1
Standardno simpleksno metodo za reševanje linearnih optimizacijskih problemov uporabimo na problemu P z n neznankami in m neenačbami. Katera od spodnjih trditev je resnična.
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaČasovna zahtevnost iskanja optimalne rešitve P je O(mn).22:33:43 dne 3/11/1000
2Zapri in oceniČasovna zahtevnost iskanja optimalne rešitve P je O(mn).22:59:46 dne 3/11/1000
Question 10
Točke: 1/1
Ob predpostavki P=NP  odloči, kateri izmed spodnjih problemov so polinomski.
V vseh primerih kot vhodni podatek dobiš graf G z n točkami.
  • I. Ali G vsebuje pot dolžine vsaj n2 .
  • II. Ali G vsebuje cikel dolžine vsaj 2n?
  • 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 vsaj n2 ?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaII, III in V.22:35:40 dne 3/11/1011
2Zapri in oceniII, III in V.22:59:46 dne 3/11/1011
Question 11
Točke: 1/1
Podan je algoritem za urejanje elementov, ki deluje tako, da pri večkratnem prehodu skozi tabelo zamenjuje sosednje elemente, ki niso v pravilni urejenosti. Po določenem številu iteracij algoritem na ta način postavi vse elemente v urejen vrstni red. Kako imenujemo opisani algoritem ze urejanje?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenanavadne zamenjave (angl. bubble sort)22:36:04 dne 3/11/1011
2Zapri in oceninavadne zamenjave (angl. bubble sort)22:59:46 dne 3/11/1011
Question 12
Točke: 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).

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO((nm+1)m)22:37:22 dne 3/11/1011
2Zapri in oceniO((nm+1)m)22:59:46 dne 3/11/1011
Question 13
Točke: 1/1
Podan je algoritem z naslednjim neformalnim opisom: Vhod algoritma je množica točk, med katerimi mora algoritem poiskati natanko eno točko, ki ustreza določenemu kriteriju. Na vsakem koraku iterativnega izvajanja algoritma algoritem izloči 3/4 točk - kandidatov - in nadaljuje s preiskovanjem preostale 1/4 točk (vsak tak korak se izvede v konstantnem času). Kakšen red časovne zahtevnosti ima ta algoritem?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(n)22:38:49 dne 3/11/1000
2OcenaO(logn) 22:39:02 dne 3/11/1011
3Zapri in oceniO(logn) 22:59:46 dne 3/11/1011
Question 14
Točke: 1/1
Naj bosta A in B disjunktni neprazni množici točk grafa G. Poiskati želimo čimveč disjunktnih AB poti tj. disjunktnih poti z enim krajiščem v A in drugim krajiščem v B. Kako?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaS prevedbo na problem pretoka v omrežjih.22:45:53 dne 3/11/1011
2Zapri in oceniS prevedbo na problem pretoka v omrežjih.22:59:46 dne 3/11/1011
Question 15
Točke: 1/1
Med naslednjimi algoritmi najdi vsiljivca, ki vsebinsko ne paše med ostale (opomba: to, da je Dijkstrov algoritem iz samo enega imena, ne pomeni, da je vsiljivec smeško ):
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaBoyer-Mooreov algoritem22:46:22 dne 3/11/1011
2Zapri in oceniBoyer-Mooreov algoritem22:59:46 dne 3/11/1011
Question 16
Točke: 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?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(nlogm) 22:47:16 dne 3/11/1000
2OcenaO(mlogm) 22:47:31 dne 3/11/1011
3Zapri in oceniO(mlogm) 22:59:46 dne 3/11/1011
Question 17
Točke: 1/1
Problem načrtovanja čim cenejših energetskih, prometnih in komunikacijskih omrežij lahko predstavimo z grafom, v katerem cene povezav predstavljajo potrebne dolžine infrastrukturnih elementov v teh omrežjih (kablov, cevi, optičnih vlaken). Zahteva, ki jo imamo pri načrtovanju teh omrežij, je ta, da je vsak kraj v omrežju povezan z vsaj enim drugim (in preko le-tega posredno do vseh ostalih v omrežju). Če želimo optimizirati cene povezav v takem omrežju, moramo na grafu, ki predstavlja ta problem, uporabiti algoritem za:
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaiskanje minimalnega vpetega drevesa22:48:28 dne 3/11/1011
2Zapri in oceniiskanje minimalnega vpetega drevesa22:59:46 dne 3/11/1011
Question 18
Točke: 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

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenadinamično programiranje22:50:49 dne 3/11/1011
2Zapri in ocenidinamično programiranje22:59:46 dne 3/11/1011
Question 19
Točke: 1/1

Implementirali smo algoritem, ki dela v odvisnosti od parametrov m in n. Za različne vrednosti teh parametrov ugotovimo, da med časom izvajanja in parametri velja odvisnost T(nm)=log4m+n5+2n2 .

Kakšen je najbolj poenostavljen zapis reda te časovne zahtevnosti s funkcijo O(_) ?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(logm+n5) 22:51:33 dne 3/11/1011
2Zapri in oceniO(logm+n5) 22:59:46 dne 3/11/1011
Question 20
Točke: 1/1

Podan je rekurziven algoritem, za katerega časovno zahtevnost ocenimo z rekurzivno enačbo:

T(n)=3n+T(n1)
T(1)=15

Ta algoritem ima pričakovano časovno zahtevnost reda

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaO(2n)22:52:13 dne 3/11/1000
2OcenaO(n2)22:52:17 dne 3/11/1011
3Zapri in oceniO(n2)22:59:46 dne 3/11/1011
Question 21
Točke: 1/1
Katerega od spodnjih problemov je možno reševati z algoritmom, zasnovanim na podlagi strategije rekurzivnega razcepa problema?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaStrassenova metoda za množenje matrik22:53:26 dne 3/11/1011
2Zapri in oceniStrassenova metoda za množenje matrik22:59:46 dne 3/11/1011
Question 22
Točke: 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?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenasestopanje22:56:50 dne 3/11/1011
2Zapri in ocenisestopanje22:59:46 dne 3/11/1011
Question 23
Točke: 0/1
Ob predpostavki P=NP  odloči, kateri izmed spodnjih problemov so polinomski.
V vseh primerih kot vhodni podatek dobiš graf G z n točkami.
  • I. Ali G vsebuje kliko (poln podgraf) na n2  točkah.
  • 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 n2  točkah vsebuje graf G?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1OcenaSamo III.22:58:34 dne 3/11/1000
2Zapri in oceniSamo III.22:59:46 dne 3/11/1000
Question 24
Točke: 1/1

Kateri od naslednjih algoritmov za urejanje ima pričakovano časovno zahtevnost boljšo kot O(n2)? Predpostavi, da uporabljamo osnovne verzije algoritmov, ki uporabljajo zaporedno pregledovanje elementov in ne dvojiškega iskanja.

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
#DejanjeOdgovorČasČisto število točkOcena
1Ocenaurejanje s porazdelitvami (angl. partition sort): urejanje, ki tabelo števil razdeli glede na mejno vrednost in z rekurzivnim razcepom nadaljuje urejanje vsakega od obeh delov22:59:39 dne 3/11/1011
2Zapri in oceniurejanje s porazdelitvami (angl. partition sort): urejanje, ki tabelo števil razdeli glede na mejno vrednost in z rekurzivnim razcepom nadaljuje urejanje vsakega od obeh delov22:59:46 dne 3/11/1011