Diskretne strukture (32 %) (doc. Gašper Fijavž)
Pregled poskusa 1
Začeto dne | sreda, 3. november 2010, 23:02 |
---|---|
Dokončano dne | četrtek, 4. november 2010, 00:09 |
Porabljeni čas | 1 ura 7 min |
Točke | 12/32 |
Ocena | 3.75 od možne ocene 10 (38%) |
Question 1
Točke: 0/1
Trimestni izjavni veznik A definiramo takole: A(p
q
r)=p
(q
r) . Katere od naslednjih trditev so resnične?




- I.
A(p lahko izrazimo samo z uporabo negacije in konjunkcije,q
r)
. - II. Implikacijo
lahko izrazimo samo z uporabo veznikaA . - III.
A ohranja vsaj eno logično vrednost. - IV.
A lahko izrazimo samo z uporabo negacije in disjunkcije, . - V.
je poln nabor izjavnih veznikov.A
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo I in III. | 23:04:31 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Samo I in III. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 2
Točke: 0/1
Kromatično število grafa G ,
(G) , je najmanjše takšno naravno število k , da lahko točke grafa G obarvamo s k
barvami tako, da sta vsaki sosednji točki različnih barv. Katera izmed
naslednjih trditev najbolje opiše kromatično število grafa?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 23:06:37 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | ![]() | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 3
Točke: 1/1
Naj bo 
permutacija iz simetrične grupe reda 7 (
si lahko predstavljaš kot bijektivno preslikavo množice
1



7
vase). Fiksna točka permutacije je število, ki ga permutacija slika sama vase. Katere izmed naslednjih trditev so resnične?









- I. Vsaj ena od permutacij
ima fiksno točko.2
3
7
- II. Vsaj ena od permutacij
ima fiksno točko.2
3
4
5
6
- III. Vsaj ena od permutacij
ima fiksno točko.3
4
7
- IV. Permutacije
imajo skupaj vsaj pet fiksnih točk.2
3
7
- V. Permutaciji
imata skupaj največ tri fiksne točke.7
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | I in III. | 23:11:17 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | I in III. | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 4
Točke: 0/1
Denimo, da izraz O(x
y) pomeni `y je otrok od x -a' in M(x) pomeni `x je moški'. Naj bo izraz H(v
w) definiran kot
M(v)
x
y(O(x
y)
O(x
v)
(y
=v)
O(y
w))
Kakšen je pomen izrazaH(v
w) ?













Kakšen je pomen izraza

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 23:12:06 dne 3/11/10 | 0 | 0 | |
2 | Zapri in oceni | 23:12:06 dne 3/11/10 | 0 | 0 |
Question 5
Točke: 1/1
Naj bo G=(V
E) povezan, neusmerjen graf z n točkami in m povezavami. Katere izmed naslednjih trditev so resnične?

- I.
G ima vsajm−n Hamiltonovih ciklov. - II.
G ima vsajm vpetih dreves.n
- III. Točke grafa lahko pravilno obarvamo s tremi barvami na vsaj
m−n načinov. - IV.
m .n
- V.
G vsebuje cikel dolžine vsajm+n .
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Nobena izmed trditev ni resnična. | 23:13:58 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Nobena izmed trditev ni resnična. | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 6
Točke: 1/1
V množici ljudi pod drobnogled vzamemo naslednje relacije: oče, prednik, polbrat, babica, nečak. Katere izmed omenjenih relacij so tranzitivne?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo prednik. | 23:15:27 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | Samo prednik. | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 7
Točke: 0/1
Trimestni izjavni veznik V je opisan takole: V(p
q
r) ima ravno nasprotno logično vrednost kot večina njegovih argumentov p
q
r . Katere od naslednjih trditev so resnične?




- I.
V lahko izrazimo samo z uporabo negacije in implikacije, . - II.
V lahko izrazimo samo z uporabo konjunkcije in disjunkcije, . - III.
V lahko izrazimo samo z uporabo negacije, konjunkcije in disjunkcije, . - IV.
V lahko izrazimo samo z uporabo konjunkcije in implikacije, .
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | II in III. | 23:16:57 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | II in III. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 8
Točke: 0/1
Kromatično število grafa G ,
(G) , je najmanjše takšno naravno število k , da lahko točke grafa G obarvamo s k barvami tako, da sta vsaki sosednji točki različnih barv.
Denimo, da ima grafG vse točke stopenj 3 ali 5, pri čemer nobeni dve točki stopnje 5 nista sosedi.
Katera izmed naslednjih trditev najbolje opiše kromatično število takšnega grafa?

Denimo, da ima graf
Katera izmed naslednjih trditev najbolje opiše kromatično število takšnega grafa?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() ![]() | 23:18:16 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | ![]() ![]() | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 9
Točke: 0/1
V družini podmnožic končne množice A definiramo relacijo R takole:
množiciB1 in B2 sta v relaciji R natanko tedaj, ko ima njuna simetrična razlika B1+B2 sodo mnogo elementov. Katere izmed naslednjih trditev so resnične?
množici
- I. Relacija
R je ekvivalenčna. - II. Nobena neprazna množica ni v relaciji sama s sabo.
- III. Če ima
A liho mnogo elementov je relacijaR prazna. - IV. Relacija
R porodi razbitje na dva ekvivalenčna razreda.
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo I. | 23:19:49 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Samo I. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 10
Točke: 1/1
Denimo, da izraz O(x
y) pomeni `y je otrok od x -a' in M(x) pomeni `x je moški'. Naj bo izraz F(v
w) definiran kot
M(v)
x
y
z(O(x
y)
O(x
z)
(y
=z)
O(y
w)
O(z
v))
Kakšen je pomen izrazaF(v
w) ?
















Kakšen je pomen izraza

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 23:21:10 dne 3/11/10 | 1 | 1 | |
2 | Zapri in oceni | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 11
Točke: 0/1
Naj bo G=(V
E) povezan, neusmerjen graf z n točkami in m povezavami. Katere izmed naslednjih trditev so resnične?

- I.
G ima vsajm−n Hamiltonovih ciklov. - II.
G ima vsajm−n vpetih dreves. - III.
m−n je vsaj 0. - IV.
G ima vsajm−n povezanih komponent. - V.
G ima vsajm−n različnih ciklov.
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 23:22:42 dne 3/11/10 | 0 | 0 | |
2 | Zapri in oceni | 23:22:42 dne 3/11/10 | 0 | 0 |
Question 12
Točke: 0/1
Opazuj sistem kongruenc
(Namig: razmisli kakšni so ostanki številax+3 pri deljenju s 3, 5 oz. 7.)
Koliko rešitev ima zgornji sistem kongruenc med števili 1,..,1000?
![]() |
![]() |
![]() |
(Namig: razmisli kakšni so ostanki števila
Koliko rešitev ima zgornji sistem kongruenc med števili 1,..,1000?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Sistem nima rešitve. | 23:31:09 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Sistem nima rešitve. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 13
Točke: 1/1
Naj bosta p in q različni praštevili. Koliko naravnih števil med 1 in (pq)2 je deljivih z vsaj enim od p
q ?

Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 23:38:18 dne 3/11/10 | 1 | 1 | |
2 | Zapri in oceni | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 14
Točke: 1/1
Pod drobnogledom imamo družino vseh grafov z 10 vozlišči in 6 povezavami. Z M oziroma m
označimo največje oziroma najmanjše možno število povezanih komponent
katerega izmed grafov v tej družini. Predpostavimo še, da so naši grafi
enostavni - brez zank in vzporednih povezav. Kaj lahko poveš o M in m ?
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 23:42:49 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | ![]() | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 15
Točke: 0/1
Polnemu grafu s točkami
1
2



10
utežimo povezave - povezavi ij priredimo utež w(ij)=i+j . Kolikšna je dolžina najkrajše Hamiltonove poti v takšnem grafu?








Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 92 | 23:48:34 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | 92 | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 16
Točke: 1/1
Naj bodo p1
p2
p3
p4
izjavne (Boolove) spremenljivke. Katere izmed naslednjih izjav lahko
izraziš z omenjenimi spremenljivkami samo z uporabo konjunkcije 
in disjunkcije 
(brez uporabe negacije)?





- I. Vsaj tri izmed
p1 so resnične.p2
p3
p4
- II. Natanko tri izmed
p1 so resnične.p2
p3
p4
- III. Sodo mnogo spremenljivk izmed
p1 je resničnih.p2
p3
p4
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Question 17
Točke: 0/1
Kateri izmed naslednjih izjavnih izrazov so tavtologije?
- I.
p (p
q)
- II.
p (q
p)
- III.
(p p)
q
- IV.
(p q)
p
- V.
(p p)
(q
q)
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Question 18
Točke: 0/1
Koliko rešitev v množici naravnih števil ima linearna diofantska enačba
5x+7y=81?
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Neskončno mnogo. | 23:52:07 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Neskončno mnogo. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 19
Točke: 0/1
Na sliki je prikazan graf skupaj s cenami povezav. Kolikšna je vrednost minimalnega vpetega drevesa v grafu?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Question 20
Točke: 1/1
Naj za moči množic A , B in C velja
A
=10 ,
B
=11 ,
C
=12 in
A
B
=7 . Z M označimo največje in z m najmanjše možno število elementov množice A
B
C . Velja:











Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 23:53:55 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | ![]() | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 21
Točke: 0/1
Katere izmed naslednjih množic so števno neskončne?
- I. Množica vseh besed nad abecedo
.a
b
c
- II. Množica vseh zveznih realnih funkcij.
- III. Množica konvergentnih zaporedij naravnih števil.
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | I in II | 23:55:05 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | I in II | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 22
Točke: 1/1
Naj bo k
1 naravno število. Kateri izmed naslednjih izrazov najbolje opisuje naraščanje izraza
ni=1ki v odvisnosti od parametra n ?


Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 23:56:09 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | ![]() | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 23
Točke: 1/1
Permutacijo 
v zapisu z disjunktnimi cikli zapišemo takole
=(1234)(567)(89)
Kolikšen je red premutacije
? (Red permutacije je najmanjši eksponent k
1 , pri katerem je
k enaka identiteti.)


Kolikšen je red premutacije



Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 12 | 23:56:36 dne 3/11/10 | 1 | 1 |
2 | Zapri in oceni | 12 | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 24
Točke: 0/1
Denimo, da izraz O(x
y) pomeni `y je otrok od x -a' in M(x) pomeni `x je moški'. Naj bo izraz F(v
w) definiran kot
M(v)
x
y(O(x
y)
O(x
v)
(y
=v)
O(y
w))
Kakšen je pomen izrazaF(v
w) ?













Kakšen je pomen izraza

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | 23:57:00 dne 3/11/10 | 0 | 0 | |
2 | Zapri in oceni | 23:57:00 dne 3/11/10 | 0 | 0 |
Question 25
Točke: 0/1
Naj bo G=(V
E) povezan, neusmerjen graf. Katere izmed naslednjih trditev so resnične?

- I. Vsota stopenj vozlišč grafa je sodo število.
- II.
E
V
−1
- III.
G ima vsaj eno vozlišče stopnje 1.
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo II. | 23:57:52 dne 3/11/10 | 0 | 0 |
2 | Zapri in oceni | Samo II. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 26
Točke: 1/1
Katera izmed naslednjih formul je resnična v vsaki interpretaciji?
- I.
( xP(x)
xQ(x))
x(P(x)
Q(x))
- II.
x(P(x)
Q(x))
(
xP(x)
xQ(x))
- III.
( xP(x)
xQ(x))
x(P(x)
Q(x))
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | I in III. | 00:01:51 dne 4/11/10 | 1 | 1 |
2 | Zapri in oceni | I in III. | 00:09:39 dne 4/11/10 | 1 | 1 |
Question 27
Točke: 0/1
Katera izmed naslednjih formul je resnična v vsaki interpretaciji?
- I.
x(P(x)
Q(x))
xP(x)
xQ(x)
- II.
x(P(x)
Q(x))
xP(x)
xQ(x)
- III.
x(P(x)
Q(x))
xP(x)
xQ(x)
- IV.
x(P(x)
Q(x))
xP(x)
xQ(x)
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Vse štiri. | 00:02:27 dne 4/11/10 | 0 | 0 |
2 | Zapri in oceni | Vse štiri. | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 28
Točke: 0/1
Izraz T(n) je podan z začetnim pogojem T(1)=7 in rekurzivno zvezo T(n+1)=3n+T(n) , ki velja za vse n
1 . Kateri izmed naslednjih izrazov najbolje opise rast izraza T(n) v odvisnosti od parametra n ?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() | 00:04:20 dne 4/11/10 | 0 | 0 |
2 | Zapri in oceni | ![]() | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 29
Točke: 0/1
Naj bosta R in S relaciji v A , tj. R
S
A
A . Produkt relacij R
S definiramo takole:
a(R
S)b

c(aRc
cSb)
Denimo, da sta obe relacijiR in S tranzitivni, relacija R pa je celo refleksivna. Katera trditev je resnična?









Denimo, da sta obe relaciji
Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | ![]() ![]() | 00:06:40 dne 4/11/10 | 0 | 0 |
2 | Zapri in oceni | ![]() ![]() | 00:09:39 dne 4/11/10 | 0 | 0 |
Question 30
Točke: 0/1
Koliko Hamiltonovih ciklov ima graf na sliki?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Question 31
Točke: 0/1
Koliko vpetih dreves ima graf na sliki?

Izberite en odgovor.
Napačno
Točke za to oddajo: 0/1.
Question 32
Točke: 1/1
Naj bo G=(V
E) končen usmerjen graf brez (usmerjenih) ciklov z vsaj eno povezavo. Katere izmed naslednjih trditev so resnične?

- I.
G ima vozlišče brez vhodne povezave. - II.
G ima vozlišče brez izhodne povezave. - III.
G ima izolirano vozlišče, takšno ki se ne dotika nobene izmed povezav.
Izberite en odgovor.
Pravilno
Točke za to oddajo: 1/1.
Zgodovina odgovorov:
# | Dejanje | Odgovor | Čas | Čisto število točk | Ocena |
---|---|---|---|---|---|
1 | Ocena | Samo I in II. | 00:09:28 dne 4/11/10 | 1 | 1 |
2 | Zapri in oceni | Samo I in II. | 00:09:39 dne 4/11/10 | 1 | 1 |