MIMINF:Matematyka dyskretna

Z Studia Informatyczne
Wersja z dnia 08:46, 17 paź 2006 autorstwa Diks (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 (), 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.