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

Stage en Master informatique 2008 (premier sujet)

Stage en Master informatique 2008 (second sujet)

Stage en Master informatique 2008 (troisième sujet)

Stage en Master informatique 2008 (quatrième sujet)


Last modified: Fri Dec 17 15:17:12 CET 2004