CTG
Chromatyczna Teoria Grafów
Egzamin poprawkowy 4.09 (sobota) g 13:30 sala 422A.
Zestaw przygotowawczy do egzaminu/zaliczenia
Przykładowy zestaw zadań na egzamin | inny zestaw
Osoby które chcą przyjść na zaliczenie/ egzamin zerowy 26 stycznia proszę w pisanie się na listę imieniem i nazwiskiem.
Zapisy na termin zerowy http://doodle.com/participation.html?pollId=t6peisk4a4b32ssg
Na wykładzie 19 stycznia będę rozwiązywał przykładowe zadania oraz przeprowadzę plebiscyt na najbardziej niechciany dowód. Zwycięzca zostanie skreślony z listy - wygrało twierdzenie o numerze 2, czyli lemat 11.2.
Na egzaminie/ zaliczeniu będą dwa dowody do napisania do wyboru po jednym z pary.
Program, autorstwa Zbigniewa Lisa i Michała Okulewicza, do edycji grafów do którego można podłączyć swój algorytm kolorujący można ściągnąć z http://beta.mini.pw.edu.pl/~okulewiczm/CTG.zip
We wtorek 13 X autorzy przedstawią jak to zrobić
A tu http://strefamini.kp.nsf.pl/viewtopic.php?t=1914 autorzy przyjmują (podobno) wnioski i zażalenia
Za projekt można otrzymać 40 pkt za egzamin 60pkt. Warunkiem koniecznym zaliczenia przedmiotu jest uzyskanie co najmniej 30pkt z egzaminu i co najmniej 20 pkt z projektu.
Program wykładu: Celem wykładu jest przestawienie różnych modeli i metod kolorowania grafów wraz z zastosowaniami. W szczególności wykład obejmuje:
- Algorytmy dokładne i przybliżone znajdujące pokolorowanie grafu,
- kolorowanie grafów w trybie on-line,
- sprawiedliwe kolorowanie grafów
- sumacyjne kolorowanie grafów,
- kontrastowe kolorowanie grafów,
- harmoniczne kolorowanie grafów,
- cyrkularne kolorowanie grafów,
- zwarte kolorowanie grafów ,
- listowe kolorowanie grafów,
- acykliczne kolorowanie grafów,
- rozgrywane kolorowanie grafów,
- kolorowanie grafów planarnych.
Program projektu - Implementacja i badanie własności omawianych algorytmów.
Przedmioty poprzedzające:
- Matematyka Dyskretna.
- Algorytmy i struktury danych.
Literatura podstawowa:
- - Optymalizacja dyskretna – modele i metody kolorowania
grafów. Pod redakcją Marka Kubale.
Wersja elektorniczna dostępna w bazie ibook przez przeglądarkę ze strony nasze biblioteki (trzeba się zalogować - logowanie nie jest jak do biblioteki lecz tak jak do e-źródeł dostępnych dla użytkowników biblioteki. Tzn login to numer karty bibliotecznej, hasło to samo ale pisane małymi literami) . Wersja angielska na google books
Harmonogram oddawania projektów:
Śr 9XII
8:15 A.K, P.A. P.C
8:30
8:45
9:00 TK TF
9:15 MD MP
9:30 PK, ŁM
9:45 R.M, M.S.
15:15 JR AS
15:30
15:45
Pn 14XII
8:15 PS PZ
8:30 RG AK
8:45 KK PA US
9:00 KP PS
9:15
9:30 MD BM
9:45 MS MP
Śr 16XII
8:15 AP,
8:30
8:45 AM KR
9:00 TH DW
9:15 MK SK
9:30 AT KG
9:45 PM MB
Pn 21XII
8:15
8:30
8:45
9:00
9:15
9:30
9:45 TH DW
Śr 23 XII
8:15
8:30
8:45
9:00
9:15 PF KK
9:30
9:45 KK RW