Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna (I)
Koordynator przedmiotu:
dr Paweł NAROSKI
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Przedmioty techniczne
Kod przedmiotu:
MAD
Semestr nominalny:
2 / rok ak. 2015/2016
Liczba punktów ECTS:
3
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
- udział w wykładach: 15×2=30 godz., - przygotowanie do wykładów (przejrzenie podręczników i notatek) : 10 godz., - przygotowanie do ćwiczeń (rozwiązanie kilku zadań z udostępnionych zestawów): 10 godz., - udział w ćwiczeniach: 15×1=15 godz., - przygotowanie do kolokwiów (rozwiązanie samodzielne odpowiedniej liczby zadań): 2×10=20 godz., - przygotowanie do egzaminu (powtórzenie teorii, przejrzenie notatek z ćwiczeń, rozwiązanie udostępnionych zestawów zadań z poprzednich egzaminów): 20 godz. Suma: 30+10+10+15+20+20=105 godz.
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
1
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
2
Formy zajęć i ich wymiar w semestrze:
  • Wykład30h
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Znajomość matematyki na poziomie pierwszego semestru studiów inżynierskich - w szczególności podstaw logiki i teorii mnogości, algebry liniowej oraz teorii szeregów.
Limit liczby studentów:
130
Cel przedmiotu:
Zapoznanie studentów z podstawowymi pojęciami i metodami matematyki dyskretnej ze szczególnym podkreśleniem ich roli w projektowaniu algorytmów.
Treści kształcenia:
Treść wykładu : 1. Zliczanie (14 h): • Elementarne prawa i metody przeliczania. • Permutacje, kombinacje, współczynniki dwumianowe, kombinacje z powtórzeniami, podziały liczb, wariacje. • Podziały liczb. • Podwójne zliczanie. • Zasada włączeń i wyłączeń. • Zasada szufladkowa. • Równania rekurencyjne i funkcje tworzące. 2. Teorii grafów (16h): • Podstawowe pojęcia. • Drzewa, twierdzenie Cayleya, kod Prüfera. • Izomorfizm grafów. • Drzewa rozpinające. • Drogi i cykle, algorytm Dijkstry. • Skojrzenia w grafach i twierdzenie Halla. • Grafy eulerowskie i hamiltonowskie. • Kolorowanie krawędzi, twierdzenie Vizinga, kolorowanie wierzchołków, twierdzenie Brooksa. • Planarność grafów, twierdzenie Kuratowskiego. • Spójność grafów i twierdzenie Mengera oraz wnioski z niego. Definicje, twierdzenia, dowody oraz przykłady prezentowane są na wykładzie na tablicy. Zakres ćwiczeń 1. Przeliczanie obiektów. Dowodzenie tożsamości kombinatorycznych. (2h) 2. Przeliczanie obiektów metodą włączeń i wyłączeń. (2h) 3. Wykorzystanie zasady szufladkowej i innych narzędzi kombinatorycznych do rozwiązywanie problemów. (1h) 4. Układanie równań rekurencyjnych i ich rozwiązywanie. (2h) 5. Zliczanie grafów i drzew. Wyznaczanie kodów Prüfera. Badanie istnienia izomorfizmu grafów. (2h) 6. Znajdowanie i badanie istnienia skojarzeń doskonałych i pokrywających dany zbiór wierzchołków. (1h) 7. Wyznaczanie indeksu chromatycznego i liczby chromatycznej grafów. (1h) 8. Badanie istnienia cyklów Eulera i Hamiltona. (1h) 9. Badanie k-spójności grafów. (1h)
Metody oceny:
Dwa kolokwia oraz egzamin.
Egzamin:
tak
Literatura:
1. Victor Bryant, Aspekty kombinatoryki, WNT, 1997. 2. Ronald Graham, Donald Knuth, Oren Patashnik, Matematyka konkretna, PWN, 2013. 2. Witold Lipski, Kombinatoryka dla programistów, WNT, 1989. 3. Zbigniew Palka, Andrzej Ruciński, Wykłady z kombinatoryki, WNT, 1998. 4. Robin Wilson, Wprowadzenie do teorii grafów, PWN, 2012.
Witryna www przedmiotu:
http://www.mini.pw.edu.pl/~pnaroski/www/?Dydaktyka:MAD
Uwagi:
Brak

Efekty uczenia się

Profil praktyczny - wiedza

Efekt Wpisz opis
Posiada wiedzę teoretyczną umożliwiającą ścisłe formułowanie problemów praktycznych i elementarne metody kombinatoryczne ich rozwiązywania. Wie, gdzie szukać rozwiązań problemów bardziej złożonych.
Weryfikacja: Kolokwia i egzamin. Bardziej złożone zadania w zestawach zadań na ćwiczenia wymagające rozszerzenia wiedzy podanej na zajęciach.
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:

Profil praktyczny - umiejętności

Efekt Wpisz opis
Posiada elementarne umiejętności posługiwania się pojęciami i metodami matematyki dyskretnej. Potrafi na podstawowym poziomie modelować praktyczne problemy za pomocą teorii grafów.
Weryfikacja: Kolokwia i egzamin.
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:

Profil ogólnoakademicki - wiedza

Efekt MAD_W01
Student zna podstawowe definicje i twierdzenia matematyki dyskretnej, rozumie pojęcie istotności założeń w poznanych twierdzeniach; zna podstawowe przykłady ilustrujące poznane pojęcia
Weryfikacja: kolokwia i egzamin
Powiązane efekty kierunkowe: K_W01, K_W11, K_W19
Powiązane efekty obszarowe: T1A_W01, T1A_W02, T1A_W03, T1A_W07, T1A_W03, T1A_W07
Efekt MAD_W02
Posiada wiedzę na temat podstawowych metod przeliczania obiektów dyskretnych
Weryfikacja: kolokwia i egzamin
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01, T1A_W02, T1A_W03, T1A_W07
Efekt MAD_W03
Zna podstawowe algorytmy rozwiązywania pewnych typów równań rekurencyjnych
Weryfikacja: kolokwium, egzamin
Powiązane efekty kierunkowe: K_W01
Powiązane efekty obszarowe: T1A_W01, T1A_W02, T1A_W03, T1A_W07

Profil ogólnoakademicki - umiejętności

Efekt MAD_U01
Umie posługiwać się, w różnych kontekstach, podstawowymi pojęciami matematyki dyskretnej
Weryfikacja: 2 kolokwia, egzamin
Powiązane efekty kierunkowe: K_U01
Powiązane efekty obszarowe: T1A_U09
Efekt MAD_U02
Umie zliczać pewne obiekty dyskretne posługując się poznanymi metodami, umie sprawdzać własności grafów posługując sie poznanymi definicjami i twierdzeniami.
Weryfikacja: kolokwia i egzamin
Powiązane efekty kierunkowe: K_U01, K_U02, K_U05, K_U09
Powiązane efekty obszarowe: T1A_U09, T1A_U08, T1A_U09, T1A_U01, T1A_U15, T1A_U05
Efekt MAD_U03
Umie tworzyć i rozwiązywać pewne typy równań rekurencyjnych.
Weryfikacja: kolokwium, egzamin
Powiązane efekty kierunkowe: K_U01, K_U02, K_U05, K_U09
Powiązane efekty obszarowe: T1A_U09, T1A_U08, T1A_U09, T1A_U01, T1A_U15, T1A_U05

Profil ogólnoakademicki - kompetencje społeczne

Efekt MAD_K01
Potrafi przekazywać, werbalnie oraz pisemnie, abstrakcyjne idee innym.
Weryfikacja: Rozwiązywanie zadań na ćwiczeniach pod okiem ćwiczeniowca, kolokwia, egzaminy.
Powiązane efekty kierunkowe: K_K01, K_K02, K_K03
Powiązane efekty obszarowe: T1A_K01, T1A_K02, T1A_K03