• Šifra predmeta:63280
  • Kreditne točke:6
  • Semester: poletni
  • Vsebina

Predavanja:

  1. Uvod: splošno o metodah razvoja algoritmov,  o analizi algoritmov,  o računski zahtevnosti algoritmov in problemov
  2. Deli in vladaj: opis metode, primeri problemov in algoritmov (glejte primere v točki 12 spodaj)
  3. Požrešna metoda: opis metode, primeri
  4. Postopno izboljševanje: opis, primeri
  5. Dinamično programiranje: opis, primeri
  6. Sestopanje: opis metode, primeri
  7. Razveji in omeji: opis metode, primeri
  8. Linearno programiranje: opis metode,  Simpleksni algoritem, primeri
  9. Izbrane višje podatkovne strukture
  10. NP-težki računski problemi: spodnja meja časovne zahtevnosti, intuitivno o razredih P, NP in NP-težkih problemih
  11. Metode reševanja NP-težkih problemov: hevristični algoritmi,  aproksimacijski algoritmi, verjetnostni algoritmi, parametrizirani algoritmi, eksaktni eksponentni algoritmi, primeri
  12. Primeri problemov in algoritmov: napredno urejanje & Heapsort, Quicksort; problem izbiranja & linearni algoritmi; matrično množenje & Strassenov alg.; diskretna Fourierova transormacija & FFT alg.,  iskanje v nizih & Knuth-Morris-Prattov algoritem;  osnovni in zahtevnejši problemi in algoritmi na grafih (iskanje v grafu; topološko urejanje; maksimalni pretok & Ford-Fulkersonov alg.; najkrajše poti &  Bellman-Fordov ter Floyd-Warshallov alg.) ; izbrani problemi iz računske geometrije.

Vaje:  Na vajah bodo študentje utrjevali snov, podano na predavanjih. Snov bodo uporabili za reševanje praktičnih problemov, pri čemer bo   poudarek na samostojnem delu ob pomoči asistentov. Implementirali  bodo več manjših programov (kot domače naloge) in obsežnejše programe (kot seminarske naloge), ki jih bodo zagovarjali na vajah.

  • Študijski programi
  • Porazdelitev ur na semester
45
ur
predavanj
30
ur
laboratorijskih vaj
  • Izvajalci
Nosilec predmeta
Prostor:R2.05
Asistent
Prostor:R2.30-LALG