Egzamin z matematyki dyskretnej 21 wrzesień 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. NWD(x, y) oznacza największy wspólny dzielnik liczb x i y

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

8. 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.

9. Za żadne z ośmiu zadań nie można uzyskać mniej niż 0 pkt.

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

Zad. 1. (10 pkt. 2/0/0) Na ile sposobów można wypełnić macierz 3x3:

1. liczbami ze zbioru {1, 2, ..., 10} tak, aby każda z liczb występowała co najwyżej raz _{................................}

2. liczbami ze zbioru {1, 2, 3, 4} tak, aby w żadnym wierszu liczby się nie powtarzały_{..............................}

3. liczbami ze zbioru {1, 2} tak, aby suma wszystkich liczb wynosiła 15 _{............................}

4. liczbami ze zbioru {1, 2, 3} tak, aby w żadnym wierszu ani w żadnej kolumnie, liczby się nie powtarzały _{...................................}

5. liczbami ze zbioru {1, 2, 3, 4} tak, aby każda z nich wystąpiła co najmniej dwa razy _{........................}

Zad. 2. (10 pkt. 1/0/0) Niech A = {1, 2, ..., 12}. Dana jest relacja S ⊆ A², gdzie xSy ⇔ NWD(x, y) > 1 ∧ 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 narysuj diagram Hass'ego tej relacji i wyznacz:

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

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

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. (10 pkt. 2/0/0) Dla grafu G na rysunku poniżej wyznacz

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

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

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

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

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

Uwaga: każda krawędź w tym grafie ma długość 1

Zad. 4. (10 pkt. 2/0/0) Podaj przykład funkcji f : N → R⁺ takiej, że:

1. f(n) = o(n + log n) ∧ f(n) = ω(n - n^1/2); f(n) =_{...........................................................................}

2. f(n) = o(3ⁿ + n⁵) ∧ f(n) = ω(5ⁿ + n³) ; f(n) =_{...................................................................................}

3. f(n) = o(5ⁿ + n³) ∧ f(n) = ω(3ⁿ + n⁵) ; f(n) =_{...................................................................................}

4. f(n) = O(2ⁿ / n) ∧ ∀_n∈N(f(n) > 2ⁿ) ; f(n) =_{...............................................................}

5. f(n) = O(2ⁿ - logn) ∧ ∀_n∈N(f(n) > 2ⁿ) ; f(n) =_{.............................................................................}

Jeżeli funkcja taka nie istnieje, to wpisz #.

_...

Zad. 5. (12 pkt. 1/0/-1) Zaznacz w tabeli poniżej, które własności spełniają poszczególne relacje określone w zbiorze liczb naturalnych. Pamiętaj, że 0 ∉ N. Wpisz słowa Tak lub Nie.

	przeciwzwrotna	syme­tryczna	anty­syme­tryczna	prze­chod­nia
xRy ⇔ NWD(3x, 5y) = 2
xRy ⇔ x ≥ 2y - 3
xRy ⇔ x ≥ 2y - 4

Zad. 6. (10 pkt. 2.5/0/0) Dla każdej kolumny z zadania 5 wybierz jeden dowolny przypadek, gdzie udzieliłeś negatywnej odpowiedzi i odpowiedź tę uzasadnij.

Zad. 7. (10 pkt.) Udowodnij, że graf z zadania 3 nie jest planarny, wskazując podgraf homeomorficzny z K_3,3 lub K₅. Narysuj ten podgraf.

Zad. 8 (10 pkt.) Wyznacz zwarty wzór na n-ty wyraz sumy:

Uzasadnij poprawność uzyskanego wzoru (np. stosując indukcję).

---