Preskoči na glavno vsebino
e-učilnica UP FAMNIT
Trenutno uporabljate gostujoči dostop (
Prijavite se
)
Pregledni predmet računalništva in informatike - Teoretične osnove računalništva
Domov
Predmeti
Študijsko leto 2020/2021
Računalništvo in informatika (1. stopnja, 2. stopnja, 3. stopnja)
3.stopnja
1.letnik
Pregledni predmet računalništva in informatike - Teoretične osnove računalništva
13. teden - NP-težkost, NP-polnost in obvladljivost (povzetek)
Posnetek z vaj dne 21.5.2020
Posnetek z vaj dne 21.5.2020
Kliknite na povezavo
Posnetek z vaj dne 21.5.2020
, če želite odpreti vir.
◄ Slika (P, NP, NP-polno, NP-težko, Co-NP, Co-NP-polno, Co-NP-težko) - v angleščini
Skoči na ...
Skoči na ...
Obvestila
Klepetalnica
Splošni podatki o predmetu
Izvedbeni predmetnik
Naloga 01 - DKA
Naloga 02 - NKA
Naloga 03 - NKA --> DKA + minimizacija
Naloga 04 - RI
Naloga 05 - CNF
Naloga 06 - SA
Naloga 07 - CYK
Naloga 08 - TS
Naloga 09 - Zadovoljivost
Namen in načrt predmeta
Uvod v končne avtomate
Deterministični končni avtomati
Na vajah
Kaj sem se naučil/a?
Nedeterministični končni avtomati
Končni avtomati z izhodom
Regularni izrazi
Kaj sem se naučil/a?
Uporabna vrednost regularnih izrazov
Odločitveni algoritmi za regularne jezike
Lastnosti regularnih jezikov
Kaj sem se naučil/a?
Posnetek predavanj z dne 9.3.2020
Rešene naloge (1 in 2)
Rešene naloge (3)
Rešene naloge (4)
Rešene naloge (5a)
Rešene naloge (5b)
Regularni jeziki (povzetek)
JFLAP - Grafično orodja za učenje teorije formalnih jezikov
1. kviz - Regularni jeziki
Posnetek vaj z dne 12.3.2020
Povzetek (regularni jeziki)
Rešene naloge (DKA --> RI) (a)
Rešene naloge (DKA --> RI) (b)
Rešene naloge (minimizacija DKA)
Uvod v kontekstno neodvisne slovnice
Drevesa izpeljave
Normalne oblike KNS - CNF
Kaj sem se naučil/a?
Posnetek predavanj z dne 16.3.2020
Posnetek vaj z dne 19.3.2020
Povzetek (KNS)
Rešene naloge (definicija KNS, izpeljave)
Rešene naloge (dvoumnost KNS)
Rešene naloge (CNF - lažji primer)
Rešene naloge (CNF - zahtevnejši primer)
Posnetek (CNF primer v JFLAP-u) z dne 21.3.2020
Skladovni avtomati (SA)
Ekvivalenca SA in KNS
Več o KNS
Kaj sem se naučil/a?
Posnetek predavanj z dne 23.3.2020
Posnetek vaj z dne 26.3.2020
Rešene naloge ( N(P) --> L(P'') )
Rešene naloge (SA --> KNS)
Rešene naloge (KNS --> SA)
Rešene naloge (RI --> KNS)
Kontekstno neodvisni jeziki (povzetek)
2. kviz - Kontekstno neodvisni jeziki
Primer lanskega 1. kolokvija
Rešene naloge ( L(P) --> N(P') )
Rešene naloge (KNS --> SA) - 2. primer
Rešene naloge (minimizacija DKA) - is spleta
Minimizacija DKA (iz spleta) - dodatno pojasnilo
Rešene (izbrane) naloge iz knjige
Posnetek vaj z dne 2.4.2020
Rešene naloge - lanski kolokvij (1. naloga)
Rešene naloge - lanski kolokvij (2. naloga)
Rešene naloge - lanski kolokvij (3. naloga)
Rešene naloge - lanski kolokvij (4. naloga)
Lema o napihovanju za KNJ
Odločitvene lastnosti in lastnosti zaprtja za KNJ
Kaj sem se naučil/a?
3. kviz - Normalna oblika po Chomskem in CYK algoritem
Posnetek predavanj z dne 6.4.2020
Posnetek vaj z dne 9.4.2020
Rešene naloge (CYK algoritem - 1. primer)
Rešene naloge (CYK algoritem - 2. primer)
Rešene naloge (lema o napihovanju za KNJ)
Rešene naloge (zaprtost KNJ za unijo, stik, Kleenovo ovojnico, homomorfizem)
Turingovi stroji
Razširitve, omejitve in lastnosti TS
Kaj sem se naučil/a?
Posnetek predavanj z dne 15.4.2020
Posnetek vaj z dne 16.4.2020
Rešene naloge (TS - L = 0^n1^n2^n - 1. del)
Rešene naloge (TS - L = 0^n1^n2^n - 2. del)
Rešene naloge (TS - L = 0^n1^n2^n - 3. del)
Rešene naloge (TS - L = ww^R)
Rešene naloge (TS, ki sešteje dve pozitivni celi števili)
Rešene naloge (TS, ki odšteje dve pozitivni celi števili)
Odločljivost
Več o neodločljivih problemih (delno v ANG)
Kaj sem se naučil/a?
4. kviz - Skladovni avtomati in Turingovi stroji
Posnetek predavanj z dne 20.4.2020
Posnetek vaj z dne 23.4.2020
Prevedba L_U --> L_MPCP (pravilno rešena naloga z vaj)
Rešene naloge (pregled)
Rešene naloge (univerzalni TS)
Rešene naloge (L_U --> L_MPCP - pari)
Rešene naloge (L_U --> L_MPCP - simulacija)
Rešene naloge (L_MPCP --> L_PCP)
Rešene naloge (L_PCP --> L_AMB)
Turingovi stroji & odločljivost (povzetek)
Posnetek predavanj z dne 4.5.2020
Rešene naloge (L_U --> L_MPCP)
Rešene naloge (Naloga 07 - CYK)
Posnetek vaj z dne 7.5.2020
Rešene naloge (L_U --> L_ne)
Rešene naloge (KNS v CFG + popravek prevedbe)
P in NP (delno v ANG)
Zadovoljivost (delno v ANG)
Kaj sem se naučil/a?
Posnetek predavanj z dne 11.5.2020
Posnetek vaj z dne 14.5.2020
Pravila logičnega sklepanja v predikatni logiki
Logični izrazi v Wolfram Alpha
Rešene naloge (pretvorba v KNO)
Rešene naloge (pretvorba v 3-KNO)
Nekateri NP-polni problemi (delno v ANG)
Kaj sem se naučil/a?
Obvladljivost, P, NP & zadovoljivost (povzetek)
5. kviz - Univerzalni Turingov stroj, odločljivost, P in NP
Posnetek predavanj z dne 18.5.2020
Razlaga s sliko (P, NP, NP-polno, NP-težko) - v angleščini
Slika (P, NP, NP-polno, NP-težko, Co-NP, Co-NP-polno, Co-NP-težko) - v angleščini
Rešene naloge (skladovni avtomat, KNS)
Rešene naloge (CNF, CYK)
Rešene naloge (KNO, 3-KNO, VC)
Rešene naloge (Turingov stroj, ID)
Rešene naloge (KNO, 3-KNO, VC - 2. primer)
Rešene naloge (regularnost, DKA, KNS)
Rešene naloge (NKA --> DKA)
Primer lanskega 2. kolokvija
Primer lanskega pisnega izpita
Rešene naloge (skladovni avtomat, KNS) ►