md& czerwiec 07

Egzamin z matematyki dyskretnej 26 czerwca 2007

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Uwagi:

1.    Czas rozwiązywania 90 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 e N.

5.    Zapis *a \ tf oznacza "a jest dzielnikiem tf czyli "b jest podzielne przez <f.

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ń 1 i 6 należy umieścić na odwrocie.

Zad. 1. (10 pkt. 10/0/0) Wyznacz wszystkie liczby naturalne, których nie da się wyrazić w postaci sumy 3m + 5n, gdzie ne N. Pamiętaj, że przyjmujemy 0 ł N. Odpowiedź uzasadnij. (Wskazówka: Korzystając z indukcji wykaż, że każdą „dużą” liczbę naturalną można przedstawić w zadanej powyżej postaci.)

Zad. 2. (10 pkt. 2.5/0/0) Dany jest zbiór A = {1, 2,...,10}. W zbiorze A² określono relację R. formułą (a, b) R (c, d) <=> ad < bc. Niech S będzie zwrotnym domknięciem relacji R.

(a)    Wyznacz wszystkie elementy minimalne w A² względem 5:.............................................................

(b)    Wyznacz wszystkie elementy maksymalne w A² względem S:..............................................................

(c)    Przedstaw najdłuższy antyłańcuch w A² względem S..............................................................................................

(d)    Wyznacz długość najdłuższego łańcucha w A² względem S................................

Zad. 4. (10 pkt. 2.5/0/0) Wyznacz liczbę:

(a)    Wszystkich cykli w grafie Af_10:................................

(b)    Wszystkich automorfizmów w grafie Aj₀₁₀....................................................................

(c)    Wszystkich dróg otwartych maksymalnej długości w grafie K₁₀.|₀..............................................................

(d)    Wszystkich cykli długości 5 w grafie K_]0,io,io.........................

Zad. 4. (10,5 pkt. 0.5/0/-0.5) Wyznacz wybrane parametry następujących grafów:

	*23 + *l	+ c4	C4 + A/3
X(G)
X’(G)
rad(G)
<G)
chl(G)^a
co(G)
cir(G)^b

Zad. 5 (10 pkt.) Uporządkuj według niemalejącego tępa wzrostu następujące funkcje (tak, że jeśli/występuje przed g, to zachodzi/= O(g)):

/,(«) = 2ⁿ⁺'^ogn f₂(n) = 2001ⁿn^mi /₃(/i) = 3ⁿ⁽'^,_2007)

/,<«) = ""    /₆(_n) = 2007^M,‘

W powyższej tabelce należy wpisać jedynie indeksy funkcji, a nie formuły.

> Zad. 6 (10 pkt. 10/0/0) Dany jest ciąg (a„), określony rekurencyjnie: a, = 3, a₂ = 7, a„ = 5a„_, - 6a„_₂. dla n > 2. Wyznacz zwarty wzór na n-ty wyraz tego ciągu.

^a Długość marszruty chińskiego listonosza ^b Długość najdłuższego cyklu