BMETE91MM00

Nyomtatóbarát változatNyomtatóbarát változat
Tantárgy azonosító adatok
A tárgy címe: 
Elméleti számítástudomány
A tárgy angol címe: 
Theoretical Computer Science
A tárgy rövid címe: 
ElmSzámtud
3
1
0
f
Kredit: 
5
A tantárgy felelős tanszéke: 
Algebra Tanszék
A tantárgy felelős oktatója: 
Dr. Ferenczi Miklós
A tantárgy felelős oktatójának beosztása: 
egyetemi docens
Akkreditációs adatok
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
A tantárgy az alábbi témakörök ismeretére épít: 
Algebra, lineáris algebra.
A tantárgy szerepe a képzés céljának megvalósításában: 
TTK Matematikus és Alkalmazott matematikus MSc képzések kötelezően választható törzstárgya
A tantárgy részletes tematikája magyarul és angolul: 

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.

Követelmények szorgalmi időszakban: 
Házi feladok elkészítése. Szóbeli beszámoló
Pótlási lehetőségek: 
A TVSz előírásai szerint.
Konzultációs lehetőségek: 
Igény szerint
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.
A tárgy elvégzéséhez átlagosan szükséges tanulmányi munka mennyisége órákban (a teljes szemeszterre számítva)
Kontakt óra: 
56
Félévközi felkészülés órákra: 
56
Felkészülés zárthelyire: 
0
Zárthelyik megírása: 
0
Házi feladat elkészítése: 
20
Kijelölt írásos tananyag elsajátítása (beszámoló): 
18
Egyéb elfoglaltság: 
0
Vizsgafelkészülés: 
0
Összesen: 
150
Ellenőrző adat: 
150
A tárgy tematikáját kidolgozta
Név: 
Dr. Rónyai Lajos
Beosztás: 
egyetemi tanár
Munkahely (tanszék, kutatóintézet, stb.): 
Algebra Tanszék
Név: 
Dr. Friedl Katalin
Beosztás: 
egyetemi docens
Munkahely (tanszék, kutatóintézet, stb.): 
Szit
Név: 
Dr. Ivanyos Gábor
Munkahely (tanszék, kutatóintézet, stb.): 
Sztaki
A tanszékvezető neve: 
Dr. Rónyai Lajos
A tantárgy adatlapja PDF-ben: