Politechnika
Warszawska

Katalog
ECTS

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. 2015/2016

Liczba punktów ECTS:

4

Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:

1. godziny kontaktowe – 65 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) konsultacje – 5 h 2. praca własna studenta – 55 h; w tym a) przygotowanie do ćwiczeń – 30 h b) zapoznanie się z literaturą – 10 h c) przygotowanie do kolokwiów i egzaminu – 15 h

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:

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 kon-cepcjami, strukturami, rezultatami i metodami matematyki dyskretnej oraz pokazanie ich użyteczności w informatyce. Studenci poznają wła-snoś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 8 pkt oraz egzamin 60 pkt. 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, War-szawa 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