Budapesti Műszaki és Gazdaságtudományi Egyetem
Természettudományi Kar		 Tantárgy Adatlap
Tantárgy kód BMETE91MM00
Tantárgy azonosító adatok
1. A tárgy címe Elméleti számítástudomány
2. A tárgy angol címe Theoretical Computer Science
3. Heti óraszámok (ea + gy + lab) és a félévvégi követelmény típusa 3 + 1 + 0 f Kredit 5
4. Ajánlott/kötelező előtanulmányi rend
vagy Tantárgy kód 1 Rövid cím 1 Tantárgy kód 2 Rövid cím 2 Tantárgy kód 3 Rövid cím 3
4.1
4.2
4.3
5. Kizáró tantárgyak
6. A tantárgy felelős tanszéke Algebra Tanszék
7. A tantárgy felelős oktatója Dr. Ferenczi Miklós beosztása egyetemi docens
Akkreditációs adatok
8. Akkreditációra benyújtás időpontja 2008.10.18. Akkreditációs bizottság döntési időpontja 2009.03.30.
Tematika
9. A tantárgy az alábbi témakörök ismeretére épít
Algebra, lineáris algebra.
10. A tantárgy szerepe a képzés céljának megvalósításában (szak, kötelező, kötelezően választható, szabadon választható)
TTK Matematikus és Alkalmazott matematikus MSc képzések kötelezően választható törzstárgya
11. A tárgy részletes tematikája
A logikai programozás és gépi bizonyítás elméleti alapjai. Véges modellek és bonyolultság. Nem-klasszikus logikák a számítástudományban: temporális, dinamikus, program logikák. Rekurzív függvények és a lambda-kalkulus kapcsolata. Boole-algebrák, reláció algebrák és alkalmazásaik. Fontosabb gépmodellek. Bonyolultságelméleti alapfogalmak, nevezetes idő és tárosztályok. NP-teljesség. Randomizált számítások. Algoritmustervezési módszerek. Fejlett adatszerkezetek, amortizációs elemzés. Mintaillesztés szövegben. Adattömörítés.
12. Követelmények, az osztályzat (aláírás) kialakításának módja
szorgalmi
időszakban		 Házi feladok elkészítése. Szóbeli beszámoló vizsga-
időszakban
13. Pótlási lehetőségek
A TVSz előírásai szerint.
14. Konzultációs lehetőségek
Igény szerint
15. Jegyzet, tankönyv, felhasználható irodalom
Carmen, T.H., Leiserson, C.E., Rivest: Algoritmusok, Műszaki Kiadó, 1999.
Rónyai L., Ivanyos G., Szabó R.: Algoritmusok, Typotex, 2001.; Ferenczi M.: Matematikai Logika, Műszaki Kiadó, 2002.
Galton, A.: Logic for Information Technology, Wiley, 1990.
16. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
16.1 Kontakt óra
56
16.2 Félévközi felkészülés órákra
56
16.3 Felkészülés zárthelyire
0
16.4 Zárthelyik megírása
0
16.5 Házi feladat elkészítése
20
16.6 Kijelölt írásos tananyag elsajátítása (beszámoló)
18
16.7 Egyéb elfoglaltság
0
16.8 Vizsgafelkészülés
0
16.9 Összesen
150
17. Ellenőrző adat Kredit * 30
150
A tárgy tematikáját kidolgozta
18. Név beosztás Munkahely (tanszék, kutatóintézet, stb.)
Dr. Rónyai Lajos
egyetemi tanár
Algebra Tanszék
Dr. Friedl Katalin
egyetemi docens
Szit
Dr. Ivanyos Gábor
Sztaki
A tanszékvezető
19. Neve aláírása
Dr. Rónyai Lajos