Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Matematyka dyskretna
Koordynator przedmiotu:
dr Konstanty Junosza-Szaniawski
Status przedmiotu:
Obowiązkowy
Poziom kształcenia:
Studia I stopnia
Program:
Matematyka
Grupa przedmiotów:
Kod przedmiotu:
Semestr nominalny:
2 / rok ak. 2011/2012
Liczba punktów ECTS:
3
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
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Przedmioty poprzedzające: Elementy logiki i teorii mnogości.
Limit liczby studentów:
Cel przedmiotu:
Zapoznanie studentów z podstawowymi koncepcjami, strukturami, rezultatami i metodami matematyki dyskretnej
Treści kształcenia:
Program wykładu i ćwiczeń: 1. Indukcja matematyczna, definicje rekurencyjne, równania rekurencyjne, 2. Podstawy kombinatoryki - podstawowe struktury kombinatoryczne, permutacje, kombinacje, współczynniki Newtona, podstawowe metody zliczania, tożsamości kombinatoryczne, zasada włączania-wyłączania. 3. Podstawy teorii grafów - podstawowe pojęcia. 4. Drzewa, minimalne drzewa rozpinające, algorytm Kruskala. 5. Spójność, twierdzenie Mengera. 6. Obwód i ścieżka Eulera. 7. Cykl i ścieżka Hamiltona, problem komiwojażera. 8. Planarność, formuła Eulera, twierdzenie Kuratowskiego. 9. Kolorowanie krawędzi, indeks chromatyczny, twierdzenie Vizinga. 10. Kolorowanie wierzchołków, liczba chromatyczna.
Metody oceny:
Podstawę zaliczenia stanowią dwa kolokwia po 16 punktów, aktywność na ćwiczeniach 8pkt oraz egzamin 60 pkt. 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. V. Bryant, Aspekty kombinatoryki, WNT, Warszawa 1997. 2. W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989. 3. R. J. Wilson, Wstęp do teorii grafów, PWN, Warszawa 1998.
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się