Wykład ,,Matematyka dyskretna dla informatyków”

I rok, Informatyka (studia inżynierskie), inżynieria systemów informatycznych

EGZAMIN: 17 czerwca, godz. 9:00, aula B (test), 18-19 czerwca sala A1/6 (egzamin ustny)
EGZAMIN POPRAWKOWY I: 6 września, godz. 9:00, aula B (test – piszą wszyscy studenci), sala A1/6 (egzamin ustny)
EGZAMIN POPRAWKOWY II: 16 września, sala A1/6 (egzamin ustny) godzina 13:00

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. Kolorowanie grafów

15. Grafy eulerowskie i hamiltonowskie

16. Grafy planarne

sylabus

Sposób zaliczenia ćwiczeń: Należy zdobyć minimum połowę punktów z cotygodniowych zadań domowych (40% możliwych punktów do uzyskania), wyników dwóch kolokwiów (50%) 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:

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

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

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

6. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, 1986

A.D. 6.09.2024