ENS de Cachan
Département
Informatique
Conférences de rentrée 2010









André Seznec

Le 3/9 de 10h30 à 13h (M1-M2), Salle de Conférences, Pavillon des Jardins

De la microarchitecture

On est aujourd'hui capable d'intégrer plusieurs milliards de transistors sur un seul composant, de cadencer un processeur à 4 Ghz, d'exécuter 4 voire 10 instructions par cycle sur ce processeur et aujourd'hui de mettre plusieurs dizaines de processeurs sur un seul composant. Pourtant les programmes exécutables ont toujours une sémantique séquentielle et une exécution séquentielle des instructions ne permettrait qu'une instruction tous les 1000 cycles.

Le but de cette conférence est d'introduire les principaux mécanismes de microarchitecture qui permettent aux applications de s'exécuter avec une performance proche des performances de crête: le pipeline, l'exécution spéculative, la hiérarchie mémoire, le parallélisme d'instruction et le parallélisme de processus.

Frédéric Magniez

Le 6/9 de 14 à 17h (M1-M2), Salle de Conférences, Pavillon des Jardins

Utilisation de l'aléa en algorithmique

Le but du cours est de montrer comment l'utilisation de l'aléa permet d'élaborer des algorithmes plus efficaces. Au-delà de l'approche traditionnelle, essentiellement fondée sur des systèmes déterministes et discrets, un algorithme probabiliste se saisit des phénomènes probabilistes afin d'optimiser l'utilisation de ses ressources, par exemple de temps et mémoire. Le cours sera divisé en trois parties liées à l'utilisation de trois outils différents :
1. Recherche d'éléments hors d'un sous-groupe par échantillonnage
2. Vérification d'identité polynomiale par échantillonnage (lemme de Schwatz-Zippel)
3. Recherche guidée par une marche aléatoire

Les problèmes pour lesquels seront proposés des algorithmes probabilistes simples, élégants et efficaces sont : Matrix Mutliplication Testing, Commutativity Testing, Perfect Matching, Fingerprint, Associativity Testing, 2-SAT, 3-SAT.

Jean-Paul Laumond

Le 8/9 de 10h à 13h (L3-M1-M2), Salle de Conférences, Pavillon des Jardins

Bases mathématiques du mouvement en robotique

L'algorithmique de la planification de mouvement en robotique est un domaine de recherche apparu il y a une trentaine d'années pour répondre aux besoins de conceptions de machines autonomes, agissant par le mouvement sur leur environnement. La planification de mouvement vise à de doter un système mécanique de capacités de calcul lui permettant de trouver un mouvement répondant à la tâche assignée et respectant les contraintes de non-collision avec les obstacles. Le problème consistant à chercher un mouvement sans collision pour des corps évoluant dans l'espace 3D peut être formulé comme un problème de recherche de chemin pour un point dans un espace caractéristique du système, l'espace des configurations. Cette transformation, empruntée à la mécanique, permet de réduire le problème de la planification de mouvement en un problème de recherche des composantes connexes de l'espace des configurations sans collision.

Comment transformer ce problème de nature topologique en un problème de nature combinatoire ? C'est tout l'enjeu de l'algorithmique de la planification de mouvement.

L'exposé balaiera un historique du domaine qui touche tout aussi bien à la géométrie algébrique réelle qu'à la géométrie différentielle en passant par la géométrie algorithmique. Il présentera des résultats en robotique (programmation de robots et robotique mobile), et également en réalité viruelle et, de manière plus surprenante, en modélisation moléculaire. La conclusion portera sur un certain nombre de problèmes mathématiques ouverts et sur l'ouverture du domaine aux neurosciences.

Hugo Gimbert

Le 9/9 de 14h à 17h (M1-M2), Salle de Conférences, Pavillon des Jardins

Algorithmes pour les jeux stochastiques

Les jeux stochastiques sont un modèle naturel des systèmes à événements discrets dont l'état peut être modifié à la fois par leur environnement, leur contrôleur ou le hasard.

Etant donnés un tel système et une spécification de son comportement, on cherche à calculer un contrôleur qui maximise la probabilité que le comportement du système soit correct, quelque soit les actions de l'environnement.

En d'autres termes, on cherche à calculer la valeur du jeu stochastique ainsi qu'une stratégie optimale du joueur maximiseur. On présentera quelques algorithmes qui permettent ce calcul.

Hubert Comon

Le 14/9 de 9h15 à 10h45 (L3 Math et Info), Salle de Conférences, Pavillon des Jardins

Logique, calculabilité et fondements des mathématiques

Les paradoxes exposés à la fin du 19ème siècle et au début du 20ème ont poussé les mathématiciens a tenter de donner des fondements sûrs aux mathématiques. C'est le programme de Hilbert. Ce programme a déclenché l'essor de la logique mathématique et de la calculabilité, dont un des résultats marquants est dû à Gödel, qui prouve l'impossibilté de compléter le programme de Hilbert. Cet échec n'a nullement mis fin à l'essor de la logique et de la calculabilité, car il se trouve que les bases mathématiques ainsi posées sont aujourd'hui essentielles dans le développement de nombreuses branches de l'informatique.


Contacter le Département Informatique
Dernières modifications : le 09/09/2010