Différences entre les versions de « Séminaire du 19/06/2014, 11h »
Aller à la navigation
Aller à la recherche
(Page créée avec « jeudi 19 juin 2014, 11h00 ===== A survey on discrete tomography ===== Conférencier : '''[http://www-desir.lip6.fr/~durrc/ Christoph Dürr] ''' (LIP6) Résumé : à venir. ») |
|||
| Ligne 1 : | Ligne 1 : | ||
jeudi 19 juin 2014, 11h00 | jeudi 19 juin 2014, 11h00 | ||
| − | ===== | + | ===== Anciens et nouveaux problèmes en tomographie discrète ===== |
Conférencier : '''[http://www-desir.lip6.fr/~durrc/ Christoph Dürr] ''' (LIP6) | Conférencier : '''[http://www-desir.lip6.fr/~durrc/ Christoph Dürr] ''' (LIP6) | ||
| − | Résumé : à | + | Résumé : La tomographie discrète consiste à produire une matrice — pour faire simple — dont la somme sur chaque ligne et colonne, correspond à des valeurs données, appelés projections. Cet exposé donnera un survol des techniques principales utilisées dans ce domaine pour terminer sur un problème ouvert. Concrètement on mentionnera : |
| + | * le théorème de Ryser qui caractérise les vecteurs r,s tel qu'il existe une matrice binaire M, avec ri = sum_j Mij et sj= sum_i Mij. La caractérisation demande que le conjugué de r domine s. | ||
| + | * un algorithme pour le cas où on demande que les 1 dans M soient dans des positions convexes. Cet algorithme repose sur une réduction vers 2-SAT. | ||
| + | * une description de la réduction clé pour un algorithme de reconstruction de pavages de dominoes | ||
| + | * l'énoncé de la conjecture de partition large. | ||
Version actuelle datée du 16 juin 2014 à 08:26
jeudi 19 juin 2014, 11h00
Anciens et nouveaux problèmes en tomographie discrète
Conférencier : Christoph Dürr (LIP6)
Résumé : La tomographie discrète consiste à produire une matrice — pour faire simple — dont la somme sur chaque ligne et colonne, correspond à des valeurs données, appelés projections. Cet exposé donnera un survol des techniques principales utilisées dans ce domaine pour terminer sur un problème ouvert. Concrètement on mentionnera :
- le théorème de Ryser qui caractérise les vecteurs r,s tel qu'il existe une matrice binaire M, avec ri = sum_j Mij et sj= sum_i Mij. La caractérisation demande que le conjugué de r domine s.
- un algorithme pour le cas où on demande que les 1 dans M soient dans des positions convexes. Cet algorithme repose sur une réduction vers 2-SAT.
- une description de la réduction clé pour un algorithme de reconstruction de pavages de dominoes
- l'énoncé de la conjecture de partition large.