Fakultet tehničkih nauka

Predmet: Teorija algoritama (17.IFE211)

Matične organizacione jedinice predmeta: Katedra za primenjene računarske nauke
Osnovne informacije:
 
Kategorija Teorijsko-metodološki
Uža naučna oblast Primenjene računarske nauke i informatika
ESPB 5

Obrazovni cilj predmeta je razvoj algoritamske kulture savremenog inženjera, kao važnog činioca opšte inženjerske kulture. Konkretni obrazovni ciljevi su osposobljavanje studenata za a) razumevanje osnovnih pojmova iz oblasti teorije algoritama i računarske složenosti, b) određivanje algoritamske težine problema, c) odabir algoritamskih postupaka koji su adekvatni težini rešavanog problema i d) primenu odgovarajućih algoritama u rešavanju problema od interesa.

Osnovna stečena znanja su razumevanje i određivanje algoritamske težine problema i kompleksnosti algoritma, kao i sposobnost za samostalno algoritamsko rešavanje inženjerskih problema od interesa.

Uvod u teoriju algoritama i računarske složenosti. Određivanje algoritamske težine problema. Redukcije među problemima. Asimptotska notacija, vremenska i prostorna kompleksnost. Osnovne klase kompleksnosti. Vrste algoritama. Pohlepni algoritmi, algoritmi tipa podeli-pa-reši, pretraga u dubinu i širinu, dinamičko programiranje, algoritmi ograničenog grananja. Randomizovani i probabilistički algoritmi. Parametrizovani i aproksimativni algoritmi. Algoritamske heuristike i meta-heuristike. Matematičko programiranje. Algoritmi za rešavanje problema sa jednim i više ciljeva optimizacije. Paralelni i distribuirani algoritmi.

Predavanja. Auditorne i računarske vežbe. Konsultacije. Na predavanjima se studenti upoznaju sa opštim algoritamskim postupcima, koji su adekvatni rešavanju problema različitih algoritamskih težina. Izlaganja na predavanjima su praćena odgovarajućim primerima na auditornim i računarskim vežbama, koja doprinose razumevanju gradiva. Pored predavanja i vežbi, redovno se održavaju i konsultacije.

Autori Naziv Godina Izdavač Jezik
Christos H. Papadimitriou Computational Complexity 1995 Addison Wesley Longman Engleski
R. Sedgewick, K. Wayne Algorithms (4th Edition) 2011 Pearson Education, Inc. Engleski
Kozen, Dexter, C Theory of computation 2006 Springer Engleski
Zbigniew Michalewicz, David B. Fogel How to Solve It: Modern Heuristics 2010 Springer, 2nd Rev&Ext. edition Engleski
Cormen, T.H. et al. Introduction to Algorithms 2009 MIT Press, Cambridge Engleski
G. Ausiello, P. Crescenzi, V. Kann, Marchetti-sp, Giorgio Gambosi, Alberto M. Spaccamela Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties 1999 Springer Engleski
Predmetna aktivnost Predispitna Obavezna Broj poena
Predmetna aktivnost
Usmeni deo ispita
Predispitna
Ne
Obavezna
Da
Broj poena
30.00
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predmetna aktivnost
Složeni oblici vežbi
Predispitna
Da
Obavezna
Da
Broj poena
30.00
Predmetna aktivnost
Složeni oblici vežbi
Predispitna
Da
Obavezna
Da
Broj poena
20.00
Predmetna aktivnost
Test
Predispitna
Da
Obavezna
Da
Broj poena
10.00
Predavanja
Predavanja
Računarske vežbe
Računarske vežbe
Računarske vežbe