Računska zahtevnost

2022/2023
Program:
Magistrski študijski program 2. stopnje Matematika
Letnik:
1 ali 2 letnik
Semester:
prvi ali drugi
Vrsta:
izbirni
Skupina:
R1
ECTS:
6
Jezik:
slovenski, angleški
Nosilci predmeta:
Ure na teden – 1. ali 2. semester:
Predavanja
2
Seminar
1
Vaje
2
Laboratorij
0
Vsebina

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.

Temeljni literatura in viri

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.

Cilji in kompetence

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

Predvideni študijski rezultati

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.

Metode poučevanja in učenja

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

Načini ocenjevanja

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

Reference nosilca

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]