Sujets de TER pour les masterM1
Année 09-10
TITRE : Sur les protocoles auto-stabilisants : applications au problème de l'exclusion mutuele pour les anneaux anonymes
Descriptif et objectifs :
L'autostabilisation
est la propriété d'un algorithme réparti capable de retrouver seul un
fonctionnement correct après apparition d'une panne transitoire.
Une
panne transitoire affecte toute donnée volatile, qu'elle soit en cours
d'acheminement (message) ou dans une mémoire. Les mémoires non
volatiles (ROM) ne sont pas altérées par les pannes transitoires. De
même, sur chaque site, le code des algorithmes est supposé ne pas être
modifié par les pannes transitoires. Cela correspond par exemple aux
algorithmes câblés, ou bien aux algorithmes régulièrement restaurés
depuis un support non volatile. Lorsqu'une telle panne affecte le
système, celui-ci peut atteindre un état quelconque.
Si la
spécification de l'algorithme réparti concerne un état particulier (par
ex. une distance doit être calculée), alors l'algorithme retrouvera une
configuration légitime en temps fini après que la panne transitoire a
cessé. Pour ce type d'algorithme, la spécification porte sur les
configurations du système, c'est-à-dire sur l'état de chaque site et de
chaque canal de communication. L'algorithme autostabilisant retrouve en
temps fini une configuration légitime, c'est-à-dire une configuration
dans laquelle l'état voulu est réalisé (eg. la distance est calculée et
est correcte).
Si la spécification de l'algorithme réparti concerne
un comportement particulier (par exemple circulation sans fin d'un
jeton sur chaque site), alors l'algorithme retrouvera en temps fini une
séquence de configuration dans laquelle le comportement est réalisé
(eg. le jeton visite effectivement chaque site). Pour ce type
d'algorithme, la spécification porte sur les exécutions (enchaînement
de configurations). L'algorithme autostabilisant converge en temps fini
vers une exécution correcte légitime.
Le concept d'autostabilisation a été formulé pour la première fois par Dijkstra en 1974.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
TITRE : Etude d'un problème d'ordonnancement appliqué à un problème d'acquisition de données d'une torpille en immersion
Descriptif et objectifs :
L'étude du problème d'orodnnancer des tâches-couplées soumises à des
contraintes de compatiblité est motivée par le problème d'acquisition
de données ar une torpille en immersion. En effet, la torpille possède
des capteurs qui collectent des informations qui sont alors traitées
sur un monoprocesseur. Une sonde émet une onde qui se propage sous
l'eau pour recueillir des données, appelée tâches d'acquisition. Ainsi,
nous aurons deux sous-tâches une qui envoie l'écho l'autre qui le
reçoit et un temps d'inactivité incompressible et indilatable entre les
deux sous-tâches qui représente la propagation de l'écho sos l'eau. Les
tâches d'acquisition peuvent être assimilées à des tâches-couplées.
Pendant ce tmeps d'inactvité, nous pouvons envoyer d'autres échos sur
d'autres sondes afin d'employer le temps d'inactivité. Cependant, la
localisation trop proche des ondes provoquent des perturbations et des
interférences. Sachant que nous souhaitons traiter des informations
exemptes d'erreur, nous construisons un graphe dit de compatibilité
entre les tâches. Ce graphe décrit l'ensemble des tâches pouvant
potentiellement exécuter au moins une sous-tâche durant la période
d'inactivité d'une autre. Les informations récoltées via le retour de
l'écho sont traitées par le monoprocesseur engendrant un traitement par
le processeur. Ces tâches sont dites de traitement sont des successeurs
des tâches d'acquisition.
Ce stage porte sur l'étude algorithmique et sur le développement de
stratégies efficace pour résoudre ce type de problèmes. Dans un premier
temps nous étudierons des cas simples.
Encadrant : Simonin Gilles Giroudeau rodolphe
Mail : simonin@lirmm.fr ; rgirou@lirmm.fr
TITRE : sur le problème des Préflots
Descriptif et objectifs :
Les
préflots sont des flots qui ne vérifient pas la loi de Kirchkoff.
Le principe général ne porte pas sur la recherche de chaînes
augmentante. La méthode générique des préflots permet d'améliorer la
complexité pour trouver un flot maximum. Le but de ce stage est
d'étudier le principe des préflots, et d'implémenter plusieurs
variantes et de comparer les résultats par rapport à des méthodes déjà
vues.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
TITRE : Sur l'étude des algorithmes d'approximation de schéma polynomial (PTAS) et totalement polynomial (FPTAS)
Descriptif et objectifs :
Les
algorithmes d'approximation de schéma polynomial et totalement
polynomial sont des algorithmes d'appproximation de rapport aussi
proche que l'on veut de la solution optimale. Le ratio de la
performance relative est de 1+epsilon. Il est évident que ce ratio
proche de un induit un surcoût sur la complexité de l'algorithme.
Dans ce TER, nous étudierons les principes qui régissent ces
algorithmes, et nous illustrerons par des exemples sur des problèmes
classiques en optimisation combinatoire. Vous validerez vos observations par des tests.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
TITRE : Etude de l'article << Effect od capacities variations maximums flows, minimum cuts and edge saturation'
Descriptif et objectifs :
Cet article porte sur l'étude de la varations des paramètres (capacités, ...) dans un réseau.
Le travail consiste à comprendre l'article et à programmer les solutions préconnisées.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
Année 07-08
Last modified: Fri Dec 17 15:17:12 CET 2004