Mathématiques discrètes

5 crédits

30.0 h + 15.0 h

Cette unité d'enseignement n'est pas dispensée en 2018-2019

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

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

Bachelier en sciences informatiques

SINF1BA

LINFO1112