Izračunljivost in računska zahtevnost

Matematični uvod
V prvem delu se bomo posvetili matematičnim osnovam, ki so ključne za razumevanje kompleksnosti. Obravnavali bomo:
• Dokazovanje: Pregled osnovnih dokazovalnih tehnik, s poudarkom na tem, kaj študenti poznajo iz Diskretnih struktur.
• Predstavitev podatkov, problemov in jezikov: Kako matematično formalizirati računske probleme.
• Bijekcije: Pomen bijektivnih preslikav v kontekstu primerjave velikosti množic.
• Diagonalizacija: Močno orodje za dokazovanje obstoja neizračunljivih in kompleksnejših problemov.

Uvod v računske modele (avtomati)
Spoznali bomo prve abstraktne modele računanja, ki so temelj za razumevanje kompleksnejših modelov. Vsebina zajema:
• Avtomati in njihove ekvivalence: Deterministični in nedeterministični končni avtomati.
• Regulirane izraze (RI): Povezava med avtomati in formalnimi jeziki.
• Lema o napihovanju: Metoda za dokazovanje, da nekateri jeziki niso regularni.
• Myhill-Nerodejev izrek: Ključni izrek za minimizacijo avtomatov.

Splošni model računanja in neizračunljivost
Ta del bo predstavil univerzalni model računanja in meje, ki jih ima računalništvo. Obravnavali bomo:
• Turingov stroj (TS) in njegove variacije: Univerzalni model računanja in njegova robustnost.
• Univerzalni Turingov stroj: Koncept, ki omogoča simulacijo poljubnega Turingovega stroja.
• Neizračunljivost: Obstoj problemov, za katere ni mogoče najti algoritma.
• Prevedbe: Osnovni mehanizem za dokazovanje, da so problemi med seboj povezani.
• Riceov izrek: Pomemben izrek o neizračunljivosti lastnosti netrivialnih jezikov Turingovih strojev.

Zahtevnost
V zadnjem delu se bomo posvetili klasifikaciji problemov glede na njihovo računsko zahtevnost. Vsebina je:
• Deterministični in nedeterministični razredi: Razred P kot zbirka "lažjih" problemov in razred NP kot zbirka "težjih" problemov.
• P in NP (ter PSPACE): Poglobljena analiza teh razredov, vključno s Savitchovim izrekom, ki povezuje deterministični in nedeterministični prostor.
• Karpove prevedbe: Tehnike za dokazovanje, da je problem NP-poln.
• Cook-Levinov izrek: Temeljni izrek, ki dokazuje, da je problem zadovoljivosti (SAT) NP-poln.
• Primeri NP-polnih problemov: Obravnavali bomo klasične primere, kot so problem zadovoljivosti (SAT), klike, barvanje grafov, problem vsote podniza (subset-sum), Hamiltonov cikel (HC) in drugi.

1. Sipser, M. Introduction to the Theory of Computation. Publisher: PWS Publishing, Year: 2013.
2. Hopcroft, J.E., Motwani, R., Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Publisher: Addison-Wesley, Year: 2007.
3. Barak, B. Introduction to Theoretical Computer Science. Prosto dostopen učbenik (introtcs.org); 2025

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

Študent bo po opravljenem predmetu sposoben:
• Razumeti osnovne modele računanja: Študent bo imel trdno razumevanje delovanja in uporabe končnih avtomatov, regularnih jezikov, izrazov in gramatik.
• Spoznati meje računanja: Študent bo spoznal univerzalni model računanja s Turingovim strojem in razumel koncept izračunljivih ter neizračunljivih problemov.
• Povezati teorijo z realnostjo: Študent bo razumel (Church/Turingovo) tezo o izračunljivosti in zvezo med različnimi razredi jezikov (izračunljivi, izračunljivo preštevni, neizračunljivi) ter problemi (odločljivi, polodločljivi, neodločljivi).
• Prepoznati nerešljive probleme: Študent bo spoznal nekaj klasičnih nerešljivih računskih problemov, kar bo okrepilo njegovo razumevanje omejitev računanja.
• Razumeti vlogo nedeterminizma: Študent bo razumel pomen nedeterminizma v računanju in njegov vpliv na obravnavane računske modele.
• Analizirati zahtevnost problemov: Študent bo razumel časovno in prostorsko zahtevnost računskih problemov ter poznal osnovne razrede zahtevnosti (npr. P, NP, PSPACE).
• Uporabljati napredne koncepte: Študent bo razumel pojme NP-polnosti in NP-težkosti ter se seznanil z metodo dokazovanja NP-polnosti s prevedbo, s poudarkom na problemu zadovoljivosti (SAT) in drugih ključnih NP-polnih problemih.

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.

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.
Ocene: 6-10 pozitivno, 5 negativno (v skladu s Statutom UL)

1. ČIBEJ, Uroš, LI, Aaron, MIKLÓS, István, NASIR, Sohaib, SRIKANTH, Varun. Constructing bounded degree graphs with prescribed degree and neighbor degree sequences. Discrete applied mathematics. 2023
2. ČIBEJ, Uroš, SLIVNIK, Boštjan, ROBIČ, Borut. The complexity of static data replication in data grids. Parallel computing, 2007
3. ČIBEJ, Uroš, ROBIČ, Borut, MIHELIČ, Jurij. Empirical estimation of the halting probabilities. Computability in Europe, 2014
4. ČIBEJ, Uroš, MIHELIČ, Jurij. Improvements to Ullmann’s algorithm for the subgraph isomorphism problem. International journal of pattern recognition and artificial intelligence.
5. ČIBEJ, Uroš, MIHELIČ, Jurij. A polynomial-time algorithm for recognizing subgraph-symmetry-compressible graphs, MATCOS 2019
6. ČIBEJ, Uroš, FÜRST, Luka, MIHELIČ, Jurij. A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms. Symmetry.