Egzamin z matematyki dyskretnej 22 czerwiec 2004
Imię: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Nazwisko: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
Grupa: |
|
Numer Indeksu: |
|
|
|
|
|
|
Rezygnuje z zadania nr: |
|
Uwagi:
Czas rozwiązywania 130 minut.
Należy rozwiązać 8 z 9 zadań. Zadanie z którego rozwiązujący rezygnuje należy wymienić powyżej w nagłówku (w przeciwnym razie losowo wybrane zadanie zostanie odrzucone przez sprawdzającego). Można zrezygnować wyłącznie z zadania za 9 pkt.
Ewentualne wątpliwości związane z niejednoznacznością sformułowań w zadaniach należy umieścić obok udzielonych odpowiedzi.
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.
Zbiór liczb naturalnych nie zawiera zera: 0 ∉ N.
Zapis "a | b" oznacza "a jest dzielnikiem b" czyli "b jest podzielne przez a". Zapis NWD(x,y) oznacza największy wspólny dzielnik liczb x i y.
W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.
Skala ocen jest opisana notacją (a/b/c) gdzie a - liczba pkt. za błędną odp., b - liczba pkt. za brak odp., c - liczba pkt. za dobrą odp.
Za żadne z dziewięciu zadań nie można uzyskać mniej niż 0 pkt.
Rozwiązania zadań 5, 6, 7, 8 należy umieścić na odwrocie (w ostateczności na osobnej kartce).
Zad. 1. (9 pkt. 0/0/3) Wyznacz liczbę klas abstrakcji domknięć rownoważnościowych następujących relacji Ri ⊆ N2:
xR1y ⇔ NWD (x, y) = 2. Liczba klas abstrakcji p(s(z(R1))): ...........................
xR2y ⇔ x2 + y2 mod 3 ≠ 1. Liczba klas abstrakcji p(s(z(R2))): ...........................
xR3y ⇔ x ≥ 10 ∧ x | y. Liczba klas abstrakcji p(s(z(R3))): ...........................
Zad. 2. (9 pkt. 0/0/3) Na ile sposobów można rozdać talię 52 (rozróżnialnych) kart pomiędzy 4 (rozróżnialne) osoby tak, aby:
Każdy otrzymał tyle samo kart............................................
Każdy otrzymał co najmniej jedną kartę..........................................................
Każdy otrzymał 1 asa, 1 króla, 1 damę, ...., 1 trójkę i 1 dwójkę........................................
Zad. 3. (9 pkt. 0/0/6+3) Rozwiąż problem chińskiego listonosza dla grafu nr 1 (suma wag w tym grafie wynosi 72). Odpowiedz na pytania:
Jaka jest długość drogi przebytej przez chińskiego listonosza:....................................
Jaka jest waga minimalnego drzewa spinającego w tym grafie:.......................
Zad. 4. (12 pkt. T/N -1.5/0/0.5 Num. 0/0/0.5) Wypełnij poniższą tabelę wpisując TAK/NIE lub odpowiednie wartości liczbowe:
G |
Hamilto-nowski |
Euler-owski |
Planarny |
diam(G) |
χ(G) |
χ'(G) |
Graf 1 |
|
|
|
|
|
|
Graf 2 |
|
|
|
|
|
|
Graf 3 |
|
|
|
|
|
|
Graf 4 |
|
|
|
|
|
|
Zad. 5. (9 pkt.) Podaj przykład dwóch spójnych grafów kubicznych (reg. stp. 3) o tej samej liczbie wierzchołków (nie więcej niż 8), które nie są izomorficzne. Odpowiedź uzasadnij.
Zad. 6. (9 pkt. (grafy dla większych r będą wyżej punktowane)) Dla wszystkich możliwych r ∈ N przedstaw planarny graf regularny stopnia r o najmniejszej możliwej liczbie wierzchołków.
Zad. 7. (9 pkt.) Wyznacz zwarty wzór na an, gdzie a1 = a3, a2 = -2 oraz an = an-1 + 2an-2 + 6n - 15. Udowodnij poprawność przedstawionego wzoru za pomocą indukcji.
Zad. 8. (9 pkt.) Znajdź wszystkie 1 ≤ n ≤ 2004, n ∈ N takie, że 99 | (n + 12)(n + 38)
Zad. 9. (9 pkt. 0/0/2+7*1) Niech A = { (x, y) : x, y ∈ N ∧ x ≤ 5 ∧ y ≤ 5 ∧ 2 | x + y + 1}
Dana jest relacja porządku częściowego R ⊆ A2 określona formułą: (a, b)R(c, d) ⇔ a ≤ c ∧ b ≤ d. Wyznacz (względem relacji R):
Wszystkie elementy minimalne w A: ...................................................................................
Wszystkie elementy maksymalne w A: ...................................................................................
Element największy w A: ......................................
Element najmniejszy w A: ......................................
Wysokość porządku częściowego (A, R): ....................................
Szerokość porządku częściowego (A, R): ....................................
Narysuj diagram Hassego tej relacji poniżej: