LI214: Structures Discrètes

Ceci est l'ancienne page de LI214, où vous trouverez des informations d'ordre pédagogique ; les informations récentes d'horaires et de nouvelles se trouvent site officiel

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 11 semaines. Elle a lieu au premier et au second semestres. Les informations, erreurs, omissions de cette page sont la responsabilité de Irène Guessarian.

La note finale est calculée à comme suit : le maximum entre la note d'examen ET la note d'examen pondérée par le controle continu ( note d'examen (60%) et note de contrôle continu (40%) ), soit en formule : MAX (note-exam, [0,6note-exam +0,4note-controlecontinu] ) ; voir Règlement officiel. La note de contrôle continu (non obligatoire) se composera de 3 notes (si vous êtes absent à un contrôle, la note correspondant à cette absence est 0)  une note de partiel (50%), une note de devoir en TD (35%) et une note de TME (15%).

Répartition. Cours: 1h30 .     TD: 3h30 les cinq premières semaines.     TD: 1h45, TP: 1h45 à partir de la sixième semaine de TD.

UN FORUM EST ACCESSIBLE POUR VOS QUESTIONS: http://www.liafa.jussieu.fr/~ig/l2/forum/ ET VOS RECLAMATIONS

Le Forum n'est plus utilisable.

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 : aucuns.

Buts :

Ces buts sont largements repris dans les unités de niveau (300) de spécialisation, dont voici quelques exemples :

Les arbres, vus dans le chapitre sur l'induction, sont par ailleurs implémentés en C, dans l'unité LI215 (Programmation impérative et structures de données en C) ...

[ Vous pouvez aussi consulter la définition officielle de l'unité LI214. ]

Contenu indicatif par semaine

  1. Définitions inductives d'ensembles et de structures.
  2. Définitions inductives de structurefonctions.
  3. Preuves (directes, par l'absurde, par induction, ...) ; exemples.
  4. Ensembles, relations, fonctions.
  5. Ensembles ordonnés, cardinalité : ensembles finis et dénombrables.
  6. Récursivité, terminaison, ordres bien fondés.
  7. Calcul Booléen.
  8. Calcul Propositionnel.
  9. Introduction au calcul des prédicats.
  10. Automates finis; opérations sur les automates finis. Langages reconnaissables et langages réguliers.
  11. Système d'équations associé à un automate fini; expressions rationnelles langages rationnels. Théorème de Kleene.
  12. Minimisation d'automates.

Bibliographie

Pour plus d'informations, veuillez vous reporter à l'emploi du temps du L2 Informatique.

Ressources

Annales

Tous les sujets d'examen ou de partiel sont fournis avec un corrigé. Je remercie Pierre Takla (promotion 2009), Mélina Gallopin et Chourouk Ghorbel, promotion 2007, qui ont trouvé et m'ont signalé plusieurs erreurs dans les corrigés.

Maquette par Jérémie Lumbroso.

Site miroir.