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









Emmanuel Grolleau

Le 1/9, 14h-17h (M1-M2),

Introduction au temps réel

Cette présentation introduit la problématique de la validation temporelle pour les systèmes embarqués critiques temps réel. La première partie montre comment on modélise temporellement les systèmes temps réel. La seconde partie présente les résultats classiques de la littérature (années 70 au milieu des années 90) qui sont utilisés sur les systèmes temps réel industriels aujourd'hui. La troisième partie montre comment, depuis les années 90, les modèles et techniques ont évolué pour faciliter le passage à l'échelle des gros systèmes, mais aussi pour réduire le surdimensionnement inhérent à la validation temporelle, et pour faciliter l'aide à la conception et le dimensionnement. Enfin, nous concluons sur les enjeux industriels de demain, où les systèmes seront de plus en plus complexes, et les architectures matérielles embarquées seront multicoeur.

Marie-Claude Gaudel

Le 5/9, 14h-17h (M1-M2),

Test de systèmes informatiques basé sur des méthodes formelles

L'activité de test de logiciel est souvent perçue, à tort, comme purement empirique et ad hoc. Or le test de logiciel pose des problèmes théoriques intéressants, et des approches rigoureuses, basées sur des méthodes formelles, existent et sont l'objet de nombreuses recherches. Après une introduction au sujet, cette conférence donnera un panorama des principaux résultats et des recherches actuelles.

Nicolas Maudet

Le 6/9, 10h-13h (L3-M1-M2),

Choix social computationnel

Lorsque différents agents aux préférences potentiellement contradictoires cherchent à s'accorder sur un choix (typiquement, entre différents candidats lors d'une élection politique), il est courant de procéder à un vote. Mais il existe bien des procédures de vote, aux propriétés très différentes. La théorie du choix social étudie ces questions en adoptant (souvent) une approche axiomatique reposant sur l'identification de propriétés "souhaitables" des règles de vote.

Je commencerai par un bref survol de résultats fondateurs de la théorie du choix social, en illustrant au passage la grande variété de règles de vote envisageables. Je présenterai ensuite un panorama de quelques questions épineuses qui se posent lorsque ces problèmes sont envisagés sous leur aspect computationnel. Par exemple, est-il toujours facile de déterminer le résultat d'une élection ? Quelle quantité d'information faut-il échanger pour y parvenir ? Le système électoral est-il manipulable par les votants ou par les organisateurs ? Est-il raisonnablement utilisable avec un grand nombre de candidats et/ou en présence d'informations incomplètes ?

Olivier Gascuel

Le 7/9, 14h-17h (L3-M1-M2),

Arbres formels et arbre de la vie : définitions, modèles et algorithmes (transparents 1 et 2)

Depuis Darwin les arbres sont centraux pour représenter l'évolution des espèces et des objets biologiques. Je présenterai les nombreuses définitions de la notion d'arbre, la manière de dénombrer les arbres, de les comparer et d'en faire le consensus. Je présenterai plusieurs modèles d'arbres aléatoires, issus de la biologie, de la physique et des mathématiques. J'expliquerai quelques méthodes simples pour reconstruire des arbres évolutifs à partir de séquences biologiques. Je donnerai quelques applications des arbres en biologie et montrerai pourquoi l'inférence des arbres phylogénétiques est centrale dans de nombreux domaines allant de la génomique aux études de biodiversité.

Claire Gardent

Le 8/9, 14h-17h (M1-M2),

Traitement des Langues Naturelles

Le traitement des langues naturelles (TAL) cherche à "faire parler les ordinateurs" et plus précisément, à fournir une modélisation informatique de nos capacités linguistiques. Je commencerai par passer en revue les caractéristiques des langues naturelles et les problèmes que celles ci soulèvent pour un traitement informatique. J'illustrerai ensuite chacun des deux grands courants, statistique et symbolique, exploités dans le domaine du TAL par la présentation de deux sous-tâches du TAL. La première, l'étiquettage morpho-syntaxique, vise à associer les mots d'un texte avec la catégorie morpho-syntaxique appropriée étant donné son contexte. Nous examinerons plusieurs approches possibles dont notamment, une approche probabiliste utilisant les modèles de Markov cachés. La seconde, la génération de phrases, consiste à verbaliser des données numériques ou symboliques et sera utilisée pour illustrer l'approche symbolique. Nous y verrons en particulier, comment des algorithmes d'analyse syntaxique (parsing) peuvent être adaptés pour générer plutôt que pour analyser des phrases.

Lionel Moisan

Le 13/9 de 9h15 à 10h45 (L3 Math et Info),

Synthèse d'images de textures: modèles mathématiques, modèles algorithmiques

Nicolas Ollinger

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

Automates cellulaires, indécidabilité et pavages

Introduits par Ulam et von Neumann dans les années 40, les automates cellulaires forment une riche famille de systèmes dynamiques discrets. L'objectif de cet exposé est d'étudier une propriété dynamique simple de ces objets : la convergence vers un unique point fixe. Plus précisément, existe-t-il un algorithme qui décide si un automate cellulaire possède cette propriété ? Pour répondre à ce type de question, il convient d'abord de préciser ce qu'est un algorithme. C'est la question fondatrice de la théorie de la calculabilité, qui formalise la notion de calcul, de problème indécidable et de réduction adéquate. L'indécidabilité du problème de l'arrêt de machines de Turing permet alors d'établir l'indécidabilité de la pavabilité du plan par un jeu de tuiles colorées, qui permet de démontrer le résultat escompté : il n'existe pas d'algorithme qui décide si toutes les configurations d'un automate cellulaire convergent vers un unique point fixe.


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