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 — Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki, Instytut Informatyki
• Adam Malinowski — 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 ($O,\mathrm{\Omega },\mathrm{\Theta },o,\omega$), 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ść, wielospójność i twierdzenie Mengera;

sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona; planarność i twierdzenie Kuratowskiego; kolorowanie grafów (w tym planarnych)

Literatura

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