Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision 		Révision précédente
fr:research:thesis-defense [2016/03/23 13:52]
apeiron 		fr:research:thesis-defense [2021/04/05 17:20]
apeiron effacer thèse
Ligne 1: Ligne 1:
-====== Le manuscrit ====== 
- 
-**Caractérisation impérative des algorithmes séquentiels en temps quelconque, primitif récursif et polynomial** 
- 
-Voici {{:​manuscrit-these.pdf|le manuscrit}} de thèse. 
- 
 ====== Résumé ====== ====== Résumé ======
  
Ligne 17: Ligne 11:
  
 Notre soucis de la faisabilité nous a également conduit à étudier en terme de complexité implicite deux restrictions des ASMs : celles en temps primitif récursif (les opérations usuelles et terminales) et celles en temps polynomial (les exécutions réalistes). Nous montrons d'une part que si les structures de données sont également primitives récursives,​ alors une variante LoopC du langage Loop de Meyer et Ritchie est complète pour les algorithmes en temps primitif récursif. D'​autre part, une restriction syntaxique LoopCstat de LoopC est complète pour les algorithmes en temps polynomial, sans restriction sur les structures de données et en caractérisant syntaxiquement le degré du polynôme. Notre soucis de la faisabilité nous a également conduit à étudier en terme de complexité implicite deux restrictions des ASMs : celles en temps primitif récursif (les opérations usuelles et terminales) et celles en temps polynomial (les exécutions réalistes). Nous montrons d'une part que si les structures de données sont également primitives récursives,​ alors une variante LoopC du langage Loop de Meyer et Ritchie est complète pour les algorithmes en temps primitif récursif. D'​autre part, une restriction syntaxique LoopCstat de LoopC est complète pour les algorithmes en temps polynomial, sans restriction sur les structures de données et en caractérisant syntaxiquement le degré du polynôme.
 +
 +**Mots-clés** : Algorithme séquentiel,​ ASM, calculabilité,​ complexité implicite, langage impératif, simulation, temps récursif primitif, temps polynomial.
 +
 +====== Manuscrit ======
 +
 +**Caractérisation impérative des algorithmes séquentiels en temps quelconque, primitif récursif et polynomial**
 +
 +Les rapporteurs ayant examiné mon manuscrit sont :
 +  * Patrick Baillot, directeur de recherche au CNRS
 +  * Gilles Dowek, directeur de recherche à INRIA
 +  * Daniel Leivant, professeur à l'​Indiana University Bloomington
 +
 +Voici {{:​manuscrit-these.pdf|la version finale}}.
  
 ====== Soutenance ====== ====== Soutenance ======
  
-J'ai soutenu ma thèse en informatique le vendredi 9 octobre 2015 à Créteil.+J'ai soutenu ma thèse en informatique le vendredi 9 octobre 2015 à Créteil. Voici {{ :​undefined:​soutenance.pdf | les slides}}.
  
 Le jury était composé de : Le jury était composé de :
Ligne 30: Ligne 37:
  
 Ma soutenance a été filmée((Un grand merci à Marie Le Cun !)), voici [[https://​www.youtube.com/​watch?​v=Nx7ZDE7vV-c|la vidéo]] postée sur ma chaîne. Ma soutenance a été filmée((Un grand merci à Marie Le Cun !)), voici [[https://​www.youtube.com/​watch?​v=Nx7ZDE7vV-c|la vidéo]] postée sur ma chaîne.
 +
 +====== Publications ======
 +
 +Ce travail de thèse a donné lieu à deux publications :
 +  * [[fr:​research:​fi-while|Algorithmic Completeness of Imperative Programming Languages]] (Yoann Marquer), accepté par Fundamenta Informaticae en 2016
 +  *  [[fr:​research:​ploopc|Imperative Characterization of Polynomial Time Algorithms]] (Yoann Marquer, Pierre Valarcher), publié en 2016 dans Developments in Implicit Computational Complexity, volume 3, pages 91 - 130