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

Luc Bougé
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

Philippe Schnoebelen
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.

Christiane Frougny
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

Renaud Keriven
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

Isabelle Guérin Lassous
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

Tristan Cazenave
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

Nathalie Revol
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

Stéphane Gaubert
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

Marie-Pierre Béal
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

Hervé Rivano
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»

Loïc Prylli
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