Séminaire : Anciens et nouveaux problèmes en tomographie discrète

Christoph Dürr , chercheur au CNRS DR2 de l'Université Pierre et Marie Curie,  fera une présentation de ses travaux de recherche le jeudi 19 juin 2014 à 11h00 dans la salle C218 au Pôle API d’Illkirch.

Titre : Anciens et nouveaux problèmes en tomographie discrète

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 dominoe

• l'énoncé de la conjecture de partition large.