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.
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".