Predavanja:
- Uvod: splošno o metodah razvoja algoritmov, o analizi algoritmov, o računski zahtevnosti algoritmov in problemov
- Deli in vladaj: opis metode, primeri problemov in algoritmov (glejte primere v točki 12 spodaj)
- Požrešna metoda: opis metode, primeri
- Postopno izboljševanje: opis, primeri
- Dinamično programiranje: opis, primeri
- Sestopanje: opis metode, primeri
- Razveji in omeji: opis metode, primeri
- Linearno programiranje: opis metode, Simpleksni algoritem, primeri
- Izbrane višje podatkovne strukture
- NP-težki računski problemi: spodnja meja časovne zahtevnosti, intuitivno o razredih P, NP in NP-težkih problemih
- Metode reševanja NP-težkih problemov: hevristični algoritmi, aproksimacijski algoritmi, verjetnostni algoritmi, parametrizirani algoritmi, eksaktni eksponentni algoritmi, primeri
- 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.
