Wykład ,,Kombinatoryka i teoria grafów”

I rok, Informatyka (studia inżynierskie), Data science i artificial intelligence w praktyce


poniedziałki, godz. 9:45-11:15, C0/2

Treści zajęć (zagadnienia na egzamin):

  1. Zasada indukcji matematycznej

  2. Podstawowe zasady i prawa przeliczania: zasada bijekcji, prawa dodawania i mnożenia

  3. Schematy wyboru i permutacje

  4. Zasada szufladkowa Dirichleta

  5. Zasada włączania i wyłączania

  6. Tożsamości kombinatoryczne

  7. Jednorodne liniowe zależności rekurencyjne – metoda funkcji charakterystycznej

  8. Niejednorodne liniowe rekurencje o stałych współczynnikach

  9. Funkcje tworzące i ich zastosowania w kombinatoryce oraz rozwiązywaniu rekurencji

  10. Liczby Catalana

  11. Podstawowe pojęcia teorii grafów

  12. Spójność grafów

  13. Lasy i drzewa

  14. Grafy eulerowskie i hamiltonowskie

  15. Kolorowanie grafów


sylabus

Sposób zaliczenia ćwiczeń: Należy zdobyć minimum połowę punktów (łącznie) z cotygodniowych zadań domowych (30% możliwych punktów do uzyskania), wyników dwóch kolokwiów (60%) i aktywności na zajęciach (10%).

Sposób zaliczenia wykładu: Egzamin ustny (odpowiedź na wybrane losowo trzy pytania) poprzedzony testem.

przykładowy test z ubiegłych lat

Literatura podstawowa:

  1. J. Jaworski, J. Szymański, Z. Palka, Matematyka dyskretna dla informatykow, Część I: Elementy kombinatoryki, Wydawnictwo Naukowe UAM, Poznan 2007

  2. R. J. Wilson, Wprowadzenie do teorii grafów, PWN, 2008

Literatura uzupełniająca:

  1. V. Bryant, Aspekty kombinatoryki, WNT, 2007

  2. M. Zakrzewski, Matematyka dyskretna, Oficyna Wydawnicza GiS, Wrocław 2014

  3. K. A. Ross, C. R. B. Wright, Matematyka dyskretna, PWN, 2011

A.D. 20.02.2025