Note
aux orateurs
Contact et renseignements :
Natacha Portier
.
Tous les séminaires ont lieu le mardi à 13h30 dans l'amphi
B de l'ENS Lyon
"Ne pouvant me fier à mon raisonnement, j'ai appris par coeur tous les résultats possibles de toutes les multiplications possibles" dit l'élève dans La Leçon de Ionesco. Elle a bien raison, si elle a une bonne mémoire.
Les ordinateurs ont une bonne mémoire (par
ailleurs on peut aussi se fier à leur raisonnement). Dans ce séminaire,
nous étudierons, sur différents exemples d'algorithmes de
base, les compromis entre le "par coeur" et le "raisonnement" (disons plutôt
calcul). Nous présenterons en détail une famille de méthodes
pour le calcul des fonctions élémentaires qui, sans être
idiote, fait massivement appel au "par coeur".
Les strategies pour repartir les donnees et les calculs d'une application determinent les parallelisations possibles et finalement les performances qui peuvent etre atteintes. La repartition des donnees par blocs, supportee par les langages High Performance Fortran (HPF) et OpenMP, conduit souvent a des performances acceptables pour de nombreuses applications regulieres. En revanche, pour les applications effectuant des phases de calculs iteratifs le long de chacune des dimensions de donnees multi-dimensionnelles, les performances des versions par blocs compilees sont relativement mauvaises par rapport aux versions optimisees a la main. Ce type de schema de calcul se retrouve frequemment par exemple dans les methodes ADI (Alternating Direction Implicit) permettant de resoudre des equations aux derivees partielles. Pour ce type d'applications, la repartition par bloc sequentialise completement les calculs le long de l'une des dimensions.
Le "multi-partitionnement" est la technique utilisee pour ce type d'applications dans les versions codees a la main, et non la repartition par bloc. La propriete principale du multi-partitioning est que, pour chaque phase de calculs mono-dimensionnelle, tous les processeurs en parallele ont un bloc a calculer, sans sequentialisation. Le deuxieme avantage est la granularite importante des communications necessaires. Le principe sous-jacent est de repartir les blocs sous-forme de "carre latin": en dimension 2, tout numero de processeur apparait exactement une fois dans chaque ligne et chaque colonne de la matrice des donnees. Ce principe a neanmoins une restriction puisqu'on ne manipule que des "carres" multi-dimensionnels: en dimension d, le nombre de processeurs doit etre un entier a la puissance d-1 (un carre en dimension 3).
Le but de notre travail etait de generaliser ce principe a n'importe quel nombre de processeurs (on s'interessera donc a des rectangles et non plus des carres magiques) et d'essayer, par la compilation, d'approcher les performances des versions codees a la main. D'un point de vue theorique, deux problemes doivent etre resolus: premierement, determiner le nombre de tranches dans chaque dimension (ce qui determine les blocs et la taille du "rectangle magique") de sorte que les communications entre processeurs soient minimisees, tout en conservant l'equilibrage de charge; deuxiemement, definir l'allocation des blocs aux processeurs, c'est-a-dire definir les valeurs du "rectangle magique".
D'un point de vue mathematique, le probleme est le suivant. Etant donne
un nombre de processeurs p, on veut definir un tableau de blocs tel que,
pour chaque "tranche" (une dimension de moins) du tableau, le nombre de
blocs est un multiple de p (condition necessaire evidente pour garantir
l'equilibrage de charge). De plus, on veut choisir les tailles de ce tableau
pour minimiser une certaine fonction objective (en pratique, la somme des
tailles ou une fonction lineaire). Nous proposons de resoudre ce probleme
comme une variation d'un autre probleme connu, trouver le nombre de partitions
d'un entier (etudie par Euler et Ramanujam entre autres). Puis, etant donne
un tel tableau de blocs, on veut attribuer a chaque bloc un numero (entre
1 et p) de sorte que, dans chaque tranche, chaque nombre apparait exactement
le meme nombre de fois (equilibrage de charge a nouveau). Il se trouve que
la condition necessaire enoncee plus haut est (heureusement) egalement suffisante.
Si, pour chaque tranche, le nombre de blocs est un multiple de p, on peut
construire un "rectangle latin magique". Pour cela, on utilise une allocation
cyclique multi-dimensionnelle, a l'aide de proprietes sur les groupes abeliens
(formes d'Hermite, theoreme d'Hajos), proprietes qui ont egalement des liens
avec la theorie des pavages.
Jean-Christophe Filliatre
<< La programmation est une science exacte >>, affirmait il y a plus de trente ans déjà C. A. R. Hoare. Malheureusement, on ne peut que constater que la programmation est plutôt traitée comme une science expérimentale, reposant plus sur des tests que sur des raisonnements. Mais il n'est pas toujours facile de tester un programme, par exemple lorsque l'on cherche à calculer plusieurs milliards de décimales de $\pi$ ou à piloter une fusée. Dans le premier cas, on n'a pas de moyen de vérifier le résultat, et dans le second cas ce moyen est bien trop coûteux. Il faut alors se persuader mathématiquement de la correction du programme.
Si cette vérification peut être effectuée manuellement --- ce qui a d'ailleurs été démontré avec brio par d'illustres personnes telles que Dijkstra, Gries, Floyd, ou encore Knuth --- ce travail devient rapidement fastidieux et propice aux erreurs. L'assistance d'une machine est nécessaire, autant pour garantir la correction de ce travail que pour en automatiser certaines parties.
Notre exposé sera composé de deux parties. Dans la première, nous présenterons le système Coq, un assistant de preuve développé au LRI et à l'INRIA Rocquencourt. Nous montrerons en particulier comment des programmes fonctionnels corrects peuvent être automatiquement extraits de preuves en logique constructive. Dans un second temps, nous montrerons comment le système Coq peut être également utilisé pour établir la correction de programmes impératifs.
La conférence portera sur le passage de l'état de chercheur
à l'état de porteur de projet et à l'état d'entrepreneur
: construction de nouveaux référentiels et de nouveaux systèmes
identitaires, ce dans un contexte de cohérence homme-projet.
Les intervenants :
Michel Coster : Professeur-chercheur en entrepreunariat à EM Lyon, DESS Finance, DEA de droit, vice-président de l'académie de l'entrepreunariat, conseil d'entrepreneurs ayant développé des entreprises dans le domaine de la haute technologie, plus particulièrement sur les questions d'association et d'alliances stratégiques.
Eric Le Bihan : normalien (Ulm, 1986, sciences), docteur 3ème cycle et agrégé de Physique, ingénieur du corps des Télécoms. Il a travaillé de 1987 à 1995 pour France Télécom (lancement du système VISIOPASS de FT Télévision à péage puis responsabilité du département Commutation et Nouveaux Services à FTRSI). Il a ensuite rejoint Nortel comme directeur technique pour les nouveaux opérateurs puis comme responsable de la business unit Webphone (1995-1998). Depuis 1998 il a participé à la création puis assuré le développement de la start-up internet Netgem, spécialiste européen de l'internet sur la télévision. Il a été vice-Président produit et solution de NetGem avec la responsabilité de la définition des solutions proposées, de leur évolution et du support technique d'avant vente. Il est actuellement Vice-Président Ventes & Support de France Telecom Long Distance, basé à Londres.
Présentation de NetGem
Mission
Fournisseur de technologies de télévision interactive reposant
sur des standards ouverts DVD et Internet, NetGem licencie sa plate-forme
logicielle de TV interactive :
La technologie NetGem permet le déploiement de servives interactifs
tels que le commerce en ligne, l'accès à Internet, la messagerie,
la publicité interactive, la vidéo, la musique à la
demande...
Chifres Clés
CA2000 112M (730MF)
Effectifs 150 salariés (60% d'ingénieurs)
Nombre de solutions vendues 750 000
Introduit au nouveau marché en avril 2000
Organisation de cette séance du séminaire :
Isabelle Servais, Chargée d'Etudes
Centre des Entrepreneurs
E.M. Lyon
Le but de la phylogénie est d'inférer, à partir des
ressemblances et différences observées entre espèces,
leurs liens de parenté dont la représentation s'exprime classiquement
par un arbre. L'évolution de
cette discipline est couplée depuis une vingtaine d'année
à celle de l'informatique (algorithme de recherche d'arbres, alignement
de séquences, entre autres).
Jusqu'à présent, toutes les méthodes de reconstruction d'arbres phylogénétiques supposent que les espèces évoluent et accumulent des changements à une vitesse constante au cours du temps. Des travaux récents ont cependant montré que la plupart des caractères moléculaires des espèces ont évolué à des vitesses variables au cours du temps. Maintenant, on cherche à estimer l'importance du biais induit par ce phénomène sur la topologie inférée des arbres phylogénétiques par les méthodes n'incluant pas des vitesses de changements variables au cours du temps.
La première partie de l'exposé porte sur une présentation rapide de la phylogénie, et de ses liens avec l'informatique, en insistant sur les problèmes liés aux variations de vitesse d'évolution au cours du temps. La deuxième partie s'intéresse au problème suivant: étant donné un arbre phylogénétique dans lequel ont peut localiser les changements évolutifs pour chaque caractère, comment détecter un caractère dont la vitesse d'évolution a été variable au cours du temps.
Lorsqu'on fait des mathématiques, on raisonne rarement en logique pure, mais on se place en général dans une théorie - par exemple la théorie des ensembles - qui définit les objets dont parlent les mathématiques. La manière la plus simple de définir une théorie est de poser un certain nombre d'axiomes. Cependant il en existe d'autres, dont certaines sont beaucoup plus pratiques quand on les utilise concrètement, en particulier quand on utilise un ordinateur pour faire des mathématiques. Cet exposé propose de retracer les évolutions récentes de la notion de théorie.
Qu'est-ce qu'une suite au hasard ? On peut imaginer par exemple qu'on
montre à un ``joueur professionnel de pile ou face'' une suite (très
longue, voire infinie) de piles et de faces et, qu'on lui demande : cette
suite vous paraît-elle provenir d'une succession de tirages à
pile ou face, et la pièce qui a servi était-elle truquée
à votre avis ? À défaut de définir rigoureusement
la notion de suite au hasard, on peut essayer de définir des notions
de suites ``non au hasard'' : de bonnes candidates sont les suites engendrées
par des ``algorithmes''. Le mot algorithme peut être pris en un sens
voisin de celui de
``recette de cuisine très précise'', et l'on aura plusieurs
notions de suites non au hasard, suivant la classe d'algorithmes choisie.
Nous nous proposons de décrire les suites engendrées par ``substitutions''
(on dit aussi ``morphismes de monoïde libre'' ou ``règles d'inflation'')
et de montrer quelques unes de leurs nombreuses propriétés
et utilisations en théorie des nombres, en analyse harmonique, en
combinatoire ou en informatique théorique, ainsi qu'en physique en
rapport avec les quasi-cristaux.
Approximation is a natural approach to deal with optimization problems
which are
NP-hard or not known to be in P. We are interested in algorithms with a worst
case
guarantee, both in terms of running time and in terms of the relative error
of the
approximation.
In this lecture I will focus on approximation techniques based on rounding,
and
present several paradigms via examples.
1.Approximation using rounding and exhaustive search.
Example: Clustering in two dimensions with the Euclidian
metric.
2.Approximation using rounding and dynamic programming.
Example: Subset-sum.
3.Approximation using rounding and linear programming.
Examples: Bin-packing, bin-covering.
La basse consommation d'énergie est une contrainte de conception de plus en plus forte pour les circuits intégrés. Avec le développement actuel des appareils portables, les circuits intégrés doivent effectuer des tâches complexes tout en ne consommant que très peu d'énergie. Même dans les processeurs de bureau, la consommation d'énergie peut être critique (problème de dissipation, densité de courant élevée, écologie, bruits...).
Cet exposé sera décomposé en deux grandes parties. Dans la première, nous allons regarder pourquoi les circuits intégrés consomment et quelles sont les techniques classiques pour réduire la consommation. En particulier, nous allons voir que la basse consommation peut être abordée depuis le niveau algorithmique jusqu'au plus bas niveau électrique. Dans la seconde partie de l'exposé, nous regarderons le cas de quelques opérateurs arithmétiques matériels simples (addition et multiplication essentiellement).
Remarque: cet exposé sera une réédition (avec quelques mises à jour) du séminaire présenté au LIP en mai 2001
Les modèles dynamiques discrets, dans lesquels on étudie
le comportement d'un ensemble d'entités soumises à des règles
d'interaction locales, sont en train de prendre une place de plus en plus
importante dans la compréhension de problèmes issus de domaines
très variés (physique, biologie, économie...). L'approche
informatique (en un sens que l'on précisera) permet d'éclairer
d'un jour nouveau ces questions. Nous présenterons quelques-uns de
ces modèles et essaierons de mettre en évidence les questions
de fond que pose leur étude.
Dans cet exposé, nous montrerons les liens qui existent entre
le jeu des galets (pebble game) sur un graphe, le calcul d'un système
d'équations de récurrence uniforme
et le nombre de registres d'un circuit digital.
Des techniques élémentaires utilisées sur des graphes
infinis réguliers permettent de calculer la quantité de mémoire
minimale dans tous ces cas. Elle correspond à la taille d'une coupe
minimale dans le graphe infini associé.
Ce travail est le fruit d'une collaboration avec Jean Mairesse et Alain Jean-Marie.
Les résultats en calculabilité et en complexité concernent principalement les modèles de calculs à temps discret, comme les machines de Turing. Mais il est aussi envisageable de considérer des modèles où le temps est continu, comme par exemple des systèmes définis par des équations différentielles.
Dans cet exposé nous présenterons quelques résultats sur la puissance de ces systèmes.
L'exposé sera basé entre autre sur les résultats de la thèse de Manuel Campagnolo.
Page modifiée le 24 avril 2002
Vous êtes à l'adresse :
http://www.ens-lyon.fr/~nportier/enseign/sem.html