Drukuj Eksport do pliku (MS Word)
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. 2021/2022
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ą 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:
e.mini.pw.edu.pl
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: