Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Licenţă
Domeniul: Informatică
Programul de studii: Informatică - linia de studiu maghiară
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MIF0006	Analiza algoritmilor	

Félév	Órák: E+Sz+L	Kategória	Típus	
5	2+1+1	szakirány	opcionális	

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
Algoritmusok elemzése és tervezése mechanizmusainak megismerése.
Algoritmusok bonyolultságának elemzése. 
Feladatosztályok felismerése.
A dinamikus programozás módszerének tanulmányozása és alkalmazásának gyakorlása.
Közelítő algoritmusok megismerése és alkalmazásuknak gyakorlása.
Algoritmusok hatékonyságának növelése a bináris keresés alapötletének alkalmazásával.
Bonyolult adatszerkezetek tanulmányozása (kupacok, fák különleges fajtái)	

IV. A tantárgy tartalma
Algoritmusok elemzése és tervezése
1. Bevezetés. Különböző (ismert és ezután tanulmányozandó) algoritmusok áttekintése
2. Programozási tételek
3. Programozási módszerek
4. Algoritmusok elemzése és algoritmusok tervezése
5. Függvények növekedése
6. Függvények rekurzív megadása 
7. Gyorsrendezés 
8. Mediánok és rendezett minták 
9. Fejlett elemzési és tervezési módszerek 
10. NP-teljesség 
11. Közelítő algoritmusok 
12. Algoritmusok hatékonyságának növelése 
13. Fejlett adatszerkezetek 
14. Geometriai algoritmusok  	

V. Könyvészet
1. Cormen, T., Leiserson, Ch., Rivest, R., Stein, C. – Új Algoritmusok, Scolar Kiadó, Budapest, 2003 (könyvtár).
2. Cormen, T., Leiserson, Ch., Rivest, R. – Introducere în algoritmi, Editura Computer Libris Agora, Cluj-Napoca, 2000 (könyvtár).
3. Brassard, G., Bratley, P. – Fundamentals of Algorithmics, Prentice Hall, 1996.
4. Horowitz, E., Sahni, S., Rajasekaran, S. – Computer Algorithms, Computer Science Press, 1998. 
5. Knuth, D. – Arta programării calculatoarelor, Vol. Iii, Sortare Şi Căutare, Editura Teora, Bucuresti, 2001.
6. Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999. 
7. Wirth, N. – Algorithms + Data Structures = Programs, Prentice Hall, 1976.
8. Ionescu, K. – Bevezetés az algoritmikába, Presa Universitară Clujeană, 2005 (könyvtár).	

VI. Az oktatói tevékenység heti tematikája
Algoritmusok elemzése és tervezése
(Az alábbi oldalszámok a könyvészet sorszámait tartalmazzák a tulajdonképpeni oldalszám előtt. Ahol nincs explicite megadott oldalszám, a hallgatók az Interneten megtalálják az általam feltett anyagokat a www.cs.ubbcluj.ro/~clara/Algoritmusok címen.)
1. Előadás
1. Bevezetés. Különböző (ismert és ezután tanulmányozandó) algoritmusok 
     áttekintése
	1.1. Bevezetés	8: 38
	1.2. Algoritmusok helyessége	8: 39
	1.3. Az algoritmus végrehajtásához szükséges idő	8: 42
	1.4. Az algoritmus által feldolgozott adatok számára szükséges memória mérete	8: 47
	1.5. Algoritmusok egyszerűsége	8: 47
	1.6. Algoritmusok optimalitása	8: 47
	1.7. Lépések finomítása	8: 57

2. Programozási tételek
	2.1. Egyszerű programozási tételek	8: 83
	2.2. Összetett programozási tételek	8: 100

3. Programozási módszerek
	3.1. Backtracking 	8: 187
	3.2. Divide et Impera 	8: 223 
	3.3. Mohó algoritmusok	8: 249 
	3.4. Heurisztikus mohó algoritmusok 	8: 276
	3.5. A dinamikus programozás módszere 
	3.6. Branch & Bound 

2. Előadás
4. Algoritmusok elemzése és algoritmusok tervezése	1: 31
	4.1. Bevezetés	
	4.2. Beszúró rendezés
		4.2.1. A beszúró rendezés ciklusinvariánsai és helyessége
	4.3. Algoritmusok elemzése
		4.3.1. A beszúró rendezés elemzése
		4.3.2. A legrosszabb eset és az átlagos eset elemzése
	4.4. Növekedési rend
	4.5. Algoritmusok tervezése
		4.5.1. Az oszd meg és uralkodj megközelítés
		4.5.2. Az Oszd meg és uralkodj algoritmusok elemzése
		4.5.3. Az összefésülő rendezés elemzése

3. Előadás
5. Függvények növekedése	1: 53
	5.1. Aszimptotikus jelölések

6. Függvények rekurzív megadása 	1: 70
	6.1. A helyettesítő módszer 
		6.2. A jó eredmény megsejtése
		6.3. Új változó bevezetése
		6.4. A rekurziós fa módszer
	6.2. Az iterációs módszer 
	6.3. A mester módszer 

4. Előadás
7. Gyorsrendezés 	1: 141
	7.1. A gyorsrendezés leírása 
	7.2. A gyorsrendezés hatékonysága 
	7.3. A gyorsrendezés véletlen változatai 
	7.4. A gyorsrendezés elemzése 

8. Mediánok és rendezett minták 	1: 172
	8.1. Minimális és maximális elem
	8.2. Kiválasztás átlagosan lineáris időben
	8.3. Kiválasztás legrosszabb esetben lineáris időben 
 
5. Előadás
9. Fejlett elemzési és tervezési módszerek 	1: 288
	9.1. Bevezetés 
	9.2. Dinamikus programozás 
		9.2.1. Megoldott feladatok

6. Előadás
10. NP-teljesség 	1: 820
	10.1. Polinomiális idő 
	10.2. Polinomiális idejű ellenőrzés 
	10.3. NP-teljesség és visszavezethetőség 
	10.4. NP-teljességi bizonyítások 

7. Előadás
10.5. NP-teljes problmák 	1: 848
	10.6. NP-teljes feladatok megoldási lehetőségei
	10.7. A „nem-érdekes” helyzetek kizárása 
	10.8. Depth First Search with Iterative Deepening

8. Előadás
11. Közelítő algoritmusok 	1: 863
	11.1. A közelítő algoritmusok teljesítménykorlátai
	11.2. Heurisztikus mohó algoritmusok
	11.3. Heurisztikával megoldott feladatok

9. Előadás
	11.4. Véletlenített algoritmusok
	11.5. Véletlenített algoritmusokkal megoldott feladatok

10. Előadás
12. Algoritmusok hatékonyságának növelése 
	12.1. A bináris keresés 
	12.2. Algoritmusok bonyolultságának csökkentése a bináris keresés elvének alkalmazásával
	12.3. Megoldott feladatok

11. Előadás
13. Fejlett adatszerkezetek 	1: 380
	12.1. Bevezetés 
	12.2. B-fák 
		12.2.1. A B-fák alapműveletei 

12. Előadás
	12.3. Bináris maximum-kupacok
	12.4. Intervallum-kupacok 
		12.4.1. Minimum és maximum
		12.4.2. Műveletek

13. Előadás
	12.5. Binomiális kupacok 	1: 398
		12.5.1. Binomiális fák 
		12.5.2. Binomiális kupacok
		12.5.3. Műveletek
	12.6. Min-Max kupacok
		12.6.1. A Hasse-diagram
		12.6.2. A Min-Max kupac létrehozatala
		12.6.3. Műveletek

14. Előadás
13. Geometriai algoritmusok 	1: 793
	13.1. Szakaszok tulajdonságai 
	13.2. Metsző szakasz-pár keresése 
	13.3. Konvex burok meghatározása 
	13.4. Legközelebbi pontpár keresése 	

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 ismeretlen feladatok elemzésében és megoldásában.
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ónak egyénileg oldja meg, kérésre el kell tudja magyarázni, módosítani. A házi feladatokra minden hallgató kap két érdemjegyet: egyet a részleges vizsga előtt és egyet a félév végén (H1, H2).
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 (Í) és géptermi (L)) lesz. A részleges vizsga jegye RV = [(Í + L + H1)/3].
4. A szesszióban írásbeli és géptermi vizsga lesz. A téli szessziób jegye (TV) = [(Í + L + H2)/3]. A végleges vizsga jegye: VV = [(RV + TV)/2].
5. Átlagok csak átmenő érdemjegyek esetében számolandók.
6. É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.).   	

IX. Kiegészítő könyvészet
1. Brassard G., Bratley P. – Algorithmics – Theory and Practice, Prentice-Hall, Inc, 1988.
2. Horowitz, E., Sahni, S. – Fundamentals of Computer Algorithms, Computer Science Press, 1978.
3. Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002 (könyvtár).
4. Bălan, G., Giurgea, M., Ionescu C. – Informatică pentru grupele de excelenţă, clasa a X-a, Editura Dacia, Cluj, 2003.	

	Dátum,						Eloadás felelőse,
								Lect. Dr. IONESCU Clara