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
| 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 |
| |
|
| 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.
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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!
|
|
|
| |
|
| 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.
|
|
|
| |
|
| 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/ |
| |
|
| 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.
|
|
|
| |
|