Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
FIŞA DISCIPLINEI

Codul	Disciplina	
MO265	Combinatorică algoritmică	

Specializarea	Semestrul	Ore: C+S+L	Categoria	Statutul	
Matematică Computatională - în limba maghiară	2	2+2+0		obligatorie	

Titularii de disciplină	Conf. Dr. BEGE Antal, bege@math.ubbcluj.ro	
Obiective	Prezentarea problemelor de baza si a problemelor actuale din combinatorica algoritmica
si din teoria algoritmica a numerelor.	
Conţinutul	1. Notiuni fundamentale
   Functia parte intreaga
   Complexitatea algoritmilor
2. Numere prime
   Formule asimptotice
   Postulatul lui Bertrand
   Proprietatea combinatorica al lui Bertrand
   Algoritmi de gasirea numerelor prime
   Cateva probleme asupra numerelor prime
3. Functii aritmetice
   Functia lui Mobius
   Functia lui Euler
   Numarul divizorilor si suma lor
   Formula de convolutie al lui Dirichlet
   Algoritmi asupra functiilor aritmetice
4. Numere perfecte si numere pseudoprime
   Numere perfecte si superperfecte
   Numere pseudoperfecte si numere Charmichael generalizate
5. Algoritmi de combinatorica
   Grafuri de Bruin
   Cuvinte Dyck si Motzkin
6. Complexitatea unor algoritmi
   Algoritmul lui Euclid
   Algoritmul AKS
	
Bibliografie	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: Muszaki Konyvkiado, 1998.
9. VAN LINT, J. H.-WILSON, R. M.: A course in combinatorics., Cambridge: Cambridge University Press,  2001.
	
Evaluare	30% rezolvari de probleme, 30% prezentarea unei lucrari, 40% examen