Topic outline

  • General

    Logo Télécom Bretagne

    INFORMATIQUE

    Logique et langages

    (Majeure Informatique 424)

    Eric Cousin et Yannis Haralambous

    La théorie des langages formels fait partie des fondements de l'informatique. Dans ce module nous abordons d'abord certaines notions de cette théorie : les automates d'états finis, les expressions régulières, les grammaires formelles, les traitements sémantiques.

    Dans une deuxième partie, nous abordons la logique formelle : principes, applications, techniques de résolution.

    Fiche présentation

  • This topic

    Langages formels

    Un langage est un ensemble de «mots» définis sur un «alphabet». Les expressions régulières (que l'on retrouve dans tous les langages de programmation modernes) sont un moyen de définir une classe particulière de langages, appelés langages réguliers. Les automates en donnent une description analytique (un mot appartient à un langage s'il peut être obtenu par une suite de transitions entre états de l'automate) et les grammaires formelles une description générative (un mot appartient à un langage s'il peut être obtenu par une suite de productions à partir d'un axiome de départ).
    Cette partie du module permet de :

    • comprendre les notions d'automate, de langage formel, d'expression régulière, de grammaire formelle ;
    • utiliser les expressions régulières dans plusieurs contextes
    • comprendre le principe de traitement sémantique et ses applications (compilation, transformation de document)

    Plus détails sur les objectifs d'apprentissages sont donnés dans un document spécifique.

  • Topic 2

    Logique

    La logique étudie les principes du raisonnement. Dans ce cours, nous allons nous restreindre à la logique des prédicats (tout en considérant la logique propositionnelle en tant que cas particulier).

    La logique des prédicats ou logique de premier ordre est une formalisation du langage des mathématiques. Elle utilise des fonctions, des variables, des prédicats, des connecteurs et des quantificateurs, assemblés en énoncés. Grâce à l'inférence on peut raisonner, c'est-à-dire obtenir de nouveaux énoncés à partir d'énoncés donnés. Néanmoins, ces opérations sont purement syntaxiques.

    L'utilité de la logique provient du fait que les énoncés peuvent être interprétés. Une interprétation est l'application d'un énoncé dans un domaine donné (qui peut faire partie des mathématiques ou du monde réel) et a alors une valeur de vérité. Une interprétation pour laquelle un énoncé est vrai est appelée un modèle de celui-ci. Ainsi, par le biais des modèles, les raisonnements logiques s'appliquent à des problèmes du monde réel.

    En guise d'application de cette partie du cours on s'intéressera à la formalisation et preuve de programmes informatiques.

    Cette partie du module permet de :

    • comprendre les notions de système formel, d'énoncé, de prédicat, d'inférence, d'interprétation, de modèle, de conséquence, de satisfaisabilité ;
    • appliquer des méthodes comme la CNF, la skolémisation, la résolution, pour déterminer si un énoncé est conséquence d'une base de connaissances
    • vérifier la correction d'un petit programme informatique.

    Un polycopié est distribué aux élèves.

    Creative Commons License
    Logique et langages, par Yannis HARALAMBOUS, est mis à disposition selon les termes de la licence Creative Commons Paternité-Pas d'Utilisation Commerciale-Partage des Conditions Initiales à l'Identique 2.0 France.