Izračunljivost in računska zahtevnost

2022/2023
Program:
Interdisciplinarni univerzitetni študijski program 1. stopnje Računalništvo in matematika
Letnik:
2 letnik
Semester:
prvi
Vrsta:
obvezni
ECTS:
6
Jezik:
slovenski
Nosilci predmeta:

Borut Robič

Ure na teden – 1. semester:
Predavanja
3
Seminar
0
Vaje
0
Laboratorij
2
Vsebina

Predavanja:
Uvod: Algoritem intuitivno.
Zgodovina: Kriza v osnovah matematike 20. stoletja. Reševanje iz krize. Formalni sistemi. Hilbertov program. Godlova izreka.
Uvod v izračunljivost: Kaj je algoritem in računanje? Računski modeli. Church-Turingova teza. Turingov stroj in različice. Nedeterminizem.
Univerzalni TS. Model RAM in splošno namenski računalniki. Izrek o rekurziji, rekurzivno definiranje in računanje.
Neizračunljivost. Jezik in množica. Odločitveni problemi. Neizračunljivi problemi obstajajo. Metode za dokazovanje neizračunljivosti (diagonalizacija, prevedbe, Riceov izrek) Primeri neizr. problemov in praktične posledice na raznih področjih.(Osnovno o relat. izračunljivosti in hieararhijah.)

Avtomati, gramatike, jeziki: Končni avtomat, regularna gramatika, izraz in jezik. Skladovni avtomat, kontekstno neodvisna gramatika in jezik. Linearno omejeni avtomat, kontekstno odvisna gramatika in jezik. Primeri in uporaba.
Uvod v računsko zahtevnost: Časovna, prostorska, in druge zahtevnosti. Lahki in težki problemi. Razreda P, NP, EXP in drugi. NP-polnost/težkost in njeno dokazovanje. Primeri in uporaba.
Obvladovanje težkih problemov: Osnovno o verjetnostnem, aproksimativnem in paralelnem računanju. Osnovno o interaktivnem dokazovanju. Primeri v praksi.
Novejši pristopi: Osnovno o kvantnem računanju.
Vaje: Na vajah bodo študentje utrjevali snov, podano na predavanjih. Snov bodo uporabili za reševanje praktičnih problemov, pri čemer bo poudarek na samostojnem delu ob pomoči asistentov. Implementirali bodo več manjših programov (kot domače naloge) in obsežnejše programe (kot seminarske naloge), ki jih bodo zagovarjali na vajah.
Domače in seminarske naloge:
Namen domačih nalog je ponuditi študentom priložnost za samostojno reševanje zahtevnejših nalog s področja izračunljivost in računske zahtevnosti, ki poleg domiselnosti zahtevajo nekoliko temeljitejši teoretični premislek. Oboje presega možnosti pri vajah in navaja k samostojnemu delu.

Temeljni literatura in viri

B. Robič: The Foundations of Computability Theory, Springer, 2014 (to appear)
S.Arora, B.Barak Computational Complexity: A modern approach, Cambridge Univ Press (2009)
Dodatna literatura:
M. Sipser: Introduction to the Theory of Computation, Course Technology (2006)
B. Robič: Aproksimacijski algoritmi, Založba FE in FRI, 2. izd. (2009)

Cilji in kompetence

Cilj predmeta je dvojen: 1) študenta opremiti s sodobnim znanjem s področja teoretičnega računalništva in 2) študenta usposobiti, da bo lahko to znanje uspešno uporabljal pri reševanju problemov v praksi

Predvideni študijski rezultati

Znanje in razumevanje:
Poznavanje osnovnih principov delovanja sistemov za upravljanje s podatkovnimi bazami. Poznavanje tehnik načrtovanja podatkovnih baz. Poznavanje formalnih jezikov za poizvedovanje po podatkovnih bazah. Poznavanje prednosti uporabe podatkovnih baz.
Uporaba:
Uporaba v sklopu razvoja informacijskih sistemov in druge programske opreme, ki zahteva obvladovanje večjih količin podatkov.
Refleksija:
Zmožnost izboljševanja pristopov modeliranja, predstavitve in hranjenja podatkov v okviru praktičnih problemov.
Prenosljive spretnosti - niso vezane le na en
predmet:
Spretnosti uporabe domače in tuje literature in drugih virov, uporaba IKT, uporaba sistematičnih pristopov, analiza potreb, identifikacija in reševanje problemov, delo v timih.

Metode poučevanja in učenja

Predavanja, domače naloge, seminarski način dela pri vajah. Poudarek je na sprotnem študiju in samostojnem delu pri vajah, seminarskih in domačih nalogah.

Načini ocenjevanja

Oceno sestavljata dva dela: prvi (50%) je za sprotno delo,
drugi (50%) pa za ustni in pisni izpit
Obveznosti predmeta so uspešno opravljene le, če sta oba dela pozitivna. V sprotno delo sodijo vaje in seminarske naloge.

Reference nosilca

ROBIČ, Borut. The foundations of computability theory. Heidelberg [etc.]: Springer, cop. 2015. XX, 331 str., ilustr. ISBN 978-3-662-44807-6. ISBN 978-3-662-44808-3, doi: 10.1007/978-3-662-44808-3. [COBISS-SI-ID 1536557251]
BEZENŠEK, Mitja, ROBIČ, Borut. A survey of parallel and distributed algorithms for the Steiner tree problem. International journal of parallel programming, ISSN 0885-7458. [Print ed.], 2014, vol. 42, no. 2, str. 287-319. [COBISS-SI-ID 9891924]
MIHELIČ, Jurij, MAHJOUB, Amine, RAPINE, Christophe, ROBIČ, Borut. Two-stage flexible-choice problems under uncertainty. European journal of operational research, ISSN 0377-2217. [Print ed.], Mar. 2010, vol. 201, no. 2, str. 399-403, ilustr. [COBISS-SI-ID 7087444]
MIHELIČ, Jurij, ROBIČ, Borut. Flexible-attribute problems. Computational optimization and applications, ISSN 0926-6003. [Print ed.], 2010, vol. 47, no. 3, str. 553-566, ilustr. [COBISS-SI-ID 7087700]
TROBEC, Roman, ŠTERK, Marjan, ROBIČ, Borut. Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Computers & Structures, ISSN 0045-7949. [Print ed.], 2009, vol. 87, no. 1/2, str. 81-90. [COBISS-SI-ID 21895463]