Enseignement
Cours :
      Théorie des langages :
      L’objectif du cours est la maitrise des concepts de mot, de langage, de problème de reconnaisance d'un langage et des outils nécessaire à cette reconnaissance : automate, mémoire, déterminisme, non déterminisme.

    • Chapitre 0 : (Plan du cours, bibliographie)

    • Chapitre 1 Langages formels (Alphabet, Langages, Problème de décision, Opérations ensemblistes, Etoile de Kleene, Grammaire, Dérivation, Ambigüité, Hiérarchie de Chomsky)
    • Chapitre 2 Automates à états finis (Automates, Déterminisme (AFD), Fonction de transition, Non déterminisme (AFN), Equivalence d'automates, Déterminisation, Epsilon transition, Automate canonique, Minimisation par affinage).
    • Chapitre 3 Langages rationnels (Langage et expression rationnels, Théorème de Kleen, Langage non rationnels, Lemme de l'étoile).

    • Travaux dirigés : Langages ,   Langages rationnels,   Automates à états finis ,   Frontière des langages rationnels,   Automates à piles,  



      • Algorithmique :
      L’objectif de ce cours la maitrise des outils d'analyse et de preuve d'algorithme (Induction, invariant, preuve d'arrêt, complexité de problème et d'algorithme) et des paradigmes de conception (récursivité, gloutonnerie, programmation dynamique).

    • Chapitre 0 : Avant propos (Plan du cours, bibliographie)

    • Chapitre 1 Niveaux de description (Machine, Mémoire, Langages, Compilation, Langage de description d'algorithmes)
    • Chapitre 2 Type de données abstraits (TDA) (Structure de données, Encapsulation, TDA : Tas, Ensembles dynamique, Dictionnaire, files de priorités, familles d'ensembles)
    • Chapitre 4 Analyse et complexité (Problème, Classe de complexité, Complexité algorithmique, Fonction temporelle de complexité, Notations asymptotiques, Codage et modèle de calcule, Problème intraitables)
    • Chapitre 5 Algorithmes glouton (Paradigme glouton, Propriété du choix glouton, Propriété de sous structure optimale, Problème du choix d'activités, Codage de Huffman)
    • Chapitre 6 Programmation dynamique (Principe d'optimalité de Bellman, Définition récursive d'une solution optimale, Calcul d'une valeur et d'une solution optimale, Nombres de Fibonacci, Calcul des chemins optimaux dans un graphe orienté)

    • Travaux dirigés : Induction,   Terminaison,   Invariant ,   Programmation dynamique,  



      • Calculabilité :
      L’objectif de ce cours est la maitrise du périmètre de la science du calcul, du point de vue epistémologique à celui de la science fondamentale..

    • Chapitre 0 : Avant propos (Plan du cours, bibliographie)

    • Chapitre 1 Conscience Artificielle Nosce te ipsum (Machine de Turing, Problème de décision, Langage, Hypothèse I.A. Test de Turing, Chambre de Searle, Problème de Hilbert, Indécidabilité de Gödel)
    • Chapitre 2 Infinis Capax infinity (Infinis, Paradoxe, Cardinal, Ensembles dénombrables et non dénombrables, Hiérarchie de Cantor, Hypothèse du continu, Théorème de Cantor-Berstein, Antinomie de Russel, Axiomatique ZFC et au delà)
    • Chapitre 3 Langages formels Ad Litteram (Fonctions récursives primitives, Existence de fonction non récursive primitives, Fonction d’Ackermann-Péter, Fonctions récursives, partielles et totales, Modèle des machines à registres, Notation)
    • Chapitre 4 Boucles étranges Alter ego (Conscience, Système de codages, Théorèmes d’itération, Théorèmes de récursion et du point fixe de Kleene. Attention volontaire, Ensemble sémantique, Décidabilité, Théorème de Rice)

    • Travaux dirigés : Ensembles dénombrables,   Ensembles non dénombrables,   Etude de conjectures ,   Fonctions récursives,   Machines à registres,   Modèle de Turing ,   Problème de correspondance de Post