Babes-Bolyai University of Cluj-Napoca
Faculty of Mathematics and Computer Science
Study Cycle: Master
SUBJECT
| MO265 | Algorithmic Combinatorics |
| Teaching Staff in Charge |
Lect. ANDRAS Szilard Karoly, andrasz math.ubbcluj.ro |
| Aims |
|
We present some problems and recent results concerning arithmetical functions, prime numbers pseudo prime numbers and about special combinatorial problems. |
| Content |
|
Basic notions: divisors, primes, lcm, gcd, integer parts, motion of a billiard ball
Asymptotic formulas and complexity The Bertrand postulate and combinatorial algorithms for finding primes Arithmetical functions, the Mobius function, the inversion formula, Euler’s totient function, the number and the sum of divisors, Dirichlet convolutions and applications Arithmetical functions and algorithms Primes and pseudoprimes, Carmichael numbers Complexity of algorithms, the Euclidian algorithm |
| References |
|
1. AIGNER, M.-ZIEGLER, G. M.: Proofs from the BOOK, Springer Verlag, 1998.
2. BACH E.- SHALLIT, J.: Algorithmic number theory, Cambridge: MIT Press, 1996. 3. BRESSOUD, D.-WAGON, S.: A course in computational number theory, Springer Verlag, 2000. 4. ERDOS, P.-GRAHAM, R. L.: Old and new problems and results in combinatorial number theory, L. Enseigment Math., 1980. 5. GRAHAM, R. L.-KNUTH D, E-PATASHNIK, O.: Konkret matematika, Budapest: Műszaki Konyvkiado, 1998. 6. VAN LINT, J. H.-WILSON, R. M.: A course in combinatorics, Cambridge: Cambridge University Press, 2001. 7. ANDRÁS SZILÁRD: Dinamikus rendszerek, Editura didactica si pedagogica, 2008 8. J.G. MICHAELS, J.L. GROSS, J.W. GROSSMAN, D.R. SHIER: Handbook of discrete and combinatorial mathematics, CRC Press, 1999 9. H.S.WILF: Algorithms and complexity, www.math.upenn.edu/~wilf/AlgoComp.pdf 1994 |
| Assessment |
|
Activity (courses and seminars): 30% Project: 30% Final exam 40% If a student’s absentees is greater than 40% from the number of all activities, the student has to prepare a special presentation (paper) in a subject specified by the professor. |
| Links: | Syllabus for all subjects Romanian version for this subject Rtf format for this subject |