Elméleti számítástudomány,
1. rész
2020 tavasz
- Óra: A
félév első 7 hetében (február 10-től március 25-ig) hétfőn
12.30-14.00-ig (10 perc szünettel, mindkét rész 40 perces) a
T604-ben és szerdán 14.15-16.00 (10 perc szünettel, az egyik
rész 45 perces, a másik 50 perces) a T606-ban. 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 időpontja az első rész utolsó alkalmának órája, azaz
március 25., szerda, 14-16-ig.
- A zh-n hat feladat lesz, mindegyik 10 pont. Az egyik feladat
egy elméleti kérdés (tanult bizonyítás felidézése), a többi az
órán láttottakhoz hasonló feladat. A zh 40%-tól sikeres.
- A tárgy félévi jegye a két rész (logika és ez a rész)
pontjainak átlaga alapján keletkezik, de meg kell lenni
külön-külön mindkét részből a sikeres zhnak.
- 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ó.
Órai feladatsorok:
1. óra (február 10.) Turing
gép konstrukciók
2. óra: nem volt új feladatsor
3. óra (február 17.) Turing-gépek kódolása,
diagonális nyelv
4. óra (február 19.) R és RE zártságai, coRE
5. óra (február 24.) (diagonális eljárás)
6. óra (február 26.) (Rice-tétel)
7. óra (március 2.) (Kiszámolós TG)
8. óra (március 4.) (PCP, Dominó)
Extra feladatsor (március 4.)
9. órán nem volt új feladatsor
10. óra (március 11.)
11. óra (március 23)
12. óra (március 25.)
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