Operations Research Group ROSE, EPFL
April 25, 2008, 14:15, Room ME B3 31 (click here for the map)
En tomographie discrète l’un des problèmes de base est la reconstruction d’une image à partir de ses projections (horzontales et verticales). En d’autres termes on a un tableau m x n où chaque case correspond à un pixel qui peut avoir l’une des couleurs 1,2,…, k. On donne pour chaque rangée (ligne ou colonne) le nombre de pixels de chaque couleur qui s’y trouvent . Il s’agit alors de voir si l’on peut construire une affectation de couleurs aux pixels qui satisfasse ces conditions de projection. Des modèles de graphes ont été proposés pour aborder ces problèmes et on en a étudié diverses variations et généralisations. Ceci a permis de formuler divers problèmes d’ordonnancement en particulier qui n’ont rien de tomographique. Nous discuterons certaines de ces variations. Nous montrerons quels sont les problèmes qui sont facilement solubles et nous étudierons la complexité d’autres problèmes. Nous montrerons comment divers modèles classiques de recherche opérationnelle permettent d’appréhender des cas particuliers du problème de la reconstruction d’image et nous mentionnerons quelques problèmes ouverts.
Originaire de St-Maurice et Sion (VS), Dominique de Werra est n� en1942. Il obtient son dipl�me d'ing�nieur-physicien de l'EPUL en 1965, puis en 1969, le titre de docteur �s sciences techniques. De 1969 � 1971, il est professeur au d�partement de sciences du management � l'Universit� de Waterloo; il est professeur invit� dans diverses Hautes Ecoles europ�ennes et am�ricaines. Depuis 1971, il est professeur de recherche op�rationnelle � l'EPFL. Il a pr�sid� la conf�rence des chefs de d�partement en 1990, il est nomm� vice-pr�sident de l'EPFL en 1990 et en plus, directeur de la formation depuis l'automne 93. Ses recherches portent sur les math�matiques discr�tes (optimisation combinatoire, th�orie des graphes, algorithmique, etc.) et leurs applications aux syst�mes industriels et informatiques. Il a particip� � et/ou dirig� divers projets interdisciplinaires en productique, distributique, �nerg�tique et ordonnancement. Il dirige des travaux dans les domaines pr�cit�s et en particulier sur les probl�mes d'emploi du temps et plus g�n�ralement de gestion de calendriers et de ressources dans l'ex�cution de grand projets (sports, enseignement, etc.). En 1987-1988, il a pr�sid� l'association EURO qui regroupe les soci�t�s nationales de recherche op�rationnelle en Europe. Il est docteur h.c. de l'Universit� de Paris et de l'Ecole polytechnique de Poznan et laur�at de la m�daille d'or europ�enne (EURO) de recherche op�rationnelle en 1995. En mars 2000, il est nomm� doyen des affaires internationales.