M
M
a
a
t
t
e
e
m
m
a
a
t
t
y
y
k
k
a
a
d
d
y
y
s
s
k
k
r
r
e
e
t
t
n
n
a
a
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:
≡
≡
25
mod
10
17
mod
5
x
x
4. Napisz zasadę włączeń i wyłączeń. Ile jest liczb naturalnych n < 10
7
które nie są
podzielne przez 4, 9 lub 25 ?
5. Niech a
n
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 a
8
6. Szereg generujący dla ciągu
∞
=1
)
(
n
n
a
jest następujący:
3
2
3
1
5
3
2
)
(
t
t
t
t
t
A
+
−
+
+
=
Podaj wzór rekurencyjny oraz wyrazy od a
1
do a
5
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.