Drukuj Eksport do pliku (MS Word)
Nazwa przedmiotu:
Chromatyczna teoria grafów
Koordynator przedmiotu:
dr Konstanty Junosza-Szaniawski
Status przedmiotu:
Fakultatywny ograniczonego wyboru
Poziom kształcenia:
Studia II stopnia
Program:
Informatyka
Grupa przedmiotów:
Wspólne
Kod przedmiotu:
Semestr nominalny:
1 / 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
  • Ćwiczenia0h
  • Laboratorium0h
  • Projekt15h
  • Lekcje komputerowe0h
Wymagania wstępne:
- Matematyka Dyskretna. - Algorytmy i struktury danych.  
Limit liczby studentów:
Cel przedmiotu:
Celem przedmiotu jest zapoznanie studentów z różnymi modelami kolorowanie grafów, ich zastosowaniami w szeroko rozumianym przemyśle oraz metodami, zarówno aproksymacyjnymi jak i dokładnymi, kolorowania grafów zgodnie z omówionymi modelami.
Treści kształcenia:
1. Algorytmy przybliżone klasycznego kolorowania grafów: zachłanny, LargestFirst, SmalestLast, DSatur, ConnectedSequential, GreedyIndependentSet, MasimumSetCover. 2. Algorytm dokładny działający w oparciu o zasadę włączania-wyłączania. 3. Omawiane modele z wybranymi zastosowaniami: - kolorowanie listowe, - kolorowanie sprawiedliwe (równościowe), - sumacyjne, - cyrkularne (podziału zasobów w procesach cyklicznych), - zwarte kolorowanie krawędzi (szeregowanie zadań), - harmoniczne (radiolokalizacji), - kolorowanie grafów w trybie on-line (przydział pamięci procesora).   Program projektu - Implementacja i badanie własności omawianych algorytmów.  
Metody oceny:
Z egzaminu można zdobyć 60 punktów, z projektu 40. Warunkiem koniecznym zaliczenia jest zdobycie co najmniej 30 pkt z egzaminu oraz co najmniej 20 z projektu. 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.
Egzamin:
Literatura:
- Optymalizacja dyskretna – modele i metody kolorowania grafów. Pod redakcją Marka Kubale. - Graph Coloring Problems, Tommy R. Jensen, Bjarne Toft.  
Witryna www przedmiotu:
Uwagi:

Efekty uczenia się