Matematyka dyskretna 1

Z Studia Informatyczne
Wersja z dnia 16:10, 11 cze 2006 autorstwa Idziak (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 (30 godzin) + ćwiczenia (30 godzin)

Opis

Wykład wprowadza aparat matematyczny niezbędny do konstruowania i analizy algorytmów.

Składa się z elementów kombinatoryki, teorii grafów i teorii liczb.

Sylabus

Autorzy

  • Paweł Idziak
  • Bartłomiej Bosek
  • Piotr Micek

Wymagania wstępne

  • Logika i teoria mnogości

Zawartość

  • Indukcja matematyczna
    • zasada indukcji
    • zasady minimum i maksimum
    • zależności rekurencujne
  • Sumy skończone
  • Zliczanie zbiorów i funkcji
    • zliczanie podzbiorów
    • zliczanie bijekcji
    • zliczanie injekcji
    • zliczanie funkcji
    • współczynniki dwumianowe
  • Permutacje i liczby Stirlinga
  • Funkcje tworzące
  • Zliczanie obiektów kombinatorycznych
    • zasada szufladkowa Dirichleta
    • zasada włączania-wyłączania
    • liczby Catalana
    • podziały liczby na sumy
  • Asymptotyka
    • notacja
    • twierdzenie o rekursji uniwersalnej
  • Grafy
    • podstawowe pojęcia
    • drzewa i cykle
    • cykle Eulera i Hamiltona
    • spójność (i tw. Mengera)
    • dwudzielność (i tw. Halla)
    • planarność (i tw. Kuratowskiego)
    • sieci i przepływy
  • Kolorowania grafów (w tym planarnych)
  • Metody algebraiczne w teorii grafów
  • Teoria liczb
    • NWD, NWW, liczby pierwsze
    • algorytm Euklidesa
    • rozkład na czynniki pierwsze
  • Arytmetyka modularna
    • twierdzenie Fermata
    • chińskie twierdzenie o resztach

Literatura

  1. V.Bryant, Aspekty kombinatoryki, WNT 1977,
  2. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka Konkretna, PWN 1996
  3. W.Lipski, Kombinatoryka dla programistów
  4. W.Lipski, W.Marek, Analiza kombinatoryczna, PWN 1986
  5. K.A.Ross, Ch.R.B.Wright, Matematyka Dyskretna, PWN 1996
  6. Z.Pałka, A.Ruciński, Wykłady z kombinatoryki, WNT 1998
  7. R.J.Wilson, Wprowadzenie do teorii grafów, PWN 1985

Moduły

Literatura uzupełniająca

  1. N.L.Biggs, Discrete Mathematics, Oxford University Press 1989
  2. B.Bollobas, Modern Graph Theory, Springer 1998
  3. Th.H.Cormen, Ch.E.Leiserson, R.L.Rivest, C.Stein,Wprowadzenie do algorytmów, WNT, 2004.
  4. R.Diestel, Graph Theory, Springer 1997
  5. G.Polya, R.E.Tarjan, D.R.Woods, Notes on Introductory Combinatorics, Birkhauser 1983
  6. J.Riordan, An Introduction to Combinatorial Analysis, Princeton University Press 1978