- Nazwa przedmiotu:
- Matematyka dyskretna II
- Koordynator przedmiotu:
- dr Konstanty Junosza-Szaniawski
- Status przedmiotu:
- Obowiązkowy
- Poziom kształcenia:
- Studia I stopnia
- Program:
- Informatyka
- Grupa przedmiotów:
- Wspólne
- Kod przedmiotu:
- Semestr nominalny:
- 3 / rok ak. 2013/2014
- Liczba punktów ECTS:
- 4
- Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- 1. godziny kontaktowe – 60 h; w tym
a. obecność na wykładach – 30 h
b. obecność na ćwiczeniach – 30 h
2. przygotowanie do ćwiczeń – 30 h
3. zapoznanie się z literaturą – 10 h
4. konsultacje – 5 h
5. przygotowanie do kolokwiów – 15 h
Łączny nakład pracy studenta wynosi 120 h co odpowiada 4 pkt. ECTS
- Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
- 1. obecność na wykładach – 30 h
2. obecność na ćwiczeniach – 30 h
3. konsultacje – 5 h
Razem 65 h, co odpowiada 3 pkt. ECTS
- Język prowadzenia zajęć:
- polski
- Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
- Formy zajęć i ich wymiar w semestrze:
-
- Wykład30h
- Ćwiczenia30h
- Laboratorium0h
- Projekt0h
- Lekcje komputerowe0h
- Wymagania wstępne:
- Matematyka Dyskretna I, Analiza matematyczna I, Algebra z geometrią analityczną, Elementy logiki i teorii mnogości.
- Limit liczby studentów:
- Bez limitu
- Cel przedmiotu:
- Celem przedmiotu jest zapoznanie studentów z podstawowymi koncepcjami, strukturami, rezultatami i metodami matematyki dyskretnej oraz pokazanie ich użyteczności w informatyce. Studenci poznają własności struktur dyskretnych pod kątem ich wykorzystania do rozwiązywania problemów informatycznych.
Po ukończeniu kursu studenci powinni znać następujące pojęcia matematyki dyskretnej (i związanych z nią dziedzin matematyki) ich własności: spójność grafów, obwody i ścieżki Eulera, cykle i ścieżki Hamiltona, planarność grafów, chromatyka grafów, systemy różnych reprezentantów, przepływy w sieciach, matroidy, algorytmy zachłanne, podstawy teorii Ramseya. Powinni także posiadać następujące umiejętności:
wykorzystania nabytej wiedzy do rozwiązania (w sposób dokładny lub przybliżony) optymalizacyjnych problemów kombinatorycznych (m. in. problemu chińskiego listonosza, problemu komiwojażera, pewnych problemów szeregowania zadań, problemu największego przepływu w sieci)
odróżnienia, w przypadku podstawowych problemów teorii grafów, które z tych problemów są obliczeniowo trudne, a które łatwe
określenia spójności grafu
znalezienia za pomocą odpowiedniego algorytmu cyklu i ścieżka Eulera w grafie, o ile istnieje
określenia czy graf jest planarny
znajdowania liczby chromatycznej i indeksu chromatycznego grafu (dla grafów niewielkiego rozmiaru)
wykorzystania teorii matroidów do konstrukcji algorytmów zachłannych.
- Treści kształcenia:
- Program wykładu i ćwiczeń:
Spójność, twierdzenie Mengera.
Obwód i ścieżka Eulera, problem chińskiego listonosza.
Cykl i ścieżka Hamiltona, problem komiwojażera.
Planarność, formuła Eulera, twierdzenie Kuratowskiego.
Kolorowanie krawędzi, indeks chromatyczny, twierdzenie Vizinga.
Kolorowanie wierzchołków, liczba chromatyczna, zastosowanie problemu kolorowania do problemów szeregowania zadań.
Systemy różnych reprezentantów, twierdzenie Halla, twierdzenie Königa.
Przepływy w sieciach, twierdzenie Forda-Fulkersona, algorytm znajdujący największy przepływ.
Matroidy, algorytmy zachłanne, twierdzenie Edmondsa.
Liczba Ramseya.
- Metody oceny:
- Podstawę zaliczenia stanowią dwa kolokwia po 16 punktów, aktywność na ćwiczeniach 8pkt oraz egzamin 60pkt. Razem 100 pkt. Ocena 3.0 – 50-59 pkt, 3.5 – 60-69 pkt, 4.0 – 70-79 pkt, 4.5 – 80-89 pkt, 5.0 – 90-100 pkt. Nie ma możliwości poprawy kolokwiów. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nieusprawiedliwiona nieobecność.
- Egzamin:
- tak
- Literatura:
- [1] W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986.
[2] W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989.
[3] Z. Palka, A. Ruciński, Wykłady z Kombinatoryki, cz. 1, WNT, Warszawa 1998.
[4] V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997.
[5] R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.
- Witryna www przedmiotu:
- brak
- Uwagi:
Efekty uczenia się
Profil ogólnoakademicki - wiedza
- Efekt W01
- Ma wiedzę z matematyki dyskretnej przydatną do formułowania i rozwiązywania prostych zadań związanych z informatyką.
Weryfikacja: egzamin
Powiązane efekty kierunkowe:
K_W01
Powiązane efekty obszarowe:
T1A_W01
- Efekt W02
- Ma wiedzę ogólną w zakresie algorytmów teorio- grafowych i ich złożoności obliczeniowej.
Weryfikacja: egzamin
Powiązane efekty kierunkowe:
K_W04
Powiązane efekty obszarowe:
T1A_W03
- Efekt W03
- Zna podstawowe metody stosowane do rozwiązywania prostych problemów optymalizacji kombinatorycznej.
Weryfikacja: egzamin
Powiązane efekty kierunkowe:
K_W04
Powiązane efekty obszarowe:
T1A_W03
Profil ogólnoakademicki - umiejętności
- Efekt U01
- Potrafi wykorzystać nabytą wiedzę z matematyki dyskretnej do tworzenia modeli w obszarze informatyki oraz do konstruowania prostych algorytmów.
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane efekty kierunkowe:
K_U01, K_U11
Powiązane efekty obszarowe:
T1A_U09, T1A_U09, T1A_U14, T1A_U15
- Efekt U02
- Potrafi zidentyfikować dyskretne struktury matematyczne w problemach i wykorzystać teoretyczną wiedzę dotyczącą tych struktur do analizy i rozwiązania tych problemów.
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane efekty kierunkowe:
K_U04
Powiązane efekty obszarowe:
T1A_U09
- Efekt U03
- Potrafi wykorzystać wiedzę z teorii grafów do tworzenia, analizowania i stosowania modeli matematycznych służących do rozwiązywania problemów z różnych dziedzin.
Weryfikacja: kolokwia i ocena punktowa aktywności na zajęciach
Powiązane efekty kierunkowe:
K_U03
Powiązane efekty obszarowe:
T1A_U09