Ensimag Rubrique Formation 2022

Fondements logiques pour l'informatique - 4MMFLI

  • Volumes horaires

    • CM 16.5
    • Projet -
    • TD 16.5
    • Stage -
    • TP -
    • DS -

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

Ce cours a pour but de présenter aux élèves certaines notions fondamentales de Logique,qui sont fréquemment employées en informatique. Les élèves y voient entre autre les notions formelles de preuves et de modèles, ainsi que certains liens entre l'expressivité d'une logique et sa décidabilité. L'accent est mis sur la logique propositionnelle et sur la logique du premier ordre, mais quelques notions avancées comme la Satisfaisabilité Modulo des Théories sont également introduites.

Responsable(s)

Nicolas PELTIER, Mnacho ECHENIM

Contenu(s)

Logique propositionnelle

  • Normalisation, forme normale conjonctive, renommée
  • Systèmes d'inférence par réfutation, Résolution
  • Théorème de compacité, algorithme DPLL
    Logique du premier ordre
  • Syntaxe et sémantique
  • Théorème de Herbrand, Skolémisation
  • Calcul de Résolution
  • Clôture de congruence, Satisfaisabilité Modulo des Théories
  • Autres logiques pour l'informatique

Prérequis

Mathématiques discrètes (définition d'un langage, définitions et preuves par induction structurelle)
Notions de base de théorie des ensembles (opérations ensemblistes de base, définition ensembliste d'une fonction, d'une relation...)

Contrôle des connaissances

Evaluation : 25% de Devoir à la maison et 75% de Examen Ecrit (2h)

Rattrapage : Examen Ecrit (2h)

CONTRÔLE CONTINU :
Type d'évaluation (ex : TP, assiduité, participation) :
DM

SESSION NORMALE :
Type d'examen (écrit, oral, examen sur machine) :
écrit
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : une feuille A4 recto-verso manuscrite
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : tout matériel électronique
    Commentaires :

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : écrit
Salle spécifique :
Durée : 2h
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : une feuille A4 recto-verso manuscrite
Documents interdits (ex : livres, tous documents) :
Matériel (ex : calculatrices):

  • matériel autorisé, préciser :
  • matériel interdit, préciser : tout matériel électronique

Calendrier

Le cours est programmé dans ces filières :

cf. l'emploi du temps 2025/2026

Informations complémentaires

Code de l'enseignement : 4MMFLI
Langue(s) d'enseignement : FR

Le cours est rattaché aux structures d'enseignement suivantes :

  • Equipe Bases théoriques de l'informatique

Vous pouvez retrouver ce cours dans la liste de tous les cours.

Bibliographie

T. Boy de la Tour, M. Echenim: Eléments du cours de Logique 2A Ensimag
R. Caferra: Logique pour l'informatique et pour l'intelligence artificielle. Editions Hermès - Lavoisier