1. komponenta

Vrsta nastave	Ukupno
Predavanja	45

* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)

CILJ KOLEGIJA: Oblikovanje efikasnih algoritama i precizna analiza njihove složenosti u teoriji i praksi. Neki teško rješivi problemi i efikasni približni algoritmi za njihovo rješavanje.

NASTAVNI SADRŽAJI:
1. Uvod. Pojam složenosti algoritma. Asimptotsko ponašanje funkcija. Red veličine. Zapis složenosti algoritma.
2. Rekurzivni algoritmi. Rekurzivne jednadžbe. Primjeri rekurzivnih algoritama i njihova složenost.
3. Sortiranje. Jednostavni postupci za sortiranje uspoređivanjem. Složeniji algoritmi: Quicksort, Heapsort, Mergesort. Praktična analiza složenosti opisanih algoritama. Donja ograda za složenost sortiranja uspoređivanjem. Prosječna složenost Quicksort-a.
4. Konstrukcija efikasnih algoritama. Problemi najkraćih puteva, razapinjućih stabala i komponenti povezanosti. Efikasna realizacija putem strukture disjunktnih skupova. Brza Fourierova transformacija i neke primjene.
5. Teško rješivi problemi. Intuitivni pojam klasa P i NP. Neki NP-potpuni i NP-teški problemi. Problemi ruksaka i trgovačkog putnika. Konstrukcija algoritama za egzaktno i približno rješenje ovih problema.

1. Oblikovanje i analiza algoritama, Saša Singer, skripta PMF - Matematičkog odsjeka (u pripremi), 2005.
2. Algorithmics, G. Brassard, P. Bratley, Prentice-Hall, 1988.
3. Introduction to Algorithms, 2nd edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, MIT Press, 2001.
4. Algorithms - Design Techniques and Analysis, M. H. Alsuwaiyel, World Scientific, 1999.
5. The Art of Computer Programming, Vols. 1, 2, 3, D. E. Knuth, Addison-Wesley, 1997.
6. Algorithms and Complexity, H. S. Wilf, Prentice-Hall, 1986.

Obavezni predmet - Redovni Studij - Računarstvo i matematika