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)

Mnacho ECHENIM

Contenu(s)

Systèmes d'inférence et logiques
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

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

    • MCC en présentiel **
      N1 = 1/4 CC + 3/4 examen écrit
      N2 = examen écrit
    • MCC en distanciel **
      N1 = 1/3 CC + 2/3 devoir à la maison
      N2 = examen écrit ou oral

Calendrier

Le cours est programmé dans ces filières :

cf. l'emploi du temps 2023/2024

Informations complémentaires

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

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

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