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
-*Zliczanie zbiorów i funkcji
+*Sumy skończone
-*Permutacje
 *Współczynniki dwumianowe
-*Sumy skończone
+*Permutacje i podziały
 *Funkcje tworzące i ich zastosowania
+*Metody zliczania
+**enumeratory
+**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 rekursji uniwersalnej
+** twierdzenie o rekurencji uniwersalnej
 *Elementarna teoria liczb:
-**podzielność, NWD, NWW, liczby pierwsze
+**podzielność, liczby pierwsze, rozkład na czynniki pierwsze
-**algorytm Euklidesa
+**NWD i algorytm Euklidesa
-**rozkład na czynniki pierwsze
 *Arytmetyka modularna:
-**twierdzenie Fermata
+**małe twierdzenie Fermata i twierdzenie Eulera
-**twierdzenie Eulera
 **chińskie twierdzenie o resztach
 **rozwiązywanie równań modularnych
@@ Linia 41: / Linia 41: @@
 **cykle Eulera i Hamiltona
 **grafy dwudzielne, skojarzenia i twierdzenie Halla
-**spójność i twierdzenie Mengera
+**planarność
-**sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona
-**planarność i twierdzenie Kuratowskiego
 **kolorowanie grafów