Mathématiques discrètes

5.00 crédits

30.0 h + 15.0 h

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 :

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 des conditions.
Un projet/cas d'étude obligatoire portant sur l'implémentation d'un algorithme.

Modes d'évaluation
des acquis des étudiants

Un projet/cas d'étude obligatoire comptant pour 3 points sur 20. 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 17 points sur 20. En présentiel ou distanciel, selon la situation.

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
Mathématiques discrètes de K. Rosen

Faculté ou entité
en charge

INFO

Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme

Sigle

Crédits

Prérequis

Acquis
d'apprentissage

Master [120] en science des données, orientation statistique

DATS2M

Bachelier en sciences informatiques

SINF1BA

LINFO1112