Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna (I)
Koordynator przedmiotu:
dr hab. Wojciech DOMITRZ
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. 2012/2013
Liczba punktów ECTS:
4
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:
4
Język prowadzenia zajęć:
polski
Liczba punktów ECTS, którą student uzyskuje w ramach zajęć o charakterze praktycznym:
0
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.
Limit liczby studentów:
130
Cel przedmiotu:
Zapoznanie studentów z podstawową wiedzą z zakresu matematyki dyskretnej. Ukształtowanie umiejętności rozwiązywania zadań rachunkowych oraz problemów związanych z omawianymi zagadnieniami.
Treści kształcenia:
Treść wykładu : 1. 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. 2. 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. 3. Elementy teorii grup i teorii liczb (4h): • Grupy, działania grup, orbity. • Liczby pierwsze i względnie pierwsze, algorytm Euklidesa. 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. Zliczanie grafów i drzew. Wyznaczanie kodów Prüfera. Badanie izomorficzności grafów. (2h) 3. Znajdowanie i badanie istnienia systemów różnych reprezentantów i skojarzeń (1h) 4. Wykorzystanie zasady dwoistości i zasady szufladkowej do rozwiązywanie problemów kombinatorycznych. (1h) 5. Przeliczanie obiektów metodą włączeń-wyłączeń.(2h) 6. Wyznaczanie równań rekurencyjnych i ich rozwiązywanie. (3h) 7. Obliczenia indeksu chromatycznego i liczby chromatycznej grafów.(1h) 8. Sprawdzanie eulerowskości, hamiltonowskości i planarności grafów. Szukanie cyklów Eulera i Hamiltona(1h)
Metody oceny:
2 kolokwia, egzamin
Egzamin:
tak
Literatura:
1. Victor Bryant, Aspekty kombinatoryki, WNT, Warszawa, 1997. 2. Witold Lipski, Kombinatoryka dla programistów, WNT, Warszawa, 1989. 3. Zbigniew Palka, Andrzej Ruciński, Wykłady z kombinatoryki, WNT, Warszawa, 1998.
Witryna www przedmiotu:
http://www.mini.pw.edu.pl/~domitrz/mad.html
Uwagi:
Brak

Efekty uczenia się

Profil ogólnoakademicki - wiedza

Efekt T1A_W01
Zna podstawowe algorytmy rozwiązywania pewnych typów równań rekurencyjnych
Weryfikacja: kolokwium, egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe:

Profil ogólnoakademicki - umiejętności

Efekt T1A_U02
Umie tworzyć i rozwiązywać pewne typy równań rekurencyjnych.
Weryfikacja: kolokwium, egzamin
Powiązane efekty kierunkowe:
Powiązane efekty obszarowe: