DEgz3-2010, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy zadania i odpowiedzi


Egzamin z matematyki dyskretnej 10 lutego 2011

Imię:

Nazwisko:

Grupa:

Numer Indeksu:

Uwagi:

  1. Czas rozwiązywania 100 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. NWD(x, y) oznacza największy wspólny dzielnik liczb x i y.

  5. Cn oznacza cykl o n wierzchołkach, Pn oznacza ścieżkę o n wierzchołkach, Wn oznacza koło o n wierzchołkach

  6. W trakcie egzaminu nie wolno opuszczać sali przed oddaniem pracy.

Zad. 1. (9 pkt.) Czy następująca funkcja zdaniowa:

[ (AB) \ C = ∅ ˄ (A B) \ (C \ A) = (AB) ˄ C B] ⇒ [BC ∅]

jest prawdziwa dla każdych trzech podzbiorów zbioru {1,2,3}? (Tak/Nie)? .............

Jeśli odpowiedziałeś "Nie", przedstaw kontrprzykład przez wskazanie trzech (niekoniecznie różnych) zbiorów A, B, C ⊆ {1, 2, 3}, dla których ta funkcja staje się zdaniem fałszywym.

Kontrprzykład (opcjonalnie): A = ....................................... B = ....................................... C = .......................................

Zad. 2. (9 pkt.) Uzupełnij poniższe formuły symbolami zmiennych zdaniowych tak, aby powstałe schematy logiczne były logicznie równoważne schematowi (pr) → (rq). Możesz używać wyłącznie symboli zmiennych zdaniowych (np. p, q, r, s). Dopisywanie spójników logicznych jest niedozwolone. Jeżeli uważasz, że w którymś przypadku takie uzupełnienie nie jest możliwe, wpisz obok formuły sformułowanie "brak rozwiązania".

(a) [..... ˄ (~..... )] ∨ [..... ˄ (~..... )] (b) [..... ˄ (~..... )] ˄ [..... ∨ (~..... )] (c) ~ (..........)

Zad. 3. (9 pkt.) Uniwersum jest zbiorem studentów. Definiujemy następujące predykaty: Z(x) - x zdał egzamin z matematyki; W(x) - x chodził na wykłady z matematyki; R(x, y) - x i y to ten sam student.

Wyraź w języku rachunku predykatów pierwszego rzędu następujące zdania: (a) Dokładnie dwóch studentów nie zdało egzaminu z matematyki. (b) Żaden, spośród studentów, którzy chodzili na wykłady z matematyki, nie oblał egzaminu z tego przedmiotu (c) Co najwyżej jeden student zdał egzamin z matematyki. Nie wolno używać żadnych innych symboli niż: nawiasy, wymienione powyżej predykaty, zmienne, kwantyfikatory oraz spójniki logiczne.

(a) ...................................................................................................................................................................................................................

(b) ...................................................................................................................................................................................................................

(c) ...................................................................................................................................................................................................................

Zad. 4. (9 pkt.) Porzedstaw przykład relacji porządku liniowego w zbiorze liczb naturalych N, która nie jest dobrym porządkiem. Odpowiedź uzasadnij.

Zad. 5. (9 pkt.). W zbiorze A = {1, 2, ..., 10} zdefiniowano relację binarną S:

xSy ⇔ ( x < y ∧ NWD(x, 2y + 3 ) > 1)

Niech R = p(z(S)). Dla zbioru częściowo uporządkowanego (A, R) Wyznacz:

(a) Wszystkie elementy minimalne: ...........................................................................................................................

(b) Wszystkie elementy maksymalne:.........................................................................................................................

(c) Najliczniejszy antyłańcuch: ..................................................................................................

Na odwrocie przedstaw diagram Hassego tego porządku.

0x01 graphic

Zad. 6. (10 pkt.) Dla grafu przestawionego powyżej wyznacz:

(a) Wagę minimalnego drzewa spinającego: .....................................

(b) Długość optymalnej trasy chińskiego listonosza:.....................................

(c) Długość najkrótszej marszruty zamkniętej zawierającej wszystkie wierzchołki (praktyczna odmiana problemu komiwojażera):.................

(d) Liczbę chromatyczną :.................

Zad. 7. (10 pkt.) Wyznacz liczbę podgrafów pełnego grafu K10, które są izomorficzne z grafem:

(a) K1,1,8: ............................................................. (b) P8: ...............................................................................

(c) K3,3: ............................................................ (d) W6: ................................................................................



Wyszukiwarka

Podobne podstrony:
DEgz3-2010 rozw, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzam
DEgz2-2011 rozw, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzam
DEgz1, Studia informatyczne, Matematyka, Matematyka Dyskretna, Matematyka Dyskretna, Egzaminy zadani
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
ako pytania zadania cz2 2010, Studia - informatyka, materialy, Architektura komputerów
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

więcej podobnych podstron