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 — Uniwersytet Jagielloński
• Bartłomiej Bosek — Uniwersytet Jagielloński
• Piotr Micek — Uniwersytet Jagielloński

Wymagania wstępne

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

Zawartość

• Efekty mini-maxowe:
  • skojarzenia
  • pokrycia wierzchołkowe i krawędziowe
  • twierdzenia Gallai, Koniga, Frobeniusa, Halla
• Porządki częściowe i twierdzenie Dilwortha:
  • pokrycie łańcuchowe
  • twierdzenie Dilwortha
  • rodziny Spernera
• Własności podziałowe:
  • zasada podziałowa
  • twierdzenie Ramseya
  • liczby Ramseya
• Elementy teorii grup:
  • grupy cykliczne i rząd elementu grupy
  • grupy symetrii wielokątów
  • twierdzenie Lagrange’a
• Zastosowania teorii grup w zliczaniu obiektów kombinatorycznych:
  • działanie grupy na zbiorze
  • twierdzenie Polya
• Ciała skończone:
  • Pierścienie wielomianów
  • Konstrukcja ciał skończonych
  • Jednoznaczność ciał skończonych
• Zastosowanie teorii liczb w kryptografii:
  • kryptosystem RSA
  • test pierwszości Fermata
  • ticzby Carmichaela
  • test pierwszości Millera-Rabina

Literatura

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

Moduły

1. Zagadnienia Mini-Maksowe w grafach (ćwiczenia) (test)
2. Porządki Częściowe i twierdzenie Dilworth'a (ćwiczenia) (test)
3. Własności podziałowe i Twierdzenie Ramsey'a (ćwiczenia) (test)
4. Elementy teorii grup (ćwiczenia) (test)
5. Zastosowania teorii grup w zliczaniu (ćwiczenia) (test)
6. Ciała skończone (ćwiczenia) (test)
7. Zastosowanie teorii liczb w kryptografii (ćwiczenia) (test)

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