Učebné materiály

• skriptá k predmetu
• Dodatok - aktualizované 11.12.2019
• Študijné poznámky

Čo a z ktorého študijného materiálu (skriptá, Dodatok, Studijné poznámky) treba vedieť na skúške, je popísané v Dodatku.

Link týždňa

• http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm Minesweeper is NP-complete! :)
• http://www.cs.umd.edu/~gasarch/papers/poll.pdf Anketa od L. A. Hemaspaandra o tom, čo si múdri ľudia myslia o budúcnosti P=?NP problému.
• http://www.scottaaronson.com/talks/anthropic.html Prednáška Scotta Aaronsona nielen o výpočtovej zložitosti, upútavka: "If suicide really were a solution to life's problems, then one could exploit that fact to solve NP-complete problems in polynomial time!"
• http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP#Polynomial-time_algorithms Popis deterministického algoritmu, ktorý v polynomiálnom čase rieši NP-úplný problém. Samozrejme, iba ak P=NP. :)
• http://qwiki.stanford.edu/wiki/Complexity_Zoo Complexity ZOO - zložitostné triedy od výmyslu sveta... "There are now 495 classes and counting!"