Mathématiques discrètes

Techniques de preuve mathématique. Comptage élémentaire : factorielles, coefficients binomiaux et multinomiaux. Formule d'inclusion-exclusion. Récurrences linéaires. Récurrences non-linéaires, dont récurrences dites "diviser-pour-régner". Relations et ordres. Graphes et arbres. Fonctions génératrices. Comportements asymptotiques, dont formule de Stirling. Nombres de Fibonacci, de Catalan, de Bernouilli, harmoniques. Arithmétique élémentaire.

A l'issue de cette unité d'enseignement, un étudiant sera capable de :

• rédiger des preuves d'énoncés mathématiques;
• résoudre des problèmes de comptage;
• estimer le comportement asymptotique de suites, dont en particulier la solution d'une récurrence "diviser-pour-régner";
• mener une réflexion formelle au sujet et à l'aide de graphes et relations.

Connaissances et compétences pré-requises ou co-requises

 

Cours pré-requis

Cours ayant celui-ci comme co-requis

Cours magistral. Séances d'exercices.

Références, bibliographie et lectures recommandées

• Lehman, Leighton and Meyer. Mathematics for Computer Science, 2018.
• Graham, Knuth et Patashnik, Concrete mathematics, Addison-Wesley, 1989.
• Cameron, Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1994.
• Van Lint et Wilson, A Course in Combinatorics, Cambridge University Press 2001.
• Flajolet et Sedgewick, Analytic Combinatorics. Cambridge University Press 2009.

Support(s) de cours

• Université virtuelle

Informations complémentaires

 

Contacts

`Paolo SARACCO : paolo.saracco@ulb.be

Campus

Plaine

Méthode(s) d'évaluation

• Examen écrit

Examen écrit

Un examen écrit en présentiel sera organisé pendant la session de janvier, et un autre pendant la seconde session.

Cet examen écrit sera d'une durée d'environ 3h, et portera sur la théorie et les exercices du cours.

Construction de la note (en ce compris, la pondération des notes partielles)

Langue(s) d'évaluation

• français