Politechnika
Warszawska

Katalog
ECTS

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