Babeş-Bolyai Tudományegyetem Kolozsvár
Matematika és Informatika Kar
Képzési szint: mesteri
Doménium: informatika
Szak: Informatikai rendszerek optimalizálása 
Előadás nyelve: Magyar
SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MMC1010	Sztochasztikus keresési módszerek	

Félév	Órák: C+S+L	Kategória	Típus	
1	2+0+2	Szak	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	
Soós Anna	Dr.	docens	Numerikus analízis és statisztika	*		*	

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
A sztochasztikus keresési módszerek és algoritmusok megismerése. A kereső algoritmusok implementálása és felhasználása  valós feladatok megoldására. 	

IV. A tantárgy tartalma
1.	A valószínűségszámítás elemei
2.	Sztochasztikus folyamatok
3.	Sztochasztikus keresés és optimalizálás elemei
4.	Globális és lokális minimum
5.	Determinisztikus keresés
6.	Sztochsztikus keresési algoritmusok: szimulált hűtés, tabukeresés, genetikus algoritmusok, evolutív programozás. Keresés fában, becsléses keresés
7.	Alkalmazások 
8.	Markov lánc Monte Carlo módszerek.

V. Könyvészet
1.	A. Almos, S. Gyori, G. Horvath, A. Koczy: Genetikus algoritmusok, Typotex, 2002
2.	Thomas Bäck. Evolutionary algorithms in theory and practice. OxfordUniversity Press, New York, 1996.
3.	M. Mitzenmacher, E. Upfal: Probability and Computing, Cambridge University Press, 2005  
4.	A. Noga: The probabilistic method, Wiley,  2001
5.	H.P. Schwefel. Evolution and Optimum Seeking. Wiley, 1995.
6.	 A. Soós:  A valószínűségszámítás elemei, Egyetemi Kiadó, Kolozsvár, 2001  
7.	J.C. Spall: Introduction to Stochastic Search and Optimization, Amazon, 2002

VI. Az oktatói tevékenység heti tematikája
1.	A valószínűségszámítás elemei: a valószínűség fogalma, valószínűségi változó, folytonos és diszkrét eset, Véletlenszámok.
2.	A nagy számok törvényei, gyenge és erős törvények. Határeloszlás tételek.
3.	Sztochasztikus folyamatok. Markov láncok. Gauss folyamatok.
4.	A sztochasztikus keresés és optimalizálás elemei
5.	Lokális és globális optimum. Számítógépes szimulálás. Heurisztikák.
6.	Determinisztikus optimalizálás: legkisebb négyzetek módszere, gradiens módszer, grafikus megoldás.
7.	Optimalizáló algoritmusok. Az algoritmusok konvergenciája.
8.	Direkt  sztochasztikus keresési algoritmusok. Sztochasztikus gradiens módszer.
9.	Szimulált hűtés. Metropolis algoritmus. A szimulált hűtés algoritmusának konvergenciája. Optimalizálás szimulált hűtéssel.
10.	Genetikus algoritmusok. Genetikus operátorok. Sémák. Az algoritmus konvergenciája.
11.	Evolutív stratégiák. Evolutív programozás.
12.	Más keresési algoritmusok: Tabukeresés. Keresés fákkal. Becslésés optimalizálás. 
13.	Alkalmazások: TSP, hátizsák feladat, szimulált hozzárendelés.
14.	Markov lánc Monte Carlo módszerek.	

VII. Alkalmazott didaktikai módszerek
Előadás, felfedeztetés, egyéni munka
Felhasznált software: MATLAB	

VIII. Értékelés
3 db laborgyakorlat bemutatása 3o%, projektkészítés és bemutatás 7o%	

IX. Kiegészíto könyvészet

1.	 T. Bäck, F. Hoffmeister, and H. Schwefel. A survey of evolution strategies. In Belew and Booker editors. The Proceedings of the Fourth International Conference on Genetic Algorithms. Morgan Kaufmann, 1991.
2.	 R. K. Belew and M. D. Vose, editors. Foundations of Genetic Algorithms IV. Morgan Kaufmann, 1997.
3.	 A. E. Eiben and J. K. van der Hauw. Graph coloring with adaptive genetic algorithms. Journal of Heuristics, 4(1), 1998.
4.	 David B. Fogel. Evolutionary Computation. IEEE Press, 1995.
5.	P. Medvegyev: Sztochasztikus  analízis, Typotex, 2004
6.	A.N. Shiryaev, Probability, Springer, 1996
7.	M. D. Vose. The simple genetic algorithm: foundations and theory. MIT Press, 1998.
8.	L. D. Whitley, editor. Foundations of Genetic Algorithms II. Morgan Kaufmann, 1993.
9.	L. D. Whitley and M. D. Vose, editors. Foundations of Genetic Algorithms III. Morgan Kaufmann, 1995.
10.	M. Yagiura and T Ibaraki. Genetic and local search algorithms as robust and simple optimization tools. In Osman and Kelly editors. Meta-Heuristics: Theory and Application. pages 63—82, Kluwer Academic Publishers,1996	

	Dátum 2008.09.21.					Előadás felelőse,
								dr. Soós Anna, docens

Tanszékvezető					Dékán
dr. Petru Blaga egyetemi tanár			dr. Leon Ţămbulea egyetemi tanár