Note aux orateurs
Contact et renseignements : Florent de Dinechin.
Dans cet exposé je vais introduire les principales idées permettant de construire une théorie algorithmique de l'information. Le premier but de la théorie est de définir la quantité d'information contenue dans un objet. Cette quantité est définie par la complexité de Kolmogorov de l'objet: la taille de sa plus petite représentation comprimée. Ainsi, on peut établir que la quantité d'information contenue dans l'objet est la taille de ce que donnerait un algorithme "idéal" de compression appliqué a l'objet. Malheureusement, on prouve que cet algorithme n'existe pas: la complexité de Kolmogorov n'est pas calculable. Cette théorie est connue pour son élégance et admet de nombreuses applications en logique, en combinatoire, en complexité, ainsi que pour définir ce qu'est une suite infinie aleatoire sur {0,1}.
Les microprocesseurs sont généraux, donc relativement lents : lorsqu'on veut vraiment de la performance, on fabrique un circuit intégré spécifique, qui sera deux ou trois ordres de grandeur plus rapide, mais bien plus cher et bien moins souple. Mais voici que les progrès de l'intégration nous apportent les réseaux logiques reconfigurables, ou FPGA (pour field programmable gate array). Ce sont des circuits intégrés composés d'un grand nombre de portes logiques simples dont la fonction est programmable. Ces portes sont reliées entre elles par un réseau également configurable. Un tel circuit va pouvoir simuler n'importe quel circuit intégré assez petit pour rentrer dedans. On aura des performances proches du circuit specialisé, mais a une fraction du coût puisque les FPGAs sont produits en grande serie. Et l'on pourra très facilement deboguer et mettre a jour son application.
Je commencerai par un survol des nombreuses applications des FPGAs : assistance au calcul, prétraitement d'entrées/sorties, prototypage rapide, etc. Puis je ferai un état de l'art en disséquant les principales familles actuelles de FPGA. Enfin je parlerai de la programmation des FPGA, avec les problemes qu'elle pose. Tiens, ce sont les mêmes que pour la programmation des machines parallèles. Dans cet exposé, il y aura de nombreux axes de recherche encore ouverts.
Depuis Darwin on sait que l'Évolution des espèces suit un schéma arborescent dans lequel les feuilles de l'arbre représentent les espèces contemporaines tandis que la racine figure leur ancêtre commun. Les premières methodes mathématiques pour retrouver cet arbre à partir des données contemporaines reposaient sur l'arbre de Steiner. Les espèces étaient représentées par des points dans un espace multi-dimensionel, et on cherchait l'arbre le plus court permettant de relier ces points. L'idée était que l'arbre ainsi obtenu constitue une explication parcimonieuse de l'Évolution, et reposait donc sur le principe d'Occam. Depuis un vingtaine d'années, on dispose de données génétiques où chaque espèce est représentée par (une portion de) son ADN. Ces donneés sont maintenant très abondantes, si bien qu'il est possible de reconstruire l'Évolution de genres entiers sur lesquels on n'avait auparavant aucune information, comme par exemple les bactéries. Les méthodes de parcimonie sont toujours d'actualité, mais d'autres approches ont vu le jour. Notamment, on utilise de plus en plus fréquemment des modélisations mathématiques de l'Évolution, et on recherche l'arbre le plus vraisemblable au sein d'un modele donné.
Au cours de l'exposé je présenterai l'ensemble de ces approches, en les insérant dans leur contexte méthodologique qui est lié aux mathématiques discrètes, à l'optimisation discrète et continue, à certains aspects géometriques et à divers outils statistiques et probabilistes. L'exposé, pédagogique, devrait être accessible au plus grand nombre. Finalement, je donnerai un apercu sur les recherches en cours au sein de notre équipe du département Informatique Fondamentale et Applications, à Montpellier (LIRMM).
Gordon Bell hosts his two-part program on the evolution of electronic computing from its pre-WWII origin through the development of the first commercial computers. His narration traces the development of the stored program computer architecture which remains the foundation of today's computer.
Video #1: The builders of the first five machines, the Bell Labs Model 1, the Zuse Z1-3, the Atanasoff-Berry Computer, the Harvard Mark1, and the SSEC, tell their stories (53mn)
Video #2: Vintage films and first-hand accounts enliven this video, which focusses on the ENIAC, and the three lines of machines descending from it: the Eckert-Mauchli EDVAC, BINAC and UNIVAC; Maurice Wilkes' EDSAC; and John von Neumann's IAS machines and their clones, the ILLIAC, MANIAC, etc (54mn).
La future génération des systèmes de gestion d'information doit intégrer des possibilités de stockage (de), d'accès (à) et de raisonnement (sur) de gros volumes d'information (avec une distribution spatiale naturelle et une hetérogénéité de ces informations). Le développement de ces systèmes requiert une approche pluridisciplinaire qui s'appuie sur des concepts empruntés à l'intelligence artificielle, à la modélisation de données, aux bases de données, etc.
Cet exposé survole les approches, les principes et les directions de recherche destinés a supporter les caractéristiques avancées des systèmes d'information de la prochaine génération qui seront dotés d'une intelligence affinée et de nouveaux mécanismes de coopération à différents niveaux. Les applications qui effectivement bénéficieront de ces développements sont, par exemple, les entrepôts de données, le multimédia axé sur le contenu, WWW, etc.
En utilisant la nature quantique de la matière à l'échelle atomique, l'informatique peut devenir un outil de calcul exponentiellement plus puissant que les meilleurs calculateurs du siècle à venir. Par exemple elle serait capable de factoriser les entiers en temps polynomial, ce qui aurait des retombées monumentales en cryptographie.
Cependant ses capacités sont limitées par le phénomène de décohérence provoqué par l'interaction avec le milieu exterieur. Heureusement la recherche récente en algorithmique quantique suggère qu'il est possible de résoudre ces problèmes grace à des codes quantiques de correction d'erreurs.
Si les physiciens peuvent réaliser un tel ordinateur, ce n'est que le début d'une longue avancée technologique.
Pour beaucoups de programmeurs, le typage d'un programme n'est qu'un garde-fou lui evitant de commettre des erreurs trop evidentes. En fait, cette utilisation du typage ne represente que la face visible de l'iceberg. Dans de nombreux compilateurs, les types sont utilises a des fins d'optimisations et d'analyses : d'ou ces capacites proviennent-elles ?
Dans cet expose, j'aborderai la question "qu'est-ce qu'un type?" de differents points de vues. Je commencerai en montrant qu'un type decrit des proprietes de programmes. Nous verrons une application etonante permettant de decouvrir du code mort d'un programme uniquement en analysant son type. Inversement, je passerai aux connections entre la logique et le typage et montrerai comment des programmes peuvent etre exploites, par le truchement du typage, a des fins purement mathematiques. Finalement, je presenterais les objets mathematiques interpretant les types (ce ne sont pas des ensembles!) pour une semantique donnee du lambda-calcul.
Dans une premiere partie de cet expose, je presenterai la collaboration entre Matra Systèmes et Information et le LIP dans le cadre du LHPC ainsi que leurs activités autour de systèmes multimedia . Ensuite, je parlerai plus specifiquement des enjeux et problématiques des serveurs vidéo. En particulier, j'aborderai les principes de base des serveurs de stockage multimédia ( algorithmes d'ordonnancement des accès disques, placement des données,...) en nous plaçant dans le cadre d'un système de stockage distribué.
Contrairement à ce qui se passe pour l'implantation des quatre fonctions arithmétiques de base, l'implantation sur machine des fonctions "élémentaires" (sinus, cosinus, log, ect.) laisse encore parfois franchement à desirer, et la qualité obtenue est très dépendante des machines utilisées. Ce problème est essentiellement dû au "dilemme du fabricant de tables" (ou TMD, de "Table Maker's Dilemma"), qui est, en gros, qu'on ne sait pas avec quelle precision on doit effectuer les calculs intermédiaires pour toujours garantir que l'on fournira l'arrondi au plus près du résultat exact. On va faire le point sur l'état actuel de ce problème (résultats de théorie des nombres liés au TMD, tests exhaustifs, etc.) et sur nos expériences en cours.
AF2 est un logiciel permettant de réaliser des preuves avec l'aide d'un ordinateur. Les démonstrations sont alors verifiées par la machine et leur correction est garantie.
Cet assistant de preuve a été développé dans le but de simplifier au maximum l'apprentisage du système et la réalisation des preuves (les preuves formelles pouvant être très fastidieuses). Il a été utilisé auprès d'étudiants de divers niveaux avec un certain succès.
Lors de cet exposé, je présenterai les principes du système sur des exemples (avec un rétroprojecteur d'ecran). J'essaierai d'expliquer quelles sont les solutions qui sont disponibles dans le système pour faciliter la formalisation des démonstrations.
Nous introduisons d'abord la problématique de l'extraction de règles depuis des grands volumes de données (par exemple A, B, C [5] -> E [15] 0.71 pour dire que lorsque les événements A, B et C se produisent dans un temps de 5 unités alors l'événement E se produit dans un temps de 15 unités et ceci dans 71 % des cas). Il s'agit d'un cas particulier de processus de "datamining" ayant un fort potentiel applicatif (commerce électronique, sécurité, médecine et épidémiologie, etc). En prenant le scénario type de la découverte de règles d'associations, nous montrons que les phases délicates de ces processus posent de nouveaux problèmes aux spécialistes des bases de données, que ce soit pour assurer le prétraitement des données dans lesquels l'extraction doit s'exercer, pour avoir des processus d'extraction calculables en pratique ou encore pour réaliser les indispensables post-traitements sur les collections extraites (souvent des millions de règles).
Nous exposerons les principaux "challenge" algorithmiques pour l'extraction de règles variées puis nous introduirons les besoins en termes de langages de requêtes. Nous terminerons l'exposé en présentant une recherche en cours (coopération Lyon-Helsinki) sur le concept de base de données inductive. Ce concept original permet de traiter l'ensemble des processus d'extraction comme des séquences de requêtes et offre des bonnes perspectives pour l'optimisation de processus complexes.