Matematyka dyskretna 0600-IS1-1MDY
Wykład (WYK) Rok akademicki 2017/18

Literatura podstawowa:

1. K.A.Ross, Ch.R.B.Wright, Matematyka dyskretna, PWN, Warszawa 1996

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

3. Z.Palka, A.Ruciński, Wykłady z kombinatoryki, WNT, Warszawa 1998

Literatura uzupełniająca:

1. W.Lipski, Kombinatoryka dla programistów, WNT, Warszawa 2004

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

3. N.J. Wilenkin, Kombinatoryka, PWN, Warszawa 1972

4. R.L.Graham, D.E.Knuth, O.Patashnik, Matematyka konkretna, PWN, Warszawa 1996

Efekty kształcenia w ramach realizacji przedmiotu:

zna aparat matematyczny niezbędny do konstruowania i analizy algorytmów. K_W01, K_W03

zna podstawowe pojęcia z kombinatoryki, teorii grafów i liczb. K_W01

umie stosować kombinatorykę, rekurencję i indukcję matematyczną do rozwiązywania prostych problemów o charakterze informatycznym. K_U02, K_U04

Umie zastosować przeszukiwanie grafu ważonego metodą wszerz w problemie wyszukiwania najkrótszych ścieżek . K_U06

Rozumie potrzebę ustawicznego kształcenia się. K_K02

Sposoby weryfikacji: egzamin pisemny lub egzamin ustny.

Zaliczenie przedmiotu na podstawie pomyślnie zdanego egzaminu pisemnego lub ustnego. Warunkiem przystąpienia do egzaminu jest zaliczenie ćwiczeń.

Indukcja matematyczna. Definicje rekurencyjne. Podstawowe zagadnienia kombinatoryczne. Wzór włączeń i wyłączeń. Rozkład permutacji na cykle. Liczby Stirlinga i Bella. Problemy i metody teorii grafów. Cykl Eulera i cykl Hamiltona. Przeszukiwanie grafów. Drzewa. Elementy teorii liczb. Algorytm Euklidesa. Kongruencje.

Wykład, dyskusja