Egzamin z Matematyki Dyskretnej dla 1 roku Informatyki (z dnia 23 czerwca 2008)
u dr W. Kraśkiewicza
1. Zdefiniuj NWD pary liczb całkowitych.
Przedstaw algorytm Euklidesa. Co możesz powiedzieć o efektywności algorytmu?
2. Zdefiniuj liczby pierwsze i uzasadnij, że jest ich nieskończenie wiele. Sformułuj zasadnicze
twierdzenie arytmetyki.
3. Sformułuj i udowodnij chińskie twierdzenie o resztach.
Znajdz
wszystkie x, dla których:
xa"5śąmod 17źą
xa"10 śąmod 25źą
4. Sformułuj zasadę włączeń i wyłączeń. Ile jest naturalnych rozwiązań równania
X ƒÄ…X ƒÄ…X ƒÄ… X ƒÄ… X =40
1 2 3 4 5
0Ä…Ä…X Ä…Ä…9
spełniających nierówność ?
i
an
5. Niech oznacza liczbę ciągów ternarnych (tj. o wartościach 0,1 i 2) długości n,
w których każde dwa symbole niezerowe są podzielone przynajmniej jednym zerem.
a10
śąanźą"
Znajdz
wzór rekurencyjny oraz wzór zwarty dla ciągu Czemu jest równe
n=0
śąanźą"
6. Szereg generujÄ…cy dla ciÄ…gu dany jest wzorem
n=0
2ƒÄ…3tƒÄ…5t2
Aśąt źą=
1-3tƒÄ…t3
Podaj wzór rekurencyjny dla tego ciągu oraz jego 5 pierwszych wyrazów.
7. Zdefiniuj pojęcie wielomianu wieżowego (szachowego) i oblicz ten wielomian dla
szachownicy
X X X
X X X
X X X