A tantárgy adatlapja

1.	A képzési program adatai
1.1 Felsőoktatási intézmény	Babeș-Bolyai Tudományegyetem	
1.2 Kar 	Matematika és Informatika	
1.3 Intézet	Magyar Matematika és Informatika	
1.4 Szakterület	informatika	
1.5 Képzési szint	alap	
1.6 Szak / Képesítés	Matematika, Matematika-informatika és Informatika	

2.	A tantárgy adatai
2.1 A tantárgy neve	Adatszerkezetek és algoritmusok	
2.2 Az előadásért felelős tanár neve	Ionescu Klára	
2.3 A szemináriumért felelős tanár neve	Ionescu Klára	
2.4 Tanulmányi év	1	2.5 Félév	2	2.6	Értékelés módja	vizsga	2.7 Tantárgy típusa	kötelező –alap 	

3.	Teljes becsült idő (az oktatási tevékenység féléves óraszáma)
3.1 Heti óraszám	3	melyből: 3.2 előadás	2	3.3 szeminárium/labor	1	
3.4 Tantervben szereplő összóraszám	42	melyből: 3.5 előadás	28	3.6 szeminárium/labor	14	
A tanulmányi idő elosztása:	óra	
A tankönyv, a jegyzet, a szakirodalom vagy saját jegyzetek tanulmányozása	25	
Könyvtárban, elektronikus adatbázisokban vagy terepen való további tájékozódás	5	
Szemináriumok / laborok, házi feladatok, portofóliók, referátumok, esszék kidolgozása	30	
Egyéni készségfejlesztés (tutorálás)	3	
Vizsgák	6	
Más tevékenységek: ..................		
3.7 Egyéni munka össz-óraszáma	70	
3.8 A félév össz-óraszáma	112	
3.9 Kreditszám	5 (M), 5 (MI), 5 (I)	

4.	Előfeltételek (ha vannak)
4.1 Tantervi	•	Nincs	
4.2 Kompetenciabeli	•	Elemi algoritmusok ismerete	

5.	Feltételek 
5.1 Az előadás lebonyolításának feltételei	•	Táblával és videoprojektorral felszerelt előadó	
5.2 A szeminárium / labor lebonyolításának feltételei	•	Számítógépes terem, a gépeken Pascal/C++	

6.	Elsajátítandó jellemző kompetenciák
Szakmai kompetenciák	•	Az algoritmus fogalmának megértése, az algoritmusok ábrázolási módozatainak elsajátítása 
•	Az algoritmusok tervezéséhez szükséges készségek kialakítása, a fegyelmezett, logikus és algoritmikus gondolkozás kialakítása
•	A strukturált programozás, a moduláris programtervezés, valamint a top-down és bottom-up programtervezés alapszabályainak megismerése és elsajátítása
•	Adott feladatosztályokhoz tartozó feladatok megoldási algoritmusainak és a szükséges adatszerkezeteknek megismerése és elsajátítása: számok, karakterláncok feldolgozása, sorozatok, kétdimenziós tömbök, keresés, összefésülés, rendezés stb.
•	A megtervezett algoritmusok implementálása egyszerű Pascal/C/C++ programok segítségével
•	A legfontosabb programozási módszerek (visszalépéses keresés, oszd meg és uralkodj, mohó algoritmusok) elsajátítása és a megfelelő feladatmegoldási készség kialakítása
•	Helyes, átlátható programozási stílus kialakítása, a dokumentálás alapszabályainak megismerése
•	Szoftver-komponensek fejlesztése adatstruktúrák, algoritmusok, technikák és fejlett programozási nyelvek felhasználásával
•	A programozási nyelvek, technikák és módszerek frissítése, úgy hogy a fejlesztett szoftver-komponensek tükrözzék az Információs Technológia és Kommunikáció fejlettségi állapotát 
•	A fejlesztési folyamat szakaszaira vonatkozó követelmények meghatározása, annak érdekében, hogy nagy teljesítményű szoftver-komponenseket kapjunk, modern technológiák alkalmazásával
•	A szoftverfejlesztési folyamatra jellemző tevékenységek kidolgozása, mennyiségi, minőségi és a gazdasági hatékonyság szempontokat követve
•	Komplex rendszerekbe beépíthető szoftver-komponensek megvalósítására alkalmas adatstruktúrák, utasítások és probléma-osztályok ismertetése 	
Transzverzális kompetenciák 	•	Matematikai problémák megoldása informatikai eszközökkel
•	A diák elemző és szintetizáló képességének fejlesztése.
•	A szakmai etika elveinek, normáinak és értékeinek alkalmazása egy felelős, hatékony és igényes munkastratégia kialakításában.
•	A képzési lehetőségek beazonosítása és a tanulási módszerek és erőforrások hatékony felhasználása a hallgató fejlődésének érdekében.

7.	A tantárgy célkitűzései (az elsajátítandó jellemző kompetenciák alapján)
7.1 A tantárgy általános célkitűzése	•	Modellezési, feladatmegoldói, informatikai szövegértési készségek, jártasságok fejlesztése.
•	Az alkotókészség fejlesztése.
•	Egyéni munkára nevelés és a csapatszellem kialakítása.	
7.2 A tantárgy sajátos célkitűzései
	•	Fegyelmezett, logikus és algoritmikus gondolkozás kialakítása.
•	Programozási módszerek elsajátítása és gyakorlása.
•	A szoftvertervezés alapszabályainak megismerése.	

8.	A tantárgy tartalma
8.1 Előadások	Didaktikai módszerek	Megjegyzések	
1. Bevezetés
	1.1. Absztrakt adatszerkezetek 
	1.2. Definíciók
	1.3. Egy egyszerű példa
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
			A) Egyszerű típusok
			B) Összetett típusok
		2.3.2. Az absztrakt adattípusok használatának előnyei
			A) Egyszerűség
			B) Egységesség (integritás)
			C) Az implementáció függetlensége
	2.4. Az elemek és a szerkezet
		2.4.1. Az adatok elemei
		2.4.2. A szerkezet
		2.4.3. Lineáris és rendezett adatszerkezetek
		2.4.4. A címkiszámolásos és a láncolt ábrázolás
	2.5. Virtuális és fizikai adattípusok
	2.6. Statikus változók. Mutatók. Dinamikus változók
		2.6.1. Mutatók	1.	Előadás	[3] pp: 11-32	
3. Adatszerkezetek logikai megközelítése
	3.1. Általánosságok
	3.2. Logikai (absztrakt) 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. 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)
		3.5.3. A hálózat (Network)
4. A tétel
	4.1. Rögzített (fix) tételtípus
	4.2. A tétel absztrakt adattípus
	4.3. „Változó” (variánsokkal rendelkező) tételek
	4.4. Tételek C-ben és C++-ban	2.	Előadás	[3] pp: 33-51	
5. 	Tömbök
	5.1. Definíciók és tulajdonságok
	5.2. Ábrázolásmódok
		5.2.1. A tömbök deklarációja különböző programozási 
				nyelvekben
		5.2.2. Helyfoglalás tömbök számára különböző 
				programozási nyelvekben
	5.3. A tömb absztrakt adattípus
	5.4. Implementálás
	5.5. Tömbszakasz és részsorozat 
	5.6. A tömbök megfeleltetési függvényei
	5.7. A tömbök paraméterei
	5.8. A tömbök leírása tételekkel	3.	Előadás	[3] pp: 51-71
	
	5.9. Sajátos tömbök
		5.9.1. Háromszögű mátrix
		5.9.2. Ritka tömbök
			A) Háromsoros reprezentáció
			B) Négysoros reprezentáció
	5.10. A polinom absztrakt adattípus
		5.10.1. A polinomokról általában
		5.10.2. Lehetséges ábrázolások
			A) A polinom ábrázolása tömbök segítségével
			B) A polinom ábrázolása dinamikusan tárolt tömbök 
				segítségével
			C) A polinom ábrázolása monomjainak sorozataként	4.	Előadás	[3] pp: 72-82
	
6. Karakterláncok
	6.1. Karakterláncokkal végezhető műveletek
	6.2. Mintaillesztés 
		6.2.1. Egyszerű algoritmus
			A) Mintaillesztés tömbök segítségével implementált 
			karakterláncokkal
			B) Mintaillesztés dinamikusan tárolt karakterláncokkal
		6.2.2. A Knuth, Morris, Pratt algoritmus
		6.2.3. A Boyer-Moore algoritmus
7. Halmazok
	7.1. Alapfogalmak
	7.2. Ábrázolásmódok
		7.2.1. A halmazok deklarációja különböző programozási 
				nyelvekben
	7.3. A halmaz absztrakt adattípus
	7.4. A Halmaz osztály	5.	Előadás	[3] pp: 83-100

[3] pp: 101-106	
8. Listák
	8.1. Dinamikus adatszerkezetek
	8.2. Egyszeresen (szimplán) láncolt listák 
		8.2.1. Listák implementálása tömbökkel
		8.2.2. Listák implementálása a dinamikus tárban
	8.3. A verem
		8.3.1. Műveletek
		8.3.2. A verem absztrakt adattípus
		8.3.3. Ábrázolásmódok és implementálás
			A) Statikus implementáció
			B) Dinamikus implementáció	6.	Előadás	[3] pp: 107-116
	
	8.4. A várakozási sor
		8.4.1. Műveletek
		8.4.2. A várakozási sor absztrakt adattípus
		8.4.3. Ábrázolásmódok és implementálás
			A) Statikus implementáció
			B) Dinamikus ábrázolás és implementálás
	8.5. Tetszőleges listák	7.	Előadás	[3] pp: 117-130
	
 	8.6. Rendezett lista
	8.7. Kétszeresen (duplán) láncolt lista
	8.8. Körkörös listák
	8.9. A dinamikus tárkezelés alkalmazásai
		8.9.1. Polinomok ábrázolása láncolt listák segítségével
			A) Polinomok összeadása
			B) Polinomok törlése	8.	Előadás	[3] pp: 131-148	
9. Fák
	9.1. Motiváció
	9.2. Bináris fák
	9.3. A fák ábrázolásmódjai
		9.3.1. Ábrázolás a memóriában
			A) Bináris fák ábrázolása
			B) Tetszőleges fák ábrázolása
		9.3.2. Kimeneti ábrázolásmódok (megjelenítések)
		9.3.3. A bemeneti ábrázolásmódok (a fa beolvasása)
	9.4. Műveletek
		9.4.1. Tökéletesen egyensúlyozott bináris fa létrehozása
		9.4.2. Bejárás
			A) Mélységi bejárás
			B) Nem rekurzív bejárás
			C) Konstans tárigényű bejárás 
			D) Tetszőleges fák szélességi bejárása	9.	Előadás	[3] pp: 149-166	
	9.5. Keresőfák
		9.5.1. Keresés
		9.5.2. Beszúrás egy keresőfába 
		9.5.3. Törlés
		9.5.4. A legkisebb (és a legnagyobb) kulcsú elem 
				megkeresése
		9.5.6. A következő kulcsú elem megkeresése
	9.6. AVL-egyensúlyozott bináris fák 
		9.6.1. Specifikáció – AVL fák
			A) Beszúrás AVL-fákba
			B) Törlés AVL-fákból
		9.6.2. Implementálás	10.	Előadás	[3] pp: 167-178	
	9.7. „Piros-fekete” fák
		9.7.1. A piros-fekete fa absztrakt adattípus
		9.7.2. Forgatások
		9.7.3. Beszúrás a piros–fekete fákba
		9.7.4. Törlés a piros-fekete fákból	11.	 Előadás	[3] pp: 193-209	
	9.8. Splay-fák (kifordított fák, S-fák)
	9.9. Binárisan indexelt fák
		9.9.1. Bevezetés
		9.9.2. Naiv algoritmus
		9.9.3. Parciális összegek
		9.9.4. Binárisan indexelt fa
			A) Módosítás
			B) Lekérdezés	12.	 Előadás	[3] pp: 214-227	
10. Kupacok
	10.1. A bináris kupac
		10.1.1. A kupac tulajdonság fenntartása
		10.1.2. A kupac építése
		10.1.3. Kupacrendezés
	10.2. Elsőbbségi sorok	13. Előadás	[3] pp: 235-245	
11. Hasító táblák
	11.1. Bevezetés
		11.1.1. A szimbolikus táblázat osztály
	11.2. Statikus hasító táblázatok
		11.2.1. Hasító függvények
			A) Négyzetek közepe
			B) Osztás (maradékszámítás)
			C) Partícionálás
			D) Számjegy vizsgálat
			E) Szorzásos módszer
			F) Univerzális hasítási technika
	11.3. A túlcsordulás kezelése
		11.3.1. Nyitott címzés
		11.3.2. Kipróbálási technikák
		11.3.3. Láncolás
	11.4. Dinamikus hasító táblázatok
		11.4.1. Alkönyvtárakat felhasználó dinamikus hasítás	14. Előadás	[3] pp: 283-298	
Könyvészet
1.	Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar, Budapest, 2003.
2.	Horowitz E. – Fundamentals of Data Structures in C++, Computer Science Press, 1995.
3.	Ionescu K. – Adatszerkezetek, Egyetemi Könyvkiadó, Kolozsvár, 2007
4.	Preiss B. R. – Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997 (http://www.brpreiss.com/books/opus4/).
5.	Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.
6.	Wirth N. – Algorithms + Data Structures = Programs, Prentice Hall Inc., 1976.
7.	Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002.
8.	Stubbs D. F., Webre N., W. – Data Structures, Brooks/Cole Publishing Company Monterey, California, 1985.	
8.2 Szeminárium / Labor	Didaktikai módszerek	Megjegyzések	
1. Példák, statikus változókkal, mutatókkal, dinamikus változókkal.	1.	Szeminárium		
2. Példák rögzített (fix) tételtípussal (Pascalban és C++-ban), példák változó rekordokkal (Pascalban).	2.	Szeminárium		
3. Gyakorlatok a tömbök megfeleltetési függvényeivel, tömbök leírása tételekkel. Az egy- és kétdimenziós tömb AAT implementálása. 	3.	Szeminárium		
4. A háromszögű mátrix AAT és a ritka tömb AAT implementálása. A polinom ábrázolása tömbök segítségével és monomjainak sorozataként.	4.	Szeminárium		
5. Mintaillesztés tömbök segítségével implementált karakterláncokkal, illetve dinamikusan tárolt karakterláncokkal. Knuth, Morris, Pratt algoritmusa, Boyer-Moore algoritmusa 	5.	Szeminárium		
6. Listák implementálása statikusan és dinamikusan 	6.	Szeminárium		
7. Várakozási sorok implementálása statikusan és dinamikusan 	7.	Szeminárium		
8. Rendezett listák implementálása statikusan és dinamikusan 	8.	Szeminárium		
9. Parciális vizsga 	9.	Szeminárium		
10. Tökéletesen egyensúlyozott fák implementálása 	10.	Szeminárium		
11. Keresőfák implementálása 	11.	Szeminárium		
12. Piros-fekete fák implementálása	12.	Szeminárium		
13. Splay-fák és binárisan indexelt fák implementálása	13.	Szeminárium		
14. Kupacok implementálása. Alkalmazások. Az elsőbbségi sor implementálása.	14.	Szeminárium		
Könyvészet
1)	Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar, Budapest, 2003.
2)	Horowitz E. – Fundamentals of Data Structures in C++, Computer Science Press, 1995.
3)	Ionescu K. – Adatszerkezetek, Egyetemi Könyvkiadó, Kolozsvár, 2007
4)	Preiss B. R. – Data Structures and Algorithms with Object-Oriented Design Patterns in C++, 1997 (http://www.brpreiss.com/books/opus4/).
5)	Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.
6)	Wirth N. – Algorithms + Data Structures = Programs, Prentice Hall Inc., 1976.	

9.	A tantárgy tartalmának összhangba hozása az episztemikus közösségek képviselői, a szakmai egyesületek és a szakterület reprezentatív munkáltatói elvárásaival.
•	A tantárgy tartalma megegyezik az egyetemi oktatásban a fontosabb egyetemeken oktatott algoritmusok és programozás bevezető tárgy hagyományos tartalmával.
•	A tárgy keretében figyelembe vesszük a számítógép használata nyújtotta lehetőségeket a matematikai problémák vizsgálatában. 	

10.	Értékelés
Tevékenység típusa	10.1 Értékelési kritériumok	10.2 Értékelési módszerek	10.3 Aránya a végső jegyben	
10.4 Előadás 	Alapfogalmak és algoritmusok ismerete	A félév közepén parciális írásbeli és gyakorlati vizsga	33 %	
10.5 Szeminárium / Labor	Házi feladatok (helyesség, stílus, dokumentáltság, indentálás, tesztelés) 33%	A vizsgaidőszakban írásbeli és gyakorlati vizsga	33 %	
10.6 A teljesítmény minimumkövetelményei	
•	Az elemi algoritmusok ismerete, a programozási tételek alkalmazása
•	Egyszerű rekurzív algoritmusok ismerete
•	Az elemi adatszerkezetek ismerete, az ezeket feldolgozó algoritmusok implementálása és alkalmazása
•	A fejlett adatszerkezetek ismerete	

Kitöltés dátuma			Előadás felelőse			Szeminárium felelőse
2012. okt. 21. 			...............................			...................................

Az intézeti jóváhagyás dátuma				Intézetigazgató,	
2012. okt. 28.						Dr. Szenkovits Ferenc, egyet. docens
..........................