SIESTE 2008-2009
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
Résumés
Minorité
stochastique sur les graphes
Damien Regnault, LIP
Nous considérons un graphe où les cellules sont caractérisées par un
état qui est soit noir, soit blanc. À chaque pas de temps, une
cellule, choisie aléatoirement, se met à jour et passe dans l'état
minoritaire dans son voisinage. L'évolution globale de ce processus ne
semble pas dépendre de la topologie du graphe: dans un premier temps
des régions, pavées par des motifs dépendant de la topologie du
graphe, se forment rapidement. Puis dans un deuxième temps, les
frontières entre ces régions évoluent jusqu'à devenir relativement
stables. Nous étudions ce processus sous différentes topologies :
arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que
même si ce processus se comporte à priori globalement de la même
manière sur n'importe quel graphe, modifier la topologie influence la
façon dont les régions sont pavées (rayures, damiers), la structure et
les mouvements des frontières entre les régions, l'ensemble limite, le
temps de relaxation (le temps nécessaire pour que le processus
atteigne une configuration de l'ensemble limite). Ainsi, Minorité
entraîne des comportements riches et variés qui se révèlent difficile à
analyser. Comprendre cette règle simple est néanmoins nécessaire
avant de considérer des règles plus compliquées.
Du théorème de récursion de Kleene à la détection virale
Jean-Yves Marion, professeur d'université au LORIA
Dans cet exposé, nous traiterons de virologie informatique et de codes
malveillants. Si les enjeux de société sont clairs, la recherche
académique ne s'’est guère intéressée à ce sujet. Pourtant, nous
verrons que la virologie s’'appuie sur des résultats importants comme
le théorème de récursion de Kleene ou comme les systèmes
autoreproducteurs (von Neumann). Nous dresserons un rapide état général
de la recherche et des problèmes soulevés. En particulier, nous
aborderons la délicate question de la détection des malwares.
Calcul scientifique performant sur carte graphique; exemple
d'applications en traitement d'image : accélération d'un algorithme
d'Inpainting
Pierre Kestener, ingénieur-chercheur au CEA à Saclay.
Je présenterai en préalable quelques rudiments sur la programmation des
cartes graphiques modernes et expliquerai pourquoi il y a une grosse
effervescence actuelle autour de leur utilisation en calcul scientifique.
Calculs du déterminant
Guillaume Malod, maître de conférences, équipe de logique de Jussieu, sous-équipe complexité et applications à l'informatique, Paris 7
Le déterminant est un objet mathématique bien connu pour le rôle qu'il
joue en algèbre linéaire, où l'on donne en général un calcul par
élimination. Mais il est aussi intéressant pour ses interprétations en
complexité et en combinatoire. Je présenterai certain de ces aspects,
ainsi que des questions ouvertes qui demeurent.
On the Roles of Computer Science in Systems Biology
Oded Maler
, CNRS-VERIMAG
In this talk I argue that informatics (computer science) is not only a
functional *tool* in the service of Biology, but that it should be a
fundamental part of the mathematics and physics of Biology. In
particular, certain threads of CS research (which I, incidently, happen
to work on) can facilitate the proliferation of more unified dynamical
systems models into Biology. To show what I mean I first give a crash
course in verification and then illustrate with 3 examples: adding
timing information to genetic regulatory networks, reducing the number
of false positives in discrete abstractions of continuous dynamical
systems and computing tubes of trajectories for some nonlinear systems.
Décomposition de graphes
Nicolas Trotignon, chargé de recherche CNRS, LIAFA
A travers un exemple, nous verrons comment des théorèmes de
décomposition de graphes aident à résoudre des questions algorithmiques
(coloration, détection de sous-graphes). L'exemple que nous étudierons
sera celui de la classe des graphes ne contenant pas de cycle avec une
seule corde comme sous-graphe induit. Nous montrerons que ces graphes
sont ou bien dans une classe de base très simple, ou bien décomposables
selon des règles simples elles aussi. Nous un déduirons un algorithme
de coloration. Nous replacerons l'étude de cette classe de graphes dans
un contexte de recherche plus général et très actif ces dernières
années.
Factoriser des entiers pour casser RSA
Pierrick Gaudry, chargé de recherche CNRS, projet CACAO, LORIA
Le système de cryptographie à clef publique RSA est le plus célèbre
et est encore très largement utilisé. C'est par exemple très souvent
grâce à lui que les connections "https" sont sécurisées. La sécurité de
RSA
s'appuie sur la difficulté algorithmique qu'il y a à trouver la
décomposition en facteurs premiers d'un entier donné: c'est le problème
de la factorisation. Dans cet exposé, je présenterai quelques
algorithmes de factorisation, du plus simple, où l'on essaie de diviser
par tous les nombres premiers dans l'ordre, au plus complexe,
l'algorithme du crible algébrique qui est mis en oeuvre pour les plus
grosses factorisations. J'illustrerai mon propos avec des données
numériques issues du calcul en cours RSA-768, qui devrait établir un
nouveau record lorsqu'il sera
terminé.
Raccourcissement de courbes et décomposition de surfaces
Eric Colin de Verdière, Chargé de recherche CNRS dans l'équipe
GéCoaL du
Département d'Informatique de
l'École normale supérieure (Paris).
Étant donnée une surface « compliquée » (homéomorphe à une sphère à laquelle on
accole des poignées), comment la découper pour la rendre planaire (homéomorphe
à un disque) ? Comment trouver la plus courte courbe fermée qu'on ne peut pas
contracter en un point en restant sur la surface ? Comment raccourcir autant
que possible une courbe sur une surface ?
Le but de l'exposé est de présenter les techniques algorithmiques développées
récemment pour résoudre ce type de questions, qui appartiennent au domaine de
la topologie algorithmique et qui sont motivées par diverses applications. Par
exemple, découper une surface constitue souvent un passage obligé en
infographie (pour y plaquer une texture) ou en modélisation géométrique (pour
la paramétrer par un domaine planaire).
Calculer sur les réels, calculer avec les réels
Emmanuel Hainry, maître de conférences au LORIA
Les ordinateurs classiques manipulent des entiers en un temps discret.
Malgré cela, ils sont souvent utilisés pour simuler des phénomènes
physiques essentiellement continus se déroulant en temps continu. Il
existe pourtant des machines, systèmes et modèles travaillant en temps
continu et/ou sur un espace continu. Ces machines semblent donc mieux
préparées pour réaliser ces simulations.
Nous verrons dans cet exposé différentes machines et différents modèles
de calcul sur les réels. Nous présenterons en particulier les problèmes
qu'amènent le temps continu et l'espace continu. Nous verrons également
que divers modèles peuvent avoir des puissance de calcul diverses qui
peuvent aller au delà de ce que peut calculer un ordinateur classique.
Navigability Emergence in Social Networks
Pierre Fraigniaud, Directeur de Recherche au cnrs, LIAFA
We propose a dynamical process for network evolution, aiming at
explaining the emergence of the small world phenomenon, i.e., the
statistical observation that any pair of individuals are linked by a
short chain of acquaintances computable by a simple decentralized
routing algorithm, known as greedy routing. Previously proposed
dynamical processes enabled to demonstrate experimentally (by
simulations) that the small world phenomenon can emerge from local
dynamics. However, the analysis of greedy routing using the probability
distributions arising from these dynamics is quite complex because of
mutual dependencies. In contrast, our process enables complete formal
analysis. It is based on the combination of two simple processes: a
random walk process, and an harmonic forgetting process. Both processes
reflect natural behaviors of the individuals, viewed as nodes in the
network of inter-individual acquaintances. We prove that, in
k-dimensional lattices, the combination of these two processes
generates long-range links mutually independently distributed as a
k-harmonic distribution. We analyze the performances of greedy
routing at the stationary regime of our process, and prove that the
expected number of steps for routing from any source to any target in
any multidimensional lattice is a polylogarithmic function of the
distance between the two nodes in the lattice. Up to our knowledge,
these results are the first formal proof that navigability in small
worlds can emerge from a dynamical process for network evolution. Our
dynamical process can find practical applications to the design of
spatial gossip and resource location protocols.
Évolution artificielle : petits aller-retours entre modélisation et optimisation
Guillaume Beslon, Maître de Conférences au LIRIS
L'évolution artificielle est à la fois une technique d'optimisation
maintenant classique (généralement connue sous l'appellation
d'algorithmes génétiques) et une technique de modélisation et de
simulation de l'évolution biologique. Cependant, par bien des aspects,
les algorithmes évolutionnaires sont très différents des objets
biologiques dont ils sont inspirés. Dès lors se posent deux questions
clés : (i) qu'impliquent ces différences sur la connaissance produite
par les modèles évolutifs ? et (ii) serait-il possible d'améliorer les
performances des algorithmes évolutionnaires en les "rapprochant" de la biologie ?
Au cours de ce séminaire, je présenterai dans un premier temps les
principes de la sélection indirecte de l'évolvabilité (ou "évolution
de second ordre"). La sélection indirecte permet à l'évolution de
sélectionner les lignées les plus aptes à évoluer. Elle est donc
susceptible d'améliorer les performances des algorithmes. Après avoir
rapidement montré pourquoi la sélection de l'évolvabilité n'est pas
possible dans les algorithmes évolutionnaires "classiques", je
présenterai le modèle aevol, dédié à l'étude de la sélection
indirecte. Ce modèle a permis de montrer certaines des implications de
la sélection indirecte sur les génomes bactériens. Je conclurai en
montrant comment aevol peut être décliné en un algorithme
évolutionnaire dédié à l'optimisation et les intérêts d'une telle
déclinaison.
De la géométrie projective en Coq
Nicolas Magaud, Maître de conférences en Informatique à l'Université Louis Pasteur de Strasbourg. Membre de l'équipe IGG du LSIIT.
La géométrie et son axiomatisation sont
étudiées par les mathématiciens depuis l'Antiquité.
Ce domaine d'étude très riche se prête bien
à la formalisation telle qu'elle peut se faire
dans l'assistant de preuve Coq.
Dans cet exposé, nous étudions une géométrie particulière :
la géométrie projective (où dans le plan, deux droites se
croisent toujours) principalement en 2D et en 3D.
Dans ce cadre, nous décrivons formellement une théorie
axiomatique pour la géométrie projective. Nous construisons
ensuite des modèles de cette théorie. Finalement, nous mettons
en oeuvre des outils mathématiques comme la notion de matroïde
fini dans le but de systématiser les preuves de théorèmes de
la géométrie projective.
Ce travail, à la fois théorique et pratique, modélise au sens
mathématique du terme certains notions de géométrie et permet
aussi de tirer avantage des outils informatiques pour construire
interactivement des preuves dont la correction est vérifiée
automatiquement par la machine. La formalisation de ces démonstrations sur ordinateur renforce de manière très
significative la garantie qu'elles sont correctes.
Algorithmes et protocoles de population : Que peux-t-on calculer avec une population d'oiseaux ?
Johanne Cohen, Chargée de recherche CNRS, Palaiseau
Les
protocoles
de populations ont été introduits par Angluin et al pour
modéliser des réseaux de capteurs, sans contrôle sur leurs
mouvements. Un protocole de population
correspond à un ensemble d'agents anonymes,
qui interagissent les uns avec les autres par paires
pour mener à bien un calcul. Par exemple, on cherche à détecter si plus
que 5% d'oiseaux d'un groupe possèdent une certaine propriété, par le
biais d'interactions par paires entre capteurs attachés à ces oiseaux.
Dans
cet
exposé, nous présentons des algorithmes de base comme
l'élection
d'un chef, le calcul de la majorité. Nous discuterons ensuite
la puissance de calcul de ces protocoles de populations qui
correspond aux prédicats définissables dans la logique de
Presburger (travaux de
Aspnes et al).
De plus, nous discuterons un protocole de population qui calcule un nombre irrationnel algébrique quand la population tend vers l'infini.
Jouons avec les programmes
Olivier Laurent, chargé de recherche CNRS au LIP
Il n'est pas difficile d'écrire des programmes compliqués ! Un objectif
de la sémantique (dénotationnelle) est de nous fournir des outils
mathématiques pour mieux comprendre les programmes et les langages de
programmation. On partira d'une interprétation des programmes comme de
simples fonctions (des entiers dans les entiers pour des programmes de
type nat->nat, puis avec des domaines plus riches) pour montrer que
ces fonctions -- même si elles nous fournissent des informations sur
ce que calculent les programmes -- ne suffisent pas à représenter
certaines structures des algorithmes. On remplacera alors les
fonctions par des stratégies dans des jeux à deux joueurs (Joueur, qui
représente le programme étudié, et Opposant, qui représente son
environnement d'exécution). Cette sémantique des jeux permet un
interprétation très précise des programmes et une analyse fine des
différentes primitives de programmation que ceux-ci utilisent.
Pourquoi mon ordinateur calcule faux?
Sylvie Boldo chargée de recherche INRIA, LRI.
Nous confions à nos ordinateurs de nombreux calculs (météo,
simulations aéronautiques, jeux vidéos, feuilles Excel...) et nous
considérons naturellement que l'ordinateur fournira une réponse juste.
Malheureusement, la machine a ses limites que l'esprit humain n'a
pas Elle utilise une arithmétique dite flottante qui a ses
contraintes. D'une part chaque calcul est effectué avec un certain
nombre de chiffres (souvent environ 15 chiffres décimaux) et donc
chaque calcul peut créer une erreur, certes faible, mais qui peut
s'accumuler avec les précédentes pour fournir un résultat complètement
faux. D'autre part, les valeurs que l'ordinateur appréhende ont des
limites vers l'infiniment petit et l'infiniment grand. Hors de ces
bornes, l'ordinateur produit des valeurs spéciales souvent
inattendues. Cet exposé montrera que l'ordinateur n'est pas
infaillible ou plutôt que son utilisation est parfois abusive.
|
Last Updated ( Monday, 20 April 2009 )
|