Ostatnia aktualizacja:
September 25. 2017 20:32:33
Aktualności / News > Dydaktyka / Teaching > Historia / History > Algorytmy Współczesnej Kombinatoryki, lato 12/13

Algorytmy Współczesnej Kombinatoryki, lato 12/13


Prezentacje projektów


Każda grupa powinna przygotować krótką (ok. 10 minut) prezentację na temat swego projektu:
  • prezentacja problemu
  • bardzo ogólna idea algorytmu (i wskazanie techniki konstruowania algorytmów, z której Państwo korzystają)
  • wyniki testów
Tutaj można zarezerwować sobie czas prezentacji. Bardzo proszę o przyjście i obejrzenie prezentacji swoich koleżanek i kolegów.

Tematy

Zapisy na tematy

Przykładowe grafy do testów można znaleźć tu i tu.

Zasady oceniania

Przedmiot składa się z dwóch części - ćwiczeń i projektu.

Ćwiczenia

Zaliczenie ćwiczeń odbywa się na podstawie prezentacji (przygotowywanej w parach). Studenci powinni przygotować ok. 45-minutową prezentację techniki konstruowania algorytmów. Prezentacja powinna zawierać podstawy teoretyczne oraz co najmniej kilka przykładów zastosowania tej techniki w konstrukcji algorytmów (wraz z analizą złożoności).

Za prezentację można uzyskać 30 pkt. Warunkiem zaliczenia ćwiczeń jest uzyskanie co najmniej 15 pkt. za prezentację. Obecność na ćwiczeniach jest obowiązkowa.

Harmonogram ćwiczeń

Nr Data Temat 1 Temat 2
1 26.02.2013 zajęcia organizacyjne

5.03.2013


12.03.2013


19.03.2013


26.03.2013


2.04.2013 dzień wolny
2 9.04.2013 Branching (rozgałęzianie)
Measure and Conquer
3 16.04.2013 Szybkie mnożenie macierzy Właczanie-wyłączanie
4 23.04.2013 Programowanie dynamiczne Dziel i zwyciężaj

30.04.2013


7.05.2013

5 14.05.2013 Branch and Recharge
Branch and bound
6 21.05.2013 Kernelizacja Szerokość drzewowa i programowanie dynamiczne
7 28.05.2013 Iterative compression
Local search, algorytmy Las Vegas i Monte Carlo
8 4.06.2013

8
11.06.2013 Algorytmiczny LLL

Projekt

Studenci przygotowują projekty w zespołach dwuosobowych. Tematy projektów są ściśle powiązane z tematami prezentacji.

Z projektu można uzyskać 70 punktów.
Na projekt składa się:

1. Dokumentacja wstępna (15 punktów)
- opis problemu
- sformalizowanie problemu
- omówienie stosowanych technik konstrukcji algorytmów
- projekt algorytmów (pseudokod)
- analiza algorytmów (złożoność, poprawność)
- literatura

2. Aplikacja + przykłady do testów (30 punktów)
Podczas kontroli postępu prac należy pokazać aktualny stan aplikacji. Ma on wpływ na ocenę za aplikację.
Oprócz działającej aplikacji należy przestawić:
- opis zmian w stosunku do dokumentacji wstępnej (jeśli zmienił się algorytm, należy przedstawić jego analizę!)
- krótką instrukcję użytkownika
- zapisane przykłady do testów, gotowe do uruchomienia w aplikacji
Przykłady powinny być zróżnicowane i ilustrować zachowanie algorytmu w różnych przypadkach.
Ocenie podlega m.in. łatwość testowania aplikacji!

3. Raport z testów (15 punktów)
- opis przeprowadzonych testów (wydajność, jakość aproksymacji itp.)
- wyniki testów (w porównaniu z szacunkami)
- wnioski

4. Prezentacja problemu i aplikacji (10 punktów)
- na ostatnich zajęciach prezentacja projektu (będzie ogłoszone)

Uwagi:
- Warunkiem zaliczenia projektu jest uzyskanie ponad 35 punktów.
- Zaliczenie projektu jest obowiązkowe do zaliczenia przedmiotu (ocena z projektu stanowi 0.7 oceny z przedmiotu)
- Harmonogram może ulec niewielkim zmianom.
- Warunkiem koniecznym do uzyskania punktów za raport z testów i prezentację jest oddanie aplikacji.
- Każdy rozpoczęty tydzień spóźnienia z dowolną częścią to -10 pkt z ogólnej liczby punktów za projekt.
- W szczególnych usprawiedliwionych przypadkach spóźnienia mogą być rozpatrywane indywidualnie (na korzyść studenta)
- Spotkania mają charakter konsultacyjny - proszę uprzedzić mailem, że chcą Państwo przyjść.

Harmonogram projektu:
12/14.03 - podział na grupy i przydzielone tematy
16/18.04 - dokumentacja wstępna
7/9.05 - kontrola postępu prac nad aplikacją
21/23.05 - kontrola postępu prac nad aplikacją
13.06 - oddanie prac, prezentacje (jak nie starczy czasu, prezentacje będą dokończone w innym terminie)

Literatura

  1. Fedor V. Fomin, Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010

  2. Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006

  3. Vijay V. Vazirani, Algorytmy aproksymacyjne, WNT 2005

  4. Ton Kloks, Treewidth. Computations and Approximations. Springer, 1994

  5. Michael R. Garey, David S. Johnson. Computers and intractability. BTL 1979