DEgz1, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy zadania i odpowiedzi


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

    3. xR3yx ≥ 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:

  1. Każdy otrzymał tyle samo kart............................................

  2. Każdy otrzymał co najmniej jedną kartę..........................................................

  3. 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:

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

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

Planar­ny

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

  2. Wszystkie elementy maksymalne w A: ...................................................................................

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

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

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

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

Narysuj diagram Hassego tej relacji poniżej:



Wyszukiwarka

Podobne podstrony:
DEgz2-2011 rozw, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzam
DEgz3-2010, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy z
Egz1 - grafy, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy
DEgz2-2011, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy z
DEgz2, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy zadani
DEgz3-2010 rozw, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzam
PK-I-06, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
Test 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
wmd4, 1 STUDIA - Informatyka Politechnika Koszalińska, Labki, Matematyka Dyskretna i logika
TPI CH 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
Mat Dyskr i Log, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka Dyskretna i logika, MD
PK-WE Z E, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
PK-WE Z E 2, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012
Test 3, 1 STUDIA - Informatyka Politechnika Koszalińska, Matematyka dyskretna i TPI, 04-10-2012

więcej podobnych podstron