Sujets de TER pour les masterM1
Année 12-13
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
TITRE : An efficient Branch and Bound Algorithm for finding a Maximum Clique
Descriptif et objectifs :
L'article
porte sur l'étude du problème de la recherche d'une clique maximum en utilisant une méthode arborescente.
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
TITRE : La méthode des points intérieurs
Descriptif et objectifs :
La méthode des points est une méthode de complexité cubique (le simplex
n'est pas un algorithme de complexité polynomiale) pour résoudre des
programmes linéaires. LE TER porte sur la compréhension de cette
méthode et montrer les différences avec la méthode du simplexe.
Il est conseillé d'aimer les normes, les matrices, ......
Encadrant : Giroudeau rodolphe
Mail : rgirou@lirmm.fr
TITRE : Sur des algorithmes pour la résolution d'un problème de flot maximum et de coûts minimum.
Descriptif et objectifs :
Il
existe, comme pour le problème de flot maximum, divers algorithmes pour
résoudre le problème du lfot maximum de coûts minimum (scaling
algorithm, ...). Dasn ce TER vous étudierez plusieurs algorithmes du
point de vue théorique et pratique.
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
TITRE : Trouver des sous-graphes denses ou peu denses dans un graphe
DESCRIPTIF et OBJECTIFS : Etant donné un graphe G et un
entier k, le problème k-densest (resp. k-sparsest) subgraph consiste à
trouver dans G un ensemble de k sommets induisant le maximum (resp.
minimum) d'arêtes. Ces problèmes, beaucoup étudiés pour leurs
potentielles applications pratiques (recherche de communautés…etc.),
sont des problèmes NP-difficile. Le but de ce TER est d'étudier et de
comparer (d'un point de vue théorique et pratique, en générant des
graphes aléatoires) des algorithmes existants pour ces problèmes, ou
d'en proposer de nouveaux. On s'intéressera notamment à des approches
aléatoires ou bien à des algorithmes efficaces dans des classes de
graphes restreintes.
ENCADRANT : Rémi Watrigant et Giroudeau rodolphe
MAIL : watrigant@lirmm.fr et rgirou@lirmm.fr
Last modified: Fri Dec 17 15:17:12 CET 2004