RAČUNALNIŠTVO III

Izpitna vprašanja

  1. Lokalna optimizacija
  2. Linearno programiranje in postopek simpleksov
  3. Geometrijska interpretacija LP
  4. Dualnost v LP
  5. Polinomski algoritmi za LP
  6. Matrične igre
  7. Problem razvoza in LP
  8. Drevesne rešitve in dualnost pri problemu razvoza
  9. Izreki o celih rešitvah
  10. Konigov izrek, dvojno stohastične matrike
  11. Problem maksimalnega pretoka in nezasičene poti
  12. Maksimalni pretoki in Mengerjev izrek
  13. Pokritja in prirejanja v dvodelnih grafih
  14. Pokritja in prirejanja v splošnih grafih
  15. Kvadratično programiranje in optimizacija portfelja
  16. Modeli računanja, časovna zahtevnost
  17. RAM
  18. Turingov stroj, Churcheva teza
  19. Turingov stroj, razpoznavanje jezika, izračunljivost funkcij
  20. Nedeterministični TS
  21. Razreda P in NP, polinomska prevedba
  22. NP-polni problemi, Cookov izrek, pomembnejši zgledi
  23. Odločitveni in optimizacijski problemi
  24. Razred co-NP
  25. NP-težki problemi
  26. Aproksimacijski algoritmi
  27. Christofidesov algoritem
  28. Aproksimacijska shema in problem 01-nahrbtnika
  29. Verjetnostni algoritmi, groba delitev, zgledi
  30. Primeri verjetnostnih algoritmov: množenje matrik, popolno prirejanje, praštevila
  31. Kriptografija
  32. RSA in DES
  33. Kombinatorična predstavitev vložitve grafa v ravnino
  34. Konveksno risanje grafov v ravnini
  35. Vzporedni algoritmi in NC
  36. Osnovni vzporedni algoritmi na grafih (povezanost, tranzitivno zaprtje, najkrajše poti)