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
08. teden - Lema o napihovanju za KNS in lastnosti
Odločitvene lastnosti in lastnosti zaprtja za KNJ
Odločitvene lastnosti in lastnosti zaprtja za KNJ
...
Klikni na povezavo
16. Odlocitvene lastnosti in lastnosti zaprtja za KNJ.ppt
za ogled datoteke.
◄ Lema o napihovanju za KNJ
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
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
Posnetek z vaj dne 21.5.2020
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
Kaj sem se naučil/a? ►