L'unité d'enseignement « Structures discrètes » est
une UE de niveau (200) approfondissement relevant de la licence d'informatique.
Elle possède un volume de 6 ECTS et
s'étend sur 12 semaines. Elle est placée sous la responsabilité de GUESSARIAN, irène.
Description
Le but de cet enseignement est de donner les principes
de base de nature mathématique qui sont largement
utilisés dans la
plupart des domaines de l'informatique.
Après une introduction générale (ensembles, relations, fonctions, ensembles ordonnés, cardinalité),
on étudiera les définitions inductives, la récursivité,
puis la logique et enfin la théorie des automates finis et des langages reconnaissables.
Préalables et buts pédagogiques
Bibliographie
A. Arnold, I. Guessarian. Mathématiques pour l'Informatique. Dunod 2005.
K. H. Rosen. Discrete Mathematics and its applications.
Mc Graw Hill 1999.
Contenu indicatif par semaine
Ensembles, relations, fonctions.
Ensembles ordonnés, cardinalité :
ensembles finis et dénombrables.
Définitions inductives d'ensembles et de structures.
Preuves (directes, par l'absurde. par induction, ...) ; exemples.
Récursivité, terminaison, ordres bien fondés.
Calcul Booléen.
Calcul propositionnel.
Introduction au calcul des prédicats.
Automates finis; opérations sur les automates finis.
Expressions rationnelles et langages réguliers.
Système d'équations associé à un automate fini; langages reconnaissables.
Application des automates à la reconnaissance d'expressions rationnelles.
