Stages de Master (propositions de C. Banderier, Paris 13)

Organisation

Attention : je reçois plusieurs demandes de stages par jour, et je me vois donc dans l'obligation de faire une sélection en amont : inutile de me contacter si vous n'avez pas eu une moyenne >14/20 l'an passé, et des notes similaires pour votre premier semestre de master 2.

Voici une liste de sujets pour votre stage de master. Ces sujets ont de très forts liens avec les cours de calcul formel / combinatoire / analyse d'algorithmes.
La référence de base est le livre "Analytic Combinatorics" de Philippe Flajolet & Robert Sedgewick, accessible on-line.

Sujet 1 : Analyse perturbative d'algorithmes

En 2001, Spielman & Teng ont expliqué, dans l'article "Smoothed Analysis of the Simplex Algorithm" pourquoi l'algorithme du simplexe (qui a une complexité au pire exponentielle) se comporte si bien dans la pratique.

Ils ont pour cela introduit le concept de "smoothed analysis", qui peut être vu comme une "interpolation" entre la complexité au pire et la complexité en moyenne. Cette interpolation consiste à faire une moyenne sur un "voisinage" (= une "perturbation") d'une instance, et à regarder alors la "pire" région.

Ceci répond donc à une question qui échappait aux analyses classiques (en moyenne, au pire) : le pire des cas est-il "isolé", ou bien y a-t-il toute une région difficile ?

Leur perturbation est essentiellement un ajout de bruit Gaussien, et ils montrent que l'algorithme du simplexe a une complexité "smoothed" polynomiale.

Spielman consacre une page web à ce concept de smoothed analysis, qui s'avère un champ fécond qui reste grandement à défricher.

Dans Smoothed analysis of three combinatorial algorithms, C. Banderier, R. Beier et K. Mehlhorn se sont penchés sur la "smoothed complexity" de Quicksort et de la recherche de plus court chemin dans un graphe. Le premier pas consiste à s'accorder sur une définition raisonnable de "perturbation", de "voisinage" (pour des données discrètes), pour ensuite comparer la perturbation du pire des cas (qui repose surtout sur des outils de combinatoire analytique) à la pire des perturbations (qui se fait via des méthodes ad hoc).

Le stage consistera, avec l'aide de la combinatoire analytique, à étudier des algorithmes standards, afin d'en donner la "smoothed complexity".

Sujet 2 : Noyaux de graphes dirigés : énumération et asymptotique, lien avec la théorie des jeux

On peut modéliser les jeux finis à deux joueurs de la façon suivante : considérons un graphe dirigé dont l'ensemble des sommets représente l'ensemble des positions possibles, et dont les arrêtes représentent les "coups légaux" pour passer d'une position à une autre. Un noyau du graphe est alors l'ensemble des sommets (=positions) dans lesquels le premier joueur doit être, afin de s'assurer d'une stratégie gagnante. (Ce noyau peut ne pas exister, ou ne pas être unique).

On s'intéresse ici au modèle suivant : on se donne un jeu au hasard (=un graphe dirigé enraciné), et on se demande s'il faut mieux être le premier ou le deuxième joueur (i.e. on cherche à étudier la taille du noyau), etc.

De nombreuses questions relatives au noyau sont NP-complètes, et il fut donc un peu surprenant que des méthodes de séries génératrices ont permis en 2004 des avancées sur ce problème. Par exemple, pour un arbre dirigé, la question de savoir si le premier joueur était avantagé vient juste d'être tranchée (la réponse est une constante assez étrange...) dans l'article Generating functions for kernels of digraphs (Enumeration & asymptotics for a constraint from game theory) de Banderier, Le Bars, et Ravelomanana.

Le stage consistera à pousuivre dans la lancée de cet article.

Sujet 3 : Marches aléatoires dirigées avec contraintes multiples : énumération et asymptotique

Si les chemins de Dyck et la combinatoire analytique vous plaisent, alors il devrait en être de même de l'article suivant : Basic Analytic Combinatorics of Directed Lattice Paths, et donc votre rêve le plus cher est de comprendre ce qui se passe en dimension supérieure, ce que je vous propose d'étudier dans ce stage...

Sujet 4 : Résidus d'ordre supérieur dans Z/nZ : énumération et asymptotique, lien avec la factorisation d'entiers

Etant un polynome P, on procédéra à l'énumération du nombre de solutions de P(x) = 0, puis de P(x,y),... dans Z/nZ. L'énumération repose sur l'étude de fonctions multiplicatives et de séries de Bell associées. L'asympotique repose l'étude des singularités d'une série de Dirichlet associée (=généralisation de la fonction zêta de Riemann). Plus précisément, on utilisera des techniques de transformée de Mellin, mais il n'est pas nécessaire que le stagiaire que connaisse déjà ces techniques, qui peuvent s'acquérir en 1 journée pour quiconque a déjà un amour préalable du calcul de résidu ou des fonctions multiplicatives et de l'asymptotique de leur moyenne de Cesàro. On se contentera dans ce stage d'une asymptotique au premier ordre, car l'asymptotique fine débouche sur problèmes à ce jour ouverts en théorie des nombres (hypothèse de Riemann généralisée) ! Une partie de ces questions a des applications directes en cryptographie ou dans le calcul d'ordre de divers groupes, ce qui a à son tour des applications en mécanique quantique.

Sujet 5 : Structures "fractales" de zéros de famille de polynômes

Ce stage est dédié à l'étude de l'unimodalité et log-concavité de suite de nombres, et aux structures "fractales" de zéros de famille de polynômes. Si jamais vous avez accroché avec l'un des domaines suivants : théorie des nombres, combinatoire, analyse, théorie des probabilités (loi limites) et physique statistique (spectre de matrices aléatoires), programmation (algo numérique), ce stage sera surement ((c) 1990) pour vous l'occasion de creuser les jolis ponts entre ces disciplines.

Certaines familles de polynômes ont ainsi été investiguées par Odlyzko et Poonen, Zeros of polynomials with 0,1 coefficients, cf aussi : article 2, mais de nombreuses autres familles donnent des dessins avec des propriétés remarquables (forme limite, unimodalité, etc), qui sont à ce jour inexpliquées. Ce stage comporte une grande part d'expérimentation, afin d'essayer d'établir une zoologie des cas observés.

Ce stage est faisable aussi bien en M1 qu'en M2, il pourra être orienté suivant le niveau et les gouts ((c) 1990) du stagiaire vers tel ou tel des aspects sus-mentionnés.

Sujet 6 : Exposants critiques de modèles combinatoires de physique statistique

De nombreuses structures combinatoires ont une asymptotique en A^n/ n^r, r est appelé "exposant critique", et il est souvent la signature d'un comportement universel (insensibilité au réseau sous-jacent: Z^2, triangulaire, etc...). Les physiciens ont des méthodes profondes et non complètement rigoureuses (méthode des répliques, algèbre de Virasoro sous l'hypothèse d'invariance conforme, ...) qui leur permettent de conjecturer la valeur de r, par exemple pour les méandres, divers modèles de marches auto-évitantes, etc. Ce stage a pour but d'établir avec rigueur certains de ces exposants critiques, avec des méthodes alternatives de la combinatoire analytique.

Mots-clefs : combinatoire, analyse complexe, équations différentielles, algèbre, calcul formel.

Sujet 7 : Combinatoire et algorithmique du modèle de Schelling (prix Nobel d'économie 2005)

Voir le descriptif sur cette page.

Organisation

Cyril Banderier at lipn.univ-paris13.fr