Elméleti számítástudomány,
1. rész
2018 tavasz
- Óra: A
félév első 7 hetében (február 5-től március 21-ig) hétfőn
10.20-12.00-ig (10 perc szünettel) a T606-ban és szerdán
14.15-16.00 (15 perc szünettel) a T605-ben (nem lesz külön
előadás és gyakorlat alkalom, mindegyik órán belül lesz előadás
és feladatmegoldás is)
- Előadó: Csima
Judit, IB136/b, email,
weboldal
- A zh
eredménye itt
megtekinthető A pótzh eredménye itt megtekinthető. Pótpótzh
lesz május 25-én, pénteken 10.15-12.00-ig az
E505-ben, ezt javító céllal is meg lehet írni, aki ezzel
élni szeretne, az legkésőbb május 24. este 10 óráig írjon
nekem emailt (addigra meglesznek a logika pótzh eredményei is
már).
- A zh 40%-tól sikeres (24 pont).
- A tárgy félévi jegye a két rész (logika és ez a rész)
zh-jegyeinek átlaga alapján keletkezik.
- A zh pótzh-n pótolható/javítható, a pótzh a zh után nem
sokkal lesz (a pontos időpontot az érdekeltekkel majd
megbeszéljük)
- Ha még a pótzh után sincsen meg a sikeres zh vagy valaki az
év végén még javítani szeretne, akkor lesz pótpótzh is a
pótlási héten, de itt már a két anyagrész (ez és a matematikai
logika) közül csak az egyikből lehet írni.
- A zh-n könyv, jegyzet nem használható, mindegyik feladat 10
pontot ér, várhatóan hat feladat lesz.
Órai feladatsorok: 1. Turing-gép
2. Turing-gép (2. rész) 3.
Nevezetes nyelvek, Turing-gép kódolása 4.
R, RE, coR, coRE 5. Diagonális módszer,
Rice tétel 6. PCP, Dominó,
felsorolós TG Extra feladatsor az
első 7 előadás anyagához 7. Tár- és
időbonyolultság 8. Tár-idő tétel,
tanú tétel 9. Karp-redukció,
NP-teljesség
Az elhangzott előadások fontosabb témakörei:
címszavakban
Jegyzet
az előadáshoz (9., 10. és 11. fejezet). Megtalált
hibák eddig. Aki talál még benne hibát, kérem jelezze!
Nem biztos, hogy mindig pontosan ezen jegyzet alapján
fogunk haladni, de nagy eltérések nem várhatóak. A számonkérések
anyaga az, ami az órán elhangzik.
Csima Judit, BME VIK SZIT