Ime predmeta: Teoretične osnove računalništva II
Skrajšano ime: TOR II

Študijski program: Računalništvo in informatika (dodiplomski)
Tip predmeta: Obvezni predmet
Letnik: 1.

Število kreditnih točk (ECTS): 6
Trajanje: 15 tednov (spomladanski semester)
Študijsko leto: 2019/20

Predavatelj: doc. dr. Branko Kavšek
Asistent: doc. dr. Branko Kavšek


Kratek opis vsebine:

Končni avtomati in regularni izrazi:

  • model računanja in končni avtomat – DKA in NKA
  • Abeceda, jezik, regularni izraz/jezik
  • odnos med DKA, NKA in regularnimi izrazi
  • uporaba KA pri reševanju problemov
  • lema o napihovanju, neregularni jeziki

Slovnice, kontekstno (ne)odvisni jeziki in skladovni stroji:

  • slovnica, drevo izpeljave, prilastkovna slovnica
  • kontekstno odvisni in neodvisni jeziki, skladovni stroji
  • normalne oblike slovnic: po Griebach-ovi, po Chomskem (CNF)
  • prevedba slovnic v CNF
  • CYK algoritem
  • lema o napihovanju za KNJ
  • operacije nad jeziki (unije, preseki itd.)

Turingovi stroji in njihovi jeziki:

  • pojem Turingovega stroja in različne inačice, RAM
  • Church-Turingova teza
  • rekurzivno preštevni jeziki, hierarhija po Chomskem
  • nerešljivi in neodločljivi problemi, problem zaustavitve, Rice-ov izrek in Postov korespondenčni problem

Uvod v teorijo zahtevnosti:

  • P in NP – odnos med njima
  • prevajanje problemov, NP polnost
  • NP polni problemi

Cilji in kompetence:

Cilji:

  • Študent se spozna z osnovnimi formalnimi modeli računanja in preko njih spozna pojme kot so izračunljivost, odločljivost, P in NP.
  • Razvije občutek za sodelovanje in pridobi zaupanje za uporabo pridobljenega strokovnega znanja.
  • Študentu je omogočeno poglobljeno razumevanje računalništva in informatike.

Splošne kompetence:

  • Abstraktno in analitično mišljenje.
  • Zmožnost definiranja in formalizacije problema.

Predmetno-specifične kompetence:

  • Zmožnost tvorjenja modelov za reševanje problemov.
  • Zmožnost dokazovanja trditev.

Obveznosti študentov:

  • Pisni izpit ob koncu predmeta (lahko se nadomesti z dvema kolokvijema - 1. po končanem 7-8 tednu izvedbe, 2. ob koncu predmeta)
  • Velike domače naloge (na vajah)
  • Kvizi - sprotno preverjanje znanja (po vsakem predavanju)
  • Ustni izpit

Način ocenjevanja:

Aktivnost Del ocene Pogoj
Pisni izpit / 2 kolokvija 50% Doseženih več kot polovica točk.
Izjemoma manj, a ne manj kot 40%
(velja za posamezni kolokvij).
Domače naloge
 35% Oddano v roku = vse točke
Zamuda do 1 teden = polovica točk
Zamuda več kot 1 teden = nič točk
(onemogočena oddaja).
Kvizi
(po sklopu predavanj,
 skupaj 5 kvizov)		 15% Rešeno v roku = vse točke.
Zamuda = nič točk (onemogočeno reševanje).
Ustni izpit 0% Na željo študenta/ke (višanje ocene).
Skupaj: 100% Izpolnjeni vsi pogoji pri posameznih aktivnostih.


Literatura:

  1. John C. Martin, Introduction to Languages and the Theory of Computation (fourth edition), McGraw-Hill, 2010.
  2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation (third edition), Addison-Wesley, 2006. (:-))
  3. John E. Hopcroft, Jeffrey D. Ullman (Boštjan Vilfan): Uvod v teorijo avtomatov, jezikov in izračunov, Fakulteta za elektrotehniko, 1986, Ljubljana.
Zadnja sprememba: sreda, 12. februar 2020, 09.28