Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna 2
Koordynator przedmiotu:
Prof. dr hab. Zbigniew Lonc
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-IN000-ISP-0232
Semestr nominalny:
3 / rok ak. 2017/2018
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
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:
Analiza matematyczna 1 Algebra liniowa z geometrią Elementy logiki i teorii mnogości Matematyka dyskretna 1
Limit liczby studentów:
Ćwiczenia – 30 os. /grupa
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 drogi 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 drogi 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 droga Eulera, problem chińskiego listonosza. Cykl i ścieżka Hamilona, 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 17 punktów, aktywność na ćwiczeniach 6 punktów oraz egzamin 60 punktów. Razem 100 punktów. 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:
e.mini.pw.edu.pl
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