mislo

Fakulteta za računalništvo in informatiko · Univerza v Ljubljani

Izračunljivost in računska zahtevnost

Za predmet Izračunljivost in računska zahtevnost še ni zapiskov.

Imaš svoje zapiske? Objavi jih: ceno določiš ti, z naročnino ti ostane cela, DDV se doda kupcu.

Objavi zapiske

Čakaš na zapiske? Prijavi se in povej. Ko jih kdo objavi, dobiš sporočilo.

Želim zapiske

Kaj lahko narediš že danes

Naloži svoje gradivo za predmet Izračunljivost in računska zahtevnost: Mai ga prebere in ti iz njega naredi kartice, kviz in razlago, ko ti kaj ni jasno. Če zapiske kasneje objaviš, jih prodajaš tukaj.

Naloži svoje gradivo

Učni načrt

Podatki so iz učnega načrta, ki ga objavlja Fakulteta za računalništvo in informatiko. Prebrano 7. 9. 2026. Poglej izvirnik

6 kreditnih točk

Obveznosti v urah

  • Predavanja45 ur
  • Vaje30 ur
  • Samostojno delo105 ur

Vsebina

  1. Matematični uvod
  2. Dokazovanje: Pregled osnovnih dokazovalnih tehnik, s poudarkom na tem, kaj študenti poznajo iz Diskretnih struktur.
  3. Predstavitev podatkov, problemov in jezikov: Kako matematično formalizirati računske probleme.
  4. Bijekcije: Pomen bijektivnih preslikav v kontekstu primerjave velikosti množic.
  5. Diagonalizacija: Močno orodje za dokazovanje obstoja neizračunljivih in kompleksnejših problemov.
  6. Uvod v računske modele (avtomati)
  7. 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; 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)
  8. 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.)

Ocenjevanje

prvi (50%) je za sprotno delo, 50 %, drugi (50%) pa za ustni in pisni izpit. 50 %

Literatura

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

Kako deluje

  1. Zapiske kupiš enkrat in ostanejo tvoji.
  2. V aplikaciji iz njih dobiš kartice, kvize in Mai, ki pozna gradivo.
  3. Ceno določi avtor. Prodajalec je Mislo AI, račun dobiš od nas.