- English
Sadržaj predmeta
Algoritamske tehnike
- Šifra:
- 14470
- Kratica:
- ALGTEHN
- Visoko učilište:
- Fakultet strojarstva i brodogradnje
- ECTS bodovi:
- 4.0
- Opterećenje:
- 5(V) + 10(V) + 30(P)
- Nositelji:
-
prof. dr. sc. Andrej Jokić
- Izvođači:
-
prof. dr. sc. Andrej Jokić (V, P)
- Opis predmeta:
- Ciljevi predmeta: Osnovni cilj ovog kolegija je upoznati studente sa osnovama modernih algoritamskih tehnika. Dan je uvod u osnove teorije algoritama, kasifikacija problema i pregled najvažnijih algoritamskih rješenja. Kroz niz odabranih tema naglasak je stavljen i na razumjevanje algoritamskih metoda za pojedine klase teških inženjerskih problema. Uvjeti za upis predmeta i ulazne kompetencije koje su potrebne za predmet: Nema ih Obaveze studenata: Redoviti dolazak na predavanja i vježbe. Konzultacije prema potrebi. Ocjenjivanje i vrednovanje rada studenata tijekom nastave i na završnom ispitu: 30 % ocjena seminara i vježbi 30 % pismeni ispit / kolokviji 40 % usmeni ispit Načini praćenja kvalitete koji osiguravaju stjecanje izlaznih znanja, vještina i kompetencija: Seminari i domaće zadaće prate se preko Scriptrunner sustava: http: //sr4.fsb.hr i/ili http: //scriptrunner.carnet.hr Nakon uspješno savladanog kolegija student će moći (ishodi učenja): Analizirati, izračunati i prikazati u standardnom obliku (Onotacija) efikasnost/kompleksnost niza standardnih algoritama (algoritmi za sortiranje, pretraživanje grafova, skup optimizacijski algoritama) Prezentirati algoritamska rješenja za sortiranje (u obliku pseudokoda) i to za sortiranje umetanjem, sortiranje spajanjem, sortiranje brojanjem Prezentirati strukturu podataka hrpe (eng. heap) te algoritam za sortiranje na hrpama Prezentirati strukturu podataka stabla binarnog traženja (BST) te algoritme za traženje i sortiranje nad ovim strukturama Definirati funkcije za haširanje podataka i prezentirati algoritamska rješenja za izbjegavanje kolizija u haštablicama Prezentirati i na računalu implementirati algoritam širinskog pretraživanja grafa Prezentirati i na računalu implementirati algoritam dubinskog pretraživanja grafa Prezentirati i na računalu implementirati algoritme traženja najkraćeg puta na grafu Prepoznati probleme koji se mogu riješiti korištenjem metoda dinamičkog programiranja, te kreirati algoritamska rješenja ovom tehnikom Razlikovati pojmove P, NP, NPteško i NPpotpuno, definirati karakteristike ovih klasa problema i njihovo značenje Razlikovati klase optimizacijskih problema i definirati one optimizacijske probleme za koje postoje polinomni algoritmi Predavanja 1. Ciljevi kolegija; znacaj algoritama u racunarstvu i inzenjerstvu 2. Vrijeme izvršavnja, velikaO notacija, analiza programa 3. Probabilisticka analiza i randomizirani algoritmi 4. Sortiranje 5. Strukture podataka 6. Algoritmi za traženje 7. Algoritmi za grafove 8. Pohlepni algoritmi 9. Računalna geometrija (presjeci, konveksne ljuske, najbliže točke) 10. Kompleksnost (P i NPpotpuna klasa) 11. Dinamičko programiranje 12. Optimiranje i algoritamska rješenja I: teski i lagani problemi, kombinatorijsko optimiranje 13. Optimiranje i algoritamska rjesenja I: od linearnog do semidefinitnog programiranja, SOS dekompozicije 14. Distribuirano računanje i algoritmi 15. Konsenzus i distribuirano optimiranje Vježbe 1. Uvod u algoritamske tehnike 2. Primjeri analiza programa i O notacija 3. Primjeri randomiziranah algoritma 4. Primjeri iz sortiranja 5. Primjeri struktura podataka 6. Primjeri iz algoritama za traženje 7. Primjeri iz algoritmi za grafove 8. Primjeri pohlepnih algoritma 9. Primjeri iz racunalne geometrije (presjeci, konveksne ljuske, najbliže točke) 10. Primjeri P i NPpotpunih klasa 11. Primjeri iz dinamičkog programianja 12. Primjeri iz optimizacije I 13. Primjeri iz optimizacije II 14. Primjeri distribuiranih algoritama 15. Primjeri iz distribuiranog optimiranja
- Jezici izvođenja nastave:
-
Hrvatski
- Obavezna literatura:
-
1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein Introduction to Algorithms, MIT Press 3 edition (September 15, 2009)
2. S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani Algorithms, 2006
- Preporučena literatura:
-
3. B. Vocking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheidelar, H. Vollmer, D. Wagrer Algorithms Unplugged, Springer 2011
4. S.Boyd, L. Vandenberghe, Convex optimization, http //www.stanford.edu/~boyd/cvxbook/
- Predmet u nastavnom programu:
-
Šifra studija Naziv studija Razina studija Semestar izvođenja Obavezni/Izborni 16 Inženjersko modeliranje i računalne simulacije prijediplomski 5 izborni 20 Brodostrojarski prijediplomski 5 izborni 21 Industrijsko inženjerstvo i menadžment prijediplomski 5 izborni 22 Inženjerstvo materijala prijediplomski 5 izborni 23 Mehatronika i robotika prijediplomski 5 izborni 151 Dizajn medicinskih konstrukcija prijediplomski 5 izborni 153 Konstruiranje i razvoj proizvoda prijediplomski 5 izborni 154 Mehanizmi i roboti prijediplomski 5 izborni 155 Motori i vozila prijediplomski 5 izborni 171 Energetika prijediplomski 5 izborni 172 Procesna tehnika prijediplomski 5 izborni 173 Termotehnika prijediplomski 5 izborni 181 Automatika u proizvodnji prijediplomski 5 izborni 182 Osiguranje kvalitete prijediplomski 5 izborni 183 Obradni sustavi prijediplomski 5 izborni 184 Preradba i montaža prijediplomski 5 izborni 185 Zavarene konstrukcije prijediplomski 5 izborni 1137 Računalno inženjerstvo prijediplomski 5 izborni 20 Brodostrojarski prijediplomski 7 izborni 22 Inženjerstvo materijala prijediplomski 7 izborni 23 Mehatronika i robotika prijediplomski 7 izborni 151 Dizajn medicinskih konstrukcija prijediplomski 7 izborni 153 Konstruiranje i razvoj proizvoda prijediplomski 7 izborni 154 Mehanizmi i roboti prijediplomski 7 izborni 155 Motori i vozila prijediplomski 7 izborni 171 Energetika prijediplomski 7 izborni 172 Procesna tehnika prijediplomski 7 izborni 173 Termotehnika prijediplomski 7 izborni * predmet se ne predaje u tom semestru
Legenda
- P - Predavanja
- V - Vježbe