FOI Nastava - Odabrana poglavlja teorije algoritama i teorije složenosti

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Odabrana poglavlja teorije algoritama i teorije složenosti

Selected Topics in Algorithms and Complexity
2021/2022

7 ECTSa

Doktorski studij Informacijske znanosti 1.1 (PDDSIZ)

Katedra za teorijske i primijenjene osnove informacijskih znanosti

1. semestar

Osnovne informacijemdi-information-variant

Izvođači nastavemdi-account-group

Nastavni plan i programmdi-clipboard-text-outline

Model praćenjamdi-human-male-board

Ispitni rokovimdi-clipboard-check-outline

Rasporedmdi-calendar-clock

Konzultacijemdi-account-voice

Izvođenje kolegija

Studij	Studijski program	Semestar	Obavezan
Doktorski studij Informacijske znanosti 1.1 (PDDSIZ)		1	izborni

Cilj kolegija

Ovaj kolegij daje moderne rezultate iz dva povezana područja: teorije algoritama i teorije složenosti. Njime će student dobiti uvid u moderna stremljenja u razvoju progamiranja, izrade algoritama i teorije složenosti. Cilj je upoznati studente s modernim trendovima u teoirji algoritama, ali isto tako s čvrstim teorijskim temeljima, okvirom, ograničenjima i mogućnostima koje teorija nameće.

Preduvjeti

Kolegij nema definirane preduvjete

Norma kolegija

Predavanja

30 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Lovrenčić Alen	Nositelj

Sadržaj predavanja

Uvod
Pojam algoritma. Pregled standardnih metoda izgradnje algoritama. Ocjene složenosti algoritama.
Teorija automata
Konačni automat i regularni izrazi. Potisni automati i kontekstno slobodne gramatike. Turingovi strojevi
Aproksimacijski algoritmi
Heuristike (genetički algoritmi, sumulated anealling), aproksimacijske sheme. Primjeri aproksimacijksih algoritama (TSP, k-rez, problem ranca)
Teorija složenosti algoritama
Turingov stroj. Izračunljivost. Klase kompleksnosti: P i NP. NP-potpuni problemi. NP i coNP. Klasifikacija unutar klase P. Algoritmi iznad NP.
Heuristike
Genetski algoritmi. Algoritmi temeljeni na metodi simuliranog hlađenja.
Randomizirani algoritmi
Metode izgradnje randomiziranih algoritama (temeljene na teoriji igara, vjerojatnosna metoda, algebarske tehnike), Randomizirane strukture podataka, randomizirano linearno programiranje, randomizirani algoritmi na grafovima.
Paralelni algoritmi
Principi izgradnje paralelnih algoritama. Paralelizam temeljen na prosljeđivanju poruka. Paralelizam temeljen na dijeljenju memorije. Primjeri paralelnih algoritama (matrični algoritmi, sortiranje, algoritmi na grafovima, dinamičko programiranje)

Sadržaj seminara/vježbi

Ishodi učenja kolegija

Ishodi učenja programa

Osnovna literatura

S. Dagupta, C. Papadimitriu, U. Vazirani: Algorithms, Mc Graw-Hill ,2008
M. Mozgovoy: Algorithms, Languages, Automata, and Compilers, Jones and Bartlett, 2010.
C.H. Papadimitriou: Computational Complexity, Addison-Welsey, 1994.
V.V. Vazirani: Approximation Algorithms, Springer-Verlag, 2003.
R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge Universitay Press, 1995.
A. Grama, A. Gupta, G. Karypis, V. Kumar: Introduction to Parallel Computing, 2nd ed., Addison-Wesley, 2003.
L. Fortnow: The Golden Ticket, P, NP, and the Search for the Impossible, Princenton University, 2013

Dopunska literatura

R.M. Garey, D.S. Johnson: Computers and Intractability: A Guoide to the Theory of NP-Completeness, Freemanand, Co., 1979.
R. Sedgewick: Algorithms in C++, parts 1-4. Addison-Wesley, 1998.
R. Sedgewick: Algorithms in C++, part 5. Addison-Wesley, 2002.
A. Aho, J. Hopcroft, J.D. Ullman: Data Structures and Algorithms, Addison-Wesley, 1987
Atallah, M.J. ed.: Algorithms and Theory of Complexity Handbook, CRC Press, 1999.
D.E. Knuth: The Art of Computer Programming: Fundamental Algorithms, Addison-Wesley, 1968.
D.E. Knuth: The Art of Computer Programming: Seminumerical Algorithms, Addison-Wesley, 1969.
D.E. Knuth: The Art of Computer Programming:Searching and Sorting, Addison-Wesley, 1973.
E. Horowitz, S. Sahni: Fundamental of Computer Algorithms, Computer Science Press, 1978.
D.E. Knuth: Selected Papers on Analysis of Algorithms, CSLI, 2000.
J. van Leeuwen (ed.): Handbook of Theoretical computer Science, Volume A: Algorithms and Complexity, MIT Press, 1990
J. van Leeuwen (ed.): Handbook of Theoretical computer Science, Volume B: Formal Models and Semnatics, MIT Press, 1990
L.A. Hemaspaandra, M. Ogihara: The Complexity Theory Companion, Springer-Verlag, 2002.

Slični kolegiji

RWTH Aachen, http://www-mgi.informatik.rwth-aachen.de/Teaching/KT-WS01/
Universität Trier, http://eccc.uni-trier.de/eccc-local/ECCC-LectureNotes/IntroComplTh/cc-pre.html
Princeton University, http://www.cs.princeton.edu/courses/archive/spring03/cs423/
Berkeley, http://www.cs.berkeley.edu/~luca/cs278/
M.I.T., http://theory.lcs.mit.edu/~madhu/ST02/
London School of Economics and Political Science, http://www.maths.lse.ac.uk/Courses/ma314.html
San Diego State University, http://www.eli.sdsu.edu/courses/spring95/cs662/

Redoviti studenti

Izvanredni studenti

U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.