MIMINF:Matematyka dyskretna: Różnice pomiędzy wersjami

Aktualna wersja na dzień 14:24, 6 lis 2006

Wykład (45 godzin) + ćwiczenia (45 godzin)

Aparat matematyczny niezbędny do układania i analizy algorytmów: elementy kombinatoryki, teorii grafów i teorii liczb.

Krzysztof Diks — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki
Adam Malinowski — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

Indukcja matematyczna i rekurencje
Sumy skończone
Współczynniki dwumianowe
Permutacje i podziały
Funkcje tworzące i ich zastosowania
Metody zliczania
- enumeratory
- zasada włączania-wyłączania
Asymptotyka:
- notacja asymptotyczna ( $O, Ω, Θ, o, ω$ )
- twierdzenie o rekurencji uniwersalnej
Elementarna teoria liczb:
- podzielność, liczby pierwsze, rozkład na czynniki pierwsze
- NWD i algorytm Euklidesa
Arytmetyka modularna:
- małe twierdzenie Fermata i twierdzenie Eulera
- chińskie twierdzenie o resztach
- rozwiązywanie równań modularnych
Elementy kryptografii: test Millera-Rabina i system RSA
Grafy:
- ścieżki, drzewa i cykle
- cykle Eulera i Hamiltona
- grafy dwudzielne, skojarzenia i twierdzenie Halla
- planarność
- kolorowanie grafów

R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, Państwowe Wydawnictwo Naukowe, Warszawa 1996.
W.Lipski, Kombinatoryka dla programistów, Wydawnictwa Naukowo-Techniczne 2004.
R.J.Wilson, Wprowadzenie do teorii grafów, Państwowe Wydawnictwo Naukowe, Warszawa 1985.

@@ Linia 19: / Linia 19: @@
 *Indukcja matematyczna i rekurencje
-*Permutacje
+*Sumy skończone
 *Współczynniki dwumianowe
-*Sumy skończone
+*Permutacje i podziały
 *Funkcje tworzące i ich zastosowania
 *Metody zliczania
@@ Linia 27: / Linia 27: @@
 **zasada włączania-wyłączania
 *Asymptotyka:
-**notacja asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>)
+**notacja asymptotyczna (<math>O,\Omega, \Theta, o, \omega</math>)
 ** twierdzenie o rekurencji uniwersalnej
 *Elementarna teoria liczb: