Računska zahtevnost

Modeli računanja. Časovna in prostorska zahtevnost. Determinizem in nedeterminizem. Redukcije in polnost.
Fenomen NP-polnosti. Nekaj izbranih NP-polnih problemov. Tehnike dokazovanja NP-polnosti. Struktura razreda NP.
Verjetnostni algoritmi. Vrste verjetnostnih algoritmov. Verjetnostni razredi zahtevnosti. Generatorji psevdonaključnosti.
Aproksimativni algoritmi. Kakovost aproksimacije. Težavnost aproksimacije. Aproksimacijske sheme. Nekaj izbranih aproksimacijskih algorithmov.
Dodatno vsebino lahko predavatelj izbere med naslednjimi temami: Booleova vezja, interaktivni dokazi, kvantno računalništvo, izreki PCP, komunikacijska zahtevnost, parametrična zahtevnost.

S. Arora, B. Barak: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
M. R. Garey, D. S. Johnson: Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman and Co., 2003.
R. Motwani, P. Raghavan: Randomized Algorithms, Cambridge University Press, Cambridge, 1995.
V. V. Vazirani: Approximation algorithms, Springer-Verlag, 2001.

Študent se seznani z osnovnimi modeli računanja, teorijo NP-polnosti, verjetnostnimi algoritmi in z reševanjem težkih problemov z aproksimativnimi algoritmi.

Znanje in razumevanje: Študentje poznajo:
povezave med modeli računanja
teorijo NP-polnosti
pojem verjetnostnega algoritma
pojem aproksimativnega algoritma
Uporaba: Študentje znajo:
analizirati časovno zahtevnost algoritmov
dokazovati NP-polnost
načrtovati verjetnostne algoritme
načrtovati aproksimativne algoritme
Refleksija: Študentje spoznajo:
hierarhijo problemov glede na njihovo časovno zahtevnost
inherentno težke probleme
relaksacijske pristope k reševanju težkih problemov
Prenosljive spretnosti – niso vezane le na en predmet: Analiza težavnosti problemov s pomočjo redukcij med njimi.

predavanja, seminar, vaje, domače naloge, konzultacije in samostojno delo študentov

izpit iz vaj (2 kolokvija ali pisni izpit) or homework
Ustni izpit
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

Sergio Cabello:
CABELLO, Sergio, CARDINAL, Jean, LANGERMAN, Stefan. The clique problem in ray intersection graphs. Discrete & computational geometry, ISSN 0179-5376, 2013, vol. 50, iss. 3, str. 771-783. [COBISS-SI-ID 16728921]
CABELLO, Sergio. Hardness of approximation for crossing number. Discrete & computational geometry, ISSN 0179-5376, 2013, vol. 49, iss. 2, str. 348-358. [COBISS-SI-ID 16340313]
CABELLO, Sergio, LUKŠIČ, Primož. The complexity of obtaining a distance-balanced graph. The Electronic journal of combinatorics, ISSN 1077-8926. [Online ed.], 2011, vol. 18, no. 1, p49 (10 str.). [COBISS-SI-ID 15832153]
Marko Petkovšek:
PETKOVŠEK, Marko, PISANSKI, Tomaž. Izbrana poglavja iz računalništva. Del 1, Izračunljivost in rešljivost, jeziki, NP-polnost, naloge, (Matematični rokopisi, 1.a.). 1986: Društvo matematikov, fizikov in astronomov SRS, Ljubljana. 120 str. [COBISS-SI-ID 519702]
PETKOVŠEK, Marko, WILF, Herbert S., ZEILBERGER, Doron. A=B. Wellesley (Massachusetts): A. K. Peters, cop. 1996. VII, 212 str. ISBN 1-56881-063-6. [COBISS-SI-ID 4085337]
PETKOVŠEK, Marko. Letter graphs and well-quasi-order by induced subgraphs. Discrete Mathematics, ISSN 0012-365X. [Print ed.], 2002, vol. 244, no. 1-3, str. 375-388. [COBISS-SI-ID 11414873]