Ensimag Rubrique Formation 2022

Logique pour l'informatique - 3MM1LPI

  • Volumes horaires

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

    Crédits ECTS

    Crédits ECTS 3.0

Objectif(s)

La logique joue un rôle fondamental en informatique dans la spécification, construction et vérification des programmes, comme langage de programmation, dans son lien étroit avec la calculabilité. Elle joue aussi un rôle clé en intelligence artificielle, dans les bases de données, en probabilités, etc. L’objectif du cours est de donner les bases pour son utilisation dans les différents domaines.

Responsable(s)

Nils GESBERT

Contenu(s)

  • Première période : logique propositionnelle.
    1. Syntaxe des formules, symboles propositionnels, connecteurs, interprétations, tables de vérité.
    2. Notions de modèle, satisfaisabilité, validité d’une formule ; relation de conséquence logique.
    3. Formes normales.
    4. Systèmes formels. Déduction naturelle, système de Fitch
    5. Le problème SAT ; algorithme DPLL.
  • Troisième période : logique du premier ordre.
    1. Prédicats, fonctions, variables, quantificateurs.
    2. Interprétations, valuations, modèles, satisfaisabilité, validité, conséquence.
    3. Variables libres et liées, renommage ; formes normales.
    4. Système de Fitch au premier ordre.
    5. Théories du premier ordre.
    6. Propriétés des relations binaires : (anti)symétrie, (ir)réflexivité, transitivité
    7. Égalité
    8. Notions d’arithmétique de Peano et idée du théorème d’incomplétude de Gödel
    • Ce cours est donné en Période(s) Académique(s) 1 et 3 **

Prérequis

Néant

Contrôle des connaissances

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

  • matériel autorisé, préciser : aucun
  • matériel interdit, préciser : calculatrices
    Commentaires :
  • 1 examen écrit (2h) en fin de période 1 sur la logique propositionnelle (E1)
  • 1 examen écrit (2h) en fin de période 3 sur la logique du premier ordre (E2)
    la note E2 efface la note E1 si elle est supérieure, sinon c’est la moyenne des deux qui est prise en compte.

SESSION DE RATTRAPAGE :
Type d'examen (écrit, oral, examen sur machine) : oral
Salle spécifique : non
Durée : 40 mn
Documents autorisés (ex : aucun, résumé feuille A4 manuscrite, dictionnaires, tous documents) : tous documents
Matériel (ex : calculatrices):

  • matériel autorisé, préciser : aucun

Commentaires
Le rattrapage (E3) porte sur le programme des deux périodes et remplace l’ensemble de la note

N1 = max(E2, (E1 + E2)/2)
N2 = E3

Calendrier

Le cours est programmé dans ces filières :

  • Cursus ingénieur - Alternance - Alternance 1ere annee
cf. l'emploi du temps 2023/2024

Informations complémentaires

Code de l'enseignement : 3MM1LPI
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

Polycopié du cours, contenant les énoncés de tous les exercices à faire en TD ainsi que leurs corrigés
Course notes containing the solutions to all proposed problems.