Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna II
Koordynator przedmiotu:
dr Konstanty Junosza-Szaniawski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
3 / rok ak. 2009/2010
Liczba punktów ECTS:
4
Liczba godzin pracy studenta związanych z osiągnięciem efektów uczenia się:
Liczba punktów ECTS na zajęciach wymagających bezpośredniego udziału nauczycieli akademickich:
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:
Matematyka Dyskretna I, Analiza matematyczna I, Algebra z geometrią analityczną, Elementy logiki i teorii mnogości.
Limit liczby studentów:
Cel przedmiotu:
do uzupełnienia
Treści kształcenia:
Program wykładu i ćwiczeń: Spójność, twierdzenie Mengera. Obwód i ścieżka Eulera, problem chińskiego listonosza. Cykl i ścieżka Hamiltona, problem komiwojażera. Planarność, formuła Eulera, twierdzenie Kuratowskiego. Kolorowanie krawędzi, indeks chromatyczny, twierdzenie Vizinga. Kolorowanie wierzchołków, liczba chromatyczna, zastosowanie problemu kolorowania do problemów szeregowania zadań. Systemy różnych reprezentantów, twierdzenie Halla, twierdzenie Königa. Przepływy w sieciach, twierdzenie Forda-Fulkersona, algorytm znajdujący największy przepływ. Matroidy, algorytmy zachłanne, twierdzenie Edmondsa. Liczba Ramseya.
Metody oceny:
Podstawę zaliczenia stanowią dwa kolokwia po 16 punktów, aktywność na ćwiczeniach 8pkt oraz egzamin 60pkt. Razem 100 pkt.  Ocena 3.0 – 50-59 pkt, 3.5 – 60-69 pkt, 4.0 – 70-79 pkt, 4.5 – 80-89 pkt, 5.0 – 90-100 pkt. Nie ma możliwości poprawy kolokwiów. Obecność na ćwiczeniach obowiązkowa, dopuszczalna dwa razy nieusprawiedliwiona nieobecność.
Egzamin:
Literatura:
[1] W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa 1986. [2] W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989. [3] Z. Palka, A. Ruciński, Wykłady z Kombinatoryki, cz. 1, WNT, Warszawa 1998. [4] V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997. [5] R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się