Ostatnia aktualizacja:
April 19. 2024 11:17:03

1. 26.02 - spotkanie organizacyjne
2. 05.03 - wybór grup i tematów
3. 26.03 - dokumentacja wstępna
4. 14.05 - kontrola postępu prac
5. 28.05 - aplikacja i raport z testów
6. 04.06 - prezentacja

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

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

2. Aplikacja + przykłady do testów (17 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 (9 punktów)
- opis przeprowadzonych testów (wydajność, jakość aproksymacji itp.)

- wyniki testów (w porównaniu z szacunkami)

- wnioski

4. Prezentacja problemu i aplikacji (5 punktów)

- na ostatnich zajęciach prezentacja projektu

Uwagi:
- Warunkiem zaliczenia projektu jest uzyskanie ponad 20 punktów.
- Zaliczenie projektu jest obowiązkowe do zaliczenia przedmiotu (ocena z projektu stanowi 0.4 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 -5 pkt z ogólnej liczby punktów za projekt.
- W szczególnych usprawiedliwionych przypadkach spóźnienia mogą być rozpatrywane indywidualnie (na korzyść studenta)
- Ostatecznym terminem oddania dowolnej części projektu jest 06.06. Po tym terminie student otrzymuje 0 punktów za każdą nieoddaną część.

- Zajęcia nie mają wyznaczonego w planie terminu. Na prezentację lub oddanie poszczególnych części należy umówić się mailem. Pozostałe spotkania mają charakter konsultacyjny - na nie także umawiamy się mailem.

Podane artykuły są propozycjami i można wzorować się na innych lub wymyślić własne algorytmy :).

1. L(2,1)-kolorowanie drzew
• Chang G.J., Kuo D.: The L(2, 1)-labeling problem on graphs. SIAM Journal Discrete Mathematics, 9, 309–316 (1996)
• Hasunuma T., Ishii T., Ono H., Uno Y.: A linear time algorithm for L(2,1)-labeling of trees, Lecture Notes in Computer Science 5757, Algorithms - ESA 2009, 17th Annual European Symposium, Proceedings, Copenhagen, Denmark, pp. 35--46 (2009)
2. Kolorowanie grafów euklidesowych
• Graf A., Stumpf M., Weissenfels G.: On Coloring Unit Disk Graphs, Algorithmica, 20, pp. 277-293 (1994)
3. Problem przydziału kanałów częstotliwości
• Kral D., An exact algorithm for the channel assignment problem, Discrete Applied Mathematics - Structural decompositions, width parameters and graph labelings (DAS 5) vol 145 issue 2 (2005)
4. 4-L(2,1)-kolorowanie grafu
• Havet, F., Klazar, M., Kratochvil, J., Kratsch, D., Liedloff, M.: Exact Algorithms for L(2,1)-Labeling od Graphs. Algorithmica DOI 10.1007/s00453-009-9302-7
5. 3-kolorowanie grafu
• Beigel R., Eppstein D.: 3-Coloring in time O(1,3446^n): a n-MIS algorithm. 36th IEEE Symposium on Foundations of Computer Science, pp. 444-453 (1995)
6. Kolorowanie grafu w czasie 2^n
• Koivisto M.: An O*(2^n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer , FOCS pp. 583-590 (2006)
7. Równoległe algorytmy dla kolorowania grafów (należy zaimplementować algorytm równolegle!)
• Goldberg A., Plotkin S.. Parallel (Delta+1)-coloring of constant-degree graphs, Information Processing Letters, vol. 25 issue 4 pp. 241-245 (1987)
8. Maksymalne kolorowanie grafu
• Pemmaraju S.V., Raman R.: Approximation Algorithms for the Max-Coloring Problem, Lecture Notes in Computer Science, vol. 3580/2005 pp. 1064-1075 (2005)
9. Maksymalne kolorowanie krawędziowe grafu
• Feng W., Zhang L., Qu W., Wang H.: Approximation algorithm for maximum edge coloring problem. Theoretical Computer Science, vol. 410 issue 11 (2009)
10. Max-edge-coloring
• Bourgeois N., Lucarelli G., Milis I., Paschos V.Th.: Approximaring the max-edge-coloring problem. Theoretical Computer Science, vol. 411 issues 34-36, pp. 3055-3067 (2010)
  
11. Kolorowanie grafów Euklidesowych z ograniczeniem na odległość.
• Fiala J., Fishkin A., Fomin F.: On distance contrained labeling of disk graphs. Theoretical Computer Science, vol. 326, issue 1-3 (2004) 
12. Sprawiedliwe kolorowanie grafów.
• Kirstead H., Kostochka A., Mydlarz M., Szemeredi E.: A fast algorithm for equitable coloring. Combinatorica, vol. 30 no. 2, pp. 217-224 (2010)
13. Heurystyczne algorytmy dla T-kolorowania
• Liu J., Zhong W., Li J.: Multiagent Evolutionary Algorithm for T-coloring Problem. Proceeding SEAL '08. Lecture Notes in Computer Science, vol. 5361, pp. 289-298 (2008)
• Aicha M., Malika B., Habiba D.: Two hybrid ant algorithms for the general T-colouring problem, International Journal of Bio-Inspired Computation, vol. 2, no.5  pp. 353 - 362 (2010)
14. Kolorowanie grafu w wielomianowej pamięci.
    
• Bodleander H., Kratsch D.: An exact algorithm for graph coloring with polynomial memory. Department of Information and Computing Sciences,Utrecht University Technical Report UU-CS-2006-015
  
15. Kolorowanie krawędziowe dwudzielnych mutligrafów.
• Cole R., Ost K., Schirra S.: Edge-Coloring Bipartite Multigraphs in O ( E log D ) Time. Combinatorica vol. 21 no. 1pp. 5-15 (2001)
  
16. Kolorowanie grafów algorytmem mrówkowym
• Costa D., Hertz A.: Ants can colour graphs. Journal of the Operational Research Society, Volume 48, Number 3, (1997) , pp. 295-305
17. Przydział kanałów częstotliwości przez szybką transformację Zeta
• Cygan M, Kowalik Ł.: Channel Assignment via Fast Zeta Transform. arXiv:1103.2275v1
18. L(2,1)-kolorowanie grafu w czasie O*(3.87^n)
    
• Havet, F., Klazar, M., Kratochvil, J., Kratsch, D., Liedloff, M.: Exact Algorithms for L(2,1)-Labeling od Graphs. Algorithmica DOI 10.1007/s00453-009-9302-7
19. Własne propozycje tematów.