Babeş–Bolyai Tudományegyetem Kolozsvár
Matematikai és Informatikai Kar  
2006-2007-es tanév, 2. félév 

I.	A tantárgy adatai

A tantárgy neve: ADATSZERKEZETEK ÉS ALGORITMUSOK
Kód: MIE0001
Kreditszám: 5
Hol tartják?  (előadás, szeminárium):
Mikor tartják? (előadás, szeminárium):

II.	Az oktatók adatai 
 
Előadás
Név, tudományos cím: dr. Ionescu Klára
Elérhetőség (e-mail, telefon): clara@cs.ubbcluj.ro, 0745-653.687
Fogadóóra:
Szobaszám: Campus, 4. em. 440
Szeminárium
Név, tudományos cím: dr. Ionescu Klára
Elérhetőség (e-mail, telefon): clara@cs.ubbcluj.ro, 0745-653.687
Fogadóóra: Campus, 4. em. 440

III.	A tantárgy leírása: 

Célok
•	Absztrakt adatszerkezetek tanulmányozása és megtervezésüknek elemzése, illetve gyakorlása 
•	Absztrakt adatszerkezetek implementálásának elsajátítása és gyakorlása specifikáció alapján 
•	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 
•	Alkalmazások megvalósításához szükséges készségek kialakítása, adatszerkezetekben levő adatok feldolgozása
•	A dinamikus tárkezelés előnyeinek/hátrányainak tudatosítása
•	Az alkalmazásnak leginkább megfelelő adatszerkezet kiválasztása
•	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
•	Algoritmusok bonyolultságának megállapításához szükséges ismeretek bővítése

Tartalom
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

Kompetenciák
A tantárgy tanulmányozása és elsajátítása után a hallgató:
•	Megismeri és elsajátítja az adatszerkezetekhez kapcsolódó ismereteket
•	Elsajátítja az absztrakt adatszerkezetek tervezési módozatait, és gyakorolja a specifikációk pontos kidolgozását
•	Felismeri a legmegfelelőbb adatszerkezetet adott alkalmazás megtervezésekor, illetve implementálásakor 
•	Kialakítja a unitok/headerállományok megvalósításához szükséges készségeket
•	Bővíti az algoritmusok elemzéséhez és tervezéséhez szükséges készségeket 
•	Fejleszti a programok dokumentálásához elengedhetetlenül szükséges szokásait 

Módszerek
Előadások, beszélgetések, projektek, gyakorlatok, egyéni tanulás, házi feladatok.
Irányított felfedezésre épülő tanítás/tanulás, prezentációk.
 
IV.	Kötelező könyvészet:
1.	Ionescu K. – Adatszerkezetek, cs.ubbcluj.ro/~clara/Adatszerkezetek (kiadatlan egyetemi jegyzet).
2.	Cormen T., Leiserson C., Rivest R. – Algoritmusok, Műszaki Könyvkiadó, Budapest, 1997 (könyvtár).
3.	Horowitz E. – Fundamentals of Data Structures in C++, Computer Science Press, 1995 (könyvtár).

V.	 Az oktatásban használt eszközök:
Interneten elérhető forrásmunkák, cikkek, demo-programok.

VI.	A tevékenységek és ellenőrzések/részleges vizsgák órarendje:

Előadások és szemináriumok 
(Az oldalszámok Ionescu Klára „Adatszerkezetek” című kiadatlan 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.		Az értékelés módja:
-	A házi feladatokat minden hallgató egyénileg oldja meg, kérésre el kell tudja magyarázni, módosítani.
-	A szemináriumi aktív részvételért „bónusz” pontokat lehet szerezni.
-	A 7. előadás után részleges vizsga (írásbeli: RV), a szesszióban írásbeli vizsga (ÍV) lesz. 
-	É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.).   
-	Minden házi feladatra a hallgatók kapnak jegyet, ezeknek átlaga: H. 
-	A végleges vizsga jegye: Round((RV + ÍV + H)/3)

VIII.		Szervezési kérdések, a különleges esetek kezelése:
1.	Előadásra nem kötelező, szemináriumra kötelező járni. 
2.	Vizsgára csak azok jelentkezhetnek akik legtöbb kétszer hiányoztak szemináriumról. 
3.	A hiányzásokat be lehet pótolni egy másik csoporttal. 
4.	A másolt házi feladat semmis. 
5.	Aki puskázik, az csak a következő szesszióban jelentkezhet újra. 
6.	Az óvásokat a hallgatóval oldom meg, jelenlétében újból kijavítom a dolgozatát.
7.	A részleges vizsga eredménye nem kizáró jellegű, és kérésre meg lehet ismételni a szesszióban.

IX.		Ajánlott, de nem kötelező könyvészet:

1.	Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar, Budapest, 2003 (könyvtár).
1.	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.
2.	Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.
3.	Wirth N. – Algorithms + Data Structures = Programs, Prentice Hall Inc., 1976.
4.	Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002.