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

I.	A tantárgy adatai

A tantárgy neve: A PROGRAMOZÁS ALAPJAI
Kód: MID0001
Kreditszám: 6
Hol tartják?  (előadás, szeminárium, laboratórium):
Mikor tartják? (előadás, szeminárium, laborató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
Laborató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
•	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
•	Bizonyos feladatosztályokhoz tartozó feladatok megoldási algoritmusainak 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 programok segítségével
•	A legfontosabb programozási módszerek (fejlett 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 

Tartalom
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 ellenőrzése (fekete doboz módszere, átlátszó doboz módszere)
6. Rendezési algoritmusok (buborékrendezés, egyszerű felcseréléses rendezés, válogatásos rendezés, minimum/maximum kiválasztásra épülő rendezés,beszúró rendezés, leszámláló rendezés, számjegyes rendezés) 
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

Kompetenciák
A tantárgy tanulmányozása és elsajátítása után a hallgató:
•	Képes lesz fegyelmezetten, logikusan és főleg algoritmikusan gondolkozni.
•	Rendelkezni fog a strukturált programozást illető alapvető szokásrendszerrel, és könnyen és helyesen fogja alkalmazni a moduláris programtervezés, valamint a top-down és bottom-up programtervezés alapszabályait
•	Kialakítja az algoritmusok elemzéséhez és tervezéséhez szükséges készségeket 
•	Elsajátítja az algoritmusok tesztelését illető módszereket, valamint az algoritmusok helyességének bizonyítási módszereit
•	Felismeri a klasszikus feladatosztályokat, amelyeket képes lesz megoldani különböző programozási módszerekkel: visszalépéses keresés, oszd meg és uralkodj, mohó algoritmusok, heurisztikus mohó algoritmusok 
•	Elsajátítja a programok dokumentálásának alapszabályait 

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. – 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.	Frenţiu M., Lazăr Ioan – Bazele programării, Proiectarea algoritmilor, Editura Universităţii Petru Maior, Tg. Mureş, 2000 (könyvtár).
5.	Kása Z. – Algoritmusok tervezése, Stúdium Könyvkiadó, Kolozsvár, 1994 (könyvtár).
6.	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).
7.	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).

V.	 Az oktatásban használt eszközök:
Számítógép, laboratóriumi felszerelések, Interneten elérhető forrásmunkák, cikkek, demo-programok, oktatószoftverek.

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

Előadások, szemináriumok és laboratóriumi gyakorlatok
(Az oldalszámok Ionescu Klára „Bevezetés az algoritmikába” című egyetemi jegyzetéből valók)

1. előadás, szeminárium és labor: 
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 adott pontban, polinomok összege, polinomok 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
	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.5.	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: útazóügynök, gráfszínezés, összegkifizetés legkevesebb számú bankjeggyel	276
	10.5.	Szemináriumon és laboron: kitűzött feladatok	282

A hallgatók hétről hétre megoldják a kitűzött feladatokat. 

VII.		Az értékelés módja:
-	A házi feladatokat minden hallgatónak 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 és géptermi), a szesszióban írásbeli és géptermi vizsga 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.).   
-	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). 
-	A részleges vizsga jegye (RV): Round((írásbeli + laborvizsga + H1)/3)
-	A téli szesszióban (TV): Round((írásbeli + laborvizsga + H2)/3)
-	A végleges vizsga jegye: Round((RV + TV)/2)

VIII.		Szervezési kérdések, a különleges esetek kezelése:
1.	Előadásra nem kötelező, szemináriumra és laborra kötelező járni. 
2.	Vizsgára csak azok jelentkezhetnek akik legtöbb háromszor hiányoztak szemináriumról és legtöbb háromszor laborró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.	Baase S. – Computer Algorithms, Addison-Wesley, 1983.
2.	Bălan, G., Giurgea, M., Ionescu C. – Informatică pentru grupele de excelenţă, clasa a X-a, Editura Dacia, Cluj, 2003.
3.	Brassard G., Bratley P. – Algorithmics – Theory and Practice, Prentice-Hall, Inc, 1988.
4.	Ionescu E., Haidu, S., Vaida D. – Informatică pentru grupele de excelenţă, clasa a IX-a, Editura Dacia, Cluj, 2003.
5.	Kása Z. – Algoritmusok tervezése, Stúdium Könyvkiadó, Kolozsvár, 1994.
6.	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.
7.	Rónyai, L., Ivanyos, G., Szabó, R. – Algoritmusok, Typotex, Budapest, 1999.
8.	Wirth N. – Algorithms + Data Structures = Programs, Prentice Hall Inc., 1976.
9.	Sedgewick R. – Algorithms in C++, Addisson-Wesley, 1992.
10.	Storer, J.A. – An Introduction to Data Structures and Algorithms, Birkhauser Springer 2002.