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
• 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,\Omega ,\Theta ,o,\omega$)
  • 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

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.