SIESTE 2007-2008

Séminaire d'Informatique pour les Etudiants, Scientifiques, et Tous ceux que l'informatique intéresse à l'ENS Lyon

---------------- 

Note aux orateurs
Contact et renseignements : Natacha Portier
Tous les séminaires ont lieu le mardi à 13h30 dans l'amphi B ou dans l'amphi Schrödinger de l'ENS Lyon


Date Orateur Titre  
mardi  25 septembre 2007 Nathalie Revol
Arithmétique des ordinateurs : calculer de façon rapide, fiable, précise
Transparents 
mardi  2 octobre 2007 Judicaël Courant
Partage de secret
Transparents
mardi  16 octobre 2007 Raymond Namyst
Les architectures multiprocesseurs hiérarchiques seront bientôt partout... Mais sait-on vraiment les programmer ?
Voir la conférence en bas débit, en haut débit.

Transparents
mardi  30 octobre 2007 Guillaume Theyssier
Automates cellulaires : des dynamiques aux calculs, un aller-retour. Voir la conférence en bas débit, en haut débit .

Transparents
mardi  6 novembre 2007 Laure Tougne
Description robuste de formes en géométrie discrète  
mardi  27 novembre 2007
Emmanuelle Lebhar  La navigabilité dans les réseaux, ou : pourquoi connaissez- vous ce maitre yogi Tanzanien ? Voir la conférence en bas débit , en haut débit .

Transparents
mardi  4 décembre 2007
Emmanuel Jeandel

Aspects structurels des pavages
Voir la conférence en bas débit, en haut débit .

Transparents
mardi  11 décembre 2007
Frédéric Mazoit  Poursuite dans les graphes Transparents
mardi  29 janvier 2008 Rémy Malgouyres Illumination globale par voxels Transparents
mardi 12 février 2008 Laurent Bienvenu
La complexité de Kolmogorov, ou comment définir le hasard en informatique Voir la conférence en bas débit , en haut débit .
mardi  26 février 2008 Olivier Bodini
Générateur aléatoire sous modèle de Boltzmann Voir la conférence en bas débit , en haut débit .

Transparents
mardi 8 avril 2008
Arnaud Legrand  Ordonnancement non-coopératif d'applications régulières Voir la conférence en bas débit, en haut débit .

Transparents
mardi 29 avril 2008  Annie Chateau
Intervalles communs de gènes entre génomes d'espèces proches : du modèle mathématique à l'arbre de la vie... Voir la conférence en bas débit, en haut débit .

Transparents
mardi 13 mai 2008
Jacques Patarin
Conversations sur la cryptologie
Voir la conférence en bas débit, en haut débit .

Résumés


Arithmétique des ordinateurs : calculer de façon rapide, fiable, précise


Nathalie Revol, chargée de recherche INRIA, LIP.

Nous commencerons par un tour d'horizon desdifférentes représentations des nombres au cours de l'histoire. Ensuitenous revisiterons les opérations arithmétiques étudiées à l'écoleprimaire (addition, multiplication, division), puis nous verronscomment la notation scientifique vue au collège et que nous appelleronsarithmétique flottanteest utilisée et normalisée sur les ordinateurs. À chaque fois, nousnous attacherons à mettre en évidence les différences entre le calculpar un humain et par un ordinateur ; un aspect que nous souligneronsest celui de la complexité. Nous aborderons enfin les principes del'arithmétique par intervalles, qui est mon domaine de recherche.


Les architectures multiprocesseurs hiérarchiques seront bientôt
       partout... Mais sait-on vraiment les programmer ?

Raymond Namyst, Professeur à l'Université Bordeaux 1

Les calculateurs parallèles les plus puissants sont aujourd'huimajoritairement formés d'un très grand nombre de noeudsmultiprocesseurs interconnectés par un réseau rapide. Dans ce domaine,les évolutions les plus spectaculaires portent essentiellement surl'architecture des noeuds dont le nombre de niveaux hiérarchiquesatteint une ampleur sans précédent. La faute en incombe auxconstructeurs de microprocesseurs qui, après s'être livrés durant 30ans à une course à la fréquence, rivalisent désormais à coups de pucesmulti-coeurs multiprogrammées.

Vu la diversité des temps d'accès mémoire et de communication entreles différentes unités de calcul, ces nouvelles architectures exigent,pour en tirer la quintessence, de répartir les flots d'exécutions, lesdonnées et les communications avec d'extrêmes précautions.

Dans cet exposé, nous examinerons les caractéristiques de ces architectureset la façon dont les utilisateurs tentent de les programmer efficacement.Je présenterai les principaux problèmes rencontrés lorsque, pour aiderces utilisateurs, nous concevons des supports d'exécution pour ces  machines.

Partage de secret


Judicael Courant, chercheur à l'IMAG, Grenoble
(Auteurs : Tarik Kaced & Judicaël Courant)

Sa mémoire étant vacillante, sa gracieuse Majestévoudrait confier le code de la force de frappe nucléaire à ses servicessecrets. Comme un agent malhonnête risquerait de vendre le secret àAl-Qaïda, une méthode est mise au point pour que quelques agentspassants à l'ennemi n'apportent aucune information sur le secret. C'estalors qu'il apparaît que le FSB (successeur du KGB) a infiltré lesservices, de façon à ce que le secret ne puisse être reconstituécorrectement en cas d'attaque russe. Comment détecter les traîtres ?Comment s'en prémunir ? Il y a une possibilité, mais elle comporte unrisque que les ordinateurs du FSB réussissent à découvrir le secret.Comment maîtriser ce risque ?Last but not least, depuis la fin de la guerre froide, les budgetsvarient beaucoup même si la mortalité n'a pas beaucoup baissé dans cemétier ; il faut donc prévoir un moyen de distribuer ce secret à deseffectifs variables et sans cesse renouvelés, sans jamais avoir àreconstituer explicitement le secret (les bureaux n'étant pas à l'abrid'une écoute).La cryptographie au service de sa gracieuse majesté : un James Bondcomme vous n'en avez jamais vu, avec presqu'autant de suspense, un peuplus de maths (mais pas très compliquées), un peu moins d'action, etbeaucoup moins d'érotisme et de sexisme.NB : Le partage de secret a des applications civiles beaucoup plusréalistes qu'on évoquera également.

Automates cellulaires : des dynamiques aux calculs, un aller-retour.

Guillaume Theyssier, chargé de recherches CNRS au laboratoire de mathématiques de l'université de Savoie

Les automates cellulaires sont des systèmes complexes : composés denombreuses entités très simples en interaction, leur comportementglobal est néanmoins très riche et très difficile à prévoir.

La phraseprécédente sonne un peu creux ? L'objectif de cet exposé est justementde lui donner un contenu concret et solide.

Après s'être émerveillés devant quelques exemples qui ne peuvent paslaisser indifférent, nous allons présenter un certain nombre dequestions et d'outils théoriques actuels pour l'étude de ces objets.Nous verrons en particulier que le modèle des automates cellulaires sesitue à un carrefour entre systèmes dynamiques discrets et modèle decalcul, ce qui rend leur étude très riche, avec des points de vuecomplémentaires.

 Description robuste de formes en géométrie discrète


Laure Tougne, Professeure au LIRIS, Laboratoire d'Informatique en Image et Systèmes d'Information

Dans le cadre de cet exposé, nous présenterons tout d’abord la géométrie discrète ; celle-ci étant généralement définie comme l’étude des propriétés géométriques et topologiques de points d’un maillage. Son objectif est la définition d’algorithmes et de méthodes spécialement adaptés à la structure discrète des images. Ces dernières étant obtenues par binarisation après segmentation.

Nous nous focaliserons ensuite sur la problématique de descriptions de formes en utilisant les outils de la géométrie discrète. Nous présenterons alors un certain nombre de travaux ayant pour objectif soit la constitution d’une signature de forme, soit la constitution d’atlas statistiques.

Enfin, l’exposé s’achèvera par la mise en évidence de perspectives.


La navigabilité dans les réseaux, ou : pourquoi connaissez- vous ce maître yogi Tanzanien ?


Emmanuelle Lebhar, chargée de recherches CNRS, LIAFA, Paris VII

La navigabilité des réseaux, ou "effet petit monde", consiste en l'existence de chemins très courts reliant toute paire de points dans des réseaux comportant un très grande nombre d'entités, et dans le fait que ces chemins puissent être découverts localement. Ce  phénomène est aussi connu sous le nom des "6 degrés de séparation" depuis l'expérience de Milgram de 1967 sur un réseau social. Les réseaux concernés par ce phénomène sont nombreux et cruciaux : les réseaux sociaux, le réseau des pages web, la plupart des grands  réseaux de communication...
Dans cet exposé, nous nous intéresserons aux causes de ce phénomène et aux avancées récentes en termes de modélisation de réseaux pour tenter de les comprendre. Nous verrons comment des modèles de graphes aléatoires augmentés peuvent faire émerger ce phénomène et comment nous pouvons les exploiter pour produire des grands réseaux de communication décentralisés très efficaces. Nous verrons également comment l'étude du phénomène "petit monde" peut nous amener à mieux  comprendre la structure du réseau Internet, encore très méconnue.


Aspects structurels des pavages

Emmanuel Jeandel, maître de conférences au LIF

Les pavages, et plus précisément les tuiles de Wang utilisées pendantl'exposé, donnent une formalisation précise des concepts et problèmesrencontrés par tout enfant ou L3 ayant joué avec des pièces de puzzle.Plus formellement, les physiciens les rencontrent dans l'étude desquasicristaux, les mathématiciens dans l'étude de certains systèmesdynamiques, et les biologistes, selon les rumeurs, auraient des raisonsde s'y intéresser.Afin d'essayer de comprendre et d'approfondir une vieille conjecturedûe à Wang infirmée depuis longtemps, nous introduirons une notiond'ordre sur lespavages, et examinerons certaines de ses propriétés.





Poursuite dans les graphes

Frédéric Mazoit, maître de conférences au LABRI

Ces dernières années, les décompositions arborescentes ont pris uneplace de plus en plus importante dans de nombreux domaines del'informatique. En effet, elles constituent peut-être le premier outilgénéraliste de structuration des graphes.

L'une de leurs applications est l'étude de certains jeux où une équipede gendarmes poursuit un fugitif dans un graphe. En restreignantfortement le type de stratégies gagnantes pour les gendarmes et pour levoleur, on obtient deux types d'objets combinatoires: lesdécompositions arborescentes et les « brambles ». Ces deux typesd'objets ne peuvent pas coexister et, ce qui est loin d'être évident,les gendarmes ou le voleur peuvent toujours gagner en utilisant unestratégie de ce type.
Dans mon exposé, je donnerai une idée de la preuve de ce résultat -- le théorème de dualité tree-width/bramble number -- et je présenterai certaines de ses généralisations après avoir décrit en détail le jeu de poursuite, les décompositions arborescentes et les brambles.


Illumination par voxels

Rémy Malgouyres,Professeur d'informatique, Laboratoire d'Algorithmique et Image de Clermont-Ferrand (LAIC)

Générer des images de synthèses 3D impliquent deux choses :la modélisation géométrique et les algorithmes de rendusqui, à partir d'une modélisation de la scène 3D et dessources de lumière, génèrent des images.Il y a toute une panoplie d'algorithmes de rendu, selon que l'on a des contraintes de temps de calcul, comme pourl'affichage temps réel, ou que l'on met l'accent sur leréalisme. L'exposé porte sur la recherche le rendu réalistepar une simulation physiquement correcte des échangesd'énergie lumineuse dans la scène.

Après un bref tour d'horizon des méthode de rendu, on introduitl'équation d'illumination global, qui est une équation intégralelinéaire qui décrit l'état stationaire du flux d'énergie dans la scène.On présente une nouvelle approche pour discrétiser cette équation,ce qui permet d'obtenir un (énorme) système linéaire.Une méthode de complexité optimale pour résoudre numériquement cesystème est présentée, ainsi que les techniques d'affichagequi rendent la méthode praticable.



La complexité de Kolmogorov, ou comment définir le hasard en informatique


Laurent Bienvenu, étudiant en thèse au Laboratoire d'Informatique Fondamentale à Marseille

Supposons que pour occuper une de vos longues soirées d'hiver, vous ayez décidé de lancer une pièce 1000 fois et de noter le résultat de chaque lancer (0 pour pile, 1 pour face). La théorie des probabilités nous dit que toutes les suites de 0 et de 1 de longueur 1000 ont la même probabilité d'être obtenues. Cela dit, si vous obtenez le résultat 00000... (1000 fois), ou encore 000100010001... (250 fois), vous risquez d'être surpris ! La raison pour laquelle de tels résultats nous choquent est qu'ils ne semblent pas "aléatoires". Mais comment formaliser cette intuition ? La complexité de Kolmogorov apporte une réponse satisfaisante à cette question. Cet exposé présentera les bases de cette théorie, ainsi que des applications à la logique (théoreme de Gödel par exemple), à la complexité algorithmique, ou encore à la vraie vie. Aucun prérequis n'est nécessaire, meme si des bases de calculabilité sont bienvenues.


Générateur aléatoire sous modèle de Boltzmann


Olivier Bodini, maître de conférences au Laboratoire d'informatique de Paris 6, le LIP6

La génération aléatoire d'objets de grande taille joue un rôle de plus enplus important dans l'analyse et la compréhension des structures massives que notre société contemporaine génère. Il est, par exemple, possible de mettre en évidence par des jeux de générations aléatoires, l'adéquation ou non de modèles de réseaux d'interaction avec la réalité qu'ils doivent simuler (internet, réseaux biologiques, interactions sociales). De même, la pertinence d'un modèle par rapport à un autre peut être étudiée via des tests génériques.

Nous sommes manifestement confrontés au problème de construire desgénérateurs aléatoires de plus en plus performants dans le sens où ils doivent être en mesure de produire des objets de taille de plus en plus gigantesque.

Les modèles de Boltzmann issus de la physique statistique, ont donnénaissance, combinés avec de la combinatoire analytique, à des algorithmes efficaces (de complexité linéaire lorsque l'on autorise de légères variations en taille) pour la génération aléatoire d'objets dans des classes combinatoires, c'est à dire dans des structures ayant une spécification en termes de constructions combinatoires, telles que Union, Produit, Séquence, Ensemble, Cycle. Cet exposé se veut une introduction à ces méthodes nouvelles.

Ordonnancement non-coopératif d'applications régulières

Arnaud Legrand, chargé de recherche au CNRS au LIG , Grenoble

Lorsque plusieurs applications s'exécutent simultanément sur uneplate-forme de calcul hétérogène, elles entrent en compétition pourl'accès aux ressources de calcul et de communication. Dans cetexposé, nous analysons le comportement de K ordonnanceurs necoopérant pas et utilisant la stratégie qui optimise leur propreperformance. L'équité d'accès aux ressources est donc assurée auniveau du système sans tenir compte des spécificités des différentesapplications. Nous limitons notre étude aux simples plates-formesmaître-esclave et au cas où chaque application est constituée d'untrès grand nombre de tâches indépendantes. Les tâches d'une mêmeapplication ont toutes les mêmes besoins en terme de calcul et decommunications mais ces besoins peuvent varier d'une application àl'autre. Ce type d'applications est typique de celles que l'on peutrencontrer dans des desktop grids. Dans un tel contexte, il estnaturel que chaque application cherche à optimiser son propre débit.

La théorie des jeux offre un formalisme permettant de modéliser ce type de situation. Nous parlerons donc d'équilibre de Nash,d'optimalité au sens de Pareto, de paradoxe de Braess et d'équité et regarderons comment ces notions s'appliquent dans ce contexte précis.


Intervalles communs de gènes entre génomes d'espèces proches : du modèle mathématique à l'arbre de la vie...


Annie Château, Maîtresse de conférences au LIRMM.

Une application majeure des recherches en bioinformatique est de déterminer les relations de parenté entre les espèces vivantes et retracer l'évolution de leurs génomes au cours du temps. Une des façonsd'effectuer la reconstruction de l'arbre de parenté entre des espècesou de préciser à quoi ressemblait un génome ancestral est de s'intéresser à l'ordre des gènes le long de la molécule d'ADN. Eneffet, si dans deux espèces l'ordre est très conservé, il y a de fortechance pour qu'elles se soient séparées "récemment", et donc soientproches l'une de l'autre dans l'arbre des espèces. Je vous présenteraiune mesure de similarité entre les génomes, les intervalles communs,définis de manière très mathématique comme étant des ensembles demarqueurs contigûs dans deux permutations sur un ensemble de gènes ;nous verrons également quelques algorithmes qui les utilisent pourrépondre à des questions concrêtes que l'on se pose sur les génomes,ainsi que quelques exemples d'utilisations sur des données de la vraivie.

Conversations sur la cryptologie

Jacques Patarin, professeur au PRISM , Université de Versailles Saint-Quentin-en-Yvelines

Dans la première partie de cet exposé, Jacques Patarin nous présente sa discipline :la cryptologie. Dans une deuxième partie riche en anecdotes, il nous présente les grandes techniques d'attaques en cryptanalyse, et en particulier les "side channel attacks".

Last Updated ( Friday, 21 May 2010 )  
[ Back ]