Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Informatica
Programul de studii: Optimizarea modelelor informatice - în limba maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIE0001	Adatszerkezetek és algoritmusok	

Félév	Órák: E+Sz+L	Kategória	Típus	
2	2+1+0	alapképzés	kötelező	

II. Foállásban az  Egyetem  oktatói
Név	Tudományos	Oktatói	Tanszék	Tevékenység	
	fokozat	státus		E	Sz	L	
IONESCU Clara	Dr.	Adjunktus	Programozási nyelvek és módszerek	*	*		

Társult oktatók
Név	Tudományos	Intézmény	Állás	Tevékenység 	
	fokozat		típusa	E	Sz	L	

III. A tantárgy célkituzései
1. Az absztrakt adattípus fogalmának valamint a legismertebb absztrakt adattípusok felhasználásának tanulmányozása.
2. Absztrakt adatszerkezetek tanulmányozása,megtervezésüknek elemzése, a specifikációk pontos kidolgozásának gyakorlása. 
3. Absztrakt adatszerkezetek implementálásának elsajátítása és gyakorlása specifikáció alapján. 
4. Adatszerkezetek (tömbök, tételek, láncolt listák, bináris fák, hasítótáblák stb.) tulajdonságainak elsajátítása, bizonyos absztrakt adatszerkezetek implementálásához való felhasználása. 
5. Alkalmazások megvalósításához szükséges készségek kialakítása, adatszerkezetekben tárolt adatok feldolgozásának megismerése és elsajátítása.
6. A dinamikus tárkezelés előnyeinek/hátrányainak tudatosítása.
7. Az alkalmazásnak leginkább megfelelő adatszerkezet kiválasztásához szükséges ismeretek elsajátítása.
8. Azon készségek kialakítása, amelyek az adatszerkezeteket feldolgozó algoritmusok kiválasztását, megtervezését és megvalósítását illeti.
9. A matematika és informatika jellemző alkalmazásaiban használt adatszerkezetek tanulmányozása (például, grágelmélet, adatbázisok, operációs rendszerek stb.). 
10. Az algoritmusok bonyolultságának megállapításához szükséges ismeretek bővítése.	
IV. A tantárgy tartalma
1. Adatok. Algoritmusok és bonyolultság
2. Adattípusok és adatszerkezetek
3. Adatszerkezetek felülnézetből (statikus, félstatikus  és dinamikus adatszerkezetek)
4. A tömb (array)
5. A tétel (record)
6. A halmaz (set)
7. Listák (lists) 
8. Fák (trees)
9. Kupacok (heaps)
10. Hasító táblák (hashing tables)
11. Gráfok	

V. Könyvészet
1. Cormen T. H., Leiserson C., Rivest R. R. –  Algoritmusok, Műszaki Könyvkiadó, Budapest, 1997 (könyvtár).
2. Horowitz E. – Fundamentals of Data Structures in C++, Computer Science Press, 1995 (könyvtár). 
3. Ionescu K. – Adatszerkezetek, cs.ubbcluj.ro/~clara/Adatszerkezetek (kiadatlan egyetemi jegyzet).
4. Preiss B. R. – Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997 (elektronikusan az egyetem hálózatán és http://www.brpreiss.com/books/opus4/).
5. Dale Nell – C++ Plus Data Structures, Third Edition, Jones and Bartlett Publishers, 2002 (elektronikusan az egyetem hálózatán).	

VI. Az oktatói tevékenység heti tematikája
(Az oldalszámok Ionescu Klára Adatszerkezetek című egyetemi jegyzetéből valók)

1. előadás és szeminárium: 
1. Bevezetés	5
	1.1. Adatok
	1.1. Algoritmusok és bonyolultság
2. Adattípusok és adatszerkezetek
	2.1. Adattípusok
	2.2. Az adattípusok absztrakciójának szintjei
	2.3. Absztrakt adattípusok
		2.3.1. Az absztrakt adattípusok specifikálása (egyszerű és összetett adattípusok)
		2.3.2. Az implementálás kérdése
		2.3.3. Az absztrakt adattípusok használatának előnyei
	2.4. Elemek és szerkezet
		2.4.1. Az adatszerkezetek elemei
		2.4.2. A szerkezet
		2.4.3. Lineáris és rendezett adatszerkezetek
		2.4.4. Az adatszerkezetek és a magas szintű programozási nyelvek
		2.4.5. Az absztrakt adatszerkezetek ábrázolása
	2.5. Virtuális és fizikai adattípusok

2. előadás és szeminárium:
3. Adatszerkezetek felülnézetből	21
	3.1. Általánosságok
	3.2. Absztrakt (logikai) adattípusok és fizikai ábrázolásuk
	3.3. Statikus adatszerkezetek
		3.3.1. A tömb (Array)
		3.3.2. A tétel (Record)
		3.3.3. A halmaz (Set)
	3.4. Félstatikus adatszerkezetek
		3.4.1. A verem (Stack)
		3.4.2. A várakozási sor (Queue)
		3.4.3. A hasítótábla (Hashing Table)
	3.5. Dinamikus adatszerkezetek
		3.5.1. A lineáris lista (List)
		3.5.2. A fa (Tree). A bináris fa (Binary tree)
		3.5.3. A hálózat (Network)

3-4. előadás és szeminárium:
4. A tömb (array)	28
	4.1. Definíciók és tulajdonságok
	4.2. Ábrázolásmódok
	4.3. A tömb absztrakt adattípus
	4.3.1. A tömbök paraméterei
		4.3.2. A tömbök megfeleltetési függvényei (Array Mapping Functions)
		4.3.3. A tömbök leírása tételekkel
		4.3.4. Sajátos tömbök: háromszögű mátrix és ritka tömb
		4.3.5. A polinom absztrakt adattípus
	4.4. A Karakterlánc absztrakt adattípus (string)
		4.4.1. Tömbök segítségével implementált karakterláncok
		4.4.2. Dinamikusan tárolt karakterláncok
		4.4.3. Mintaillesztés (egyszerű algoritmus és Knuth, Morris, Pratt algoritmusa)

5. előadás és szeminárium:
5. A tétel (record)	58
	5.1. Rögzített (fix) tételtípus
	5.2. „Változó” rekordok (variánsokkal rendelkező tételek)
6. A halmaz (set)
	6.1. A halmaz absztrakt adattípus
	6.2. Halmaz implementálása tömbbel valamint logikai segédtömbbel
	6.3. Sajátos műveletek algoritmusai

6-7. előadás és szeminárium:
7. Listák (lists) 	66
	7.1. Statikus változók. Mutatók. Dinamikus változók
	7.2. Mutatók
	7.3. Dinamikus adatszerkezetek
	7.4. Egyszeresen (szimplán) láncolt listák
		7.4.1. Listák implementálása tömbökkel
		7.4.2. Listák implementálása a dinamikus tárban
		7.4.1. A verem absztrakt adattípus és implementálási lehetőségek
		7.4.2. A várakozási sor absztrakt adattípus és implementálási lehetőségek
		7.4.3. Rendezett lista
	7.5. Kétszeresen (duplán) láncolt listák
	7.6. Körkörös listák

8-9-10. előadás és szeminárium:
8. Fák (trees)	99
8.1. A fa absztrakt adattípus 
8.2. A fák ábrázolásmódjai
8.2.1. Ábrázolás a memóriában
8.2.2. Kimeneti ábrázolásmódok (megjelenítések) 
8.2.3. A bemeneti ábrázolásmódok (a fa beolvasása)
8.3. Sajátos műveletek
8.3.1. Tökéletesen egyensúlyozott bináris fa létrehozása
8.3.2. Bejárások (Mélységi bejárás, Nem rekurzív bejárás, Konstans tárigényű bejárás 
8.4. Keresőfák
8.4.1. Beszúrás egy keresőfába 8.4.2. Törlés a keresőfából
8.4.3. A legkisebb (legnagyobb) kulcsú elem megkeresése
8.4.4. A következő kulcsú elem megkeresése
8.5. AVL-egyensúlyozott bináris fák
		8.5.1. Beszúrás AVL-fákba
		8.5.2. Törlés AVL-fákból
	8.6. “Piros-fekete” fák
		8.6.1. Beszúrás a piros-fekete fákba
		8.6.2. Törlés a piros-fekete fákból
	8.7. B-fák
		8.7.1. Beszúrás a B-fákba
		8.7.2. Törlés a B-fákból
	8.8. Splay-fák

11-12. előadás és szeminárium:
9. Kupacok (heaps)	179
	9.1. A bináris maximum- és minimum-kupac
	9.1.1. A kupac-tulajdonság fenntartása
	9.1.2. A kupac építése
	9.1.3. Kupacrendezés 
9.2. Az elsőbbségi sor
	9.3. Intervallum-kupacok 
		9.3.1. Minimum és maximum az intervallum-kupacban
		9.3.2. Beszúrás
		9.3.3. Minimum és maximum törlése
	9.4. Binomiális kupacok 
9.4.1. Binomiális fák
9.4.2. Binomiális kupacok létrehozása
9.4.3. A minimum meghatározása
9.4.4. Egyesítés
9.4.5. Beszúrás
9.4.6. A minimum törlése 
9.5. Min-Max kupacok
9.5.1. A Hasse-diagram
9.5.2. A Min-Max kupac létrehozatala
9.5.3. A minimum meghatározása
9.5.4. A maximum meghatározása 
9.5.5. A minimum törlése
9.5.6. A maximum törlése 
9.5.7. Beszúrás

13. előadás és szeminárium:
10. Hasító táblák (hashing tables)	201
	10.1. Bevezetés
	10.2. A szimbolikus táblázat AAT
	10.3. Statikus hasító táblázatok
		10.3.1. Hasító függvények
		10.3.2. A túlcsordulás kezelése (nyitott címzés, láncolás)
	10.4. Dinamikus hasító táblázatok

14. előadás és szeminárium:
11. Gráfok	227
	11.1. Alapfogalmak
	11.2. Gráfok ábrázolásmódjai
	11.2.1. Élek sorozata
	11.2.2. Szomszédok listája
	11.2.3. Illeszkedési (adjacencia) mátrix
11.3. Gráfok ábrázolása a dinamikus tárban 

Minden fejezet végén lesznek kitűzött feladatok, amelyeket a hallgatók hétről hétre megoldanak. 	

VII. Alkalmazott didaktikai módszerek
1. Előadások: leírások, magyarázatok, dialógusok, bizonyítások, prezentációk.
2. Megbeszélések: viták, elemző és összefoglaló beszélgetések
3. Bizonyítások: elméleti jellegű bizonyítások, tesztelések, számítógépes tesztelések.
4. Modellezés: a feladatok megoldásához szükséges matematikai modellek kialakítása, a tanult algoritmusok modellként való alkalmazása.
5. Algoritmizálás: a megértés, az általánosítás, a rendszerezés, a felismerés, a megoldás, az alkotás gyakorlásához szükséges eszközök alkalmazása.
6. Problematizálás.
7. A felfedezéses oktatás különböző formáinak alkalmazása: irányított és független felfedezés, alkotó felfedezés, induktív és deduktív felfedezés.
8. Esettanulmányok, projektek, gyakorlatok, egyéni tanulás, házi feladatok.	

VIII. Értékelés
1. A házi feladatokat minden hallgató egyénileg oldja meg, kérésre el kell tudja magyarázni, módosítani.
2. A szemináriumi aktív részvételért „bónusz” pontokat lehet szerezni.
3. A 7. előadás után részleges vizsga (írásbeli: RV), a szesszióban írásbeli vizsga (ÍV) lesz. A részleges vizsga eredménye nem kizáró jellegű, és kérésre meg lehet ismételni a szesszióban.
4. Értékelési kritériumok: a feladatok megoldásainak a tanított mintákkal azonos minőségűeknek kell lenniük (hatékonyság, felhasznált memória, stílus, átláthatóság, paraméterezés, dokumentáltság stb.).   
5. Minden házi feladatra a hallgatók kapnak jegyet, ezeknek átlaga: H. 
6. A végleges vizsga jegye: [(RV + ÍV + H)/3]. 
7. Előadásra nem kötelező, szemináriumra kötelező járni. 
8. Vizsgára csak azok jelentkezhetnek akik legtöbb kétszer hiányoztak szemináriumról. 
9. A hiányzásokat be lehet pótolni egy másik csoporttal. 
10. A másolt házi feladat semmis. 
11. Aki puskázik, az csak a következő szesszióban jelentkezhet újra vizsgázni. 
12. Az esetleges óvásokat a hallgatóval oldom meg, jelenlétében újból kijavítom a dolgozatát.	

IX. Kiegészíto könyvészet
1. Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar, Budapest, 2003 (könyvtár).
2. Ambsbury W. – Data structures. From arrays to priority queues, 1993. 
3. Knuth D. E. – A számítógép-programozás művészete, I, II, III kötet, Editura Tehnică, Bucureşti, 1973, v. magyarul 1992.
4. Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.
5. Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002.
6. Wirth N. – Algorithms + Data Structures = Programs, Prentice-Hall Inc., 1976.
7. Mount D. M. – Data Structures, University of Maryland, 1993 (elektronikusan az egyetem hálózatán).
8. Saltenis S. – Algorithms and Data Structures, 2002 (elektronikusan az egyetem hálózatán).	

	Dékán,						Tanszékvezető,

	Dátum,						Előadás felelőse,
								Dr. IONESCU Clara, adjunktus