Séminaire du MIM 2000-2001
Note aux orateurs
Contact et renseignements : Natacha
Portier.
Tous les séminaires ont lieu le mardi entre 13h30 et 15h30, dans
l'amphi B de l'ENS Lyon.
A voir également:
Liste des séminaires de l'année scolaire
2000-2001
-
03-10-2000
-
Méta-computing : Si tous les ordinateurs du monde...,
Luc
Bougé
-
17-10-2000
-
Le model-checking, un outil pour la vérification
des logiciels, Philippe
Schnoebelen
-
24-10-2000
-
Fonctions de mots infinis réalisables par automate
fini.
Application à la représentation des
nombres réels, Christiane
Frougny
Vous pouvez récupérer les transparents ici
.
-
14-11-2000
-
Vision informatique du relief , Renaud
Keriven
-
28-11-2000
-
Les réseaux locaux sans fil, Isabelle
Guérin Lassous
-
12-12-2000
-
Programmation du Jeu de Go et Parcours d'Arbres,
Tristan
Cazenave
-
30-01-2001
-
Exposé dans le cadre de l' École
Jeunes Chercheurs en Algorithmique et Calcul Formel
-
20-02-2001
-
Introduction à l'arithmétique par intervalles
,
Nathalie
Revol
-
13-03-2001
-
Une introduction à l'algèbre max-plus,
Stéphane
Gaubert
-
20-03-2001
-
Codage symbolique, Marie-Pierre
Béal, ses transparents
-
03-04-2001
-
La coloration fractionnaire appliquée à
la resolution de problèmes de planification de réseaux optiques
à multiplexage en longueurs d'onde , Hervé
Rivano
-
17-04-2001
-
Architecture des systèmes de communication pour
«grappes»., Loïc
Prylli
Après l'exposé d'Eric Prylli, le séminaire MIM
se poursuivra avec Jean Duprat. Son intervention sera la suite de son exposé
lors de la semaine ski des MIM1. Il discutera du sujet suivant : "mon ordinateur
sait-il raisonner ?"
Résumés
Méta-computing : Si tous les ordinateurs du monde...
La plupart des ordinateurs, PC ou stations de travail dispersés
dans le monde sont tout à fait sous-utilisés. Pourquoi ne
pas utiliser la puissance de calcul ainsi perdue pour attaquer des problèmes
qui sont trop grands pour être traités sur les machines disponibles,
ou bien qui ne sont pas assez prioritaires pour mobiliser de tels équipements.
Il y a plusieurs exemples de tels projets: le décodage de clés
cryptographiques (
http://www.inria.fr/INedit/eve22-fra.html) et le projet de détection
de la vie extraterrestre SETI@home (
http://setiathome.ssl.berkeley.edu/).
Cependant, même des problèmes prioritaires peuvent exiger
des ressources qui ne peuvent être rassemblées en un même
lieu : acquisition des données, de calcul, de stockage, de visualisation
des résultats. Il n'y a aucune raison profonde de mettre les ordinateurs
qui analysent les résultats d'une expérience dans un synchrotron
juste à côté du synchrotron. On peut tout aussi bien
imaginer de répartir la chaîne de traitement sur plusieurs
machines dispersées dans le monde grâce à l'interconnexion
fournie par Internet. De plus, il peut être intéressant de
choisir pour chaque phase du calcul la machine la plus adaptée et/ou
la moins coûteuse. En fait, ceci revient à découpler
le problème du traitement des données de la localisation
des ressources qui sont utilisées. Un peu comme pour le courant
électrique, qui est utilisé sans référence
aux dispositifs physiques qui l'ont produit. Cette approche est au coeur
d'un grand nombre de travaux actuellement. Ils ont pour but de mettre en
place des "grilles de calcul" (Computational grids) dispersées sur
toute l'étendue de la planète. La grille expérimentale
GUSTO du projet Globus (
http://www.globus.org/research/testbeds.html ) par exemple interconnecte
125 sites dans 23 pays.
Ce nouveau type de plate-forme pose de nombreux défis pour les
chercheurs en informatique et dans les disciplines utilisatrices de l'informatique:
mathématiques, physique, chimie, biologie, etc. Nous discuterons
les problèmes et quelques approches qui ont été proposées
pour les résoudre, notamment au sein de la communauté française
( http://www.ens-lyon.fr/~desprez/OURAGAN/
).
Le model-checking, un outil pour la vérification des logiciels
Le model-checking est une technique qui permet de vérifier automatiquement
qu'un système satisfait bien les propriétés attendues.
Cette technique a permis de découvrir des bugs subtils dans des
systèmes complexes.
Dans cet exposé, nous allons présenter les idées
de base derrière le model-checking : Comment ça marche ?
Pour quelles propriétés de quels systèmes la méthode
est-elle adaptée ? Quelles sont ses limitations ?
Avec un oeil tourné vers les aspects pratiques nous présenterons
certains des outils de model-checking actuellement disponibles et leurs
domaines d'applications privilégiés.
Fonctions de mots infinis réalisables par automate fini.
Application à la représentation des nombres réels.
Les nombres réels representés en base 2 (resp. 10 )par exemple
peuvent être considérés comme des mots infinis écrits
sur un alphabet de chiffres {0,1} (resp. {0,1,...,9}). On peut donc utiliser
les notions de fonctions réalisables par automate fini pour décrire
certaines fonctions comme l'addition. On considera également les
notions de calcul séquentiel, et on montrera que de telles fonctions
sont continues. On introduira aussi le calcul en-ligne.
Vision informatique du relief
Nos deux yeux nous fournissent chacun une image plane, et pourtant le cerveau
reconstruit en permanence un monde en trois dimensions. Comment transmettre
cette faculté à l'ordinateur ? Des techniques intuitives
ne donnent pas de résultats convaincants. La réponse est
à chercher du côté d'un des domaines mathématiques
les plus actifs aujourd'hui : les Equations aux Dérivées
Partielles.
Les réseaux locaux sans fil
Et si les salles classiques de TP étaient amenées à
se modifier ?
Les réseaux locaux sans fil permettraient à chaque étudiant
équipé d'un ordinateur portable d'accéder au réseau
du campus, de la bibliothèque, de la salle de cours ou de TP ou
de la maison des élèves. La salle des TP verrait donc ses
ordinateurs fixes disparaître au profit de points d'accès
au réseau filaire. Si le réseau local sans fil est convenablement
planifié, l'étudiant peut se connecter au réseau du
campus quelle que soit sa localisation sur ce même campus avec une
seule machine.
Réaliser de tels réseaux induisent bien-sûr différentes
problématiques comme l'accès au médium radio qui est
partagé entre les ordinateurs mobiles ou le routage des données
par voie radio. Dans cet exposé, nous verrons comment fonctionnent
ces réseaux et comment répondre aux problèmes rencontrés.
Programmation du Jeu de Go et Parcours d'Arbres
La recherche en programmation des jeux de reflexions aurait pu s'arreter
sur un succes apres la victoire de Deep Blue sur Kasparov aux Echecs. La
plupart des jeux a deux joueurs et a information complete ont des programmes
qui battent les meilleurs joueurs humains (Echecs, Dames anglaises, Awele,
Othello...) Toutefois, un jeu resiste encore aux algorithmes classiquement
utilises pour resoudre ces jeux : Le jeu de Go.
C'est un jeu d'origine chinoise, pratique par des dizaines de millions
de joueurs au Japon, en Coree et en Chine. Il est repute pour la finesse
de ses raisonnements tactiques et strategiques.
Apres une presentation du jeu de Go, nous rappellerons les principaux
algorithmes de parcours d'arbres utilises en programmation des jeux. Puis
nous presenterons un nouvel algorithme de parcours d'arbres ET/OU qui permet
de trouver des solutions plus precises que l'Alpha-Beta, plus rapidement
et en parcourant moins de noeuds. D'un point de vue theorique, cet algorithme
que nous appelons Recherche Abstraite de Preuves permet des gains sur l'alpha-beta
similaires aux gains de l'alpha-beta sur le minimax. Cet algorithme et
ses generalisations sont en cours d'implementation dans Golois, notre programme
de Go.
Vous pouvez des maintenant vous familiariser au jeu de Go en l'affrontant
a l'adresse suivante :
http://www.ai.univ-paris8.fr/~cazenave/JouerAuGo.html
Introduction à l'arithmétique par intervalles
Les calculs numériques (prévision météo, simulation
d'écoulement de l'air autour des ailes d'un avion, de crash de voiture
ou d'accident dans une centrale nucléaire par exemple) utilisent
l'arithmétique flottante disponible sur ordinateur. Les nombres
utilisés ont donc une représentation finie et les résultats
de chaque opération sont arrondis, c'est-à-dire entachés
d'erreur. Or les calculs numériques actuels impliquent de plus en
plus d'opérations et donc d'erreurs : par exemple on atteint les
limites de validité théorique de certains algorithmes numériques.
Pour éviter ces problèmes, on peut utiliser une arithmétique
par intervalles : dans cette arithmétique, le résultat de
chaque opération et par extension le résultat de tout calcul
est un encadrement garanti des solutions, au sens où elles ne peuvent
pas prendre de valeurs à l'extérieur de cet intervalle résultat.
Cependant les encadrements fournis peuvent être trop larges et ce,
même si la largeur des intervalles en entrée (qui correspond
à l'imprécision sur les données) est la précision
machine.
Nous définirons l'arithmétique par intervalles, illustrerons
ce problème de grossissement des résultats et montrerons
sur quelques exemples des solutions pour limiter ce grossissement. La ``morale''
est que l'arithmétique par intervalles ne peut pas être substituée
sans précaution à l'arithmétique flottante usuelle,
mais que l'utilisation de techniques adaptées permet d'obtenir des
résultats souvent satisfaisants. En conclusion seront présentés
quelques domaines d'application.
Une introduction à l'algèbre max-plus
L'algèbre max-plus a été étudiée depuis
la fin des années 50 par plusieurs Écoles, avec des motivations
variées : problème du plus court chemin, asymptotiques, théorie
des langages, évaluation de performance de systèmes à
événements discrets. Cet exposé introductif mettra
l'accent sur un résultat central, le théorème spectral
max-plus, qui s'inscrit dans les généralisations non-linéaires
du théorème (classique) de Perron-Frobenius. On illustrera
le théorème spectral par plusieurs applications : calcul
de débit dans les réseaux, programmation dynamique avec coût
ergodique, et, pour parler de résultats plus récents, perturbation
de valeurs propres et jeux déterministes répétés
à deux joueurs et somme nulle sur des graphes.
Codage symbolique
Le codage symbolique est un traitement des données qui se fait conceptuellement
au niveau des symboles, c'est-à-dire de façon primaire par
opposition à des approches algébriques qui consistent à
voir les symboles comme des éléments d'un groupe ou d'un
corps fini. Nous présentons quelques exemples de tels codages, comme
les codages de modulation utilisés pour le stockage de données
sur bandes magnétiques, CD audio, disques optiques, etc ..., les
codages dits de rotation, utilisés dans certains systèmes
de modulation, les codages de compression sans perte.
Les suites de bits manipulées lors de ces codages sont souvent
modélisées par des automates finis ou des systèmes
dynamiques symboliques. Les méthodes de construction des codeurs
et des décodeurs utilisent donc des théories mathématiques
comme la théorie de Perron-Frobenius sur les matrices positives
(voir aussi l'exposé de Stéphane Gaubert de la semaine dernière)
et de l'algorithmique sur les graphes et les automates finis.
La coloration fractionnaire appliquée à la resolution de
problèmes de planification de réseaux optiques à multiplexage
en longueurs d'onde
La fibre optique est aujourd'hui le support priviligie des reseaux de communication.
Toutes ses caracteristiques (bande passante, taux de perte, delai, cout
lineique) rendent les reseaux "electriques" obsoletes par rapport aux reseaux
optiques aux yeux des operateurs. Une technologie recente a encore decuple
l'interet des fibres optiques : le multiplexage en longueurs d'onde (WDM)
permet en effet d'exploiter la tres grande bande passante des fibres sans
etre limite par les performances des emetteurs electroniques actuels en
faisant transiter dans la meme fibre plusieurs flux de donnees sur des
longueurs d'ondes differentes.
Apres avoir vu comment modeliser les reseaux optiques en terme de graphes,
nous nous interesserons aux problemes de planification (i.e. de dimensionnement)
qui preoccupent les operateurs (qui veulent toujours faire mieux pour moins
cher). La NP difficulte de ces problemes nous amenera a etudier une technique
d'approximation appelee la "coloration fractionnaire". Cette coloration
est une relaxation lineaire de la coloration classique des sommets d'un
graphe. Il ne s'agit donc plus d'affecter une couleur a un sommet mais
d'affecter plusieurs couleurs a chaque sommet avec des poids pour chaque
couleur. Nous verrons que cette technique amene a une approximation fine
de la coloration entiere dans le cas des reseaux fortement charges (ce
qui est le cas en pratique) et nous la prouverons polynomiale dans certains
cas particuliers.
Architecture des systèmes de communication pour «grappes»
L'exposé commencera par présenter les différents types
de matériel réseau pour les architectures de type «grappes».
A partir de là on montrera que l'interface entre les noeuds de calcul
et le réseau est une donnée toujours cruciale dans les performances
du système de communication. Nous présenterons les diverses
techniques systèmes permettant d'obtenir faibles latences et haut
débit (accès en mode utilisateur à la carte réseau,
transfert à zéro copie-mémoire, élimination
des interruptions). Et nous présenterons la problématique
d'implémentation d'un protocole asynchrone entre les différents
niveaux de l'architecture (code sur processeur principal, logiciel embarqué,
implémentation matérielle), en expliquant les problèmes
d'interaction entre ces niveaux.
Contact : Natacha.Portier.
Page modifiée le 11 juin 2001
Vous êtes à l'adresse :
http://www.ens-lyon.fr/~nportier/enseign/sem0001.html