Mathématiques discrètes

linfo1114  2019-2020  Louvain-la-Neuve

Mathématiques discrètes
Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 15.0 h
Q2
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
 

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
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 [60] en sciences informatiques

Master [120] en sciences informatiques

Bachelier en sciences informatiques

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