Matematyka dyskretna 3.4.KRK.12NX.MAD
A. Problematyka wykładu
Rekurencja, równania rekurencyjne. Symbolika asymptotyczna. Zliczanie i generowanie obiektów kombinatorycznych. Współczynniki dwumianowe. Podziały. Funkcje tworzące. Podstawowe pojęcia teorii grafów. Drzewa, drzewa z korzeniem, drzewa binarne. Drzewa rozpinające. Tranzytywne domknięcie grafu, najkrótsze ścieżki w grafie ważonym.
B. Problematyka konwersatorium
Liniowe równania rekurencyjne. Badanie asymptotyki funkcji liczbowych. Podstawowe obiekty kombinatoryczne i ich zliczanie. Badanie podstawowych własności grafów. Metody przeszukiwania grafów. Algorytmy Kruskala i Prima. Algorytmy Dijkstry.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
Ma podstawową wiedzę stosowaną w badaniu własności liniowych równań różnicowych. Zna podstawowe obiekty kombinatoryczne i metody ich zliczania. Ma wiedzę o podstawowych własnościach grafów.
Umiejętności:
Potrafi rozwiązywać liniowe równania rekurencyjne. Potrafi znaleźć „dobrą” asymptotykę funkcji liczbowych. Potrafi stosować poznane zasady zliczania do znalezienia mocy zbiorów skończonych. Potrafi stosować poznane algorytmy przeszukiwania grafów.
Kompetencje społeczne:
Rozumie potrzebę pogłębiania własnego zrozumienia danego tematu dla odnalezienia brakują-cych elementów rozumowania
Kryteria oceniania
Wykład: ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w przeciągu semestru za sprawdziany pisemne uzyskanej wiedzy przeprowadzane w trakcie konwersatorium.
Konwersatorium: ; ustalenie oceny zaliczeniowej na podstawie ocen cząstkowych otrzymywanych w trakcie trwania semestru za wystąpienia ustne i za prace pisemne sprawdzające osiągnięte umiejętności.
Literatura
A. Literatura wymagana
1. K.A.Ross, Ch.R.B.Wright, Matematyka dyskretna, PWN, 1996.
2. R.J.Wilson, Wprowadzenie do teorii grafów, PWN, Warszawa, 1985.
B. Literatura uzupełniająca
1. R. Graham, D. E. Knuth, O. Patashnik, Matematyka konkretna, PWN, Warszawa, 1996.
2. W. Narkiewicz, Teoria liczb, PWN, 2003.
Więcej informacji
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: