Nazwa przedmiotu:
Matematyka Dyskretna
Koordynator przedmiotu:
dr Tomasz Traczyk
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Matematyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
1120-MA000-LSP-0123
Semestr nominalny:
2 / rok ak. 2015/2016
Liczba punktów ECTS:
5
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
1. godziny kontaktowe – 70 h; w tym a) obecność na wykładach – 30 h b) obecność na ćwiczeniach – 30 h c) obecność na egzaminie – 5 h d) konsultacje – 5 h 2. praca własna studenta – 55 h; w tym a) przygotowanie do ćwiczeń i do kolokwiów – 35 h b) zapoznanie się z literaturą – 5 h c) przygotowanie do egzaminu – 15 h Razem 125 h, co odpowiada 5 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. obecność na egzaminie – 5 h 4. konsultacje – 5 h Razem 70 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:
brak
Limit liczby studentów:
Bez limitu
Cel przedmiotu:
Zapoznanie studenta z podstawowymi pojęciami i metodami kombinatoryki oraz teorii grafów
Treści kształcenia:
1) Podstawy kombinatoryki a) metody zliczania b) zasada włączeń i wyłączeń c) funkcje tworzące d) rekurencja. 2) Podstawowe pojęcia teorii grafów a) drzewa b) najtańsze drzewo rozpinające c) spójność d) twierdzenie Mengera e) cykl Eulera f) cykl Hamiltona g) kolorowanie grafów h) grafy planarne.
Metody oceny:
Ćwiczenia 40 pkt w tym 2 kolokwia po 16 pkt, 8 pkt aktywność na zajęciach. Egzamin pisemny 60 pkt. Do zaliczenia przedmiotu liczy się jedynie suma punktów z ćwiczeń i egzaminu: od 51pkt – 3,0 od 61pkt – 3,5 od 71pkt – 4,0 od 81pkt – 4,5 od 91pkt – 5,0
Egzamin:
tak
Literatura:
1.V. Bryant "Aspekty kombinatoryki", WNT, 2007 2. W. Lipski "Kombinatoryka dla programistów", WNT, 2009 3. R.J. Wilson "Wprowadzenie do teorii grafów", Wydawnictwo Naukowe PWN, 2012 4. Z. Palka, A. Ruciński "Wykłady z Kombinatoryki", WNT, 2007
Witryna www przedmiotu:
http://www.mini.pw.edu.pl/~tomtracz/md/info_matematyka.html
Uwagi:

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt MD_W01
Zna pojęcia kombinacji, permutacji, wariacji, zasadę włączeń i wyłączeń, zasadę Dirichleta. Zna pojęcie funkcji tworzącej i funkcji rekurencyjnej.
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_W09, ML_W10, ML_W11
Powiązane efekty obszarowe: X1A_W01, X1A_W03, X1A_W01, X1A_W02, X1A_W03, X1A_W04, X1A_W01, X1A_W02, X1A_W03
Efekt MD_W02
Zna pojęcie grafu, podgrafu i podstawowe własności grafów. Zna pojęcia drzewa, cyklu w tym cyklu Eulera i Hamiltona i podstawowe twierdzenia. Zna pojęcie kolorowania grafu, liczby chromatycznej indeksu chromatycznego. Zna pojęcie grafu planarnego, Twierdzenie Kuratowskiego i problem 4 kolorów.
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_W09, ML_W11, ML_W12
Powiązane efekty obszarowe: X1A_W01, X1A_W03, X1A_W01, X1A_W02, X1A_W03, X1A_W01, X1A_W02

Profil ogólnoakademicki - umiejętności

Efekt MD_U01
Umie posługiwać się zasadą dodawania, zasadą mnożenia, zasadą szufladkową do zliczania obiektów kombinatorycznych. Potrafi używać funkcji tworzących do zliczania obiektów kombinatorycznych.
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_U09, ML_U10
Powiązane efekty obszarowe: X1A_U01, X1A_U02, X1A_U01, X1A_U02
Efekt MD_U02
Potrafi przeanalizować definicję nowego pojęcia, przykład, dowód twierdzenia. Potrafi samodzielnie konstruować dowody prostych twierdzeń w dziedzinie teorii grafów oraz ocenić poprawność cudzego dowodu.
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_U09, ML_U10
Powiązane efekty obszarowe: X1A_U01, X1A_U02, X1A_U01, X1A_U02

Profil ogólnoakademicki - kompetencje społeczne

Efekt MD_K01
Umie stawiać pytania prowadzące do rozwiązania problemu a nie jego ukrycia.
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_KS03
Powiązane efekty obszarowe: X1A_K03
Efekt MD_K02
Umie odróżnić prawdę od fałszu
Weryfikacja: Egzamin, kolokwia
Powiązane efekty kierunkowe: ML_KS05
Powiązane efekty obszarowe: X1A_K05