INFORMATIKAI KAR DOKTORI PROGRAM
SZIGORLATI TEMATIKA

Adatszerkezetek



1. Az adattípus absztrakciós szintjei: az absztrakt adattípus (ADT) fogalma, az algebrai és a funkcionális specifikáció; az absztrakt adatszerkezet (ADS) fogalma, a szerkezeti gráf; az ábrázolás szintje, tömbös (aritmetikai) és láncolt (pointeres) ábrázolás.
2. Tömbök, verem, sor és elsobbségi sor; muveleteik, ábrázolásuk (az elsobbségi sornál több féle, pl. kupac is), alkalmazásaik algoritmusokban (pl. verem: lengyelforma, sor: gráfbejárások, kupac: kupacrendezés, gráfalgoritmusok hatékonyságának növelése).
3. Listák (egyszeru és fejelemes, egy- és kétirányú, nem-ciklikus és ciklikus); muveleteik, ábrázolásuk, alkalmazásaik.
4. Bináris fa, láncolt és aritmetikai ábrázolás; bejárásai: preorder, inorder, posztorder, ill. szintfolytonos.
5. Bináris keresofa; muveletei, hatékonyságuk. Az AVL-fa; összefüggés a fa magassága és pontszáma között; forgatási szabályok; az AVL-tulajdonság fenntartásának költsége.
6. A 2-3 fa és B-fa; összefüggés a fa magassága és pontszáma között. A 2-3 fákon értelmezett muveletek, a csúcsvágás és csúcsösszevonás; a muveletek költsége. A B-fák elhelyezése mágneslemezes háttértárolón.
7. Hasítótáblák, kulcsütközés feloldása láncolással és nyitott címzéssel; muveletek; hasító függvények.
8. Gráfok ábrázolása szomszédossági mátrixszal és éllistás módon; alkalmazásuk az suruség függvényében. Gráfok bejárásai.

 


Irodalom:


1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Új algoritmusok. Scolar Kiadó, Budapest, 2003.
2. Rónyai L., Ivanyos G., Szabó R.: Algoritmusok. Typotex Kiadó, Budapest, 1998.

Neuronhálókkal kapcsolatos forrásanyagok: http://www.neoxi.com/NNR/

Online tananyagok:

http://www.statsoftinc.com/textbook/stneunet.html
http://www.inference.phy.cam.ac.uk/mackay/itila/
http://www.benbest.com/computer/nn.html