Matematyka dyskretna
Matematyka dyskretna
Egzamin 1inf
15 września 2008 (II termin)
dr Witold Kraśkiewicz
1. Zdefiniuj NWD. Przedstaw algorytm Euklidesa. Co mo\
esz powiedzieć o jego
efektywności?
2. Zdefiniuj liczby pierwsze i podaj dowód na to \
e jest ich nieskończenie wiele. Co to
jest i do czego słu\
y sito Eratostenesa
3. Napisz chińskie twierdzenie o resztach i udowodnij je. Rozwią\
układ kongruencji:
x a" 5mod17
Å„Å‚
òÅ‚x a" 10 mod 25
ół
4. Napisz zasadę włączeń i wyłączeń. Ile jest liczb naturalnych n < 107 które nie są
podzielne przez 4, 9 lub 25 ?
5. Niech an dla n>1 oznacza ilość które mają w zapisie dziesiętnym dokładnie n-cyfr i
nie zawierają dwóch zer pod rząd. Podaj wzór jawny oraz wyraz a8
6. Szereg generujący dla ciągu (an )" jest następujący:
n=1
2 + 3t + 5t2
A(t) =
1 - 3t + t3
Podaj wzór rekurencyjny oraz wyrazy od a1 do a5
7. Zdefiniuj wielomian wie\
owy oraz oblicz ten wielomian dla szachownicy:
X X
X X
X X
X X
Punktacja:
" Ka\
de zadanie było warte 10pkt
" Max 70pkt
" Od 50% zaliczenie.