Soutenance de th
Forum 'Annonces' - Sujet créé le 2004-11-20
Bonjour,
Vous êtes conviés à ma soutenance de thèse qui aura lieu le mardi 23 novembre 2004 à 14H30 au CNAM en salle 30.-1.2.
Vous êtes aussi invités au pot qui suivra.
Fethi Jarray
Sujet de la thèse:
RESOLUTION DE PROBLEMES DE TOMOGRAPHIE DISCRETE. APPLICATION A LA PLANIFICATION DE PERSONNEL
Adresse
2 rue Conté 75003 Paris, métro 11, arrêt arts et métiers
Résumé
Nous avons étudié dans ce manuscrit des problèmes de reconstruction d'objets discrets à partir de leurs projections orthogonales sous
différents types de contraintes. Tout au long de ce travail, nous nous sommes intéressés à l'aspect
algorithmique de la résolution des problèmes. Nous
avons réussi à démontrer l'aspect polynomial de plusieurs problèmes traités. Lorsque les
problèmes ont une complexité inconnue, nous nous sommes attachés à les comparer et à traiter des
cas particuliers. Le but était double:
résoudre des problèmes particuliers
qui couvrent une grande partie des applications et appréhender par ce biais la difficulté à
résoudre le cas général.
Ce travail est composé de quatre parties.
La première partie est consacrée aux problèmes de reconstruction de matrices binaires sous différentes
contraintes d'adjacence et de périodicité. Nous montrons que le problème de reconstruction d'une matrice
binaire respectant la projection horizontale et la contrainte de 4-adjacence
est polynomial. Nous montrons aussi que le problème de reconstruction d'une matrice
binaire respectant les projections orthogonales et la contrainte de 6-adjacence est NP-Complet. Avec une contrainte de périodicité alternée, nous
montrons que les sous-problèmes de reconstruction de matrices binaires $(1,1)$ alternées périodiques
et $(0,p)$ alternées périodiques sont polynomiaux.
Dans la deuxième partie, nous étudions le problème
de reconstruction de tableaux 3-colorés. Nous formulons ce problème par un programme quadratique continu et nous traitons plusieurs cas polynomiaux.
La troisième partie est consacrée aux problèmes de pavage et
de packing de dominos et de barres. Nous montrons l'aspect polynomial des problèmes étudiés
lorsqu'une seule projection orthogonale est prise en compte. Le résultat principal
de cette partie est la polynomialité
du problème de packing de barres horizontales avec un écart minimal.
Dans la dernière partie, nous étudions un problème de planification
de personnel sous différentes stratégies de placement de repos. Nous traitons trois problèmes: le problème de "base" de planification, le
problème de planification de repos mensuels et le problème de planification de week-ends mensuels. Nous
montrons que les deux premiers problèmes sont polynomiaux en proposant une résolution très simple fondée sur des calculs
algébriques et des algorithmes de flot. Le problème de week-ends
mensuels est de complexité inconnue mais sous certaines restrictions, il est polynomial.
[/b][b]
Vous êtes conviés à ma soutenance de thèse qui aura lieu le mardi 23 novembre 2004 à 14H30 au CNAM en salle 30.-1.2.
Vous êtes aussi invités au pot qui suivra.
Fethi Jarray
Sujet de la thèse:
RESOLUTION DE PROBLEMES DE TOMOGRAPHIE DISCRETE. APPLICATION A LA PLANIFICATION DE PERSONNEL
Adresse
2 rue Conté 75003 Paris, métro 11, arrêt arts et métiers
Résumé
Nous avons étudié dans ce manuscrit des problèmes de reconstruction d'objets discrets à partir de leurs projections orthogonales sous
différents types de contraintes. Tout au long de ce travail, nous nous sommes intéressés à l'aspect
algorithmique de la résolution des problèmes. Nous
avons réussi à démontrer l'aspect polynomial de plusieurs problèmes traités. Lorsque les
problèmes ont une complexité inconnue, nous nous sommes attachés à les comparer et à traiter des
cas particuliers. Le but était double:
résoudre des problèmes particuliers
qui couvrent une grande partie des applications et appréhender par ce biais la difficulté à
résoudre le cas général.
Ce travail est composé de quatre parties.
La première partie est consacrée aux problèmes de reconstruction de matrices binaires sous différentes
contraintes d'adjacence et de périodicité. Nous montrons que le problème de reconstruction d'une matrice
binaire respectant la projection horizontale et la contrainte de 4-adjacence
est polynomial. Nous montrons aussi que le problème de reconstruction d'une matrice
binaire respectant les projections orthogonales et la contrainte de 6-adjacence est NP-Complet. Avec une contrainte de périodicité alternée, nous
montrons que les sous-problèmes de reconstruction de matrices binaires $(1,1)$ alternées périodiques
et $(0,p)$ alternées périodiques sont polynomiaux.
Dans la deuxième partie, nous étudions le problème
de reconstruction de tableaux 3-colorés. Nous formulons ce problème par un programme quadratique continu et nous traitons plusieurs cas polynomiaux.
La troisième partie est consacrée aux problèmes de pavage et
de packing de dominos et de barres. Nous montrons l'aspect polynomial des problèmes étudiés
lorsqu'une seule projection orthogonale est prise en compte. Le résultat principal
de cette partie est la polynomialité
du problème de packing de barres horizontales avec un écart minimal.
Dans la dernière partie, nous étudions un problème de planification
de personnel sous différentes stratégies de placement de repos. Nous traitons trois problèmes: le problème de "base" de planification, le
problème de planification de repos mensuels et le problème de planification de week-ends mensuels. Nous
montrons que les deux premiers problèmes sont polynomiaux en proposant une résolution très simple fondée sur des calculs
algébriques et des algorithmes de flot. Le problème de week-ends
mensuels est de complexité inconnue mais sous certaines restrictions, il est polynomial.
[/b][b]