Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Wybranie zagadnienia teorii grafów
Koordynator przedmiotu:
dr inż. Krzysztof J. Bryś
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
2 / rok ak. 2011/2012
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
  • Ćwiczenia15h
  • Laboratorium0h
  • Projekt0h
  • Lekcje komputerowe0h
Wymagania wstępne:
Matematyka Dyskretna
Limit liczby studentów:
Cel przedmiotu:
Wykorzystywania w praktyce pojęć i faktów poznanych w czasie zajęć. Umiejętność samodzielnego rozwiązywania problemów i dowodzenia twierdzeń związanych z teorią grafów.
Treści kształcenia:
1. Znajdowanie maksymalnego skojarzenia w grafie. Twierdzenie Berge’a. 2. Kolorowanie grafów. Algorytmy sekwencyjne. Grafy doskonałe. 3. Kolorowanie z listy. 4. Wielomiany chromatyczne. 5. Zliczanie drzew. Kod Prufera. 6. Zliczanie grafów izomorficznych. 7. Grafy skierowane. Silna spójność. Turnieje. 8. Ścieżki w grafie. Pokrycie grafu ścieżkami. Ścieżki między danymi wierzchołkami grafu. 9. Problem komiwojażera. Wybrane algorytmy rozwiązujące ten problem. 10. Grafy nieskończone. Lemat Koniga. 11. Elementy teorii Ramseya dla grafów. 12. Minory w grafach. 13. Grafy losowe.  
Metody oceny:
Jedno kolokwium na ostatnim wykładzie złożone z 3-4 pytań teoretycznych dotyczących wiedzy podawanej podczas wykładów oraz 2-3 zadań do samodzielnego rozwiązania analogicznych do zadań rozwiązywanych na ćwiczeniach. Maksymalna liczba punktów do zdobycia na kolokwium: 100. Do punktów uzyskanych na końcowym kolokwium doliczane będą punkty dodatkowe uzyskane za aktywność na ćwiczeniach, samodzielne wykonanie nieobowiązkowych prac domowych (0-10 punktów). Zdobycie w sumie 51 punktów oznacza zaliczenie ćwiczeń i wykładu. Oceny: 51-60 punktów w sumie - 3.0, 61-70 - 3.5, 71-80 - 4.0, 81-90 - 4.5, powyżej 90 - 5.0. Do kolokwium zaliczeniowego dopuszczeni będą wszyscy studenci zapisani na wykład. Możliwe będzie powtórne pisanie kolokwium.  
Egzamin:
Literatura:
1. N. Deo – Teoria grafów i jej zastosowania w technice i informatyce, PWN, 1985. 2. M.M. Sysło, N. Deo, J.Kowalik – Algorytmy optymalizacji dyskretnej, PWN, 1995. 3. K.A. Ross, C.R.B. Wright – Matematyka Dyskretna, PWN, 2000. 4. R.J. Wilson – Wprowadzenie do teorii grafów, PWN, 1998.  
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się