Algorytmy Grafowe 2007/08

Wiadomości:

• [16.02.2008] Wyniki z drugiego kolokwium. Reklamacje 19.02.2008, godz. 11:30-12:00 lub 14:00.
• [10.02.2008] Termin kolokwium poprawkowego: 15.02.2008 (piątek), godz. 14:00-15:30, sala EA 01. Najbliższa możliwość zaliczania seminarium i konsultacji: 15.02.2008, godz. 13:15-14:00.
• [25.01.2008] W wynikach ogłoszonych 23 stycznia istniały usterki wynikające z błędów podczas sprawdzania. Lista została uaktualniona oraz rozszerzona o punkty z innych źródeł.
• [23.01.2008] Wyniki z pierwszego kolokwium. Zapraszam na reklamacje jutro, godz. 15:00.
• [17.01.2008] Kolokwium odbędzie się dnia 23.01.2008, godz. 17:00-18:30 w EA AUD 1.
• [21.12.2007] Poniżej umieściłem propozycje zadań, które można opracować dla systemu spoj.
• [9.10.2007] Kolejność numeracji referatów jest z założenia kolejnością w jakiej będą prezentowane na zajęciach. Wysyłając maila z rezerwacją tematu prosze podawać w mailu NUMER ALBUMU (nie umieszczam nazwisk w internecie) oraz TERMIN (1 lub 2). W każdym terminie możliwe jest przydzielenie co najwyżej 13 tematów. Pierwsze pięć tematów, to tematy łatwiejsze ze względu na dostępność polskojęzycznej literatury. Kolejne 5 tematów to zagadnienia, które nie są merytorycznie trudniejsze, ale wymagają pracy na angielskich tekstach. Pozostałe tematy są merytorycznie trudniejsze. Podział na poziomy trudności jest bardzo subietkywny - można w trudnym temacie poszukać łatwego elementu, a w każdym z tematów dotrzeć do zaawansowanych zagadnień. Podział więc należy rozumieć tak, że osoby chcące zrobić coś ambitniejszego, dowiedzieć się więcej i dostać wiecej niż 100 pkt. powinny zwrócić uwagę na te ostatnie tematy, gdyż w tych przypadkach (ponownie, w moim odczuciu) jest większy ku temu potencjał.
• [9.10.2007] Uwaga natury technicznej: na komputerze, który bedzie do dyspozycji jest zainstalowany pakiet Office 2000. Aby uniknąć kłopotów należy mieć przy sobie kopię prezentacji w bardziej przenośnym formacie (np. pdf - konwersja ppt --> pdf jest dość łatwa). Najepiej przynieść pliki na dwóch nośnikach - drugi jako kopia zapasowa. Winę za klopoty wynikające z uszkodzonych plikow/nośników ponosi student. Dobrą praktyką będzie wysłanie prezentacji na moje konto pocztowe w przeddzień wystąpienia.
• [9.10.2007] Uwaga: przy tematach 2-osobowych należy określić czy osoba zgłaszająca się wybiera referat czy napisanie raportu. Zmiana w stsunku do tego, co mówiłem na zajęciach: jeśli dwie osoby wybiorą ten sam temat, to jedna z nich wygłasza referat, natomiast druga pisze 10-20 stronicowy raport i zalicza na podstawie rozmowy podczas konsultacji. Obie osoby opracowują temat niezależnie, wybierając różne algorytmy w ramach tego samego tematu.

Propozycje zadań dodatkowych (ułożenie zadania w sytemie spoj)

• Sprawdzanie, czy dany graf jest grafem przedziałowym.
  Wejście: graf prosty.
  Wyjście: odpowiedź "tak" lub "nie" zależnie od tego czy graf jest grafem przedziałowym.
• Algorytm testowania planarności grafu.
  Wejście: graf prosty.
  Wyjście: odpowiedź "tak" lub "nie" zależnie od tego czy graf jest grafem planarnym.
• Sprawdzanie, czy dany graf jest grafem cięciwowym. (zajęte)
  Wejście: graf prosty.
  Wyjście: odpowiedź "tak" lub "nie" zależnie od tego czy graf jest grafem cięciwowym.

Seminaria (przeczytaj podane powyżej uwagi przed wyborem tematu!!)

1. Tytuł: Algorytmy grafowe w trybie on-line
   • Literatura: M.Kubale (red.), Optymalizacja dyskretna, Modele i metody kolorowania grafów, WNT, Warszawa 2002.
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 97346
   • Termin 2 (godz. 13:15): 102152
2. Tytuł: Zwarte kolorowanie grafów (Interval edge-coloring of graphs).
   • Literatura: M.Kubale red. Optymalizacja dyskretna, Modele i metody kolorowania grafów, WNT, Warszawa 2002.
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 102173
   • Termin 2 (godz. 13:15): 102111
3. Tytuł: Problemy szukania optymalnych drzew Steinera (Steiner tree).
   • Definicja: Dany jest graf obciążony G oraz pozdbiór X jego wierzchołków. Należy znaleźć taki podgraf H grafu G, który jest drzewem (nazywany drzewem Steinera) aby każdy element X należał do H.
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 102179
   • Termin 2 (godz. 13:15): 97018
4. Tytuł: Problem multiprzekroju w grafach.
   • Definicja: Dla danego obciążonego grafu G dany jest zbiór par jego wierzchołków. Problem polega na znalezieniu takiego zbioru krawędzi, aby suma wag była minimana, oraz aby po usunięciu tych krawędzi z grafu nie było składowej spójności zawierającej oba wierzchołki z danej pary.
   • Literatura: V.V. Vazirani, Algorytmy aproksymacyjne, WNT W-wa 2005 (do wglądu w pok. 209)
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 103057
   • Termin 2 (godz. 13:15): 102095
5. Tytuł: Rozcyklający zbiór wierzchołków.
   • Definicja: Dla danego grafu G znajdź taki podzbiór X jego wierzchołków, aby graf G-X nie zawierał cykli. Wierzchołki grafu posiadają wagi i pytamy o zbiór X o najmniejszej sumie wag.
   • Literatura: V.V. Vazirani, Algorytmy aproksymacyjne, WNT W-wa 2005 (do wglądu w pok. 209)
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 102049
   • Termin 2 (godz. 13:15): 102058
6. Tytuł: Przeszukiwanie grafu.
   • Definicja: Dany jest graf G. Dysponujemy pewną liczbą 'strażników' (tutaj strażnik tłumaczony na ang. zwykle jako searcher) . W grafie znajduje się 'uciekinier' (fugitive), który porusza sie dowolnie szybko, lecz nie może odwiedzać wierzchołków zajetych przez strażników. Istnieje szereg odmian tego modelu oraz szereg parametrów obliczeniowych (podstawowy to minimalna liczba strażników potrzebna do znalezienia uciekiniera) (parametr nazywany jako search number of a graph).
   • Liczba osób: 1 lub 2
   • Termin 1 (godz. 12:15): 102143
   • Termin 2 (godz. 13:15): 102188
7. Tytuł: Algorytmy generowania wybranych klas grafów.
   • Liczba osób: 1 lub 2
   • Termin 1 (godz. 12:15): 102207, 102145 (pisemny raport)
   • Termin 2 (godz. 13:15): 97093, 102200 (pisemny raport)
8. Tytuł: Algorytm testowania planarności grafu.
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 102059
   • Termin 2 (godz. 13:15): 102072
9. Tytuł: Algorytmy rysowania grafów.
   • Liczba osób: 1
   • Termin 1 (godz. 12:15): 102024
   • Termin 2 (godz. 13:15): 102154
10. Tytuł: Algorytmy triangulacji (triangulation) grafów.
    • Definicja: Graf jest cięciwowy jeśli każdy cykl o długości co najmniej 4 w grafie posiada krawędź łączącą dwa wierzchołki, które nie są w cyklu sąsiednie. Problem polega na dodaniu do danego grafu G krawędzi w taki sposób, aby powstały graf był był cięciwowy. Problem funkcjonuje w dwóch wersjach: minimal triangulation (rozwiązywany wielomianowo) oraz minimum triangulation (NP-trudny).
    • Liczba osób: 1
    • Termin 1 (godz. 12:15): 102158
    • Termin 2 (godz. 13:15): 102077
11. Tytuł: Izomorfizm grafów (graph isomorphism) - algorytmy.
    • Liczba osób: 1
    • Termin 1 (godz. 12:15): 107186
    • Termin 2 (godz. 13:15): 102166
12. Tytuł: Gry na grafach - złożoność i algorytmy.
    • Literatura: Dobrym miejscem, by zacząć jest artykuł przeglądowy: Playing games with algorithms...
    • Liczba osób: 1 lub 2
    • Termin 1 (godz. 12:15): 102066
    • Termin 2 (godz. 13:15): 102090
13. Tytuł: Wyszukiwanie elementów w częściowych porządkach.
    • Definicja: Dany jest diagram Hassego, który reprezentujemy za pomocą grafu. Jeden z wierzchołków jest wierzchołkem poszukiwanym. W celu jego znalezienia możemy wykonać operację: wybieramy dowolny wierzchołek v i pytamy, czy szukany wierzchołek jest mniejszy lub równy od v. Jesli tak, to kontunuujemy poszukiwanie w podgrafie 'zakorzenionym' w v (tzn. poniżej v). Krok powtarzamy do skutku. Jest to uogólnienie wyszukiwania binarnego w posortowanej tablicy. Celem jest znalezienie strategii, która wykonuje możliwie najmniej powyższych kroków w najgorszym lub średnim przypadku.
    • Słowa kluczowe: cz. porz. = partial order, partially ordered set, poset
    • Liczba osób: 1 lub 2
    • Termin 1 (godz. 12:15): 96990
    • Termin 2 (godz. 13:15): 102120 (referat)
14. Tytuł: Szukanie rozłącznych ścieżek w grafach.
    • Definicja: dana jest para wierzchołków (źródło i ujście) oraz liczba całkowita k. Pytanie brzmi czy istnieje k rozłącznych wierzchołkowo (lub krawędziowo) ścieżek łączących źródło z ujściem. Rozważane są też wersje problemu, gdzie szukamy rozłącznych ścieżek z jednym źródłem i wieloma ujściami (każda ścieżka biegnie od źródła do danego z ujść). Kolejny model zakłada ograniczenia na maksymalną długość ścieżek.
    • Słowa kluczowe: all-pairs shortest pahts, pairwise disjoint paths.
    • Liczba osób: 1 lub 2
    • Termin 1 (godz. 12:15): 102142
    • Termin 2 (godz. 13:15): 96994
15. Tytuł: Algorytmy dynamiczne dla grafów (dynamic graph algorithms).
    • Literatura: można zacząć od: tego miejsca
    • Liczba osób: 1 lub 2
    • Termin 1 (godz. 12:15): wolny
    • Termin 2 (godz. 13:15): wolny

Wykłady

• Zasady zaliczenia [pdf]
• Wprowadzenie [pdf]
• Najkrótsze ścieżki z jednym źródłem [pdf]
• Najkrótsze ścieżki pomiędzy wszystkimi parami wierzchołków [pdf]
• Problem komiwojażera - algorytm optymalny [pdf]
• Heurystyki dla symetrycznego problemu komiwojażera [pdf]
• Drzewa spinające, problem komiwojażera dla grafów z nierównością trójkąta [pdf]
• Drzewa spinające o minimalnej średnicy i minimalnym stopniu [pdf]
• Cykle Eulera [pdf]
• Przepływy [pdf]
• Diagramy Voronoi [pdf]
• Skojarzenia [pdf]
• Kolorowanie grafów [pdf]
• Nieklasyczne modele kolorowania grafów [pdf]

Kolokwia z minionych lat:

• Termin 1 (2008) [ps]
• Termin 1 (2007) [ps]
• Termin 1 (2006) [ps]
• Termin 2 (2006) [ps]
• Termin 2 (15.02.2006) [ps]
• Termin 2 (3.02.2006) [ps]
• Termin 1 (16.01.2006), gr. 1[ps]
• Termin 1 (16.01.2006), gr. 2[ps]
• Termin 1 (7.12.2005), gr. 1[ps]
• Termin 1 (7.12.2005), gr. 2[ps]
• Termin 1, gr. 1[pdf]
• Termin 1, gr. 2[pdf]
• Termin 2, gr. 1[pdf]
• Termin 2, gr. 2[pdf]
• Studia wieczorowe (13.06.2006) [ps (gr.1) ps (gr.2)]]
• Studia wieczorowe (15.09.2006) [ps]
• Studia wieczorowe (2.02.2005) [ps]
• Studia wieczorowe, termin 1[pdf]
• Studia wieczorowe, poprawka[pdf]
• Studia wieczorowe, termin 1[pdf]