md& czerwiec 07

Egzamin z matematyki dyskretnej 26 czerwca 2007

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

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 n e N. Pamiętaj, że przyjmujemy 0 i 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 S:............................................................

(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 Ki₀.io.............................................................

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

	^2.3 + /fi	<23 + c4	c4 + /v3
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)):

f_l(n) = 2"^+IO£"    /₂(n) = 2007ⁿ/i²⁰⁰⁷    /₃(n) = 3'^,(n“²⁰⁰⁷⁾

fM = ^sr    h (») = »’    /₆(n) = 20O7”^,,‘

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