Egzamin z matematyki dyskretnej 29 czerwiec 2005

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Uwagi:

1. Czas rozwiązywania 100 minut.

2. Ewentualne wątpliwości związane z niejednoznacznością sformułowań w zadaniach należy umieścić obok udzielonych odpowiedzi.

3. Dozwolone jest korzystanie z pomocy w formie własnoręcznych notatek i wydruków slajdów z wykładu. Nie wolno korzystać z książek i urządzeń elektronicznych.

4. Zbiór liczb naturalnych nie zawiera zera: 0 ∉ N.

5. Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a".

6. W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.

7. Skala ocen jest opisana notacją (a/b/c) gdzie a - liczba pkt. za poprawną odp., b - liczba pkt. za brak odp., c - liczba pkt. za błędną odp.

8. Za żadne z siedmiu zadań nie można uzyskać mniej niż 0 pkt.

9. Rozwiązania zadań 6, 7 należy umieścić na osobnej kartce.

Zad. 1. (10 pkt. 2/0/0) Na ile sposobów można utworzyć słowo 10 literowe:

1. z liter a, b, c tak, aby każda z nich wystąpiła co najmniej raz_.......... 3¹⁰ - 3⋅2¹⁰ + 3

2. z 3 liter a i 7 liter b_{..............}10! / (3!⋅7!)

3. z 3 liter a i 7 liter b tak, aby żadne dwie litery a nie sąsiadowały ze sobą_{......................... .....}8! / (3!⋅5!)

4. z liter a, b, c tak aby po żadnym c nie występowało a ani b oraz aby po żadnym b nie występowało a (litery muszą być ułożone alfabetycznie) _.... 12! / (2!⋅10!)

5. z liter a, b, c, d, e tak, aby każda z nich wystąpiła dokładnie 2 razy_... 10! / 2⁵

Zad. 2. (9pkt. 1/0/0) Niech A = {1, 2, ..., 10}. Dana jest relacja S ⊆ A², gdzie xSy ⇔ 3 | x + y ∧ x < y. Relacja R stanowi przechodnie domknięcie zwrotnego domknięcia relacji S (R = p(z(S))).

1. Czy relacja R jest porządkiem częściowym? _{.............}Tak_{...................}

Jeżeli tak, to wyznacz:

2. {x ∈ A : xR5}_{................................}1, 2, 4, 5

3. {x ∈ A : 5Rx}_{................................}5, 7, 8, 10

4. wysokość R _{................................} 7

5. szerokość R_{................................}2

6. wszystkie elementy maksymalne w A względem R_.....9, 10

7. wszystkie elementy minimalne w A względem R_......1, 3

8. najdłuższy łańcuch w A względem R_...1, 2, 4, 5, 7, 8, 10

9. najdłuższy antyłańcuch w A względem R_....np. 1, 3

Zad. 3. (8 pkt. 1/0/-0.5) Dla grafu G na rysunku poniżej wyznacz

1. Długość optymalnej trasy chińskiego listonosza_{...............}36

2. Wagę minimalnego drzewa spinającego_{................................}10

3. Spójność wierzchołkową_{................................}3

4. Długość najdłuższego cyklu_{................................}8

5. Promień_{................................}2

6. Średnicę_{................................}3

7. Liczbę chromatyczną G_{................................}2

8. Indeks chromatyczny G_{................................}5

Uwaga:wagi przypisane krawędziom mają znaczenie wyłącznie dla pierwszych dwóch problemów. Dla pozostałych sześciu należy je zignorować.

Zad. 4 (7 pkt. 2/0/0) Uporządkuj według niemalejącego tępa wzrostu następujące funkcje (tak, że jeśli f występuje przed g, to zachodzi f = O(g)):

f₁(n) = log²n + n^1/2 + 3ⁿ / n²

f₂(n) = log³n³ + n^1/3 + 2ⁿ / n

f₃(n) = n^1/2logn + 2ⁿ / 3ⁿ

f₄(n) = (1+1/n)ⁿ + n^1/2

f₅(n) = (4/3)ⁿ + n^1/2

f₆(n) = 2005! ⋅ n²⁰⁰⁵

4

3

6

5

2

1

Zad. 5 (8 pkt. 2/0/0) Przedstaw przykłady relacji równoważności R ⊆ N² takiej, która:

1. Ma nieskończenie wiele klas abstrakcji, z których każda jest nieskończona

xSy ⇔ y = 2x

R = p(s(z(S)))

2. Ma nieskończenie wiele skończonych i nieskończenie wiele nieskończonych klas abstrakcji

xSy ⇔ y = 2x ∧ 2 | y

R = p(s(z(S)))

3. Ma 2005 klas abstrakcji, z których każda jest nieskończona

xRy ⇔ 2005 | (x - y)

4. Ma 2005 skończonych klas abstrakcji i jedną nieskończoną klasę abstrakcji

xRy ⇔ (x = y ∧ x < 2006) ∨ (x ≥ 2006 ∧ y ≥ 2006)

Każdą z odpowiedzi uzasadnij.

Zad. 6 (9 pkt. 9/0/0) Wyznacz zwarty wzór na n-ty wyraz sumy:

Uzasadnij poprawność uzyskanego wzoru.

Zad. 7 (9 pkt. 9/0/0) Niech B_n oznacza liczbę wszystkich podziałów zbioru n elementowego. Udowodnij, że
. (łatwo zauważyć, że początkowe wyrazy wynoszą odpowiednio B₀ = 1, B₁ = 1, B₂ = 2, B₃ = 5, ...)

Niech X będzie dowolnym zbiorem n + 1 elementowym. Wybierzmy pewien element x ∈ X. Sposób generowania podziału X przebiega w dwóch fazach. Najpierw wybieramy n - i elementów, które trafią do tego samego podzbioru co element x a następnie dokonujemy dowolnego podziału na podzbiory pozostałych i elementów. Mamy pewność, że każdy możliwy podział może być w ten sposób wygenerowany oraz, że dwa różne wybory w pierwszym kroku nigdy nie doprowadzą do uzyskania takiego samego podziału zbioru X.

Dla ustalonego i pierwszy krok można wykonać na
sposobów a drugi na
sposobów. Stąd ostatecznie dla ustalonego i liczba wszystkich sposobów wynosi
.

Należy rozważyć wszystkie przypadki 0 ≤ n - i ≤ n czyli 0 ≤ i ≤ n. Stąd otrzymujemy końcową formułę
.

---