RAČUNALNIŠTVO III
Izpitna vprašanja
- Lokalna optimizacija
- Linearno programiranje in postopek simpleksov
- Geometrijska interpretacija LP
- Dualnost v LP
- Polinomski algoritmi za LP
- Matrične igre
- Problem razvoza in LP
- Drevesne rešitve in dualnost pri problemu razvoza
- Izreki o celih rešitvah
- Konigov izrek, dvojno stohastične matrike
- Problem maksimalnega pretoka in nezasičene poti
- Maksimalni pretoki in Mengerjev izrek
- Pokritja in prirejanja v dvodelnih grafih
- Pokritja in prirejanja v splošnih grafih
- Kvadratično programiranje in optimizacija portfelja
- Modeli računanja, časovna zahtevnost
- RAM
- Turingov stroj, Churcheva teza
- Turingov stroj, razpoznavanje jezika, izračunljivost funkcij
- Nedeterministični TS
- Razreda P in NP, polinomska prevedba
- NP-polni problemi, Cookov izrek, pomembnejši zgledi
- Odločitveni in optimizacijski problemi
- Razred co-NP
- NP-težki problemi
- Aproksimacijski algoritmi
- Christofidesov algoritem
- Aproksimacijska shema in problem 01-nahrbtnika
- Verjetnostni algoritmi, groba delitev, zgledi
- Primeri verjetnostnih algoritmov: množenje matrik, popolno prirejanje, praštevila
- Kriptografija
- RSA in DES
- Kombinatorična predstavitev vložitve grafa v ravnino
- Konveksno risanje grafov v ravnini
- Vzporedni algoritmi in NC
- Osnovni vzporedni algoritmi na grafih (povezanost, tranzitivno zaprtje, najkrajše poti)