Langages formels, calculabilité et complexité

Cours donnés par Damien Vergnaud. (Salle Assia Djebar, le jeudi de 13h15 à 15h00)

TD donnés par Pierrick Meaux. (Salle Assia Djebar, le jeudi de 15h15 à 17h00)

L'évaluation du cours se fait par un partiel facultatif, un examen et par un travail de rédaction (ou projet). Le rattrapage est fait par un examen oral. Une liste non exhaustive de thèmes pouvant donner lieu à la rédaction d'un rapport est donnée ci-dessous.

top

Planning

  • 22 septembre

    • Cours 1 : Présentation du cours.

      Langages rationnels : Automates finis. Théorème de Kleene. Automate standard de Glushkov.

    • Cours 2 : Automates déterministes. Lemme d'Arden. Lemme(s) de l'étoile

  • 29 septembre

  • 6 octobre

  • 13 octobre

  • 20 octobre

  • 27 octobre

  • 3 novembre

    • Cours 7 : Variantes. Langages récursivement énumérables.

    • Partiel (15:00-17:00)

  • 10 novembre

    • Cours 8 : Langages décidables. Problème de correspondance de Post.

    • TD 8 :

  • 17 novembre

  • 24 novembre

    • Cours 10 et 11 : Complexité en temps et en espace. Réduction polynomiale. Définition de NP-complétude

  • 30 novembre

    • Soutenances d'exposé : 16h00 - 18h30

      • 16h00 : Lucas Willems - Algorithme d'Hopcroft
      • 16h30 : Hector Dang-Nhu - Suites automatiques
      • 17h00 : Joseph Marotte - Grammaires booléennes
      • 17h30 : Mathieu Fehr - Grammaires booléennes
      • 18h00 : Jian Qian - Transformations expression rationnelle en automate de Antimirov

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 1 décembre

    • Cours 12 : Complexité en espace. PSPACE-complétude. NL-complétude.

    • TD 10

  • 8 décembre

    • TD 11 :

    • TD 12 :

  • 13 décembre

    • Soutenances d'exposé : 17h00 - 19h00

      • 17h00 : David Reboullet - Équivalence entre logique monadique du second ordre et automates
      • 17h30 : Clément Lalanne - Automates à pile déterministes
      • 18h00 : Camille Gobert - Automates de Mealy
      • 18h30 : Lionel Zoubritzky - Hauteur d'étoile

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 15 décembre

    • Cours 13 : Circuits

    • TD 13 :

    • li>

    3 janvier

    • Soutenances d'exposé : 17h00 - 19h00

      • 17h00 : Thibaut Pérami - Lambda calcul
      • 17h30 : Alexis Thibault - Automates cellulaires
      • 18h00 : Théophile Wallez - Preuves à divulgation nulle de connaissance
      • 18h30 : Basile Coron - Calculabilité distribuée (Article de Angluin and Co)

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 4 janvier

    • Soutenances d'exposé : 16h00 - 19h00

      • 15h30 : Noëmie Fong et Lucas Pluvinage - Pavages et indécidabilité
      • 16h30 : Hsieh Yu-Guan - Modèle de Blum-Shub-Smale
      • 17h00 : Luc Chabassier - Théorème de Ladner
      • 17h30 : Milan Martos - Algorithmes de Markov
      • 18h00 : Lucas Pesenti - Classe #P

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 5 janvier

    • Cours 14 : Circuits (fin) et Crypto complexité

    • TD 14 :

  • 10 janvier

    • Soutenances d'exposé : 17h00 - 19h00

      • 17h30 : Arnaud Eteve - Théorème de Cardinalité (Article de M. Kummer)
      • 18h00 : Marc Ducret - Pavages et indécidabilité

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 12 janvier

    • Cours 15 (13h15-15h45) : Crypto complexité (fin)

  • 12 janvier

    • Soutenances d'exposé : 17h30 - 19h30

      • 17h30 : Malachi Voss - Le hardest langage
      • 18h00 : Anatole Dahan - "Undirected connectivity in log-space"
      • 18h30 : Paul-Nicolas Madelaine - Algorithme d'Hopcroft (minimisation)
      • 19h00 : Joseph Marotte - Forme normale de Greibach

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 13 janvier

    • Soutenances d'exposé : 17h30 - 19h30

      • 15h00 : Téo Sanchez - Algorithme d'Hopcroft (minimisation)
      • 15h30 : Josselin Giet - Générateurs et fonctions pseudo-aléatoires
      • 16h00 : Nathanaël Courant - Machines à compteurs
      • 16h30 : Tomas Rigaux - Preuves à divulgation nulle de connaissance
      • 17h00 : Viviane Ledoux - Théorème de Gap de Borodin
      • 17h30 : Loïc Pujet - Complexité de Kolmogorov
      • 18h00 : Jules Pondard - Complexité de communication

      Les soutenances ont lieu en salle S16 (Couloir Crypto, niveau -1 du bâtiment Rataud).

  • 16 janvier

    • Soutenances d'exposé : 17h30 - 19h30

      • 17h30 : Martin Ruffel - Équivalence machine de Turing et RAM
      • 18h00 : Florentin Guth - Complexité de communication

    • 19 janvier

      • Examen 14h - 17h

    top

Projets

Pour choisir la date de soutenance, merci de remplir le sondage à l'adresse réticulaire ci-dessous avant le 11 décembre 2016 (un seul exposé par horaire sur la base du "premier arrivé - permier servi"). Les rapports devront être envoyés au moins deux jours avant la soutenance.

Choisir sa date de soutenance

Choisir sa date de soutenance (nouvelles dates)

  • Langages rationnels
    • Transformations expression rationnelle en automate de Antimirov (Jian QIAN)
    • Algorithme d'Hopcroft (minimisation) (Lucas WILLEMS) (Paul-Nicolas MADELAINE)
    • Théorème d'Ehrenfeucht-Parikh-Rozenberg
    • Équivalence entre logique monadique du second ordre et automates (David REBOULLET)
    • Hauteur d'étoile (Lionel ZOUBRITZKY)
    • Théorème de Schützenberger
    • Automates de Mealy (Camille GOBERT)
    • Transductions rationnelles
    • Théorème de Cobham
    • Suites automatiques (Hector DANG-NHU)
  • Langages algébriques
    • Forme normale de Greibach
    • Le hardest langage (Malachi VOSS)
    • Automates à pile déterministes (Robin LEMAIRE) (Clément LALANNE)
    • Groupe de Hotz
    • Grammaires booléennes (Joseph MAROTTE) (Mathieu FEHR)
  • Calculabilité
    • Machines à compteurs (Nathanaël COURANT)
    • Lambda calcul (Thibaut PÉRAMI)
    • Automates cellulaires (Alexis THIBAULT)
    • Pavages et indécidabilité (Marc DUCRET) (Noëmie FONG) (Lucas PLUVINAGE)
    • Algorithmes de Markov (Milan MARTOS)
    • Équivalence machine de Turing et RAM (Martin RUFFEL)
    • Théorème de Rice pour les ensembles récursivement énumérable (Martin PÉPIN)
    • Théorème de Cardinalité (Article de M. Kummer) (Arnaud ETEVE)
    • Calculabilité distribuée (Article de Angluin and Co) (Basile CORON)
  • Complexité
    • Complexité de Kolmogorov (Loïc PUJET)
    • Modèle de Blum-Shub-Smale (Hsieh YU-GUAN)
    • Complexité de Valiant
    • Complexité de décision et de recherche
    • Classes de complexité randomisées
    • Limites de la méthode de diagonalisation
    • IP = PSPACE
    • Classe #P (Lucas PESENTI)
    • Théorème de Gap de Borodin (Viviane LEDOUX)
    • Théorème d'accéleration de Blum
    • Hiérarchie polynomiale
    • Théorème de Ladner (Luc CHABASSIER)
    • Complexité de communication (Florentin GUTH) (Jules PONDARD)
    • Bornes inférieures de complexité de circuits
    • Preuves à divulgation nulle de connaissance (Théophile WALLEZ) (Tomas RIGAUX)
    • Générateurs et fonctions pseudo-aléatoires (Josselin GIET)
    • Mondes cryptographiques
top

Documents

top

2006/2007 2007/2008 2008/2009 2009/2010 2010/2011 2011/2012 2012/2013 2013/2014 2014/2015