Politechnika
Warszawska

Katalog
ECTS

Nazwa przedmiotu:

Matematyka Dyskretna 1

Koordynator przedmiotu:

Prof. dr hab. Zbigniew Lonc, Dr inż. Konstanty Junosza-Szaniawski

Status przedmiotu:

Obowiązkowy

Poziom kształcenia:

Studia I stopnia

Program:

Informatyka

Grupa przedmiotów:

Wspólne

Kod przedmiotu:

1120-IN000-ISP-0010

Semestr nominalny:

2 / 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 – 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 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

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 ma-tematyki dyskretnej (i związanych z nią dziedzin matematyki) ich własności: indukcja matematyczna, definicja rekurencyjna, permutacje, podzbiory zbioru, podziały zbioru i liczby, tożsamości kombinatoryczne, współczynniki Newtona, funkcje tworzące, równania rekurencyjne, kody korygujące błędy, grafy, drzewa. Powinni także posiadać następujące umiejętności: - przeprowadzenia prostego dowodu indukcyjnego - rozwiązania elementarnych typów równań rekurencyjnych - generowania podstawowych obiektów kombinatorycznych (permutacji, podzbiorów zbioru, podziałów zbioru i liczby) - przekształcania i pokazywania prawdziwości tożsamości kombinatorycznych - zliczania obiektów dyskretnych za pomocą podstawowych metod (rozumowań indukcyjnych, funkcji tworzących, zasady włączania-wyłączania) - posługiwania się prostymi kodami korygującymi błędy do zakodowania i odkodowania informacji - znajdowania drzewa rozpinającego o minimalnej wadze w grafie

Treści kształcenia:

Indukcja matematyczna. Rekurencja: definicje i równania rekurencyjne. Asymptotyka funkcji liczbowych. Podstawy kombinatoryki – podstawowe struktury kombinatoryczne, permutacje, kombinacje, podziały zbioru i liczby, algorytmy generowania powyższych struktur. Tożsamości kombinatoryczne - współczynniki Newtona, metody znajdowania i dowodzenia tożsamości kombinatorycznych, rozwiązywanie równań rekurencyjnych. Podstawowe metody zliczania – elementarne zliczanie, funkcje tworzące, zasada włączania-wyłączania. Podzielność liczb naturalnych. Kody korygujące błędy – odległość Hamminga, problem wykrywania i korygowania błędów, przykłady konstrukcji kodów, kody liniowe, kody doskonałe. Podstawy teorii grafów – podstawowe pojęcia, drzewa, minimalne drzewa rozpinające.

Metody oceny:

Podstawę zaliczenia stanowią dwa kolokwia po 16 punktów, aktywność na ćwiczeniach 8 pkt. Razem 40 pkt. Ocena: 3.0 – 20-23 pkt, 3.5 – 24-27 pkt, 4.0 – 28-31 pkt, 4.5 – 32-35 pkt, 5.0 – 36-40 pkt. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nie-usprawiedliwiona nieobecność.

Egzamin:

nie

Literatura:

1. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986. 2. W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 2004. 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. 6. K. A. Ross, C.R.B.Wright, Matematyka Dyskretna, PWN 1999.

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: kolokwia
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01

Efekt W02

Ma wiedzę ogólną w zakresie algorytmów kombinatorycznych i ich złożoności obliczeniowej.
Weryfikacja: kolokwia
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