WZOD
Wybrane Zagadnienia Optymalizacji Dyskretnej
EGZAMIN 4 września g 14 sala 426
Każdy projekt przewidziany jest dla dwuosobowego zespołu
studentów. Projekt powinien składać się z implementacji
komputerowej (20pkt) oraz dokumentacji (20pkt).
Dokumentacja powinna zawierać:
- przedstawienie problemu i opis jego rozwiązania (4pkt),
- analizę poprawności (jakości) i złożoności stworzonego algorytmu (4pkt),
- opis programu dla użytkownika (4pkt),
- opis techniczny programu (4pkt),
- opis przykładowych testów, wnioski (4pkt).
Projekt wstępny zawierający opis problemu i jego rozwiązania należy wysłać do .........., każdy
tydzień spóźnienia -1pkt (max -4 pkt). Cały projekt należy wysłać do ........ i omówić się na
prezentacje, za każdy tydzień spóźnienia -3pkt (max -12).
Sylabus
Program przedmiotu:
- Pojęcia wstępne.
- Maksymalny przepływ w
sieciach, algorytm Edmondsa-Karpa, Diraca.
- Zastosowanie algorytmów
przeszukujących wgłąb i wszerz.
- Generowanie obiektów
kombinatorycznych: permutacji, podzbiorów, podziałów, zbiorów niezależnych
w grafach.
- Zagadnienie kolorowania
grafów: algorytmy dokładne wyznaczania liczby chromatycznej oparte na
generowaniu maksymalnych zbiorów niezależnych, sprawdzanie k-kolorowalności
grafu.
- Problem pakowania.
- Szeregowanie zadań na
jednej maszynie.
- Problem spełnialności
formuły boolowskiej (SAT): wielomianowość 2-SAT, algorytmy rozwiązujące k-SAT,
SAT.
Literatura podstawowa:
[1] T.H. Cormen. C.E. Leiserson, R.L. Rivest, Wprowadzenie do algorytmów, WNT,
1997,1998, 2004.
[2] M.M. Sysło, N. Deo, J.S. Kowalik, Algorytmy optymalizacji dyskretnej, PWN.
[3]
W. Lipski, Kombinatoryka dla programistów, Warszawa, WNT 1989.