Algoritmi i njihova složenost

Prema tekućem nastavnom planu, nastava iz predmeta Algoritmi i njihova složenost se odvija u toku VII semestra kao obavezan predmet na smeru Mikroračunarska eletronika.

Cilj predmeta je obezbediti opšti uvid u fundamentalne aspekte teorije algoritama i njihove složenosti, uključujući primere algoritama iz različitih oblasti elektrotehnike i računarstva.

Specifikacija predmeta

Oznaka predmeta: EM402
Broj ESPB: 6
Broj časova aktivne nastave nedeljno: 3+3

Nastavni kadar

Nastavnik:
  • dr Staniša Dautović, docent
kancelarija: Blok F, 1.sprat, kabinet 116; telefon: 485-2582; email: dautovic(at)uns(tačka)ac(tačka)rs

Način polaganja ispita

Materijal za predavanja:

  • L. Novak - Algoritmi i njihova složenost - skripte, FTN Novi Sad, 2007,  Srpski jezik

  • S. Dautović - Zbirka rešenih problema (određivanje vremenske složenosti algoritama) - skripte, FTN Novi Sad, 2007,  Srpski jezik

  • C.H. Papadimitriou - Computational Complexity, Addison Wesley Longman, 1995, Engleski jezik

  • T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein - Introduction to Algorithms, Third Edition, The MIT Press, 1999, Engleski jezik


Dodatne informacije

Teme (Ispitna pitanja) na kursu Algoritmi i njihova složenost 2018/19

  1.  Kritični računarski resursi (vreme, prostor, broj procesora (npr. u slučaju paralelnih algoritama), broj razmenjenih poruka (npr. u slučaju distribuiranih algoritama), potrošnja energije itd.) i načini njihovog merenja

  2. Asimptotske notacije veliko O, Θ, Ω, malo ω, o i njihove osnovne osobine

  3. Problem, instanca problema, rešenje problema

  4. Odlučiva, evaluaciona i konstruktivna formulacija optimizacionih problema

  5. Deterministička Tjuringova mašina i njene različite varijante (sa jednom i više traka, sa ulazom i izlazom itd.).

  6. Definicija algoritma preko Tjuringove mašine

  7. Formalni jezici, pojam rekurzivnog i rekurzivno-nabrojivog jezika, prihvatanje (accepting) reči jezika na TM i odlučivanje (deciding) jezika, rekurzivne funkcije

  8. Izračunavanje funkcija nad stringovima na TM

  9. Univerzalna Tjuringova mašina

  10. Halting problem i neodlučivost jezika

  11. Pojam klase kompleksnosti (complexity class)

  12. Vremenska složenost algoritma, klase TIME(f(n)) i NTIME(f(n))

  13. Određivanje vremenske složenosti iterativnih i rekurzivnih algoritama, Master teorema

  14. Tjuringove mašine sa ulazom i izlazom, prostorna kompleksnost algoritma, klase SPACE(f(n)) i NSPACE(f(n)), klase L i NL, problem 2SAT

  15. Dokaz korektnosti algoritma

  16. Pojam redukcije i kompletnosti (completeness) u okvirima neke klase kompleksnosti

  17. Klasa problema P, važni predstavnici problema iz ove klase (npr. MAX FLOW, REACHABILITY, SORTING, različiti grafovski i numerički problemi itd.)

  18. Klasa P-kompletnih problema, problem CIRCUIT VALUE

  19. Nedeterministička Tjuringova mašina, problem SAT

  20. Klasa problema NP

  21. Klasa NP-kompletnih problema, važni predstavnici problema iz ove klase (3SAT, MIS, CLIQUE, VERTEX COVER, EDGE DOMINATING SET, SET COVER, TSP, HAMILTONIAN PATH&CYCLE, 3-COLORING itd.)

  22. Ideja dokaza Kukove teoreme

  23. Rešavači problema SAT (SAT-solvers)

  24. Redukovani uređeni binarni dijagrami odlučivanja (ROBDDs)

  25. Kompleksnost Bulovih kola

  26. coNP i coNP-complete problemi, problem VALIDITY (TAUTOLOGY)

  27. Odnos klasa P, NP, coNP, NP-kompletnih i coNP-kompletnih problema

  28. Polinomijalna hijerarhija, klasa PH, klase ∏i+1P, ∑i+1P, Δi+1P

  29. Polinomijalni prostor, klasa PSPACE, problem QSAT

  30. Aproksimativni algoritmi, mere aproksimabilnosti, klase problema APX, PTAS, FPTAS

  31. Parametrizovani algoritmi

  32. Randomizovani algoritmi, klasa RP

  33. Postupci opšte namene u kombinatornoj optimizaciji (exhaustive search, backtracking, branch and bound)

  34. Matematičko programiranje

  35. Dinamičko programiranje

  36. Operacije nad polinomima, transformacije nad polinomijalnim funkcijama, algoritmi za DFT i FFT

  37. Paralelni algoritmi, klasa NC, Amdalov zakon, iregularni paralelizam

  38. On-line (dinamički) grafovi i algoritmi

  39. Distribuirani i lokalizovani algoritmi

  40. Komunikacijska kompleksnost algoritma

  41. Kolmogorovljeva (informaciona) kompleksnost algoritma

  42. Deskriptivna kompleksnost, Faginova teorema i definicija klase NP

  43. Energetska kompleksnost algoritma, klasa DENER(E(n))

  44. Kompleksnost nad poljem realnih brojeva, BSS mašina