To tylko jedna z 8 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Imię i Nazwisko ............................................................. Nr indeksu .......................
16 VI 2008
Ćwiczenia prowadzi ........................................................
Matematyka Dyskretna – Elektronika
Kolokwium nr 2. Grupa C
Część I. Zadania 1–12 są za 1pkt.
W celu ich rozwiązania proszę podać jedynie odpowiedź, którą należy
umieścić bezpośrednio pod zadaniem.
1. Ile rozwiązań w liczbach całkowitych większych niż 3 ma równanie x1 + x2 + . . . + x5 = 30?
10+4
4
2. Rozważmy wszystkie 36 pokolorowań sześcianu za pomocą 3 kolorów. Ile spośród
tych pokolorowań przechodzi na siebie, gdy sześcian odbijamy symetrycznie względem
płaszczyzny, przechodzącej przez środki krawędzi i równoległej do podstaw?
35
3. Ile spośród liczb od 1 do 2100 dzieli się przez 2, 3 lub 7?
(1050 + 700 + 300) − (350 + 150 + 100) + 50 = 1500
4. Równaniem charakterystycznym pewnego równania rekurencyjnego jest r2 + 2 = 3r. Jak
wygląda jego rozwiązanie ogólne?
an = A + B2n
5. Znajdź funkcję tworzącą ciągu an = 1 dla parzystych n
6, an = 0 dla pozostałych n.
x6
1 − x2
6. Dla jakich n graf Kn jest planarny?
n ∈ {1, 2, 3, 4}
7. Wypisz podane ciągi w kolejności od najniższego rzędu do najwyższego: n!, (1, 01)n , n2
oraz n log n.
n log n, n2 , (1, 01)n , n!
8. Znajdź kod Prüfera dla poniższego drzewa:
r8
4r
r2
7r
r3
r5
r6
557377
r1
9. Dla jakich m i n graf Km,n jest hamiltonowski?
m=n
2
10. Ile kolorów potrzeba do pokolorowania wierzchołków grafu K4,5 , a ile do pokolorowania
krawędzi tego grafu?
2 wierzchołkowo, 5 krawędziowo
11. Narysuj drzewo o kodzie zerojedynkowym 01010010110011.
r
r
r
r
r
r
r
r
12. Ile jest wszystkich grafów bez pętli, o wierzchołkach 1, 2, . . . , 8 oraz o sześciu krawędziach,
gdy dopuszczamy krawędzie wielokrotne?
6+( 8 )−1
2
= 33
6
6
1/2
Część II. W zadaniach 13–15 proszę podać sposób ich rozwiązania oraz odpowiedź, które należy
umieścić bezpośrednio pod zadaniem.
13. (3 pkt.) Ile co najwyżej krawędzi można dodać do poniższego drzewa, aby otrzymać graf
planarny?
r
r
r
r
r
r
r
r
r
r
r
Odp: 27 − 10 = 17. Rozwiązanie jest analogiczne jak w grupie A.
14. (2 pkt.) Ile drzew spinających ma poniższy graf?
r
r
r
r
d r r d r r d r r d r
r d d d d
d d r d r d r
dr d d d
Odp: (42 )4 . Rozwiązanie jest analogiczne jak w grupie A.
15. (3 pkt.) Znajdź funkcję tworzącą ciągu a0 = 2, a1 = 3, an+2 = an+1 + 3an .
∞
∞
n
f (x) =
an x = 2 + 3x +
n=0
∞
n
an+2 xn+2
an x = 2 + 3x +
n=2
n=0
∞
(an+1 + 3an )xn+2
= 2 + 3x +
n=0
∞
∞
an+1 x
= 2 + 3x + x
n+1
+ 3x
n=0
∞
2
n=0
∞
an xn + 3x2
= 2 + 3x + x
an x n
n=1
an x n
n=0
2
= 2 + 3x + x(f (x) − 2) + 3x f (x)
Skąd otrzymujemy
f (x) =
2+x
.
1 − x − 3x2
2/2
Imię i Nazwisko ............................................................. Nr indeksu .......................
16 VI 2008
Ćwiczenia prowadzi ........................................................
Matematyka Dyskretna – Elektronika
Kolokwium nr 2. Grupa D
Część
(…)
… sześcianu za pomocą 4 kolorów. Ile spośród
tych pokolorowań przechodzi na siebie, gdy sześcian odbijamy symetrycznie względem
płaszczyzny przechodzącej przez dwie przeciwległe krawędzie boczne i przekątne podstaw
sześcianu?
44 = 256
8. Ile rozwiązań w liczbach całkowitych większych niż 4 ma równanie x1 + x2 + . . . + x7 = 50?
15+6
6
9. Równaniem charakterystycznym pewnego równania rekurencyjnego jest r2…
… dla pozostałych n.
9x2
1 − 9x2
6. Dla jakich n graf Kn jest planarny?
n
4
7. Ile spośród liczb naturalnych od 1 do 420 dzieli się przez 2, 3 lub 7?
(210 + 140 + 60) − (70 + 30 + 20) + 10 = 300
8. Równaniem charakterystycznym pewnego równania rekurencyjnego jest r2 + r = 6. Jak
wygląda jego rozwiązanie ogólne?
an = A(−3)n + B2n
9. Wypisz podane ciągi w kolejności od najniższego rzędu do najwyższego: n log n, n…
... zobacz całą notatkę
Komentarze użytkowników (0)