Universitatea "Babes-Bolyai" Cluj-Napoca
Facultatea de Matematica si Informatica
FISA DISCIPLINEI

Combinatorică algoritmică
Cod
Semes-
trul
Ore: C+S+L
Credite
Tipul
Specializarea
MO265
2
2+2+0
9
obligatorie
Matematică Computaţională - în limba maghiară
Cadre didactice indrumatoare
Conf. Dr. BEGE Antal,  begemath.ubbcluj.ro
Obiective
Prezentarea problemelor de baza si a problemelor actuale din combinatorica algoritmica
si din teoria algoritmica a numerelor.
Continut
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