Licence informatique
INVALIDE-Informatique théorique
Code apogéeDIFO4ITHStructurexxDernière mise à jour le04 Juillet 2017
Responsable pédagogiqueMONIN François (Maître de conférences, 27ème section)
Intervenants
Parcours
  • INVALIDE-Licence 2 - parcours informatique
  • INVALIDE-Licence 2 - parcours international
TypeObligatoire
Semestre4Volume horaire60Crédits ECTS6.5
Nombre d'heures Cours magistraux (CM)24 Travaux dirigés (TD)24 Travaux pratiques (TP)12 
Pré-requisNotions fondamentales de mathématiques (ensembles, relations, fonctions) et d'algorithmiques (Algorithmique et Programmation, S2).
Co-requis 
Objectif Terminal 
Objectif Pédagogique 
Contenu détaillé de l'enseignementSystèmes formels et logique des propositions  30h (CM 12 h, TD 12 h, TP 6 h)
Quelques aspects fondant une logique et un raisonnement 
  • Algèbre de Boole, opérateurs et fonctions  Booléennes
    • Raisonnement à partir des états vrai et faux, des opérateurs logiques courants et des fonctions logiques. Table de vérité.
    • Application aux différents modes de raisonnement (déductif, contraposé, par l’absurde).
    • Application aux circuits logiques élémentaires, Simplifier la  logique d’un circuit (algorithme de Quine). Résoudre des équations Booléennes ou comment, connaissant la fonction logique d’un circuit et l’état de ses sorties, pouvoir déterminer l’état des ses entrées 
  • Définition d’un système formel : S’exprimer dans un système formel et raisonner à partir de cette expression.
    • Définition inductive d’un langage et notation BNF, arbre syntaxique et arbre d’analyse associé à un mot. Définition d’une logique
    • Premiers exemples simples de systèmes formels.
    • Le système formel « calcul des propositions » et applications : Aspects syntaxiques et logique dans le calcul des propositions, sémantique, procédures de démonstration (fonctions de vérités, méthodes axiomatiques, déduction naturelle, séquents de Gentzen, résolution)
    • Les limites du calcul des propositions, introduction au calcul des prédicats
Récursion, induction, langages et automates 30h (CM 12 h, TD 12 h, TP 6 h)
  • Récursion et induction: principes d'induction, ensembles et fonctions définis inductivement, preuves par induction.
  • Langages formels: alphabets, mots, facteurs, ordres sur les mots, opérations ensemblistes et algébriques sur les langages, fermeture des langages, langages réguliers, expressions régulières.
  • Automates : automates déterministes et non déterministes, calculs d'un automate, langages reconnaissables, automates complets, produits d'automates, déterminisation des automates non déterministes, automates asynchrones, théorème des éliminations des epsilon-transitions, exemples de langages reconnus, théorème de Kleene, algorithme de Brzozowski et Mac Cluskey, minimisation des automates. Exemples d'applications d'automates.
Méthodes d'enseignementCours s’appuyant sur TD et TP
Evaluation session 1

Ecrit de synthèse 3h (ES)

Evaluation session 2Ecrit de synthèse 2h
Références Bibliographiques
  1. Logique, volume 1. Paul Gochet et Pascal Gribomont. Hermes.
  2. Handbook of logic in Artficial Intelligence and Logic Programming Vol1 Oxford University Press
  3. Mathématiques pour l'Informatique. André Arnold et Irène Guessarian. EdiScience.
  4. Fondements mathématiques de l'informatique J. STERN Mc Graw-HILL
  5. Concepts fondamentaux de l'informatique A. AHO, J. ULLMAN DUNOD
  6. Optimisation combinatoire T2: programmation discrète, M. Sakarovitch, Hermann, 1984
  7. Méthodes d'optimisation, I. Charon et al., Masson, 1996