Zakład Analizy i Teorii Osobliwości

Wydział MiNI PW

 

MATEMATYKA DYSKRETNA

Wykład: dr hab. Wojciech Domitrz

Wymiar godzin zajęć: W-2 C-1

Klasy tematyczne: kombinatoryka, teoria grafów, teoria grup, teoria liczb

Wymagane przedmioty poprzedzające: algebra liniowa, logika i teoria mnogości, analiza i równania różniczkowe (semestr I)

Forma zaliczenia: egzamin

Semestr wzorcowy: 2

Słowa kluczowe: rekurencja, funkcje generujące, graf, cykl, drzewo, grupa

Program w rozbiciu na poszczególne tygodnie

  1. Prawa i metody przeliczana.
  2. Współczynniki dwumianowe i wielomianowe, podziały liczb, tożsamości kombinatoryczne.
  3. Podstawowe pojęcia teorii grafów, algorytm Dijkstry.
  4. Grupy, działania grup, orbity.
  5. Drzewa, twierdzenie Cayleya, kod Prüfera.
  6. Systemy reprezentantów, twierdzenie Halla, skojarzenia,
  7. Zasada szufladkowa, zasada dwoistości, zasada włączania-wyłączania.
  8. Grafy eulerowskie i hamiltonowskie
  9. Równania rekurencyjne
  10. Funkcje tworzące.
  11. Kolorowanie krawędzi, twierdzenieVizinga.
  12. Kolorowanie wierzchołków, twierdzenie Brooksa.
  13. Planarność grafów, twerdzenie Kuratowskiego.
  14. Liczby pierwsze i względnie pierwsze, algorytm Euklidesa.
  15. Zadania egzaminacyjne. Powtórzenie.

Zakres ćwiczeń:

Celem ćwiczeń jest nauka rozwiązywania zadań (problemów) teoretycznych oraz omawianie przykładów ilustrujących treść wykładu.

Literatura

  1. Garrett Birkhoff, Thomas C. Bartee, Współczesna algebra stosowana, PWN, Warszawa, 1983.
  2. Victor Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997.
  3. Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Matematyka konkretna , PWN, Warszawa, 1996.
  4. Neal Koblitz, Algebraiczne aspekty kryptografi , WNT, Warszawa 2000.
  5. Neal Koblitz, Wyklady z teorii liczb i kryptografi, WNT, Warszawa 1995.
  6. Witold Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 1989.
  7. Zbigniew Palka, Andrzej Ruciński, Wykłady z kombinatoryki, WNT, Warszawa, 1998.
  8. Kenneth A. Ross, Charles R. B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
  9. Robin J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1998.