Ciesielski, Info
Egzamin z Matematyki Dyskretnej
Zakres Egzaminu (omówię na ostatnim Wykładzie 17 VI):
1. Dyskretyzacja, kodowanie i kwantowanie.
2. Minimalizacja funkcji logicznych. Tablice Karnaugha.
3. Ciągłość odwzorowań na grupie abelowej cyklicznej.
4. Suriekcja, iniekcja, bijekcja, a zasada szufladkowa Dirichleta.
5. Wykazać, że w grupie 13 osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu.
6. Wykazać, że w mieście Łodzi znajdziemy dwóch Łodzian o tej samej liczbie włosów na głowie.
7. Pewna grupa ∈
osób wita się podając sobie ręce. Nikt nie wita się z samym so-
bą i żadna para osób nie wita się podwójnie. Wykazać, że w tej grupie muszą być dwie osoby, które witały taką samą liczbę osób.
8. Niech ∈
. Wykazać, że wybierając + 1 liczb ze zbioru {1,2,3, … ,2 }, wśród wybranych liczb zawsze znajdziemy dwie, z których jedna dzieli drugą.
D o w ó d . Określmy relacje ∙
∙ w zbiorze liczb naturalnych , tak by:
∀ ,
∈
⟺
= 2 ,
∈
.
Oznacza to, że
jeśli liczby ,
∈
mają ten sam największy czynnik nieparzysty.
Szufladami niech będą klasy równoważności relacji ∙
∙. Ile jest klas równoważności –
szuflad dla liczb ze zbioru {1,2,3, … ,2 }? Co najwyżej , gdyż tyle może być liczb niepa-rzystych w zbiorze {1,2,3, … ,2 }.
Skoro wybrano + 1 liczb, to rozkładając je do naszych szuflad jakieś dwie, po-wiedzmy i muszą trafić do wspólnej szuflady.
Oznacza to, że któryś z ilorazów lub jest dodatnią potęgą dwójki, a zatem dzieli lub dzieli bez reszty.
9. Zasada Minimum Maurolico. Dowód lub przykład.
10. Wykazać, że ∀ ∈
:
1 + 3 + 5 + ⋯ + (2 − 1) ≕
2 − 1 =
,
( + 1)
1 + 2 + 3 + ⋯ +
≕
=
,
2
( + 1)(2 + 1)
1 + 2 + 3 + ⋯ +
≕
=
.
6
11. Wykazać, że prostokątną czekoladę złożoną z ∈
kawałków trzeba połamać
− 1 razy.
12. Rekurencja a rekursja i Wieża Hanoi.
13. Centralne Twierdzenie Graniczne Rachunku Prawdopodobieństwa Lindeberga-Levy’ego.
14. Komputerowe Generatory Liczb Losowych.
Terminy Egzaminów:
– 1 Termin – 27 VI (poniedziałek) 2011 r. godz. 9.00-10.00 E-2,
– 2 Termin – 4 VII (poniedziałek) 2010 r. godz. 9.00-10.00 E-2 oraz
– Poprawka – 5 IX (poniedziałek) 2010 r. godz. 9.00-10.00 E-2.