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









Marc Zeitoun

Le 2/9 de 13h30 à 16h30 (M1-M2)

Deux aspects des automates en informatique. Applications à la vérification et aspects théoriques

La conférence rappellera d'abord les définitions standard et les aspects importants des automates finis. La seconde partie a pour objectif d'expliquer le rôle central des automates dans le domaine pratique de la vérification automatique de protocoles. La dernière partie traitera d'aspects plus théoriques et montrera que même ces objets très simples posent des problèmes encore ouverts.

Merouane Debbah

Le 3/9 de 13h30 à 16h30 (M1-M2)

Matrices aléatoires et télécommunications : De Wigner à Shannon

Le comportement des valeurs propres des matrices aléatoires a été étudié depuis les années 50. Les premiers travaux dans ce domaine datent d'Eugène Wigner en 1955 qui remarqua que la distribution empirique des valeurs propres d'une matrice hermitienne à entrées indépendantes et identiquement distribuées converge (quand les dimensions du système augmente) vers une distribution limite connue, la loi semi-circulaire. Dès ce moment, l'étude des matrices matrices aléatoires a eu un impact énorme en physique théorique ainsi qu'en théorie des probabilités pour prédire l'évolution des systèmes complexes.. En télécommunications, ce n'est qu'en 1997 que les matrices aléatoires sont apparues comme un moyen adéquat de prédire la capacité de Shannon du nombre importants d'éléments (portables, stations de base,..) en interaction dans le réseau sans fils. Dès lors, les recherches sont devenues très actives pour permettre le "design" des systèmes sans fils de 4ème génération (WiMAX, Long Term Evolution, radio flexible,..) de 2010. Dans cet exposé, nous décrirons les avancées majeures et les liens importants entre les matrices aléatoires et les télécommunications sans fils.

Jean-Daniel Boissonnat

Le 5/9 de 13h30 à 16h30 (L3-M1-M2)

Algorithmique des triangulations et modélisation géométrique

Trianguler des formes complexes, c'est les découper en simplexes (triangles en dimension 2, tétraèdres en dimension 3 etc). Cette approche réductionniste a été initiée par H. Poincaré, le fondateur de la topologie algébrique, au début du 20ième siècle. Elle prend avec l'informatique un nouvel essor et les triangulations se trouvent au coeur de l'analyse numérique, l'informatique graphique, la robotique qui doivent trianguler leurs objets d'étude, espaces fonctionnels, mondes virtuels ou espaces de configuration. La première partie de l'exposé présentera quelques résultats combinatoires et algorithmiques sur les triangulations des domaines plans et la difficulté qu'il y a à les étendre en dimension 3. La deuxième partie introduira une triangulation particulière, la triangulation de Delaunay. On montrera son lien avec les enveloppes convexes et par dualité avec les diagrammes de Voronoi. En découlent de nombreuses propriétés qui expliquent que les triangulations de Delaunay sont aujourd'hui utilisées dans de nombreux domaines scientifiques. On montrera également comment leur calcul est dévenu très efficace grâce au développement de techniques probabilistes (randomisation) qui ont révolutionné le calcul géométrique. La troisième partie abordera la question de la triangulation de domaines courbes. La triangulation de Delaunay joue là encore un rôle central et permet d'échantillonner et construire des approximations polyédriques de formes complexes. Bien souvent en pratique, le domaine n'est connu qu'au moyen de mesures (image 3D, nuages de point). Il s'agit alors de déterminer sous quelles conditions d'échantillonnage on peut garantir une reconstruction correcte. Les triangulations sont devenues des structures de données indispensables à la modélisation du monde réél. La géométrie retrouve avec elles son sens éthymologique.

Marie-Christine Rousset

Le 8/9 de 9h à 12h (M1-M2)

Approches logiques pour l'intégration d'informations

Face à la multiplicité et l'hétérogénéité d'informations disponibles en ligne, l'intégration d'informations est un problème majeur sur le plan pratique et théorique. Dans cet exposé, on montrera que la logique offre un cadre formel et des algorithmes d'inférence appropriés pour décrire et interroger un ensemble de sources dinformations distribuées et hétérogènes. D'un point de vue logique, le problème d'intégration d'informations a deux volets. Le problème de modélisation consiste à spécifier dans un formalisme logique les correspondances sémantiques entre les différentes sources d'information, eventuellement à travers une ontologie pivot. Le problème de raisonnement consiste à définir des algorithmes de raisonnement appropriés pour reformuler et décomposer les requêres initiales en des requêtes exécutables par les différenres sources, et combiner de manière adéquate les réponses obtenues. Dans cet exposé, on présentera certains formalismes logiques comme les logiques de description. On montrera l'impact sur la complexité du calcul des réponses, de la sémantique et du pouvoir d'expression des formalismes logiques utilisés pour la description du contenu des sources de données et les requêtes associées.

Jean-Michel Muller

Le 9/9 de 11h15 à 12h45 (L3 Math Info)

Calculs "exacts" avec une arithmétique approchée

L'arithmétique virgule flottante a été conçue comme une simple approximation de l'arithmétique réelle.Cependant, comme le comportement de chaque opération est complètement spécifié par une norme (la norme IEEE-754), l'arithmétique virgule flottante peut aussi être vue comme une structure mathématique sur laquelle on peut construire des algorithmes et des preuves. C'est ainsi que l'on peut construire des algorithmes arithmétiques nettement plus rapides et précis que ce que l'on pouvait faire auparavant. On donnera quelques exemples montrant l'intérêt de cette approche. On en profitera également pour donner un aperçu des nouveautés figurant dans la révision de la norme IEEE-754, qui est presque finalisée.

Hidde de Jong

Le 10/9 de 9h à 12h (L3-M1-M2)

Comment les bactéries s'adaptent-elles au stress ? Modélisation et simulation des réseaux de régulation génique

L'adaptation de microorganismes à leur environnement est régulée au niveau moléculaire par des réseaux complexes de réactions biochimiques. Ils impliquent des gènes, des protéines, des ARN, mais aussi des métabolites et de petites molécules de signalisation. La biologie moléculaire a permis d'identifier une grande partie des composants moléculaires de ces réseaux de régulation. Mais la compréhension du fonctionnement de l'ensemble exige de nouveaux outils, dont la modélisation mathématique et la simulation par ordinateur. La première partie des cours donne un aperçu de la problématique biologique et une introduction à la modélisation des réseaux de régulation génique par des systèmes d'équations différentielles. Dans la deuxième partie des cours, nous regardons plus en détail les modèles d'équations différentielles linéaires par morceaux, qui permettent d'analyser la dynamique qualitative des réseaux en absence de valeurs de paramètres précises. L'application de ces modèles est illustrée par une étude de la réponse à une privation en sources de carbone de la bactérie Escherichia coli.

Daniel Vanderpooten

Le 11/9 de 9h à 12h (L3-M1-M2)

Aide multicritère à la décision : concepts, méthodes et perspectives

Dans de nombreux contextes décisionnels, la prise en compte d'un critère unique pour refléter les préférences s'avère parfois délicate. En effet, dès lors que plusieurs points de vues conflictuels interviennent (ex : aspects techniques vs aspects économiques vs aspects environnementaux), ou que ces points de vue s'expriment sur des échelles hétérogènes (ce qui rend leur agrégation difficile et donc nécessairement arbitraire), il peut sembler plus approprié de recourir à une approche multicritère. Après avoir introduit quelques concepts fondamentaux, nous situerons l'approche multicritère par rapport à l'approche monocritère, soulignant l'intérêt mais aussi les difficultés qu'entraîne le recours à des critères multiples. Abordant les méthodes, nous commencerons par une présentation critique de la somme pondérée, soulignant des limites importantes, simples et souvent méconnues. Nous procéderons ensuite à un bref panorama des différentes familles de méthodes multicritères. Nous concluerons en présentant quelques-uns des enjeux qui nous semblent importants.


Contacter le Département Informatique
Dernières modifications : le 10/11/2008