En poursuivant votre navigation sur ce site, vous acceptez le dépôt de cookies dans votre navigateur. (En savoir plus)

Doctorant (H/F) : Théorèmes méta-algorithmiques en complexité paramétré

Cette offre est disponible dans les langues suivantes :
Français - Anglais

Date Limite Candidature : jeudi 1 juillet 2021

Assurez-vous que votre profil candidat soit correctement renseigné avant de postuler. Les informations de votre profil complètent celles associées à chaque candidature. Afin d’augmenter votre visibilité sur notre Portail Emploi et ainsi permettre aux recruteurs de consulter votre profil candidat, vous avez la possibilité de déposer votre CV dans notre CVThèque en un clic !

Faites connaître cette offre !

Informations générales

Référence : UMR5506-CHRPAU-001
Lieu de travail : MONTPELLIER
Date de publication : jeudi 20 mai 2021
Nom du responsable scientifique : Dimitrios Thilikos Touloupas
Type de contrat : CDD Doctorant/Contrat doctoral
Durée du contrat : 36 mois
Date de début de la thèse : 1 septembre 2021
Quotité de travail : Temps complet
Rémunération : 2 135,00 € brut mensuel

Description du sujet de thèse

La théorie des algorithmes a offert de puissants résultats unificateurs, appelés méta-théorèmes algorithmiques (MTAs) qui fournissent des conditions mathématiques générales impliquant la dérivation automatique d'algorithmes efficaces. Ces conditions sont généralement liées à la complexité descriptive des problèmes (via la logique) et aux propriétés structurelles de leurs entrées (via la combinatoire). Cette proposition de thèse vise à révéler le potentiel d'unification des MTAs dans des algorithmes discrets. Nous allons utiliser le cadre de la théorie de la complexité paramétrée, où l'efficacité d'un algorithme est mesurée non seulement par rapport à la taille de l'entrée mais aussi par rapport à des paramètres secondaires qui jouent un rôle clé dans l'explosion combinatoire du temps de calcul. Cette approche multivariée permet de prendre en compte de manière flexible les conditions logiques et structurelles qui sont généralement rencontrées dans les paramétrisations de problèmes algorithmiques. La théorie de la complexité paramétrée est une discipline pleinement développée de l'informatique théorique et a développé un arsenal étendu de techniques et de paradigmes algorithmiques. L'objectif de cette thèse est de contribuer à leur élévation systématique aux MTAs.

Pré-requis : Nous cherchons un ou une candidat(e) motivée avec des connaissances approfondies en algorithmique, combinatoire, théorie des graphes, et un intérêt notable pour le complexité paramétré et ses interactions entre la logique et les algorithmes.

Contexte de travail

L'offre est un contrat doctoral de 36 mois (01/09/2021–31/08/2024) pour travailler au sein du project de ANR/DFG (collaboration franco-allemande) UTMA ANR-20-CE92-0027 (Théories Unifiantes dans les Algorithmes Multivariées) en collaboration avec l'Université de Bremen, Allemagne.

Encadrants :
Dimitrios THILIKOS TOULOUPAS
Christophe PAUL

Le Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (LIRMM ) est une unité mixte de recherche, dépendant conjointement de l'Université Montpellier (UM) et du Centre National de la Recherche Scientifique (CNRS).

La personne recrutée intégrera l'équipe AlGCo du Département Informatique du LIRMM https://www.lirmm.fr/algco/

On en parle sur Twitter !