Sujets de RECHERCHE pour les masters M2 :
Année 11-12
TITRE : Etude
du point de vue de la complexité classique/paramétrique et algorithmes
d'approximation avec mesure classique et différentielle pour des problèmes d'ordonnancement.
Descriptif et objectifs :
Les
problèmes d'ordonnancement sont des problèmes combinatoires qui ne sont
pas trop complexes ce qui permet de procéder à une analyse analytique
(classification au sens de la complexité et de l'approximation). Dans
ce stage nous nous intéressons à des problèmes
d'ordonnancement pour lesquels nous ferons une analyse croisée
complexité classique/paramétrique et approximation dans le pire
cas/approximation via la mesure différentielle.
Encadrants : Marin bougeret et Rodolphe Giroudeau
Mail : marin.bougeret@lirmm.fr et rgirou@lirmm.fr
TITRE : Algorithmes d'optimisation pour la remodularisation de logiciels
Descriptif et objectifs :
Les
grands systèmes logiciels utilisés dans l'industrie sont utilisés sur
de longues périodes de temps et doivent par conséquent être modernisés
de manière régulière. Cette modernisation comprend des activités de
maintenance telles que la correction ou la réorganisation ainsi que des
activités d'évolution pour faire face à de nouveaux besoins ou intégrer
de nouvelles technologies. Elle permet d'éviter l'érosion du système et
une perte de qualité.
Une analyse complète de ces systèmes est
cependant devenue infaisable du fait de leur grande taille et de leur
complexité conceptuelle. Par exemple, le système Windows comprend
actuellement plus de 60 millions de lignes de code (500 000 pages
imprimées en recto-verso, soit 16 fois l'Encyclopedia Universalis).
Comme il est impossible de comprendre tous les niveaux de détails, on
doit construire et mettre à jour des vues de haut niveau sur ces
logiciels, que l'on appelle des architectures et qui capturent leur
structure modulaire. Une fois cette structure connue, elle sert de
support aux activités de compréhension, de maintenance et d'évolution,
sa qualité est donc cruciale.
Retrouver ou améliorer la
structure modulaire est un sujet déjà ancien et pour lequel différentes
approches de clustering (regroupement conceptuel) ont déjà été testées.
Ces approches présentent des défauts en ce qui concerne le passage à
l'échelle ou la prise en compte de certains éléments des langages de
programmation actuels.
Dans le présent travail, nous proposons
d'aborder le problème sous l'angle de la théorie des graphes et
l'exprimer comme un problème d'optimisation combinatoire. Les
structures logicielles qui nous intéressent sont principalement basées
sur des graphes étiquetés traduisant par exemple les appels de méthodes
par d'autres méthodes, les accès aux attributs ou les mentions de types
dans des méthodes, les inclusions de classes les unes dans les autres,
etc.
En première approche, une structure modulaire pertinente peut
s'exprimer comme une décomposition du logiciel en ensembles d'éléments
appelés modules, avec des propriétés telles qu'une forte cohésion entre
les éléments à l'intérieur d'un module et un faible couplage entre les
modules. On peut rechercher aussi des sous-modules et produire une
décomposition avec différents niveaux d'imbrication. Tout ceci peut se
traduire par une décomposition du graphe en sous-graphes ayant
certaines propriétés.
Du
point de vue de la théorie des graphes,
le problème central semble proche du problème classique de
partionnement. Cependant, avec les nouvelles fonctions objectifs
proposées ce sont des nouveaux problèmes combinatoires qu'il faut
étudier
Travail demandé :
-
Complexité (Polynomilaité, NP-complétude, FPT, W[1]-difficulté) des problèmes selon les divers fonctions objectifs
-Approximation avec la mesure dans le pire cas et la mesure différentielle
-Etude selon divers graphes structurés
Encadrants : Rémi Watrigant Marin Bougeret Rodolphe Giroudeau
Mail : remi.watrigant@lirmm.fr, marin.bougeret@lirmm.fr, et rgirou@lirmm.fr
TITRE : Optimisation du test indirect de circuits radio-fréquence $(RF)$
Descriptif et objectifs :
voir fichier pdf : Optimisation du test indirect de circuits radio-fréquence $(RF)$
Encadrant : Giroudeau rodolphe & Florence Azais
Mail : rgirou@lirmm.fr et azais@lirmm.fr