Matematyka dyskretna 2

Forma zajęć

Wykład (15 godzin) + ćwiczenia (15 godzin)

Opis

Wykład rozwija aparat matematyczny niezbędny do konstruowania i analizy algorytmów. Składa się z elementów teorii grafów, teorii liczb i algebry.

Sylabus

Autorzy

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

Wymagania wstępne

• Logika i teoria mnogości
• Matematyka dyskretna
• Algebra liniowa z geometrią analityczną

Zawartość

• Efekty mini-maxowe
  • twierdzenie Mengera
  • twierdzenie Dilwortha
  • twierdzenie Forda-Fulkersona
  • twierdzenie Koeniga-Egervary'ego
  • twierdzenie Spernera
• Własności podziałowe i twierdzenie Ramseya
• Teoria liczb
  • twierdzenie Eulera
  • RSA
  • testowanie pierwszości
• Grupy i twierdzenie Polya
• Ciała skończone
• Kody korygujące błędy

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

• [[MD2 Moduł 1|]] (Ćwiczenia)
• [[MD2 Moduł 2|]] (Ćwiczenia)
• [[MD2 Moduł 3|]] (Ćwiczenia)
• [[MD2 Moduł 4|]] (Ćwiczenia)
• [[MD2 Moduł 5|]] (Ćwiczenia)
• [[MD2 Moduł 6|]] (Ćwiczenia)
• [[MD2 Moduł 7|]] (Ćwiczenia)

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