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

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MID0001	A programozás alapjai	

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

II. Főá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. 	Lect.	Társult	*			

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élkitűzései
1. Az algoritmus fogalmának megértése, az algoritmusok ábrázolási módozatainak elsajátítása 
2. Az algoritmusok tervezéséhez szükséges készségek kialakítása, a fegyelmezett, logikus és algoritmikus gondolkozás kialakítása
3. 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
4. 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.
5. A megtervezett algoritmusok implementálása egyszerű Pascal programok segítségével
6. 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
7. Helyes, átlátható programozási stílus kialakítása, a dokumentálás alapszabályainak megismerése	

IV. A tantárgy tartalma
1. A számítógépes feladatmegoldás lépései
- Az algoritmus fogalma
- Algoritmusok ábrázolása folyamatábrák és pszeudokód nyelvek segítségével
- A strukturált programozás alapelvei
- A feladatok számítógépes megoldásához fűződő általános kérdések 
2. Lépések finomítása
3. Programozási tételek 
4. Alprogramok (top-down típusú programozás, bottom-up programozás, moduláris algoritmustervezés)
5. Algoritmusok helyességének tesztelése (fekete doboz módszere, átlátszó doboz módszere)
6. Rendezési algoritmusok ( négyzetes és lineáris bonyolultságú rendezések) 
7. Rekurzió (közvetlen és közvetett rekurzió)
8. A visszalépéses keresés módszere (backtracking) 
9. Az oszd meg és uralkodj módszer (divide et impera) 
10. Mohó algoritmusok (greedy módszer) és heurisztikus mohó algoritmusok	

V. Könyvészet
1. Ionescu K. – Bevezetés az algoritmikába, Presa Universitară Clujeană, 2005 (könyvtár).
2. Cormen T., Leiserson C., Rivest R. – Algoritmusok, Műszaki Könyvkiadó, Budapest, 1997 (könyvtár).
3. Cormen T., Leiserson C., Rivest R., Stein, C. – Új algoritmusok, Scolar, Budapest, 2003 (könyvtár).
4. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, (könyvtár).
5. Kása Z. – Algoritmusok tervezése, Stúdium Könyvkiadó, Kolozsvár, 1994 (könyvtár).
6. Baase S. – Computer Algorithms, Addison-Wesley, 1983 (könyvtár).
7. 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.
8. Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.	

VI. Az oktatói tevékenység heti tematikája
1. előadás, szeminárium és labor: 
(Az alábbi oldalszámok Ionescu Klára, Bevezetés az algoritmikába című jegyzetéből valók.)
A számítógépes feladatmegoldás lépései
	1.1. A programozói tevékenység	13
	1.2. A feladatmegoldás lépései számítógépes környezetben	14
	1.3. Alkalmazások minőségi szempontjai	16
Az algoritmusok ábrázolása	17
	2.1. Algoritmusok	17
		2.1.1. Az algoritmus fogalma	17
		2.1.2. Az algoritmusok leírásánál használt elemek	19
	2.2. Algoritmusok ábrázolása folyamatábrák és pszeudokód nyelvek segítségével	24

2. előadás, szeminárium és labor:
	2.3. A strukturált programozás alapelvei	27
		2.3.1. Lineáris struktúrák	28
		2.3.2. Elágazási struktúrák	28
		2.3.3. Ismétlő struktúrák	29
		2.3.4. Az alapstruktúrák jelölése pszeudokódban	33
		2.3.5. Egyszerű alapszabályok	37
	2.4. A feladatok számítógépes megoldásához fűződő általános kérdések	38
		2.4.1. Algoritmusok helyessége	39
		2.4.2. Az algoritmus végrehajtásához szükséges idő	42
		2.4.3. Az algoritmus által feldolgozott adatok számára szükséges memória mérete	47
		2.4.4. Algoritmusok egyszerűsége	47
		2.4.5. Algoritmusok optimalitása	47
		2.4.6. Algoritmusok létezése	49
	2.5. Szemináriumon és laboron: feladatok (felcserélés, maximumérték, elnökválasztás stb.)	49

3. előadás, szeminárium és labor:
Lépések finomítása	57
	3.1. Bevezetés	57
	3.2. Megoldott feladatok: Eukleidész algoritmusa, prímszámok, Fibonacci-számok, háromszög, fordított szám, törzstényezők, konverzió, gyors hatványozás	57
	3.3. Szemináriumon és laboron: kitűzött feladatok	79

3.-4. előadás, szeminárium és labor:
Programozási tételek	83
	4.1. Bevezetés	83
	4.2. Egyszerű programozási tételek	83
		4.2.1. Összeg és szorzat	83
		4.2.2. Döntés	86
		4.2.3. Kiválasztás	89
		4.2.4. Szekvenciális (lineáris) keresés	90
		4.2.5. Megszámlálás	94
		4.2.6. Minimum- és maximumkiválasztás	95
		4.2.7. Kiválogatás	98
	4.3. Összetett programozási tételek	100
		4.3.1. Szétválogatás	100
		4.3.2. Sorozat halmazzá alakítása	104
		4.3.3. Keresztmetszet	105
		4.3.4. Egyesítés	107
		4.3.5. Összefésülés	108
	4.4. Szemináriumon és laboron: kitűzött feladatok	111

5. előadás, szeminárium és labor:
Alprogramok	127
	5.1. Bevezetés	127
	5.2. Algoritmusok és programok fejlesztési módozatai	129
		5.2.1. A top-down típusú (fentről lefele) programozás	129
		5.2.2. A bottom-up (lentről felfele) programozás	129
		5.2.3. Moduláris algoritmustervezés	130
	5.3. A moduláris programozás alapszabályai	134
		5.3.1. Moduláris dekompozíció	134
		5.3.2. Moduláris kompozíció	135
		5.3.3. Modulok tulajdonságai	135
		5.3.4. A modularitás alapelvei	135
	5.4. Algoritmusok tesztelése	136
		5.4.1. A fekete doboz módszere	136
		5.4.2. Az átlátszó doboz módszere	137
	5.5. Megoldott feladatok: polinom értéke, polinomok összege és szorzata, determináns	138
	5.6. Szemináriumon és laboron: kitűzött feladatok	144

6. előadás, szeminárium és labor:
Rendezési algoritmusok	151
	6.1. Bevezetés	151
	6.2. Összehasonlításos rendezési módszerek	151
		6.2.1. Buborékrendezés (Bubble-sort)	151
		6.2.2. Egyszerű felcseréléses rendezés	155
		6.2.3. Válogatásos rendezés	155
		6.2.4. Minimum/maximum kiválasztásra épülő rendezés	157
		6.2.5. Beszúró rendezés	157
	6.3. Rendezések lineáris időben	158
		6.3.1. Leszámláló rendezés (ládarendezés, Binsort)	159
		6.3.2. Számjegyes rendezés (Radix-sort)	159
	6.4. Szemináriumon és laboron: részleges vizsga az eddig tanultakból (írásbeli és számítógépen)

7. előadás, szeminárium és labor:
Rekurzió	 163
	7.1. Bevezetés	163
	7.2. Közvetlen rekurzió	165
	7.3. Megoldott feladatok: egy szó betűinek megfordítása, szavak sorrendjének megfordítása, faktoriális, legnagyobb közös osztó, számjegyösszeg, Descartes-szorzat, k elemű részhalmazok, konverzió, Fibonacci-sorozat, a {0, 1, 2} halmaz elemeivel generált sorozatok, az {1, 2, ..., n} halmaz valamennyi részhalmaza, partíciók, halmazpartíciók, kamatos kamat	168
	7.4. Szemináriumon és laboron: kitűzött feladatok	185

8-9-10. előadás, szeminárium és labor:
A visszalépéses keresés módszere (backtracking)	187
	8.1. Bevezetés	187
	8.2. A visszalépéses keresés általános bemutatása	188
		8.2.1. Iteratív algoritmus	189
		8.2.2. Rekurzív algoritmus	190
		8.2.3. Megoldott feladatok: 8 királynő a sakktáblán, variációk, zárójelek, legrövidebb utak, játékok, szürjektív függvények	192
	8.3. A visszalépéses keresés bővítése	204
		8.3.1. Megoldott feladatok: S pénzösszeg kifizetése, összegkifizetés, minimum számú bankjeggyel	206
	8.4. Visszalépéses keresés a síkban	210
		8.4.1. Megoldott feladatok, labirintus, fénykép, legnagyobb méretű tárgyak	210
	8.5. Szemináriumon és laboron: kitűzött feladatok	216

11-12. előadás, szeminárium és labor:
Az oszd meg és uralkodj módszer (divide et impera)	223
	9.1. Bevezetés	223
	9.2. Az oszd meg és uralkodj módszer általános bemutatása	223
	9.3. Megoldott feladatok: szorzat, minimumszámolás, hatványozás, bináris keresés, összefésülésen alapuló rendezés, gyorsrendezés, Hanoi tornyok, úszómedence	224
	9.4. Szemináriumon és laboron: kitűzött feladatok	245

13-14. előadás, szeminárium és labor:
Mohó algoritmusok (greedy módszer)	249
	10.1. Bevezetés	249
	10.2. A mohó algoritmus általános bemutatása	250
	10.3. Megoldott feladatok: összeg, az átlagos várakozási idő minimalizálása, buszmegállók, autó bérbeadása, hátizsák, minimális feszítőfák (Kruskal és Prim), minimális hosszúságú utak (Dijkstra algoritmusa)	252
	10.4. Heurisztikus mohó algoritmusok	276
		10.4.1. Megoldott feladatok: utazóügynök, gráfszínezés, összegkifizetés legkevesebb számú bankjeggyel	276
	10.5. Szemináriumon és laboron: kitűzött feladatok	282	

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ó 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. Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002 (könyvtár).
3. Wirth N. – Algorithms + Data Structures = Programs, Prentice Hall Inc., 1976.
4. Avornicului M., Buzogány L., Lukács S., – Informatika, tankönyv a IX. osztály számára, Ábel könyvkiadó, Kolozsvár, 2002–2006 (Ábel könyvkiadó: K-vár, Eremia Grigorescu 35 sz).
5. Avornicului M., Buzogány L., Lukács S., – Informatika, tankönyv a X. osztály számára, Ábel könyvkiadó, Kolozsvár, 2002–2006 (Ábel könyvkiadó: K-vár, Eremia Grigorescu 35 sz).
6. Ionescu E., Haidu, S., Vaida D. – Informatică pentru grupele de excelenţă, clasa a IX-a, Editura Dacia, Cluj, 2003.
7. Bălan, G., Giurgea, M., Ionescu C. – Informatică pentru grupele de excelenţă, clasa a X-a, Editura Dacia, Cluj, 2003.	

	Dátum,						Előadás felelőse,
2010-11-25						Dr. IONESCU Klára, adjunktus