Složenost algoritama I019 (2+2+0) - 4 ECTS boda


CILJEVI KOLEGIJA Naučiti studente osnove rješavanja nekih složenih algoritama. Klasificirati NP-teške probleme. Vježbati programiranje (C++, Java) na složenim strukturama i algoritmima.
POTREBNO PREDZNANJE Preddiplomski studij matematike.
SADRŽAJ KOLEGIJA
1. Uvodni dio. Podjela algoritama i metode rješavanja.
2. Dinamičko programiranje. Zadatak trgovačkog putnika, bojenje grafa, Hamiltonovi ciklusi. Pretraživanje stringova: nasilno (brute force), Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp algoritmi. 
3. Cjelobrojno programiranje. Aproksimacijski algoritmi, optimalno punjenje (knapsack), metode grananja i granica (branch & bound).
4. Algoritmi na grafovima. Dohvatljivost i najkraći putevi. Warshall, Floyd, Dijkstra, Prim i Kruskal algoritmi. Obilazak grafova. Snažno povezane komponente. Podudaranje u bi-partitivnim grafovima.
5. NP-teški problemi. Genetički i evolucijski algoritmi.
IZVOĐENJE KOLEGIJA Predavanja i vježbe su obavezne. Kroz predavanja obrađuju se načela djelotvornosti algoritama s obzirom na prostorno- vremenske zahtjeve. Na vježbama studenti trebaju savladati tehnike dinamičkog i cjelobrojnog programiranja. Posebnu pozornost posvetiti algoritmima na grafovima i NP-teškim problemima. Tijekom semestra putem kolokvija i zadaća redovito se provjerava znanje studenata. Nakon odslušanih predavanja i obavljenih vježbi polaže se ispit, koji se sastoji od pismenog i usmenog dijela.



OSNOVNA LITERATURA

  1. E. Horowitz, S. Sahni, S. Rajasekaran, Computer Algorithms, W. H. Freeman, 1997.
  2. R. Sedgewick, Algorithms in C, Addison-Wesley, 1990.

LITERATURA KOJA SE PREPORUČUJE

  1. T.H. Cormen, C.D. Leiserson, R.L. Rivest, Introduction to Algorithms 2Ed, MIT Press, 2005.
  2. U. Manber, Introduction to Algorithms: A Creative Approach. Addison-Wesley, 1989.
  3. D. Salomon, Data Compression: The Complete Reference. Springer, 1998.