Résumé de séminaire

Résumé :

Le but de cet exposé est de présenter une introduction aux techniques de la tomographie discrète. Ce domaine a pour objet la reconstruction de matrice à valeurs dans {0,1} connaissant un petit nombre de projections (les projections ou contraintes tomographiques sont des vecteurs donnant par exemple le nombre de 1 sur chaque ligne et le nombre de 1 sur chaque colonne). Nous présenterons l'algorithme de Ryser pour la reconstruction de matrices connaissant les projections verticale et horizontale, puis la reconstruction de polyominos horizontalement et verticalement convexes avec contraintes tomographiques. Les méthodes utilisées font appel à la géométrie discrète mais aussi à des réductions à 2-SAT. Enfin, nous aborderons des résultats récents sur la reconstruction de matrices avec périodicité et contraintes tomographiques.

Références :

Home page : http://liafa.jussieu.fr/~vuillon