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):
Zasada indukcji matematycznej
Podstawowe zasady i prawa przeliczania: zasada bijekcji, prawa dodawania i mnożenia
Schematy wyboru i permutacje
Zasada szufladkowa Dirichleta
Zasada włączania i wyłączania
Tożsamości kombinatoryczne
Jednorodne liniowe zależności rekurencyjne – metoda funkcji charakterystycznej
Niejednorodne liniowe rekurencje o stałych współczynnikach
Funkcje tworzące i ich zastosowania w kombinatoryce oraz rozwiązywaniu rekurencji
Liczby Catalana
Podstawowe pojęcia teorii grafów
Spójność grafów
Lasy i drzewa
Grafy eulerowskie i hamiltonowskie
Kolorowanie grafów
UWAGA: Egzamin odbędzie się 23 czerwca: godz. 10:00 test (Aula C2), godz. 13:00 początek egzaminu ustnego (A1/6); osoby chcące zdawać egzamin ustny we wtorek 24 czerwca poproszę o kontakt emailowy
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:
J. Jaworski, J. Szymański, Z. Palka, Matematyka dyskretna dla informatykow, Część I: Elementy kombinatoryki, Wydawnictwo Naukowe UAM, Poznan 2007
R. J. Wilson, Wprowadzenie do teorii grafów, PWN, 2008
Literatura uzupełniająca:
V. Bryant, Aspekty kombinatoryki, WNT, 2007
M. Zakrzewski, Matematyka dyskretna, Oficyna Wydawnicza GiS, Wrocław 2014
K. A. Ross, C. R. B. Wright, Matematyka dyskretna, PWN, 2011
A.D. 13.05.2025