Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Oblikovanje i analiza algoritama

Šifra: 92979
ECTS: 5.0
Nositelji: doc. dr. sc. Goranka Nogo
Engleski jezik:

1,0,0

Nastava se odvija na hrvatskom jeziku u svim svojim elementima, a stranim studentima koji su pridruženi mješovitoj grupi nudi se mogućnost savladavanja predmeta pomoću dodatnih izravnih konzultacija s nastavnikom i asistentima na engleskom jeziku. Pri tome, nastavnik stranog studenta upućuje na odgovarajuću literaturu na engleskom jeziku te mu osigurava mogućnost polaganja predmeta na engleskom jeziku.
Opterećenje:

1. komponenta

Vrsta nastaveUkupno
Predavanja 45
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
Opis predmeta:
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.
Literatura:
  1. Saša Singer: Oblikovanje i analiza algoritama
  2. G. Brassard, P. Bratley: Algorithmics
  3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2nd edition
  4. M. H. Alsuwaiyel: Algorithms - Design Techniques and Analysis
  5. D. E. Knuth: The Art of Computer Programming, Vols. 1, 2, 3
  6. H. S. Wilf: Algorithms and Complexity
1. semestar
Obavezni predmet - Redovni Studij - Računarstvo i matematika
Termini konzultacija:
  • doc. dr. sc. Goranka Nogo:

    Ponedjeljak, 10-12

    Četvrtak, 13-14

    Lokacija: 228

SADRŽAJ

Link na stranicu kolegija: https://web.math.pmf.unizg.hr/nastava/oaa/


Obavijesti