FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2019/2020
semestar:
Izborni kolegiji

2019/2020

7ECTSa

Doktorski

Poslijediplomski doktorski studij v1.1

Program Obavezan
Doktorski studij PDDS Ne
Izborni kolegij

Odabrana poglavlja teorije algoritama i teorije složenosti npp:45225

Engleski naziv

Chosen chapters from Theory of Algorhytms and Complexity Theory

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.

Nastava

Predavanje
30sati

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)

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 predmeti

  • 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/
Nastavnik Oblik nastave Tjedana Sati tjedno Grupa
Lovrenčić Alen Predavanja doktorski studij 2 15 1
Nema definiranih ispitnih rokova
Nema podataka o rasporedu
Copyright © 2015 FOI Varaždin. All Rights Reserved. Sva prava pridržana.
Povratak na vrh