Grafowe Modelowanie Systemów

Oceny (po egzaminie 14.02.2009)

Wiadomości:
  • [20.02.09] OSTATNIA (regulaminowa) możliwość oddania projektów to 23.02.2009, godz. 10:00, pok. EA 209.
  • [18.02.09] Przypominam, że sesja poprawkowa kończy się 20 lutego. W poniedziałek, 23 lutego, następuje zwrot protokołów do dziekanatu, więc będzie to ostatni dzień oddawania zaległych projektów (godzinę podam później, lecz nie gwarantuję, że będzie to po południu). Po tym terminie możliwe będzie uzyskanie zaliczenia z mojej strony pod warunkiem, że student spowoduje, że otrzymam odpowiedni protokół z dziekanatu. Najbliższy termin oddania projektów to 20 luty, godz. 14:00 (do godz. 14:30) oraz godz. 17:00 (aż do ostatniego studenta...).
  • [14.02.09] Najbliższe terminy konsultacji to środa (18 luty), godz. 18:00 lub piątek (20 luty), godz. 17:00. Programy można wysyłać do końca sesji poprawkowej. Dodatkowych terminów egzaminu już nie będzie.
  • [10.02.09] Zgodnie z harmonogramem sesji poprawkowej, egzamin poprawkowy odbędzie się dnia 14.02.2009 (sobota) o godz. 8:15 w sali EA AUD.2. Można tego dnia po egzaminie oddać zaległe projekty.
  • [10.02.09] Konsultacje w środę, 11.02, o godz. 18:00 odbędą się - zapraszam do zaliczania projetków.
  • [30.01.09] Uwaga dot. egzaminu: termin 31 stycznia nie jest obowiązkowy. Osoba posiadająca w sumie co najmniej 100 punktów z projektów i wcześniejszego terminu kolokwium ma zaliczony przedmiot i ocena końcowa jest obliczana zgodnie z zasadami podanymi poniżej.
  • [21.01.09] Istnieje możliwość zaliczania programów projektowych dnia 27.01.2009 o godz. 18:15 w sali 209.
  • [21.01.09] Termin egzaminu: 31.01.2009 (sobota), godz. 8:15 - 10:00, sala NE AUD.2
  • [08.01.09] Termin egzaminu został wstępnie ustalony na dzień 31.01.2009. Propozycja terminu poprawkowego: 15.02.2009.

Zasady zaliczenia

Projekty:

  • algorytm Bellmana-Forda (kod: ALGBF), 20 pkt., dane testowe
  • algorytm Dijkstry (kod: SHPATH), 40 pkt., dane testowe
  • cykle Eulera (kod: EULERGMS), 20 pkt., dane testowe
  • drzewa spinające (alg. Prima lub Kruskala) (kod: SPIN_PL), 20 pkt., dane testowe
  • 6-kolorowanie grafów planarnych (kod: PL6COL), 20 pkt., dane testowe
  • drzewa spinające o minimalnej średnicy (kod: MDST), 40 pkt., małe stesty oraz pełne dane testowe
  • algorytm Johnsona (kod: JHNSN), 40 pkt. (wymaga wcześniejszej implementacji alg. Bellmana-Forda oraz Dijkstry (bez użycia kopców))
  • problem 'stabilnych małżeństw', 20 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.
  • zadanie alternatywne: TSHPATH, 20 pkt. Jest to zadanie zbudowane na podobnych danych testowych jak w przypadku SHPATH, lecz znacznie 'łatwiejszym' limitem czasowym. Zadanie nie jest objęte konkursje na najszybciej działające programy. Nie można otrzymać puntków za oba zadania SHPATH i TSHPATH (tzn. osoby, które mają zaliczone te dwa programy otrzymują 40 punktów).
  • przeszukiwanie grafu metodami DFS oraz BFS (kod: TDBFS), 30 pkt.

Wykłady:

  • 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]
  • 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:

  • Studia wieczorowe/zaoczne (13.06.2006) [ps (gr.1) ps (gr.2)]]
  • Studia wieczorowe/zaoczne (15.09.2006) [ps]
  • Studia wieczorowe/zaoczne (7.11.2006) [pdf]
  • Studia wieczorowe/zaoczne (2.02.2005) [ps]
  • Studia wieczorowe/zaoczne termin 1[pdf]
  • Studia wieczorowe/zaoczne poprawka[pdf]
  • Studia wieczorowe/zaoczne termin 1[pdf]
  • Studia wieczorowe/zaoczne termin 1 (29.11.2008) [pdf]