Course teacher(s)
Paolo SARACCO (Coordinator), Michele D'ADDERIO and Samuel FIORINIECTS credits
5
Language(s) of instruction
french
Course content
Mathematical proofs: techniques. Elementary counting: factorials, binomial and multinomial coefficients. Inclusion-exclusion formula. Linear recurrences. Non-linear recurrences, including "divide-and-conquer" recurrences and the Master Theorem. Orders and relations. Graphs and trees. Generating functions. Asymptotics, including Stirling's formula. Fibonacci, Catalan, Bernouilli and harmonic numbers. Elementary arithmetic.
Objectives (and/or specific learning outcomes)
After completing this teaching unit, the student will be able to:
- write proofs of mathematical statements;
- solve counting problems;
- estimate the asymptotic behavior of series, including in particular the solution of a "divide-and-conquer" equation.
- think formally about (or using) graphs and relations.
Prerequisites and Corequisites
Required and Corequired knowledge and skills
Required and corequired courses
Cours ayant celui-ci comme co-requis
Teaching methods and learning activities
Lectures. Exercise sessions.
References, bibliography, and recommended reading
- Lehman, Leighton and Meyer. Mathematics for Computer Science, 2018.
- Graham, Knuth and Patashnik, Concrete mathematics. Addison-Wesley, 1989.
- Cameron, Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press, 1994.
- Van Lint and Wilson, A Course in Combinatorics. Cambridge University Press 2001.
- Flajolet and Sedgewick, Analytic Combinatorics. Cambridge University Press 2009.
Course notes
- Syllabus
- Université virtuelle
Other information
Additional information
Contacts
Samuel Fiorini : Samuel.Fiorini@ulb.be
Campus
Plaine
Evaluation
Method(s) of evaluation
- Other
Other
A written exam will be organized on campus during the January exam session. The material for the exam is that of the lectures and the exercise sessions.
Language(s) of evaluation
- french