Proposition de thèse: Simulation de structures géométriques aléatoires

Contact

Olivier Devillers (olivier.devillers@inria.fr).

Équipe

Gamble, Loria and INRIA Nancy Grand-Est.

Contexte

La complexité des algorithmes géométriques est souvent données en onction de la taille des entrées et parfois de celle de la sortie, mais le comportement de ces algorithmes dépend souvent de la distribution géométrique des données. La différence entre le meilleur et le pire cas peut être grande. Une alternative consiste à utiliser des modèles probabilistes pour la distribution des  données. Quand l’entrée est une ensemble de points on peut supposer ceux-ci indépendamment distribué,  malheureusement  si cette hypothèse d’indépendance facilite les calculs elle est peut être incompatible avec certaines applications.
L’utilisation de distributions non indépendantes rends les choses difficiles à analyser théoriquement et la conception de simulateur est d’une aide précieuse pour guider l’intuition et établir des conjectures raisonnable. Malheureusement la génération d’instances aléatoire est également une question difficile. Nous prévoyons d’attaquer trois questions: la simulation de structures géométriques, de structures conditionnées et d’ensemble de points dépendants.

Sujet

Le but est de concevoir et réaliser des générateurs pour quelques objets géométriques aléatoires. Ces générateurs seront utilisés pour évaluer les performances d’algorithmes géométriques et établir de nouvelles conjectures en probabilité.

Une description détaillée est disponible ici.

Qualifications souhaitées

Aspects mathématiques (probabilité),  aspects algorithmiques,  C++ (templates, etc)

Information générale

  • Durée: 3 ans.
  • Début: 1 octobre 2018

Candidature

Envoyer à olivier.devillers@inria.fr en un seul fichier ZIP:

  • CV.
  • Lettre de motivation.
  • Diplomes (et notes) des dernières années.
  • Master (ou équivalent) si terminé. Description du master en cours sinon.
  • Publications éventuelles (il n’ai pas attendu que vous en ayez).

Une lettre de recommandation de votre encadrant de master à envoyer directement à  olivier.devillers@inria.fr. Éventuellement, au plus deux autres lettres de recommandations.

Conditions d’embauche.

  • Salaire net mensuel 1600 €.
  • Repas de midi au restaurant INRIA:  2,78 €.
  • Aide pour diverses formalités administratives.

En ce moment

Logo du CNRS
Logo Inria
Logo Université de Lorraine