Mathématiques discrètes

Enseignants

Saerens Marco;

Langue
d'enseignement

Français

Préalables

Ce cours suppose acquises les notions d'algèbre  visées par le cours LINFO1112

Le(s) prérequis de cette Unité d’enseignement (UE) sont précisés à la fin de cette fiche, en regard des programmes/formations qui proposent cette UE.

Thèmes abordés

Théorie des ensembles

• Rappels des notations et opérations ensemblistes
• Relations binaires entre ensembles : applications et lien avec les fonctions en analyse
• Cardinalité d'un ensemble (fini et infini) et notion d'inclusion-exclusion
• Equivalence, classes d'équivalence

Logique

• Introduction à la logique des propositions
• Introduction à la logique des prédicats
• Méthodes de preuve
• Induction mathématique
• Notions d'algèbre de Boole

Introduction à la théorie des nombres

• Nombres entiers naturels, principe de récurrence, nombres premiers, etc
• Division euclidienne, représentation dans une base, arithmétique modulo, représentation des entiers dans l'ordinateur
• Pcgd, algorithme d'Euclide
• Notions élémentaires de cryptographie

Combinatoire

• Comptage
• Permutations
• Arrangements
• Relations de récurrence
• Solutions d'équations de récurrence

Introduction à la théorie des graphes

• Graphes orientés et non orientés et leurs représentations matricielles
• Graphes bipartites et problèmes de matching
• Chemins sur un graphe et circuits Eulériens/Hamiltoniens
• Graphes planaires et coloriage
• Problèmes de plus court chemin
• Classement des noeuds d'un graphe : PageRank

Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :
1	Eu égard au référentiel AA du programme « Bachelier en sciences informatiques », ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants : S1.I1, S1.G1 S2.2 Les étudiants ayant suivi avec fruit ce cours seront capables de : Utiliser à bon escient la terminologie des fonctions, relations et ensemble et réaliser les opérations associées lorsque le contexte le nécessite Expliciter la structure de base des principales techniques de preuve (preuve directe, contrexemple, preuve par l'absurde, induction, récurrence) Appliquer les différentes techniques de preuve de manière convaincante en sélectionnant la plus adaptée au problème posé Analyser un problème pour déterminer les relations de récurrence sous-jacentes Calculer des comptages, permutations, arrangements sur des ensembles dans le cadre d'une application. Modéliser divers problèmes du monde réel rencontrés en informatiques en utilisant les formes appropriées de graphes Expliquer le problème du plus court chemin dans un graphe et appliquer des algorithmes classiques pour résoudre ce problème

Méthodes d'enseignement

Environ 30 heures de cours magistraux en présentiel ou distanciel selon les conditions.
Un projet/cas d'étude obligatoire portant sur l'implémentation et l'application d'un ouplusieurs algorithmes.

Modes d'évaluation
des acquis des étudiants

• Un projet/cas d'étude obligatoire comptant pour 2 à 4 points sur 20 (spécifié en début d'année académique). Si le projet n'est pas remis, l'étudiante ou l'étudiant obtiendra 0/3 pour ce projet.
• Un examen écrit organisé en session comptant pour 18 à 16 points sur 20 (spécifié en début d'année académique). En présentiel ou distanciel, selon la situation.

Concernant le projet/cas d'étude obligatoire et l'utilisation d'IA de type Chat GPT, assurez-vous que "En soumettant un travail pour évaluation, vous affirmez : (i) qu'il reflète fidèlement le phénomène étudié, et pour cela vous devez avoir vérifié les faits, surtout s'ils sont prétendus par une IA générative (dont vous devez mentionner explicitement l’utilisation en tant qu’outil de soutien à la réalisation de votre travail) ; (ii) avoir respecté toutes les exigences spécifiques du travail qui vous est confié, notamment les exigences pour la transparence et la documentation de la démarche scientifique mise en œuvre. Si l'une de ces affirmations n'est pas vraie, que ce soit intentionnellement ou par négligence, vous êtes en défaut de votre engagement déontologique vis-à-vis de la connaissance produite dans le cadre de votre travail, et éventuellement d’autres aspects de l’intégrité académique, ce qui constitue une faute académique et sera considéré comme tel".

Ressources
en ligne

Voir Moodle

Bibliographie

Rosen K., Discrete mathematics and its applications, 8th edition, 2019. Mc Graw Hill.

Support de cours

• Slide du cours
• Textbook "Mathématiques discrètes" de K. Rosen

Faculté ou entité
en charge

INFO