Session 2024

Liste des leçons proposées par le jury : Épreuve orale d’Informatique Fondamentale et Programmation

  • Leçon 1 : Algorithmes pour les graphes et NP-Complétude. Exemple du problème du Voyageur de commerce.
  • Leçon 2 : Analyse lexicale et syntaxique. Application à la compilation.
  • Leçon 3 : Automate minimal. Algorithmes pour le calcul de l'automate minimal.
  • Leçon 4: Algorithmique du texte, Exemple et application.
  • Leçon 5 : Langages rationnels et automates finis, Exemple et applications.
  • Leçon 6: Calculabilité : équivalence des modèles de calcul.
  • Leçon 7 : Calculabilité : Fonctions récursives.
  • Leçon 8: Complexité algorithmique. NP-complétude.
  • Leçon 9 : Complexité en espace : Théorème de Savitch.
  • Leçon 10 : Complétude de la logique propositionnelle.
  • Leçon 11 : Equations ensemblistes et lemme d’Arden.
  • Leçon 12 : Expressions régulières : Propriétés et méthodes de calcul, expressions régulières à partir d’un automate fini.
  • Leçon 13 : Grammaires LL(k) et LR(k).
  • Leçon 14 : Hiérarchie de Chomsky.
  • Leçon 15 : Exemple de preuve d’algorithme : Correction et terminaison.
  • Leçon 16 : Logique du premier ordre : Calcul de superposition, stratégies, restrictions.
  • Leçon 17: Logique du premier ordre : Système à la Gentzen et élimination du cut.
  • Leçon 18 : Logique du premier ordre : Calcul de résolution, stratégies, restrictions.
  • Leçon 19: Logique propositionnelle : Formes normales et clausales, calcul de résolution.
  • Leçon 20 : Logique propositionnelle : syntaxe et sémantique - satisfaisabilité et NP- complétude.
  • Leçon 21 : Décidabilité et indécidabilité. Exemples.
  • Leçon 22 : Modèles de calcul : lambda-calcul.
  • Leçon 23 : Modèles de calcul : machines de Turing simulation et applications.
  • Leçon 24 : Modèles de calcul : machines de Turing universelles.
  • Leçon 25 : Propriétés des langages hors contexte (formes normales / lemme de l'étoile / Propriétés de clôture).
  • Leçon 26 : Sémantique opérationnelle des langages de programmation.
  • Leçon 27 : Théories en logique du premier ordre : Complétude et décidabilité.
  • Leçon 28 : Théorème de compacité pour la logique propositionnelle, Exemple et application.
  • Leçon 29 : Théorème d’incomplétude de Gödel.