Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna (I)
Koordynator przedmiotu:
dr Mariusz Zając
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. 2018/2019
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 Podstawy kombinatoryki (14 h): Prawa i metody przeliczania. Permutacje, kombinacje, wariacje, współczynniki dwumianowe, współczynniki wielomianowe. Podziały liczb, podziały zbiorów. Tożsamości kombinatoryczne. Zasada Szufladkowania, zasada dwoistości, zasada włączania-wyłączania. Systemy reprezentantów, twierdzenie Halla, skojarzenia. Równania rekurencyjne i funkcje tworzące. Elementy teorii grafów (12h): Podstawowe pojęcia. Drzewa, twierdzenie Cayleya, kod Prufera, drzewa rozpinające. Drogi i cykle, algorytm Dijkstry. Grafy eulerowskie i hamiltonowskie. Kolorowanie krawędzi, twierdzenie Vizinga, kolorowanie wierzchołków, twierdzenie Brooksa. Planarność grafów, twierdzenie Kuratowskiego. Elementy teorii grup i teorii liczb (4h): Grupy, działania grup, orbity. Liczby pierwsze i względnie pierwsze, algorytm Euklidesa. Treść ćwiczeń Ćwiczenia obejmują naukę rozwiązywania zadań (problemów) związanych bezpośrednio z tematyką wykładów oraz omawianie przykładów ilustrujących treść wykładu.
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:
https://usosweb.usos.pw.edu.pl/kontroler.php?_action=katalog2/przedmioty/pokazPrzedmiot&prz_kod=103B-INxxx-ISP-MAD
Uwagi:
-

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Charakterystyka 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 charakterystyki kierunkowe: K_W01, K_W11, K_W19
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka MAD_W02
Posiada wiedzę na temat podstawowych metod przeliczania obiektów dyskretnych
Weryfikacja: kolokwia i egzamin
Powiązane charakterystyki kierunkowe: K_W01
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka MAD_W03
Zna podstawowe algorytmy rozwiązywania pewnych typów równań rekurencyjnych
Weryfikacja: kolokwium, egzamin
Powiązane charakterystyki kierunkowe: K_W01
Powiązane charakterystyki obszarowe: I.P6S_WG
Charakterystyka MAD_W04
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 charakterystyki kierunkowe: K_W01
Powiązane charakterystyki obszarowe: I.P6S_WG

Profil ogólnoakademicki - umiejętności

Charakterystyka MAD_U01
Umie posługiwać się, w różnych kontekstach, podstawowymi pojęciami matematyki dyskretnej
Weryfikacja: 2 kolokwia, egzamin
Powiązane charakterystyki kierunkowe: K_U01
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.2.o
Charakterystyka 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 charakterystyki kierunkowe: K_U02, K_U05, K_U09, K_U01
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.1.o, III.P6S_UW.2.o, I.P6S_UU
Charakterystyka MAD_U03
Umie tworzyć i rozwiązywać pewne typy równań rekurencyjnych.
Weryfikacja: kolokwium, egzamin
Powiązane charakterystyki kierunkowe: K_U01, K_U02, K_U05, K_U09
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.2.o, III.P6S_UW.1.o, I.P6S_UU
Charakterystyka MAD_U04
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 charakterystyki kierunkowe: K_U02
Powiązane charakterystyki obszarowe: I.P6S_UW, III.P6S_UW.1.o, III.P6S_UW.2.o
Charakterystyka MAD_U05
Potrafi przekazywać, werbalnie oraz pisemnie, abstrakcyjne idee innym.
Weryfikacja: Rozwiązywanie zadań na ćwiczeniach pod okiem ćwiczeniowca, kolokwia, egzaminy.
Powiązane charakterystyki kierunkowe: K_UK01, K_UK03
Powiązane charakterystyki obszarowe: I.P6S_UU, I.P6S_UO