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.