Séminaire du 19/06/2014, 11h
Aller à la navigation
Aller à la recherche
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.