J'ai le plaisir de vous inviter à ma soutenance de thèse, intitulée:
"Sur la décomposition réelle et algébrique des systèmes dépendant de paramètres",
ainsi qu'au pot qui suivra.
Elle se tiendra le mardi 9 décembre à 14h,
au LIP6 en salle 549 (5ème étage):
104 av du Président Kennedy
75016 Paris
Plan d'accès: http://www.lip6.fr/fr/informations/comment.php
Le jury sera composé de:
K. Yokoyama (Rapporteur), professeur à Rikkyo university
H. Hong (Rapporteur), professeur à North Carolina State university
M.-F. Roy (Examinateur), professeur à l'université de Rennes
D. Lazard (Examinateur), professeur à l'université Pierre et Marie Curie
P. Wenger (Examinateur), directeur de recherche à l'IRCCyN
D. Chablat (Examinateur), chargé de recherche à l'IRCCyN
F. Rouillier (Directeur), directeur de recherche à l'INRIA
Résumé:
Cette thèse traite des systèmes paramétrés. Ils modélisent de nombreuses
applications apparaissant dans divers domaines, comme la robotique ou la
calibration. Soit S un système d'équations et d'inéquations polynomiales
dépendant de paramètres. Nous abordons le problème de décrire l'ensemble des
ouverts connexes U de l'espace des paramètres tels que S restreint à U admet un
nombre constant de solutions réelles.
En robotique, notre approche nous a permis de détecter les positions cus-
pidales, importantes pour la planification de trajectoire des robots parallèles
3-RPR dans le plan. En calibration photographique, nous avons pu décrire
le nombre de solutions physiquement réalisables du problème Perspective-3-
Points.
D'un point de vue théorique, nous analysons le problème du calcul de la
variété discriminante d'un système paramétré. Sous certaines hypothèses,nous
montrons que le calcul de la variété discriminante peut se réduire à un calcul
de projection. En particulier, nous présentons un algorithme polynomial en
espace pour la calculer.
Dans le cas des systèmes d'équations polynomiales quelconques, nous in-
troduisons les décompositions régulières, où chaque composante est représen-
tée par une suite régulière en dehors d'une hypersurface. Notre algorithme
pour les calculer est basé sur la saturation d'idéal et possède de bonnes per-
formances en pratique. Cette représentation permet en outre, dans le cadre
des systèmes paramétrés, de diminuer la combinatoire liée au calcul de lieux
critiques pour la discrimination des paramètres. Par ailleurs, nous déduisons
de ces travaux un nouvel algorithme pour le calcul du radical d'un idéal.
J'ai le plaisir de vous annoncer la soutenance de ma thèse intitulée
"Génération aléatoire de structures combinatoires :
méthode de Boltzmann effective."
qui aura lieu le 3 décembre 2008 à 14h30 en salle 549, au cinquième
étage du LIP6, situé au 104 Av. du Pdt Kennedy, 75016 Paris.
Vous êtes également invités au traditionnel pot qui suivra (même
bâtiment, salle 847, 8ème étage).
---------------------------------------------------------------------------------
Composition du jury:
François Bergeron, Lacim, UQAM (rapporteur)
Alain Denise, LRI, Université de Paris Sud (rapporteur)
Philippe Flajolet, INRIA Rocquencourt (examinateur)
Patrick Gallinari, LIP6, UPMC (examinateur)
Jacques Malenfant, LIP6, UPMC (examinateur)
Conrado Martínez, Université Polytechnique de Catalogne (examinateur)
Bruno Salvy, INRIA Rocquencourt (examinateur)
Michèle Soria, LIP6, UPMC (directrice)
---------------------------------------------------------------------------------
Résumé de la thèse:
La génération aléatoire uniforme est un problème central en combinatoire
algorithmique.Dans le modèle de Boltzmann, les structures combinatoires
sont engendrées avec une taille variable ce qui permet de concevoir des
générateurs efficaces.
Cette thèse vise à rendre effective cette méthode de génération
aléatoire pour un grand nombre de classes combinatoires décomposables,
en automatisant l'ensemble des traitements intervenant dans la
conception des générateurs de Boltzmann.
La première partie est consacrée à l'étude des algorithmes de
génération. Nous commençons par compléter le dictionnaire initial des
générateurs de Boltzmann afin de pouvoir traiter les classes
combinatoires non étiquetées. Ces algorithmes génériques sont présentés
en détails, validés par des preuves et illustrés sur des exemples
classiques en combinatoire. Des données expérimentales viennent
également souligner les performances de ces générateurs; une application
à la génération aléatoire de partitions planes complète cette étude.
Dans la méthode de Boltzmann, les générateurs sont paramétrés par une
valeur numérique x qui contrôle l'espérance de la taille des
structures engendrées. L'uniformité de la génération repose sur une
fonction d'oracle qui associe à toute classe combinatoire la valeur de
sa série génératrice en x.
La seconde partie de ce mémoire présente une méthode de calcul
automatique et efficace de cet oracle, par itération de Newton
numérique. La validité de cette méthode repose sur la convergence de
l'itération de Newton pour les structures combinatoires. Cette itération
est ensuite relevée au niveau des séries formelles puis au niveau des
valeurs numériques.
L'itération sur les séries conduit par ailleurs à un algorithme de
complexité quasi-optimale pour calculer les premiers coefficients des
séries de dénombrement.
---------------------------------------------------------------------------------
Cordialement,
Carine Pivoteau.
======================
Informations pratiques
======================
Adresse :
Site Passy-Kennedy
LIP6
104 avenue du Président Kennedy
75016 Paris
Comment venir au LIP6 (site de Kennedy) :
http://www.lip6.fr/fr/informations/comment.php
Pour les personnes extérieures, vous devrez vous présenter à l'accueil
afin de pouvoir accéder à la salle de soutenance. Si vous avez le
moindre problème d'accès, vous pourrez me contacter au : 01 44 27 88 25.
