Teorija algoritmov

Cilji predmeta

- Predmet seznanja študenta z osnovami teorije algoritmov ter z najpomembnejšimi algoritmi za iskanje in optimizacijo.

Vsebina predmeta

1. Intuitivni pojem algoritma
2. Formalizacije pojma algoritma
2.1. Rekurzivne funkcije
2.2. Turingovi stroji
2.2.1. Izračunljivost po Turingu
2.2.2. Univerzalni Turingov stroj
3. Churcheva teza.
4. Odločljive in polodločljive množice
5. Časovna zahtevnost
5.1. Razred P problemov, težki problemi
5.2. Nedeterministični Turingovi stroji
5.3. Razred NP problemov
5.4. NP-polnost problemov
6. Različni algoritmi urejanja in njihova časovna zahtevnost
7. Iskanje najcenejše poti v grafu
7.1. Dijkstrov algoritem
7.2. Usmerjeno iskanje (algoritem A*)
8. IN/ALI-grafi, rešitveni podgrafi, optimalni rešitveni podgrafi
9. Iskanje rešitvenih podgrafov
9.1. Algoritem AO*
9.2. Algoritem za eksplicitno dane IN/ALI grafe
10. IN/ALI grafi pri projektiranju in vodenju projektov
11. Hipergrafi, hiperpoti
12. Lokalna optimizacija
12.1. Požrešno iskanje
12.2. Simulirano ohlajanje
12.3. Genetski algoritmi

Nosilci predmeta