Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Matematyka dyskretna 2

Koordynator przedmiotu:

Prof. dr hab. Zbigniew Lonc, Dr Paweł Rzążewski

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia I stopnia

Program:

Informatyka i Systemy Informacyjne

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

1120-IN000-ISP-0232

Semestr nominalny:

3 / rok ak. 2023/2024

Liczba punktów ECTS:

4

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

1. godziny kontaktowe – 68 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) konsultacje – 5 h d) obecność na egzaminie – 3 h 2. praca własna studenta – 52 h; w tym a) przygotowanie do ćwiczeń – 30 h b) zapoznanie się z literaturą – 7 h c) przygotowanie do kolokwiów i egzaminu – 15 h Razem 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 4. obecność na egzaminie – 3 h Razem 68 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ą 1 i 2 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, warianty kolorowania grafów, skojarzenia i systemy różnych reprezentantów, przepływy w sieciach, 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, 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, - 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).

Treści kształcenia:

Wykład i ćwiczenia: Spójność, twierdzenie Mengera. Obwód i droga Eulera, problem chińskiego listonosza. Cykl i ścieżka Hamiltona, problem komiwojażera. 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. Planarność, formuła Eulera, twierdzenie Kuratowskiego. Liczba Ramseya.

Metody oceny:

Podstawę zaliczenia stanowią dwa kolokwia (2 x 20 pkt.), aktywność na ćwiczeniach (10 pkt.) i egzamin (50 pkt.). Osoby, które dostaną z ćwiczeń co najmniej 45 pkt., są zwolnione z pisania egzaminu pisemnego. W zależności od sumy punktów z ćwiczeń i egzaminu pisemnego, można uzyskać następujące oceny: 50-59: 3.0, 60-69: 3.5, 70 i więcej: 4.0. Ocenę 4.0 mogą też uzyskać osoby zwolnione z egzaminu pisemnego. Ocenę 3.0 można też uzyskać, zdobywając co najmniej 25 punktów z egzaminu, niezależnie od liczby punktów z ćwiczeń i kolokwiów. Osoby, które po ćwiczeniach i egzaminie pisemnym uzyskały ocenę 4.0 mogą przystąpić do egzaminu ustnego. Jest to jedyny sposób uzyskania ocen 4.5 i 5.0. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nieusprawiedliwiona nieobecność.

Egzamin:

tak

Literatura:

1. J.A. Bondy, U.S.R. Murty – Graph theory with applications, North Holland 1982. 2. W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989. 3. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997. 4. R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.

Witryna www przedmiotu:

Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka W01

Ma wiedzę z matematyki dyskretnej przydatną do formułowania i rozwiązywania prostych zadań związanych z informatyką.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: K_W01
Powiązane charakterystyki obszarowe:

Charakterystyka W02

Ma wiedzę ogólną w zakresie algorytmów teorio- grafowych i ich złożoności obliczeniowej.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe:

Charakterystyka W03

Zna podstawowe metody stosowane do rozwiązywania prostych problemów optymalizacji kombinatorycznej.
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: K_W04
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - umiejętności

Charakterystyka 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 charakterystyki kierunkowe: K_U01, K_U11
Powiązane charakterystyki obszarowe:

Charakterystyka 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 charakterystyki kierunkowe: K_U04
Powiązane charakterystyki obszarowe:

Charakterystyka 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 charakterystyki kierunkowe: K_U03
Powiązane charakterystyki obszarowe:

Profil ogólnoakademicki - kompetencje społeczne

Charakterystyka K01

Rozumie znaczenie wiedzy matematycznej w opisie procesów, tworzeniu modeli, zapisie algorytmów i innych działaniach w obszarze informatyki
Weryfikacja: egzamin
Powiązane charakterystyki kierunkowe: K_K02
Powiązane charakterystyki obszarowe: