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ść i twierdzenie Mengera
  • sieci, przepływy, przekroje, twierdzenie Forda-Fulkersona
  • planarność i twierdzenie Kuratowskiego
  • kolorowanie grafów

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.