Séminaire des Elèves 2004-2005


Note aux orateurs
Contact et renseignements : Eric Thierry .
Tous les séminaires ont lieu le mardi à 13h30 (14h00 à partir de janvier) dans l'amphi B de l'ENS Lyon

Programme des séminaires

 
Date : mardi Orateur Titre
 05 octobre 2004   Pierre Lescanne (LIP, ENS Lyon)
 Les algorithmes des Babyloniens
 19 octobre 2004
 Véronique Cortier (LORIA, Nancy)
 Vérifier les protocoles cryptographiques
 02 novembre 2004
 Jean Mairesse (LIAFA, Paris)
 Tetris, traces, tresses
 16 novembre 2004
 Stéphane Messika (LSV, ENS Cachan)
 Coupling et auto-stabilisation
 30 novembre 2004
 Julien Musset (JPMorgan, Londres)
 Modélisation financière pour des produits dérivés
 14 décembre 2004
 Jérome Haubert (LIH, Le Havre)
 Les Systèmes de Gestion de Base de Données Temps Réel
 04 janvier 2005
 François Pottier (INRIA, Rocquencourt)
 Vers des analyseurs syntaxiques efficaces et bien typés
 25 janvier 2005
 Didier Caucal (IRISA, Rennes)
 Un survol sur les automates infinis
 08 février 2005
 Abdoulaye Gamatie (IRISA, Rennes)
 Approche synchrone pour la conception des systèmes temps réel
 01 mars 2005
 Laurent Vuillon (LAMA, Univ de Savoie)
 A la recherche de la combinatoire des mots
 15 mars 2005


 29 mars 2005
 Isabelle Collet (Univ Paris 10, CREF)
 Représentation de soi, représentation de l'informaticien-type :
 une piste pour comprendre des choix d'orientation différents selon les sexes?

 26 avril 2005
 Daniel Bonniot (INRIA, Rocquencourt)
 Vers des langages plus expressifs et modulaires:
 les multi-méthodes, motivations et défis

 03 mai 2005
 Claude-Pierre Jeannerod (LIP, ENS Lyon)
 Algorithmes pour la multiplication des grands entiers.


À voir également

L'historique


Résumés des séminaires


Les Algorithmes des Babyloniens



Date
05 octobre 2004

Orateur
Pierre Lescanne (Equipe Plume, LIP, ENS Lyon)

Résumé
Les Babyloniens du temps d'Hammourabi étaient de fantastiques calculateurs. Comme ils ne connaissaient pas l'algèbre, ils décrivaient leur calculs algorithmiquement. En m'inspirant d'un article de D. Knuth, je vous montrerai qu'ils avaient mis au point des méthodes très astucieuses et que notamment ils calculaient en virgule
flottante. J'espère ainsi vous montrer que le niveau de leur connaissance en "info" était, il y a quatre millénaire, plus élevé qu'on ne le croit.



Présentation

http://perso.ens-lyon.fr/pierre.lescanne/transparency.html







Vérifier les protocoles cryptographiques



Date
19 octobre 2004


Orateur
Véronique Cortier (Equipe Cassis, LORIA, Nancy)

Résumé
Les protocoles cryptographiques sont des petits programmes d'échanges de messages sur un réseau. Ils servent à assurer par exemple la confidentialité et l'authenticité des communications. Pour assurer ces propriétés de sécurité, des moyens algorithmiques, tels que les chiffrements et les fonctions à sens unique ont été mis au point; ils permettent d'assurer  par exemple qu'il est très improbable qu'un individu puisse obtenir un message en clair à partir d'un message chiffré sans connaître la clef de déchiffrement.

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.













Tetris, traces, tresses



Date
02 novembre 2004


Orateur
Jean Mairesse (LIAFA, Paris 7)

Résumé
Le but de l'exposé est de justifier la juxtaposition des trois mots apparaissant dans le titre.

La thématique générale est l'étude des "systèmes à événements discrets" (SED), c'est-à-dire des systèmes concus par l'homme, obéissant à des règles opérationnelles, ou algorithmes, et dont les transformations ont lieu à des instants discrets, en réponse à des événements ponctuels. L'objectif peut etre de calculer le débit d'un SED ou encore de l'optimiser en faisant varier certains paramètres du modèle.













Coupling et auto-stabilisation



Date
16 novembre 2004


Orateur
Stéphane Messika (LSV, ENS Cachan)


Résumé
Un système probabiliste est dit ``auto-stabilisant'' lorsque, quelle que soit sa configuration de départ, il atteint (presque sûrement) le sous-ensemble donné des configurations légales.Cette propriété fournit notamment un intéressant modèle de résistance aux pannes. Il est essentiel de pouvoir non seulement garantir la propriété d'auto-stabilisation d'un algorithme donné, mais également d'estimer le temps d'auto-stabilisation.

Nous montrons ici comment des méthodes mathématiques, telles que le "coupling", développées pour simuler des chaines de Markov, donnent de nouveaux critères d'auto-stabilisation, ainsi qu'une meilleure analyse de la vitesse de convergence. Nous donnons quelques exemples de telles méthodes et diverses applications, comme l'analyse de l'algorithme du dilemme du prisonnier itéré.

Cet exposé est basé sur l'article:

http://www.lsv.ens-cachan.fr/Publis/PAPERS/FMP-disc04.ps













Modélisation financière pour les produits dérivés



Date
30 novembre 2004


Orateur
Julien Musset (JPMorgan, Londres)

Résumé
Apres le MIM et une these en logique, je travaille en recherche derive-action en tant que chercheur quantitatif  IT
pour la banque d'investissement americaine JPMorgan.

La presentation abordera les points suivants:
 - le concept d'investissement et le role des banques d'affaires
 - exemples de produits financiers: actions, credit, produits derives
 - modelisation des risques financiers par des processus stochastiques:
        + notion de mesure de risque neutre
        + modeles binaires et stochastiques (processus d'Ito, Radon-Nykodym, theoreme de Girsanov, formule de Black-Scholes)

Je terminerai par presenter le groupe de Recherche Quantitative chez JPMorgan et des possibilites de stage ou d'emploi.













Les Systèmes de Gestion de Base de Données Temps Réel



Date
14 décembre 2004


Orateur
Jérôme Haubert (LIH, Le Havre)

Résumé
Les Systèmes de Gestion de Base de Données Temps Réel (SGBDTR) permettent de regrouper les avantages des systèmes temps réel (STR) et des SGBD classiques. En effet, ils permettent de manipuler de grandes quantités de données tout en tenant compte des contraintes temps réel à la fois des données contenues dans la base et des opérations sur ces données. Le but de ce séminaire est de présenter le fonctionnement général d'un SGBDTR et plus particulièrement la gestion des transactions temps réel. Pour cela, une représentation globale des SGBD classiques d'une part et des systèmes temps réel d'autre part permettra de comprendre la problématique des SGBDTR. Il s'agit, entre autre, d'intégrer et/ou d'adapter les résultats obtenus dans ces deux domaines pour proposer des mécanismes adéquats à la gestion des données et des transactions temps réel. Ensuite, nous nous intéresserons plus particulièrement à la gestion des transactions temps réel et au contrôle de concurrence de ces transactions. Je présenterai ainsi mes travaux de thèse et les résultats que nous avons obtenus. Pour illustrer mes propos, je garderai un exemple en fil conducteur sur lequel j'appliquerai les résultats que je présenterai. Enfin, je terminerai en exposant quelques perspectives de recherche que nous examinons à plus ou moins long terme.













Vers des analyseurs syntaxiques efficaces et bien typés



Date
04 janvier 2005


Orateur
François Pottier (INRIA)

Résumé
Les analyseurs syntaxiques produits par yacc sont constitués d'un automate à pile déterministe. La pile d'un tel automate est une structure de données hétérogène, au sens où elle contient une suite de valeurs sémantiques de
différents types. Seule la connaissance de l'état courant de l'automate permet de prédire les types de ces valeurs, donc d'exploiter le contenu de la pile. Malheureusement, le système de types de ML, trop limité, ne permet pas
d'exprimer ce lien entre état courant et structure de la pile. Ce handicap oblige les générateurs existants (ML-Yacc, ocamlyacc, happy) à choisir entre (i) produire des analyseurs syntaxiques bien typés, mais effectuant des tests dynamiques superflus et (ii) produire des analyseurs plus efficaces, mais non typés, donc potentiellement incorrects.

Au cours de cet exposé, je montrerai comment utiliser une extension récente de ML, connue sous le nom de types algébriques généralisés, pour engendrer des analyseurs syntaxiques bien typés et efficaces. Cette extension permet
d'exprimer le lien entre l'état courant de l'automate et le contenu de sa pile. Les types algébriques généralisés rappellent les types inductifs de Coq, mais n'exigent aucun recours à la notion de type dépendant.














Un survol sur les automates infinis



Date
25 janvier 2005

Orateur
Didier Caucal (IRISA, Rennes)

Résumé
Un automate est un graphe orienté étiqueté dont on a désigné des sommets d'entrée et de sortie. Un automate reconnaît le langage des mots étiquetant les chemins allant d'une entrée à une sortie. Les automates n'ayant qu'un nombre fini de sommets sont bien connus : ce sont les automates finis reconnaissant les langages réguliers.
Depuis une vingtaine d'année, des automates ayant un ensemble dénombrable de sommets et de présentation finie ont été étudiés. Le but de cet exposé est de donner un survol sur ces automates infinis, et de montrer comment la régularité de ces automates a apporté une vision nouvelle dans des domaines aussi variés que la théorie des langages, la théorie des jeux et la vérification.














Approche synchrone pour la conception des systèmes temps réel



Date
08 février 2005

Orateur
Abdoulaye Gamatie (IRISA, Rennes)

Résumé
Les systèmes temps réel sont des dispositifs constitués de matériels et de logiciels soumis à des contraintes à la fois fonctionnelles et temporelles pour réaliser des traitements, et agir sur leur environnement. Des exemples de domaines où on rencontre de tels systèmes sont les télécommunications, le nucléaire, l'avionique ou le médical. Ces systèmes sont souvent critiques à cause d'enjeux humains et économiques importants. Leur développement exige donc des méthodes très fiables. L'approche synchrone a été proposée dans le but de répondre à cette attente. Ses fondements mathématiques offrent un cadre formel propice à la description et la validation des systèmes temps réel.

L'exposé proposé commence par une introduction générale aux systèmes temps réel. Ensuite, il donne un aperçu de l'approche synchrone au travers du langage Signal. Enfin, il illustre une démarche de conception synchrone appliquée à l'avionique.














A la recherche de la combinatoire des mots



Date
01 mars 2005

Orateur
Laurent Vuillon (LAMA, Univ de Savoie)

Résumé
Le but de cette exposé est de présenter plusieurs mots infinis sur un alphabet fini donnés par morphismes itérés, par systèmes dynamiques discrets ou encore par des transducteurs. Chacun de ces mots sera construit par des règles auto-référentes disons « amusantes ». Ces objets mathématiques apparaissent naturellement en informatique théorique mais aussi dans beaucoup d'autres domaines (physique, chimie, astronomie, mathématiques, ...).

L'enjeu pour ce séminaire sera d'abord de voir certains outils de la combinatoire de mots et des systèmes dynamiques discrets. Ensuite de considérer des problèmes ouverts depuis plus de 20 ans dont les énoncés sont simples et compréhensibles par « tout le monde », mais dont la résolution reste encore inabordable à l'heure actuelle. Cette approche nous permettra de sentir la frontière entre problème résolu et problème de recherche. Et ainsi de s'approcher de la démarche du chercheur en informatique théorique qui demande imagination, pugnacité, passion et bien sûr sérieux!















Représentation de soi, représentation de l'informaticien-type : une piste pour comprendre des choix d'orientation différents selon les sexes ?



Date
29  mars 2005

Orateur
Isabelle Collet  (Université Paris 10 - CREF)

Résumé
Cette communication présente une enquête qui étudie chez les étudiant-e-s de première année de licence scientifique la stratégie d'appariement soi-prototype par rapport aux métiers de l'informatique.

Elle a été menée à Lyon I en tout début d'année universitaire 2004-2005 et utilise en toile de fond théorique un travail de thèse qui cherche à comprendre pourquoi tant de garçons mais si peu de filles choisissent la filière informatique.

Les hypothèses que cette enquète cherche à valider sont les suivantes :
- Il existe dans les représentations des étudiant-e-s un prototype de l'informaticien qui se définit avec des descripteurs considérés généralement comme relevant du masculin.
- Les étudiant-e-s visant une orientation en informatique témoignent d'un meilleur appariement soi-prototype que les autres étudiant-e-s.
- Les étudiants manifestent de manière générale une meilleure congruence entre image de soi et image de l'informaticien-type que les étudiantes.













Vers des langages plus expressifs et modulaires: les multi-méthodes, motivations et défis 



Date
26 avril 2005

Orateur
Daniel Bonniot (INRIA, Rocquencourt)


Résumé
Chaque famille de langages de programmation encourage l'écriture des programmes selon un certain style. En particulier, la plupart des langages généralistes modernes appartiennent soit à la famille des langages fonctionnels, soit à celle des langages orientés objets. Chaque style convient particulièrement bien à certaines
situations, permettant l'écriture de programmes concis et clairs. Toutefois, d'autres situations nécessitent des programmes artificiellement compliqués et difficiles à faire évoluer par la suite. Un autre langage permet parfois de mieux traiter cette situation. Il est donc très important de bien choisir un langage en fonction de la tâche à accomplir. Toutefois, il est souvent difficile de savoir à l'avance quel genre de situation on va rencontrer. Il est donc intéressant d'inventer de nouveaux langages qui combinent au maximum les avantages des différentes familles existantes.

Pour illustrer cette situation, nous allons écrire progressivement de petit programmes simulant le jeu pierre-ciseaux-papier en introduisant simplement les concepts des langages fonctionnels et orientés objets. Nous verrons ainsi les atouts et les inconvénients de chacun. Ensuite, nous chercherons à inventer un nouveau langage qui nous permettra de ne garder que les avantages, en présentant le concept de multi-méthode.

Dans un deuxième temps, nous donnerons un aperçu des thèmes de recherche ouverts par le support des multi-méthodes ainsi que les solutions existantes.



Lien

Le langage de programmation Nice: http://nice.sourceforge.net/








Algorithmes pour la multiplication des grands entiers



Date
3 mai 2005

Orateur
Claude-Pierre Jeannerod (Equipe Arenaire, LIP, ENS Lyon)


Résumé

Des domaines comme la théorie des nombres ou la cryptologie demandent de plus en plus de pouvoir manipuler de très grands nombres entiers et des bibliothèques d'arithmétique multi-précision efficace, comme GMP (GNU Multiple Precision), sont aujourd'hui disponibles. A quels algorithmes les logiciels de ce genre doivent-ils, au moins en partie, leurs performances ? Cet exposé apportera quelques réponses, en prenant l'exemple de la multiplication. Ce sera l'occasion de faire un tour d'horizon des techniques algorithmiques qui ont permis, en une petite dizaine d'années, de passer de la méthode "classique" (apprise à l'école) à un algorithme de coût quasiment-linéaire en la taille de la sortie. On verra aussi que bon nombre d'algorithmes de multiplication entière peuvent en fait être vus comme autant de cas particuliers d'une même méthode, qui consiste à évaluer/interpoler des polynômes rapidement.













Mis à jour par Eric Thierry.