Grafowe Modelowanie Systemów 2011/12

Oceny

Wiadomości:
[31.01.2012]Egzamin poprawkowy odbędzie się w poniższym terminie. Osoby chcące oddać zaległe projekty proszę o przybycie do pokoju EA 209 o godzinie 12:00 w dniu egzaminu. Istnieje również możliwość oddania projektów w dniu 3 lutego 2012 (piątek) o godzinie 14:30 w EA 209 (w przypadku mojej nieobecności proszę chwilkę poczekać). Będą to ostatnie terminy oddania projektów, które mogę zaproponować przed wysłaniem ocen do dziekanatu.
[28.01.2012]Powyżej dostępne są oceny. W przypadku błędów proszę o kontakt (email). Uwaga: osoby, które wyrażają chęć pisania egzaminu poprawkowego proszę o zgłoszenie tego faktu poprzez wysłanie do mnie wiadomości email.
[25.01.2012]Termin egzaminu poprawkowego został wyznaczony na dzień 5 lutego (niedziela) 2012 o godzinie 13:15 w sali NE AUD1L.
[17.01.2012]Egzamin odbędzie się dnia 28.01.2012 w sali EA AUD2 o godz. 14:15. Bezpośrednio po zakończeniu egzaminu można będzie zaliczać część projektową.
[20.11.2011]Zadania podstawowe numer 1 oraz 4 (Algorytm Bellmana-Forda oraz drzewa spinające) oceniane są automatycznie w systemie spox.kaims.pl. W celu otrzymania za te zadania przewidzianej liczby punktów muszą one być zaakceptowane w systemie w momencie ich oddawania na zajęciach. Pozostałe zadania oddajemy na zajęciach prezentując poprawne ich działanie na danych testowych umieszczonych na niniejszej stronie. Dotyczy wszystkich zadań: w przypadku stwierdzenia, że student nie jest zaznajomiony z kodem programu, punkty za zadanie nie są przyznawane.
[20.11.2011]Liczba punktów za poszczególne zadania została podniesiona w związku z brakiem możliwości przyznawania bounsów za czas działania programów.
[11.11.2011]Na stronie spox.kaims.pl dostępne są zadania projektowe w wersji automatycznego oceniania kodu. (Sposób logowania oraz hasło zostały podane na wykładzie.) Prosze o zgłaszanie problemów i usterek w pracy systemu.
[02.10.2011]Zadania projektowe zostały umieszczone. Ich omówienie nastąpi na najbliższym wykładzie. Istnieje możliwość pojawienia się dodatkowych zadań bonusowych w trakcie semestru. Jeśli dostępny będzie system automatycznej weryfikacji rozwiązań, to wówczas obowiązuje wspomniany "konkurs" na najszybsze kody (autorzy trzech najszybszych rozwiązań każdego zadania, z wyjątkiem Zadania 2, otrzymują odpowiednio 15, 10 oraz 5 dodatkowych punktów). Przyznanie tych punktów następuje ostatniego dnia semestru, czyli 17 stycznia 2012, o godz. 23:59.

    Zasady zaliczenia

    Projekty:

    • Podstawowe (zaliczeniowe):
    Zadanie 1:Algorytm Bellmana-Forda, 25 pkt., dane testowe oraz treść zadania
    Zadanie 2:Algorytm Dijkstry, 25 pkt. Nie można otrzymać puntków za to zadanie oraz za Zadanie B1 (tzn. osoby, które mają zaliczone te dwa programy otrzymują 40 punktów). Wymaga implementacji algorytmu Dijkstry `bez kopców', tzn. punkty za zadanie zostaną przyznane jeśli przedstawiony na zaliczenie program implementuje algorytm Dijkstry szukania najkrótszych ścieżek. Można skorzystać z danych testowych do Zadania B1. Treść zadania.
    Zadanie 3:Cykle Eulera, 25 pkt., dane testowe oraz treść zadania
    Zadanie 4:Drzewa spinające (alg. Prima lub Kruskala), 25 pkt., dane testowe oraz treść zadania
    Zadanie 5:6-kolorowanie grafów planarnych, 25 pkt., dane testowe oraz treść zadania
    • Bonusowe:
    Zadanie B1:Algorytm Dijkstry, 45 pkt., dane testowe oraz treść zadania
    Zadanie B2:Problem 'stabilnych małżeństw', 35 pkt. Jest to zadanie bounsowe, które nie było omawiane na wykładzie - algorytm można znaleźć tutaj. Dane testowe. Uwaga: w archiwum z danymi testowymi znajduje się program używany przez spoj to testowania nadesłanych rozwiązań. W komentarzu w pliku judge.c znajduje się opis jego użycia w celu samodzielnego testowania. Treść zadania.

    Uwaga: w przypadku problemów z przetłumaczeniem zadań podanych w języku angielskim proszę o kontakt.

    Wykłady:

    • Wprowadzenie [pdf]
    • Najkrótsze ścieżki z jednym źródłem [pdf]
    • Materiał dodatkowy: 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]
    • Cykle Eulera [pdf]
    • Drzewa spinające o minimalnej średnicy i minimalnym stopniu [pdf]
    • Skojarzenia [pdf]
    • Przepływy [pdf]
    • Kolorowanie grafów [pdf]

    Przykładowe kolokwia z minionych lat:

    • 11.02.2011 [pdf]
    • 30.01.2011 [pdf]
    • 29.11.2008 [pdf]
    • 07.11.2006 [pdf]
    • 15.09.2006 [pdf]
    • 13.06.2006 [grupa 1: pdf + grupa 2: pdf]
    • 02.11.2005 [pdf]
    • 21.09.2005 [pdf]
    • 17.06.2005 [pdf]
    • 02.02.2005 [pdf]