md egz 2

A.    Egzamin testowy zawiera siedem pytań i siedem poprawnych odpowiedzi, które tylko należy odpowiednio dopasować do tych pytań. Aby zdać egzamin wystarczy poprawnie dopasować choćby jedną odpowiedź. Wiadomo, że każda odpowiedź pasuje tylko do jednego pytania. He jest w tym przypadku wszystkich różnych możliwości dopasowania po jednej odpowiedzi do każdego pytania i ile spośród tych możliwości prowadzi do zdania egzaminu? (0-3 pkt.)

B.    Narysuj diagram Hassego zbioru częściowo uporządkowanego (X, |), gdzie X = {1, 2, 3, 5, 6, 10, 12, 25, 50, 60, 100}, a | oznacza relację podzielności, to znaczy a | b wtedy i tylko wtedy, gdy a jest dzielnikiem b. Podaj zbiory elementów maksymalnych i minimalnych zbioru (X, |). Czy zbiór (X, |) ma elementy największy i najmniejszy? ( 0-3 pkt. )

C.    System wieloprocesorowy składa się z siedmiu procesorów połączonych dwukierunkowymi łączami. Nie znamy struktury tego systemu. Wiemy jedynie, że liczba łączy dochodzących do poszczególnych procesorów jest równa, odpowiednio, 5,4,4,4, 3,4, 4, i że żaden procesor nie łączy się bezpośrednio z samym sobą. Procesory działają synchronicznie. Jeśli jakiś procesor otrzyma od drugiego wiadomość, to w następnym takcie wysyła ją do dokładnie jednego innego procesora. Czy jest możliwe, by w systemie tym z każdego procesora można było wysłać wiadomość, która po siedmiu taktach wróci do niego, ale wcześniej dotrze do każdego z procesorów systemu? (Wskazówka: Rozważ model systemu w postaci odpowiedniego grafu nieskierowanego i pamiętaj, że nie znamy struktury jego połączeń. Odpowiedź „nie" jest błędna; odpowiedź „tak" bez starannego uzasadnienia nie jest wiele warta) (0-4 pkt.)

D.    Projektowana sieć komputerowa ma się składać ze stu dwudziestu jeden komputerów połączonych dwukierunkowymi łączami satelitarnymi. Komputery sieci mogą się komunikować bezpośrednio albo za pośrednictwem innych komputerów tej sieci. Dzierżawa jednego dwukierunkowego łącza między dowolną parą komputerów kosztuje 600 $ miesięcznie. Jaki jest minimalny miesięczny koszt dzierżawy wszystkich łączy satelitarnych, jeśli chcemy, by istniała komunikacja między dowolną parą komputerów w tej sieci? (2 pkt.)

Liczba punktów	<0	0-2	3-5	4-6	7-9	10-12
Ocena	2.0	3.0	3.5	4.0	4.5	5.0

Ściąga

S(n,k) = S(n-l,k-l) + k-S(n- 1,A), gdzie S(_v) jest liczbą Stirlinga drugiego rodzaju.

5(0,0) = 1

i=0

^snjc ⁼ k' S(n, k), gdzie s_{n k} jest liczbąfunkcji ze zbioru n-elementowego na zbiór k-elementowy. | D_n | = n\    ■ gdzie D_n jest liczbą nieporządków na zbiorze n-elementowym