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









Jean-Pierre Jouannaud

Formal Mathematics and Application to Computational Mathematics, Software Safety and Internet Security

Les mathématiques formelles visent à outiller le raisonnement mathématique de manière à en assurer la correction. Il s'agit donc d'une étape peut-être ultime dans la voie de la rigueur, qui doit son importance en mathématiques à l'existence de théorèmes fortement calculatoires dont les preuves font nécessairement appel à des calculs

Jean-Bernard Stefani

The kell calculus: an operational basis for distributed component-based programming

We present the Kell calculus, a process calculus which, we claim, embodies key constructs for programming dynamically reconfigurable distributed systems. The Kell calculus is a higher-order pi calculus with localities and locality passivation. We discuss its relation with other process calculi with localities, and show, through examples, how it can capture key features of distributed component-based programming.

We then present a formal operational semantics for the calculus, together with its behavioral theory, and discuss open issues associated with the co-inductive characterization of contextual equivalence in the calculus. We conclude with a discussion of the modelling of component structures with sharing, that are so prevalent in system-level programming.

Véronique Cortier

Les protocoles cryptographiques : comment sécuriser les communications

Avec le développement des réseaux de communication comme internet et la téléphonie mobile, le besoin d'assurer la confidentialité et l'authenticité des messages échangés a considérablement augmenté. Les protocoles cryptographiques sont des règles d'échange entre les points du réseau, ils permettent de sécuriser les communications. Ils sont utilisés par exemple dans le commerce électronique, lorsqu'un client rentre le numéro de sa carte bancaire pour régler un achat. Mais ils interviennent également lors de la connexion à un ordinateur de manière sécurisée, lors de l'envoi des mails si l'on souhaite éviter qu'un indiscret puisse en prendre connaissance ou encore, lorsque l'on consulte le solde de son compte bancaire. Ils sont également au coeur d'objets plus récents comme le porte-monnaie électronique pour empêcher un utilisateur frauduleux de créer de la fausse monnaie artificielle ou même de construire de faux porte-monnaie. Ces quelques exemples montrent qu'il est crucial de s'assurer que les protocoles utilisés n'ont pas de défaut - ou de << failles >> - qui les rendraient vulnérables à des utilisations frauduleuses - appelées << attaques >> - par des personnes malveillantes. Deux approches très différentes ont été développées pour étudier ces protocoles. D'une part, l'approche dite "logique" considère une version simplifiée des protocoles où le chiffrement est vu comme une boîte noire. Cette approche permet d'analyser très précisément, et souvent de manière automatique, la partie "protocole". D'autre part, les algorithmes de chiffrement sont étudiés par les cryptanalystes, en tenant parfaitement compte des fonctions mathématiques utilisées dans les algorithmes. Cette approche semble être plus adaptée pour capturer toutes les attaques possibles dans la réalité mais, en contrepartie, les preuves (lourdes) de sécurité sont effectuées à la main et semblent difficilement automatisables. Nous présenterons les deux approches et nous verrons comment il est possible de combiner les deux.

Johan Montagnat

Traitement d'images médicales et grilles de calcul

Au cours de ce séminaire, je montrerai comment ma formation initiale en informatique "par et pour" la recherche, m'a conduit à étudier le domaine du traitement des images médicales, puis d'une manière plus général l'analyse de données médicales en utilisant des infrastructures telles que les grilles de calcul capables d'accueillir et de manipuler de très grands volumes de données.

Je présenterai le domaine du traitement des images médicales et j'identifierai les problématiques principales attachées à ce champ applicatif. Je dresserai un rapide état des lieux du domaine et je présenterai avec plus de détails nos travaux réalisés en modélisation de structures anatomiques et en segmentation d'images par modèles déformables. En particulier, je montrerai des résultats sur l'extraction du myocarde dans des séquences temporelles d'images cardiaques 3D provenant de différentes modalités.

Je montrerai ensuite comment partant de travaux initiaux sur l'analyse d'images nous nous sommes intéressé à la validation de procédures d'analyse d'images. En l'absence de "vérité terrain" dans le domaine médical, l'évaluation d'un algorithme quantifiant des paramètres cliniques à partir d'images ou la validation de procédures cliniques est rendue difficile. Un approche statistique permet, en s'appuyant sur un grand nombre de données, d'apporter des critères quantitatifs et objectifs sur la qualité des résultats produits.

Enfin, je discuterai du développement récent des infrastructures de grille de calcul et des espoirs qu'elles soulèvent pour l'analyse et le traitement de grand volumes de données médicales, notamment pour des études épidémiologiques ou statistiques. Je ferai état de nos travaux récent dans le domaine pour optimiser l'utilisation des ressources informatiques disponibles avec les hypothèses qui sont sous-jacentes aux infrastructures de grille et aux types d'applications que nous visons.

Je conclurai en discutant du cheminement scientifique suivi qui m'a conduit du domaine de l'analyse d'images à celui de l'informatique répartie autour d'une thématique applicative centrale.

Paul Gastin

Synthèse de contrôleurs pour les systèmes ouverts

Laurence Duchien

Michele Sebag

Apprentissage et Fouille de Données

Un défi de l'informatique, problème ouvert depuis 50 ans, est celui de l'Intelligence Artificielle. A priori, la déduction logique (si Socrate est un homme, et si tous les hommes sont mortels, alors ...) ne devrait pas présenter plus de difficultés pour la machine que le calcul arithmétique.

D'où vient alors la difficulté ? Une des réponses est que les connaissances se trouvent rarement sous forme utilisable par la machine.

L'apprentissage et la fouille de données ont pour objectif, à partir des données disponibles, de construire des hypothèses ; les connaissances ne sont autres que les hypothèses de bonne qualité.

Cet objectif peut être vu comme un jeu à information incomplète. La machine produit des hypothèses à partir d'une information incomplète (par exemple, les données disponibles décrivent un ensemble d'individus malades ou en bonne santé). Les hypothèses produites sont de bonne qualité si elles sont compatibles avec des informations nouvelles (i.e., si elles permettent de classer correctement comme malade ou non des individus ne faisant pas partie de l'échantillon initial).

Le cours illustrera sur plusieurs applications les enjeux et les approches de l'apprentissage et de la fouille de données.

1/L'application Skicat (1994), l'une des premières applications en fouille de données, a montré que l'exploitation automatique des monceaux de données disponibles en astronomie, pouvait rendre faisables des objectifs ambitieux - précédemment hors de portée des astronomes.

2/ Quelles sont les limites de l'apprentissage ? Le surapprentissage consiste à essayer d'apprendre des hypothèses plus précises que ce que les données disponibles autorisent. Informellement : ce n'est pas sérieux de faire des statistiques sur 10 cas... ; formellement, on introduira la théorie de l'apprentissage statistique (Vapnik 95).

3/ Apprentissage fort / apprentissage faible. De manière intéressante, si l'on sait produire des hypothèses "un peu meilleures que le hasard" (sur toute distribution), alors on sait produire des hypothèses arbitrairement bonnes. Ce théorème (Schapire 90) conduit aux approches dites apprentissage d'ensembles (boosting, bagging).

4/ Dans 90% des cas, l'apprentissage et la fouille de données considèrent des exemples représentés par des vecteurs de valeurs (éléments de R^n, ou {0,1}^n). Mais les domaines complexes (langage naturel, chimie,...) font intervenir des exemples structurés. Ainsi, dans le cadre de la caractérisation de molécules cancérigènes, les exemples sont des graphes. L'apprentissage à partir de données structurées s'intéresse à la construction de programmes Prolog (programmation logique inductive).

5/ [Si le temps le permet] l'une des questions clé qui traverse le domaine est de savoir si le résultat de l'apprentissage doit nécessairement être intelligible. Cette question sera discutée, à la lumière de la robotique et de l'aide à la navigation aérienne.

Alain Darte

Optimisations polyhedrales et transformations de programme multi-dimensionnelles


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