Egzamin z matematyki dyskretnej 22 czerwiec 2004



Pobieranie 42.16 Kb.
Data06.05.2016
Rozmiar42.16 Kb.
Egzamin z matematyki dyskretnej 22 czerwiec 2004

Imię:























































Nazwisko:























































Grupa:




Numer Indeksu:



















Rezygnuje z zadania nr:





Uwagi:

  1. Czas rozwiązywania 130 minut.

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

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

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

  5. Zbiór liczb naturalnych nie zawiera zera: 0  N.

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

  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 błędną odp., b – liczba pkt. za brak odp., c – liczba pkt. za dobrą odp.

  9. Za żadne z dziewięciu zadań nie można uzyskać mniej niż 0 pkt.

  10. 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 RiN2:

    1. xR1y  NWD (x, y) = 2. Liczba klas abstrakcji p(s(z(R1))): ...........................

    2. xR2yx2 + y2 mod 3  1. Liczba klas abstrakcji p(s(z(R2))): ........2...................

    3. xR3yx  10  x | y. Liczba klas abstrakcji p(s(z(R3))): ............10...............

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:

  1. Każdy otrzymał tyle samo kart.........52!/(13!)4...................................

  2. Każdy otrzymał co najmniej jedną kartę..........452 ­– 4352 + 6252 – 4 .......

  3. Każdy otrzymał 1 asa, 1 króla, 1 damę, ...., 1 trójkę i 1 dwójkę..........(4!)13...................

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:

  1. Jaka jest długość drogi przebytej przez chińskiego listonosza:......80..............................

  2. Jaka jest waga minimalnego drzewa spinającego w tym grafie:.........22..............

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

Planar­ny

diam(G)

(G)

'(G)

Graf 1

N

N

T

3

3

5

Graf 2

N

N

T

3

2

4

Graf 3

T

T

N

4

2

4

Graf 4

T

T

T

2

3

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 rN 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, a­2 = –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, nN 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 RA2 określona formułą: (a, b)R(c, d)  acbd. Wyznacz (względem relacji R):



  1. Wszystkie elementy minimalne w A: .....................(1,2), (2, 1)..............................................................

  2. Wszystkie elementy maksymalne w A: .................(4, 5), (5, 4)..................................................................

  3. Element największy w A: .............#.........................

  4. Element najmniejszy w A: ..............#........................

  5. Wysokość porządku częściowego (A, R): ........4............................

  6. Szerokość porządku częściowego (A, R): ...........4.........................

Narysuj diagram Hassego tej relacji poniżej:





Pobieranie 42.16 Kb.





©absta.pl 2020
wyślij wiadomość

    Strona główna