Search

National audience; De plus en plus souvent, l'information relative à un domaine ou à un thème particulier est disséminée sur de nombreux supports physiques (base de données, fichier texte, fichier Excel, etc.). Aussi, lorsqu'on souhaite faire une analyse ou qu'un décideur doit prendre une décision, il faut la plupart du temps centraliser cette information et la transformer en indicateurs pour la rendre pertinente. Ces étapes de centralisation et de transformation s'avèrent souvent fastidieuses et difficiles à réaliser dans un délai raisonnable. L'information décisionnelle (Business Intelligence) est un pan de l'informatique qui propose des méthodes et des outils facilitant la centralisation de cette information au sein d'entrepôts de données tout en la structurant pour des analyses ou des prises de décisions. Des outils OLAP (OnLine Analytical Processing) ou SOLAP (Spatial OLAP) permettent de naviguer dans ces entrepôts de données restituant ces données sous forme cohérente, lisible et facile d'accès.

The Fibonacci cube is an isometric subgraph of the hypercube having a Fibonacci number of vertices. The Fibonacci cube was originally proposed by W-J. Hsu as an interconnection network and like the hypercube it has very attractive topological properties but with a more moderated growth. Among these properties, we discuss the hamiltonicity in the Fibonacci cube and also in the Lucas cube which is obtained by removing all the strings that begin and end with 1 from the Fibonacci cube. We give also the eccentricity sequences of the Fibonacci and the Lucas cubes. Finally, we present a study of both cubes from the domination and the 2-packing points of view., Le cube de Fibonacci est un sous-graphe isométrique de l'hyper- cube ayant un nombre de Fibonacci de sommets. Le cube de Fibonacci a été initialement introduit par W-J. Hsu comme un réseau d'interconnexion et, comme l'hypercube, il a des propriétés topologiques très attractives, mais avec une croissance plus modérée. Parmi ces propriétés, nous discutons de l'hamiltonicité dans le cube de Fibonacci et aussi dans le cube de Lucas qui est obtenu à partir du cube de Fibonacci en supprimant toutes les chaînes qui commencent et nissent avec 1. Nous trouvons également le nombre de som- mets des cubes de Fibonacci et Lucas ayant une certaine excentricité. En n, nous présentons une étude de deux cubes du point de vue de la domination et du 2-packing.

The aim of this thesis is to prove that certain family of graphs are embeddable into hypercube. Another problem will be treated. It concerns the partitioning of hypercube in vertex-disjoint cycles of even length. We prove that hypercubes of dimension n can be partitioned into k vertex-disjoint cycles of even length if k, Le but principal de ce manuscrit est de montrer que certaines familles de graphes sont des graphes plongeables dans l'hypercube. Un problème d'une autre nature sera traité, il concerne la partition de l'hypercube en des cycles sommet-disjoints de longueur paires. Nous prouvons que l'hypercube de dimension n peut être partitionné en k cycles sommet-disjoints si k

Ce travail a été réalisé dans le cadre d'une convention CIFRE entre le LAAS-CNRS et la société ACTIA qui développe des outils d'aide au diagnostic de pannes automobiles. Le but était l'utilisation des réseaux de neurones artificiels pour la conception d'une nouvelle méthode de diagnostic de pannes automobiles sans modèle, ni information symbolique mais avec seulement des observations du système en bon et en mauvais fonctionnement. C'est donc une approche du diagnostic de système complexe par reconnaissance de formes. Après avoir mis au point le système d'acquisition, nous avons conçu une première maquette qui a démontré la faisabilité d'un tel système et l'intérêt des réseaux de neurones, mais qui a soulevé de nombreux problèmes. L'utilisation particulière des réseaux de neurones dans cette application a nécessité l'usage d'algorithmes de construction. Après une étude théorique des structures de l'hypercube qui n'a pas abouti à un algorithme de construction mais qui a fourni plusieurs résultats, nous avons développé une famille d'algorithmes pour la construction des réseaux de neurones binaires. La base de ces outils est une nouvelle méthode d'apprentissage d'unités à seuil très performante dénommée Barycentric Correction Procedure (BCP). L'aboutissement est un algorithme novateur car très général (entrées quelconques et sorties multiples), rapide et avec un bon pouvoir de généralisation. Nous avons finalement mis au point une nouvelle méthodologie de diagnostic, dans laquelle l'utilisation de méthodes statistiques et d'analyse de données en collaboration avec les réseaux neuronaux paru nécessaire. Cette méthodologie utilise donc des techniques très diverses : analyse en composantes principales, estimation de densité de probabilité, classification automatique, calcul d'enveloppes convexes, génération géométrique de bases d'apprentissage, construction de réseaux de neurones binaires, réseaux de neurones gaussiens et méthodes de diagnostic simples. Cette méthodologie a été appliquée avec succès au problème de la détection de pannes automobiles et a aussi montré des potentialités pour le diagnostic préventif. Elle est de plus assez générique pour avoir de nombreuses applications potentielles.; non disponible

L'hypercube a suscité de nombreuses études engendrant une littérature très dense aussi bien en mathématiques discrètes qu'en informatique. Cet intérêt sans cesse croissant est largement motivé par l'utilisation de sa structure dans de nombreux domaines (architectures parallèles, transfert de l'information, décision multicritère,...). Chacun peut s'étonner des raisons qui font que le cube soit le cube?. Sa simple définition peut déjà apporter une réponse quoique partielle à une telle question. Plusieurs propriétés spécifiques à l'hypercube ont, soit, défini de nouvelles classes de graphes, soit, fait ressortir le rôle remarquable joué par celui-ci dans plusieurs classes déjà existantes. Les (0, 2)-graphes sont une généralisation naturelle de l'hypercube. Il est maximal dans cette classe. Le thème de cette thèse consiste en la définition et la caractérisation de quelques classes de (0, 2)-graphes obtenues à partir de l'hypercube par rajout d'arêtes ou identification de sommets. Nous caractérisons au chapitre II, le graphe de l'hyperoctaèdre comme un {2(n-2), 2(n-1)}-graphe d'ordre 2n, et nous prouvons l'unicité de son cycle hamiltonien et cela à une équivalence naturelle près. Nous donnons, au chapitre III, une caractérisation de l'hypercube en tant que graphe distance-régulier de vecteur d'intersection {d, d-1, ..., 1; 1, 2, ..., d}. Une classe de (0, 2)-graphes minimaux -les graphes de Shrikhande généralisés- y est étudiée et une caractérisation des graphes de Laborde-Mulder comme (0, 2)-graphes de diamètre minimum [d/2] parmi ceux d'ordre 2d-1 et de degré d impair est donnée. Au chapitre IV, nous caractérisons parmi les hypercubes généralisés ceux qui sont des (0, 2)-graphes. Nous présentons une construction de (0, 2)-graphes non sommet-transitifs. On montre enfin que les graphes de Laborde-Mulder et du demi-cube sont plongeables dans le carré de l'hypercube. Dans un dernier chapitre, nous nous intéressons au problème d'existence de (0, 2)-graphe d'un ordre donné. Nous donnons une condition nécessaire d'existence de tels graphes pour un ordre impair. Nous montrons ensuite qu'à l'ordre 18 et 20, il n'existe pas de (0, 2)-graphes, en utilisant à cette fin un algorithme de construction de (0, 2)-graphes. Nous présentons enfin quelques résultats sur la structure locale des (0, 2)-graphes

Nous étudions le comportement dynamique d'un réseau d'automates introduit dans la littérature sous le nom de "chip firing game" et qui intervient dans la modélisation de certains phénomènes physiques tels que des systèmes de balles qui rebondissent sur des parois mobiles en leur faisant subir des mouvements de translation. Nous nous intéressons au cas particulier où des règles d'évolution sont associées aux orientations du graphe sous-jacent. Dans le cas où le graphe est un hypercube de dimension n, nous présentons des techniques qui permettent de construire des évolutions de périodes variées et en particulier de toutes les longueurs paires comprises entre 0 et 2n. Ensuite, en utilisant un système composé d'une cascade d'anneaux, nous exhibons des évolutions dont les périodes sont exponentielles par rapport à la taille du graphe. (Résumé d'auteur)

Cette thèse propose une methode de codage optimise d'automate synchrone dans un environnement du type compilateur de silicium. Dans une première partie, on recherche sur le graphe d'état des situations prédictives de minimisation des équations des variables internes et des sorties. Ceci définit des contraintes sur le codage en terme d'une liste de groupes d'adjacence d'états a immerger sur des faces ou cubes de l'hypercube. Dans une deuxième partie le codage est réalisé en satisfaisant au mieux ces affectations de faces et leurs intersections. Les principes de base de cette approche sont les suivants: (i) pour la première phase, la recherche de situations prédictives de minimisation est fondée sur la théorie des paires de partition de Hartmannis. Les situations sont recherchées entrée par entrée; cette approche locale permettra de faire face aux grandes complexités; remarquons que le codage des entrées n'est pas aborde. La priorité est donnée aux fusions potentielles de monômes dans les équations. On ne recherchera pas de façon indifférenciée comme dans d'autres approches (mustang) toutes les minimisations possibles incluant les factorisations. En effet, il est raisonnablement estime que seule la fusion de monômes assure un gain de surface et en connectique; (ii) pour la deuxième phase, les techniques d'immersion dans l'hypercube seront très sophistiquées. Elles reprendront une représentation de l'hypercube par le treillis de l'ensemble des parties de n éléments. Pour résoudre les problèmes des contraintes intersectantes, c'est-a-dire des contraintes impliquant des sous-ensembles d'états en commun, une théorie dite théorie des cubes intersectant sera proposée. Les résultats de cette thèse ont donne lieu a un logiciel intégré dans le système asyl. Les résultats obtenus en gain de surface sur silicium, de chemin critique et de facteurs de routage sont les meilleurs actuellement connus

Cette thèse est composée de deux parties: les développements lies à la génération des nombres premiers et l'implantation du crible quadratique. Dans la première partie, nous analysons les stratégies d'allocation des données aux processeurs pour le crible d'Eratosthène dans un environnement à mémoire partagée en vue d'améliorer l'équilibrage de la charge de travail. Puis, nous proposons des implantations sur l'hypercube FPS T40 a mémoire distribuée. Comme le caractère centralise du crible d'Eratosthène (de type maitre/esclaves) s'accommode mal des exigences de l'architecture distribuée, nous étudions un algorithme de génération des nombres premiers par divisions successives sur un anneau. Cet algorithme nécessite la mise en œuvre d'une technique de détection de la terminaison distribuée, par un dénombrement des processeurs ayant termine l'exécution de leur programme. Enfin, l'aspect maitre/esclaves du crible d'Eratosthène permet l'étude de méthodologies d'implantation de ce type d'algorithmes sur un réseau linéaire et une grille de processeurs. La deuxième partie est consacrée au crible quadratique multipolynomial, algorithme de factorisation des grands entiers, utilise en cryptographie. Notre but est d'extraire le maximum de parallélisme de chacune des étapes de cet algorithme dans un environnement distribue, afin d'utiliser au mieux la puissance des calculateurs massivement parallèles. Cette étude conduit a une implantation efficace sur l'hypercube FPS T40

Étude de divers problèmes lies aux graphes de Hamming

Université : Université scientifique et médicale de Grenoble