L'accès à ce séminaire est libre mais nous vous demandons de nous adresser un mail à l'adresse suivante Annie.Marchal@ensta.fr

14h00 Frederic Magniez, LRI, Université Paris-Sud

Chaque année les ordinateurs sont de plus en plus rapides, mais utilisent fondamentalement tous la même physique de Newton. Feynman s'est interrogé en 1982 sur cette restriction. L'idée de l'ordinateur quantique est d'utiliser des phénomènes quantiques pour mener à bien des tâches que nos machines ne savent pas réaliser aujourd'hui. En partant de cette reflexion, Bennett et Brassard ont exhibé en 1984 le premier protocole quantique permettant des conversations chiffrées parfaitement sûres, alors qu'une telle sûreté inconditionelle n'existe pas en classique. A l'opposé, Shor a montré en 1994 comment la plupart des systàmes cryptographiques classiques actuels deviendraient vulnérables par l'utilisation d'un ordinateur quantique (par exemple : cartes bleues, signatures numeriques, conversations chiffrées...). Dans cet exposé, je presenterai les notions importantes de la cryptographie quantique et du calcul quantique ainsi que plusieurs exemples de protocoles et d'algorithmes battant leurs analogues classiques.

15h30 Maurice Margenstern, LITA, Université de Metz

Après un bref rappel de géométrie hyperbolique s'appuyant sur le modèle du disque de Poncaré, nous présenterons la méthode du découpage et la technologie fibonaccienne qu'elle induit sur la pentagrille. Nous verrons comment la méthode s'étend à d'autres pavages du plan hyperbolique ainsi qu'aux espaces hyperboliques de dimension 3 et 4, nous restreignant aux pavages engendrés à partir du pentagone rectangle par complétion orthogonale. Nous verrons ensuite comment on peut implanter des automates cellulaires dans ce contexte, en particulier des automates universels et même intrinsèquement universels. Nous évoquerons au passage des résultats de complexité surprenants touchant au problème P/NP puis nous examinerons quelques problèmes de localisation et d'initialisation liés à l'implantation d'automates cellulaires que nous pourrons rèsoudre grâce à la théorie (élémentaire) des corps.
Nous illustrerons ces possibilités de calcul sur trois exemples à caractère applicatif.