md& czerwiec 07

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 A2 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 A2 względem S:............................................................

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

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

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

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

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

(b)    Wszystkich automorfizmów w grafie Aj010...................................................................

(c)    Wszystkich dróg otwartych maksymalnej długości w grafie Ki0.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)):

fl(n) = 2"+IO£"    /2(n) = 2007n/i2007    /3(n) = 3',(n2007)

fM = ^sr    h (») = »’    /6(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, a2 = 7, a„ = 5a„_, - 6a„_2, 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


Wyszukiwarka

Podobne podstrony:
md& czerwiec 07 Egzamin z matematyki dyskretnej 26 czerwca
DEgz1 2009 odp Egzamin z matematyki dyskretnej 19 czerwca
DEgz1 2009 odp Egzamin z matematyki dyskretnej 19 czerwca
md egz 1 0,‘jO NAZWISKO i Imię Grupa 07.01.2001 IW Egzamin z MATEMATYKI DYSKRETNEJOdpowiedz
md egz 1 0,‘jO NAZWISKO i Imię Grupa 07.01.2001 IW Egzamin z MATEMATYKI DYSKRETNEJOdpowiedz
egzamin z dyskretnej 07.02.2013 !mie i nazwisko Egzamin /. matematyki dyskretnej 1.   &nbs
q EGZAMIN MAT DYSKRETNA Egzamin z Matematyki Dyskretnej, Kierunek Informatyka Lublin, 20. czerwca 20
dyskretna z lipca 04 Wydział Informatyki WSISiZ Egzamin z matematyki dyskretnejNazwisko i Imię :
MAD egzamin Egzamin z matematyki dyskretnej (EiTI) z dnia 27.06.2002 Imię i nazwisko: Wszyskie odpow
mad egzamin2001 H*Q 27.01.2001 C PJWSTK: Egzamin z matematyki dyskretnej 1.    (5 pkt
mad e 2 Egzamin z matematyki dyskretnej (EiTi) z’dnia.3.02.2003 :Imię.i .nazwiska    

więcej podobnych podstron