Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu les jeudi 7 décembre et vendredi 8 décembre 2006 à 14 heures en salle amphi Masters (KB). ----------------------------------------------------------------------- Le programme du 7 décembre: *VAUCANSON, THÉORIE DES JEUX & OLENA* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2006-12-07 VAUCANSON 14h00 : Présentation du TAF-Kit -- Robert Bigaignon 14h45 : État des lieux des propositions XML pour les automates -- Florent Terrones THÉORIE DES JEUX 15h45 : Recherche d'un epsilon-Nash de support de taille 2 -- Michaël Cadilhac OLENA 16h30 : Extractions d'objets : l'algorithme Fast Level Lines Transform (FLLT) -- Christophe Berger ----------------------------------------------------------------------- Le programme du 8 décembre: *OLENA, THÉORIE DES JEUX, BDD & PARALLÉLISATION DE CALCULS* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2006-12-08 OLENA 14h00 : Extraction automatique d'artères à partir d'images médicales 3D -- Nicolas Widynski THÉORIE DES JEUX 14h45 : Poker AI -- Johan Oudinet BDD 15h45 : BDD distribués, Java, Threads, et optimisations -- Guillaume Guirado PARALLÉLISATION DE CALCULS 16h45 : Parallélisme appliqué au traitement d'image -- Alexandre Borghi THÉORIE DES JEUX 17h30 : Les systèmes de recommandations -- Thomas Largillier ----------------------------------------------------------------------- Les Résumés des exposés du 7 décembre : *************************************** VAUCANSON * Présentation du TAF-Kit -- Robert Bigaignon La plate-forme de manipulation d'automates finis Vaucanson propose depuis peu un ensemble d'outils permettant la manipulation d'automates au travers de simples programmes Unix, à la façon de FSM (http://www.research.att.com/~fsmtools/fsm/). Ces programmes sont réunis dans le Typed Automata Functions Kit (TAF-Kit) et s'appuient directement sur la bibliothèque C++, cœur du projet Vaucanson. Ils fournissent ainsi à l'utilisateur un sous-ensemble des services déjà présents dans Vaucanson (algorithmes et entrées-sorties) tout en lui épargnant l'écriture de programmes C++. Nous présenterons les fonctionnalités du TAF-Kit ainsi que les outils dont il dispose pour mesurer ses performances. * État des lieux des propositions XML pour les automates -- Florent Terrones Les utilisateurs de logiciels de manipulation d'automates ont exprimé depuis quelques années le besoin de disposer d'un format de fichier universel de description d'automates. L'équipe Vaucanson a présenté dès 2004 pour la conférence CIAA'04 une proposition de format XML pour la description d'automates à états finis. Cette dernière a subi de nombreuses modifications et suivi différentes lignes directrices pour en arriver à la version actuelle. Le but de ce séminaire est de faire un état des lieux de cette proposition et des avantages qu'elle apporte. Une description des autres propositions ainsi que leurs différentes caractéristiques seront également présentées. THÉORIE DES JEUX * Recherche d'un epsilon-Nash de support de taille 2 -- Michaël Cadilhac Dans le cadre de la théorie des jeux, la recherche d'un équilibre tel qu'aucun joueur ne puisse augmenter ses gains en changeant de stratégie est primordiale. De récents résultats montrent que l'obtention algorithmique de cet équilibre, dit de Nash, n'est pas abordable en temps raisonnable. Depuis 2003 et les résultats de Lipton, on s'est rendu compte que chercher un équilibre approximatif, à un epsilon près, amenait à des algorithmes de plus faible complexité et un contexte plus humainement parlant. Nous étudierons des algorithmes permettant la recherche d'un équilibre de Nash approximé dans un cadre où les joueurs choisissent de manière probabiliste entre deux stratégies parmi une multitude. OLENA * Extractions d'objets : l'algorithme Fast Level Lines Transform (FLLT) -- Christophe Berger Il existe de nombreux algorithmes de segmentation. Nous présenterons ici le FLLT qui se base sur le principe de composantes connexes séparées par les lignes de niveaux. En effet, il existe sur une image, comme sur une carte géographique, des lignes formées par les différences entre les zones. Dans une image ces différences sont matérialisées par la teinte ou le contraste. Nous verrons tout d'abord les spécificités de cet algorithme et des différentes structures utilisées afin de détecter les lignes de niveaux, nous proposerons également une comparaison avec le max-tree et présenterons les différences de ces deux méthodes. Finalement nous verrons en quoi FLLT est intéressant dans la pratique grâce a son implémentation dans Olena. ----------------------------------------------------------------------- Les Résumés des exposés du 8 décembre : *************************************** OLENA * Extraction automatique d'artères à partir d'images médicales 3D -- Nicolas Widynski Depuis le début du 20ème siècle, les techniques d'acquisition employées en imagerie médicale sont en constante évolution. Rayons X, IRM, ultra-sons et imagerie nucléaire sont des outils physiques permettant l'acquisition de différentes données telles que le scanner, l'echographie, la radiographie... Face à l'amélioration de ces techniques d'acquisition et au nombre croissant des données à traiter, le rôle du traiteur d'images médicales est d'extraire le maximum de caractéristiques et d'agencer au mieux les données, dans le but d'aider le spécialiste médical à effectuer son diagnostique. Plus spécialement, le scanner peut nous permettre d'acquérir des données 3D. Notre rôle consiste ici à en extraire les artères coronaires. Pour ce faire, nous emploierons la méthode décrite par Thierry Géraud et Jean-Baptiste Mouret dans Fast Road Network Extraction in Satellite Images Using Mathematical Morphology and Markov Random Field (EURASIP 2004), en divisant notre chaîne de traitement en deux étapes : l'extraction d'une surface à partir de données 3D, puis l'extraction d'une ligne, représentant notre artère, à partir de cette surface. Nous développerons également les outils nécessaires à cette segmentation, à savoir la convolution gaussienne, la ligne de partage des eaux, le graphe d'adjacence de régions et les champs Markoviens. THÉORIE DES JEUX * Poker AI -- Johan Oudinet Une des stratégies les plus utilisées pour créer une intelligence artificielle (IA) dans un jeu où les joueurs jouent à tour de rôle, consiste à construire l'arbre associé : chaque branche d'un nœud correspond à une stratégie possible du joueur qui doit jouer à ce nœud. Le problème avec le poker, ou tout autre jeu à information imparfaite, c'est qu'on ne connaît pas les stratégies accessibles à l'adversaire (elles dépendent des cartes qu'il a reçues). Ainsi, à chaque décision prise par l'adversaire, on doit se référer à son modèle pour améliorer la qualité des décisions. Un excellent joueur de poker arrive à deviner avec précision la main de son adversaire, c'est l'objectif que doit atteindre le modèle. Au cours de cette présentation, nous nous intéresserons au Texas Hold'em qui est une des variantes les plus complexes du poker et la plus populaire actuellement. Nous présenterons une IA utilisant un modèle d'adversaire pertinent. BDD * BDD distribués, Java, Threads, et optimisations -- Guillaume Guirado Lors d'une précédente présentation, les BDD (diagrammes de décision binaires) distribués ont été étudiés. Leur implantation, en Java, a montré ses limites lors des tests de performances. Une des idées proposées afin d'accélérer les calculs était de mieux gérer les processus, ou threads. Premièrement, limiter le nombre de processus simultanés permet d'éviter de nombreuses restaurations des registres du processeur. Second point, une file d'attente des processus avec un contrôle intelligent des processus prioritaires ou non pourrait augmenter la parallélisation de l'application. Nous verrons ce qu'il en est dans les faits. Enfin, le monde Java dispose de nombreux compilateurs ou optimiseurs susceptibles d'améliorer les performances. Nous testerons un certain nombre de ces outils et verrons si oui ou non, les résultats en sont améliorés. PARALLÉLISATION DE CALCULS * Parallélisme appliqué au traitement d'image -- Alexandre Borghi Le parallélisme permet d'effectuer plusieurs opérations simultanément tout en tirant parti d'une mémoire partagée. Aujourd'hui, l'informatique grand public permet d'utiliser cette capacité autrefois réservée aux professionnels du fait de leurs grands besoins en puissance de calcul. Ce séminaire vise à explorer certaines techniques permettant la conception de bibliothèques parallélisées. L'objectif est de faciliter l'écriture d'algorithmes parallèles tout en cachant un maximum de détails implémentatoires superflus sans perdre en fonctionnalité. Le traitement d'image a été choisi comme cadre de travail et plusieurs algorithmes ont été sélectionnés pour illustrer les concepts rencontrés. THÉORIE DES JEUX * Les systèmes de recommandations -- Thomas Largillier La multiplication des sites de ventes sur le Net a poussé à une plus grande fidélisation des clients. Ceci passe par une offre plus ciblée correspondant mieux à chaque utilisateur. On assiste donc à une émergence des systèmes de recommandations. Ces systèmes se basent sur les achats déjà effectués et la ressemblance de comportements entre les utilisateurs pour proposer des produits toujours plus attractifs. Nous ferons ici une présentation de plusieurs d'entre eux ainsi qu'une comparaison. -- Daniela Becker