Séminaire du 19/06/2014, 11h

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.