Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Matematica
Programul de studii: Matematică Computaţională (în limba maghiară)
Limba de predare: Maghiară

SYLLABUS

I. Általános adatok
Kód	Tantárgy neve	
MO265	Combinatorică algoritmică	

Félév	Órák: C+S+L	Kategória	Típus	
2	2+2+0		obligatorie	

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	
ANDRAS Szilard Karoly	Dr.	Lect.	Ecuaţii Diferenţiale	*	*		

III. A tantárgy célkituzései
Bevezetés az algoritmikus kombinatorika és a kombinatorikus számelmélet problémáiba	

IV. A tantárgy tartalma
1. Alapfogalmak:
Egészrész függvény, algoritmusok komplexitása
2. Prímszámok
Aszimptotikus forrmulák, a Bertrand posztulátum, a Bertrand-féle kombinatorikus tulajdonság, prímszámok megtalálása
3. Aritmetikai függvények
  Mobius függvény, Euler függvény, az osztók száma és összege, a Dirichlet konvolúció
Aritmetikai függvények és algoritmusok
4. Tökéletes számok, pszeudoprímek (álprímek)
Tökéletes és szupertökéletes számok, Charmichael és általánosított Charmichael számok
5. Kombinatorikus algoritmusok
   de Bruin gráfok
   Dyck és Motzkin szavak
6. Algoritmusok komplexitása
   Az Euklideszi algoritmus
   Az AKS algoritmus

V. Könyvészet

1. AIGNER, M.-ZIEGLER, G. M.:  Proofs from the BOOK,  Springer Verlag, 1998.
2. AIGNER, M.-ZIEGLER, G. M.:   Bizonyitasok a KONYVBOL, Budapest: Typotex, 2004.
3. BACH E.- SHALLIT, J.: Algorithmic number theory,  Cambridge: MIT Press,  1996.
4. BEGE, ANTAL: Beveztes a szamelmeletbe, Cluj Napoca: Scientia Kiado,  2002.
5. BEGE, ANTAL-DEMETER, ALBERT-LUKACS ANDOR: Szamelmeleti feladatgyujtemeny, Cluj Napoca: Scientia Kiado,  2002.
6. BRESSOUD, D.-WAGON, S.: A course in computational number theory, Springer Verlag, 2000.
7. ERDOS, P.-GRAHAM, R. L.: Old and new problems and results in combinatorial number theory, L. Enseigment Math., 1980.
8. GRAHAM, R. L.-KNUTH D, E-PATASHNIK, O.: Konkret matematika, Budapest: Műszaki Konyvkiado, 1998.
9. VAN LINT, J. H.-WILSON, R. M.: A course in combinatorics, Cambridge: Cambridge University Press,  2001.

VI. Az oktatói tevékenység heti tematikája

1. Alapfogalmak: osztók, lnko, lkkt, rácsok
2. Egészrész függvény, algoritmusok komplexitása
2. Prímszámok, aszimptotikus forrmulák
4. A Bertrand posztulátum, a Bertrand-féle kombinatorikus tulajdonság, prímszámok megtalálása
5. Mobius függvény, Euler függvény, az osztók száma és összege
6. A Dirichlet konvolúció
7. Aritmetikai függvények és algoritmusok
8. Tökéletes számok, pszeudoprímek (álprímek)
9. Tökéletes és szupertökéletes számok, Charmichael és általánosított Charmichael számok
10. Kombinatorikus algoritmusok, de Bruin gráfok
11. Dyck és Motzkin szavak
12. Algoritmusok komplexitása
13. Az Euklideszi algoritmus
14. Az AKS algoritmus

VII. Alkalmazott didaktikai módszerek

Előadás, problematizálás, modellezés, csoporttevékenység, projektmunka, Internet, projektor, számítógép, könyvtár	

VIII. Értékelés

30% feladatmegoldások, 30% házi dolgozat, 40% vizsga

Szervezési részletek, kivételes esetek kezelése:
Ha valaki a tevékenységek több mint 40%-áról hiányzott, akkor egy külön dolgozatot kell bemutatnia az oktató által kijelölt témából, a vizsgán való csalás a vizsgáról való kizárást vonja maga után.
	
IX. Kiegészíto könyvészet

ANDRÁS SZILÁRD: Dinamikus rendszerek, Editura didactica si pedagogica, 2008
J.G. MICHAELS, J.L. GROSS, J.W. GROSSMAN, D.R. SHIER: Handbook of discrete and combinatorial mathematics, CRC Press, 1999
H.S.WILF: Algorithms and complexity, www.math.upenn.edu/~wilf/AlgoComp.pdf 1994	

Elérhetőség (e-mail cím, esetleg telefonszám): andraszk@yahoo.com vagy andrasz@math.ubbcluj.ro  Tel: 0745561201
Fogadási óra: csütörtök 15-16, differenciálegyenletek tanszék, Mathematicum épülete

	Dátum, 28. 09. 2008						Előadás felelőse,
								Lect. Dr. ANDRÁS Szilárd Károly

Tanszékvezető,						Dékán,