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 _{................................}

2. z 3 liter a i 7 liter b_{................................}

3. z 3 liter a i 7 liter b tak, aby żadne dwie litery a nie sąsiadowały ze sobą_{................................}

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) _{................................}

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

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? _{................................}

Jeżeli tak, to wyznacz:

2. {x ∈ A : xR5}_{................................}

3. {x ∈ A : 5Rx}_{................................}

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

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

6. wszystkie elementy maksymalne w A względem R_{................................}

7. wszystkie elementy minimalne w A względem R_{................................}

8. najdłuższy łańcuch w A względem R_{................................}

9. najdłuższy antyłańcuch w A względem R_{................................}

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

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

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

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

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

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

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

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

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

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²⁰⁰⁵

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

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

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

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

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, ...)

---