Tekst źródłowy strony MIMINF:Matematyka dyskretna

== Forma zajęć ==
Wykład (45 godzin) + ćwiczenia (45 godzin)

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

== Sylabus ==

=== Autorzy === 
* Krzysztof Diks &mdash; Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki
* Adam Malinowski &mdash;  Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki

=== Wymagania wstępne ===
* Podstawy matematyki
* Geometria z algebrą liniową
* Analiza matematyczna 1

=== Zawartość ===

*Indukcja matematyczna i rekurencje
*Zliczanie zbiorów i funkcji
*Permutacje
*Współczynniki dwumianowe 
*Sumy skończone
*Funkcje tworzące i ich zastosowania
*Asymptotyka: 
**notacja asymtotyczna (<math>O,\Omega, \Theta, o, \omega</math>) 
** twierdzenie o rekursji uniwersalnej 
*Elementarna teoria liczb: 
**podzielność, NWD, NWW, liczby pierwsze 
**algorytm Euklidesa 
**rozkład na czynniki pierwsze 
*Arytmetyka modularna: 
**twierdzenie Fermata 
**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 
**spójność i twierdzenie Mengera 
**sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona 
**planarność i twierdzenie Kuratowskiego 
**kolorowanie grafów

=== Literatura ===
# 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.