SIESTE 2006-2007

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 mercredi à 18h00 dans l'amphi B de l'ENS Lyon


Date	Orateur	Titre
mercredi 27 septembre 2006	Jean-Michel Muller	Arithmétique virgule flottante
mercredi 11 octobre 2006	Ines Klimann	Automates et séries sur des semi-anneaux exotiques : que peut-on décider ?
mercredi 8 novembre 2006	Thomas Colcombet	Automates, jetons et logiques
mercredi 22 novembre 2006	Alain Daurat	Reconstruction des convexes à partir de leurs projections tomographiques
mercredi 13 décembre 2006	Isabelle Guérin-Lassous	Partage de bande passante dans les réseaux radio multisauts
mercredi 7 février 2007	Pierre Lescanne	Les algorithmes babyloniens
mercredi 28 février 2007	Pierre Castéran	L'Hydre et le Coq reporté
mercredi 14 mars 2007	Malika More	50 ans de problème du spectre en logique
mercredi 28 mars 2007	Hervé Rivano	optimisation des réseaux radio maillés
mercredi 18 avril 2007	Pierre Castéran	L'Hydre et le Coq
mercredi 2 mai 2007
mercredi 16 mai 2007	Bruno Martin	Aiguiser la hache des Wisigoths

Les archives du SIESTE, autrefois SMIM
Conférences d'intérêt général de l'ENS Lyon
le Séminaire du LIP

Résumés

Bruno Martin

Aiguiser la hache des Wisigoths

Entretenir le réseau routier d'une ville pendant 25 ans ou vendre 144 minutes de publicité chaque jour, ça s'optimise !

En partant d'exemples récents de projets d'optimisation (recherche opérationelle), je vous raconterai comment j'utilise ma formation scientifique au sein du groupe Bouygues.

Hervé Rivano

Optimisation des réseaux maillés.

Les réseaux radio maillés (WMNs) sont une réponse intéressante aux besoins de connectivité et communication permanentes. Cependant, les réseaux radio sont connus pour gaspiller leur capacité déjà rare quand leur taille augmente. Il est donc crucial de donner aux opérateurs les moyens de garantir une qualité de service minimale à leurs clients pour un investissement raisonnable.
Maximiser la capacité d'un réseau nécessite d'optimiser conjointement le placement de passerelles, le routage et l'ordonnancement des appels en prenant en compte les interférences propres à medium radio.
Dans cet exposé, nous montrerons tout d'abord quelques résultats fondamentaux sur la capacité des réseaux aléatoire. Ensuite, nous présenterons des modèles en programmation linéaire pour le calcul de réseaux radio maillés de type WiFi 802.11a ou WiMax 802.16 et de capacité optimale.

Malika More

50 ans de problème du spectre en logique

En logique, le spectre d'une propriété est l'ensemble des nombres d'éléments des objets finis qui possèdent cette propriété. Depuis les années 1950, la notion de spectre a été étudiée selon plusieurs approches successives. Dans cet exposé historique, je présenterai un tour d'horizon des questions principales et des résultats les plus importants du domaine, en insistant sur les liens avec des questions d'informatique fondamentale moderne.

Pierre Castéran

L'Hydre et le Coq

Les suites de Goodstein et les "Batailles d'Hydre" sont des problèmes combinatoires célèbres. La convergence des suites de Goodstein et la terminaison des batailles d'Hydre se prouvent classiquement à l'aide de nombres ordinaux.
La représentation de ces objets et de ces preuves dans l'assistant à la démonstration Coq nous permet de donner un aperçu de la preuve de théorèmes sur machine et de quelques techniques intéressantes.

Quelques liens:

Sur les suites de Goodstein:
http://en.wikipedia.org/wiki/Goodstein 's_theorem

Sur le système Coq:
http://coq.inria.fr

Ines Klimann

Automates et séries sur des semi-anneaux exotiques : que peut-on décider ?

Résumé : Après avoir brièvement définie la notion de décidabilité, je m'attacherai à donner des exemples de questions naturelles sur les automates à multiplicités dans des semi-anneaux de type (|N, min, +) ou (|R, max, +) et sur les séries qu'ils reconnaissent. Pour chacun de ces exemples, j'esquisserai les preuves de leur décidabilité ou de leur indécidabilité. Enfin je donnerai des exemples de problèmes encore ouverts dans ce domaine.

Thomas Colcombet

Automates, jetons et logiques

Les automates cheminants ont été introduits il y a une trentaine d'années comme une alternative aux automates d'arbres à branchements maintenant communément utilisés. L'étude de ce modèle s'est trouvée récemment relancée avec l'arrivée de XML, et plus particulièrement du language XPath. D'autres travaux ont également montré le lien très fort entre les automates à jetons (pebble automata, une extension des automates cheminants), et la logique FO+TC (premier ordre augmenté d'un opérateur de cloture transitive) sur les arbres.

Cet exposé sera l'occasion de dresser un panorama de cette théorie qui s'est substantiellement enrichie ces dernières années. Nous présenterons les principaux résultats ainsi que les grandes questions ouvertes.

Isabelle Guerin-Lassous

Partage du médium radio dans les réseaux ad hoc

Les réseaux ad hoc sont des réseaux radio multisauts. Ces réseaux, constitués d'entités sans fil et potentiellement mobiles, ne reposent sur aucune infrastructure fixe. Les applications en vogue actuellement de ces réseaux sont les réseaux véhiculaires, les réseaux de capteurs ou les réseaux maillés. La plupart des travaux dans ce domaine supposent que ces réseaux reposent sur la technologie sans fil IEEE 802.11. Or cette technologie utilise un protocole
d'accès au médium radio de type CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) qui est inadaptée au partage du médium tel qu'il se réalise dans les réseaux ad hoc.

Après avoir décrit les caractéristiques et les applications de ces réseaux, je vous montrerais quels sont les problèmes qui se posent au niveau du partage du médium. Puis, s'il nous reste du temps, je vous décrirai les pistes de recherche qui sont actuellement développées pour proposer des solutions à ces problèmes.