Dans la présente thèse nous étudions l'extraction d'arbres dans des graphes arêtes-coloriés.Nous nous concentrons sur la recherche d'arbres couvrants proprement arête-coloriés et faiblement arête-coloriés, notée PST et WST. Nous montrons que les versions d'optimisation de ces problèmes sont NP-Complete dans le cas général des graphes arêtes-coloriés, et nous proposons des algorithmes pour trouver ces arbres dans le cas des graphes arêtes-coloriés sans cycles proprement arêtes-coloriés.Nous donnons également quelques limites de nonapproximabilité. Nous proposons des conditions suffisantes pour l'existence de la PST dans des graphes arêtes-coloriés (pas forcément propre), en fonction de différents paramètres de graphes, tels que : nombre total de couleurs, la connectivité et le nombre d'arêtes incidentes dedifférentes couleurs pour un sommet. Nous nous intéressons aux chemins hamiltoniens proprement arêtes-coloriés dans le casdes multigraphes arêtes-coloriés. Ils présentent de l'intérêt pour notre étude, car ce sontégalement des arbres couvrants proprement arêtes-coloriés. Nous établissons des conditions suffisantes pour qu'un multigraphe contienne un chemin hamiltonien proprement arêtes-coloriés, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré d'arêtes, etc. Puisque l'une des conditions suffisantes pour l'existence des arbres couvrants proprement arêtes-coloriés est la connectivité, nous prouvons plusieurs bornes supérieures pour le plus petit nombre de couleurs nécessaires pour la k-connectivité-propre. Nous énonçons plusieurs conjectures pour les graphes généraux et bipartis, et on arrive à les prouver pour k = 1.

La mobilité est un aspect important des sociétés modernes. Par conséquent, il y a une demande croissante pour des solutions informatiques de calcul d'itinéraire. Dans cette thèse, le routage multimodal et le système Dial-a-Ride sont étudiés. Ils contribuent à une utilisation plus efficace de l'infrastructure de transport disponible, élément déterminant dans la perspective d'un développement durable. La planification d'itinéraires multimodaux est rendus complexe en raison des différents modes de transport qui doivent être combinés. Une généralisation de l'algorithme de Dijkstra peut être utilisée pour trouver les chemins les plus courts sur un réseau multimodal. Cependant, sa performance n'est pas suffisante pour les applications industrielles. De ce fait, cette thèse introduit un nouvel algorithme appelé SDALT. Il s'agit d'une adaptation de la technique d'accélération ALT. Pour évaluer la performance de SDALT, un graphe a été construit à partir d'un réseau multimodal réel basé sur les données de transport de la région française Ile-de-France. Il inclut la marche, les transports en commun, la voiture, la bicyclette ainsi que des informations relative aux horaires les horaires et les conditions de circulation. Les tests de performance montrent que SDALT fonctionne bien, avec un temps de calcul réduit d'un facteur compris entre 1,5 et 60 par rapport à l'algorithme de base. Dans un contexte multimodal autre la question de la détermination du chemin le plus court, se pose celle de trouver un chemin aller-retour multimodal optimal entre un point de départ et un point d'arrivée. Un véhicule privé (voiture ou bicyclette) utilisé pour une première partie du trajet aller doit être récupéré au cours du trajet retour pour être ramené au point de départ. Pour cette raison, le parking doit être choisi de manière à optimiser les temps de déplacement du trajet aller et du trajet retour combinés. L'algorithme qui est proposé ici résout ce problème plus rapidement que les techniques actuelles. Le système Dial-a-Ride offre aux passagers le confort et la flexibilité des voitures privées et des taxis à un moindre coût et avec plus d'éco-efficacité car il regroupe les demandes de transport similaires. Il fonctionne de la manière suivante: les passagers demandent le service en appelant un opérateur. Ils communiquent leur point de départ, leur point de destination, le nombre de passagers, et quelques précisions sur les horaires de service. Un algorithme calcule ensuite les itinéraires et les horaires des véhicules. Cette thèse propose une nouvelle heuristique efficace et rapide de type Granular Tabu Search, capable de produire de bonnes solutions dans des délais courts (jusqu'à 3 minutes). Comparativement aux autres méthodes, et au regard des instances de test de la littérature, cet algorithme donne de bons résultats.

La spectroscopie est un outil primordial pour le diagnostic des plasmas, qu'il s'agisse de ceux des étoiles, permettant d'espérer comprendre toujours mieux leurs formations et leurs évolutions, ou celui des laboratoires, tout spécialement ceux rencontrés dans le cadre des expérimentations visant la fusion thermonucléaire contrôlée, telles que le projet ITER.La modélisation des profils de raie Lyman-alpha de l'hydrogène conduit à élaborer différentes approches dont le formalisme mérite d'être toujours investigué, et possiblement enrichi, en vue d'améliorer nos capacités de diagnostic. Nous avons donc successivement exploré une approche par intégrale de chemin, en vue de conserver au maximum l'information liée à la nature quantique des processus d'interaction, puis le rôle de la chronologie, le potentiel d'interaction du système atomique avec le plasma ne commutant pas à deux instants différents, et enfin une approche modélisant le champ électrique par des processus stochastiques dont les propriétés statistiques déterminent les caractéristiques des profils de raie des plasmas étudiés. Dans ce dernier cas, le travail réalisé montre que la modélisation du champ électrique par des processus stochastiques contient de sérieuses pistes de recherche de nature à améliorer encore les résultats obtenus. / Spectroscopy is an essential tool for plasma diagnostics, especially for studying stars, allowing hope to understand always better their origin and their evolution, or for laboratory plasmas, especially those encountered in the experiments for controlled thermonuclear fusion, such as ITER.Modeling profiles of Lyman-alpha hydrogen leads to develop different approaches whose formalism deserves to still remain under investigation, and can possibly be enriched, to improve our diagnostic capabilities. We therefore explored the subject successively by a path integral approach, in order to retain maximum information related to the quantum nature of the interaction process, then the role of chronology, as the interaction potential of the atomic system with the plasma does not commute at two different times, and finally we worked on an approach modeling the electric field by stochastic processes whose statistical properties determine the characteristics of the line profiles of the studied plasmas. In the latter case, the work shows that the modeling of the electric field by stochastic processes contains serious research possibilities which should be able to further improve present results.

Le terme de robustesse structurale donne lieu à diverses définitions et domaines d'application. Dans le domaine de l'ingénierie structurale, le cadre réglementaire des Eurocodes définit la robustesse structurale comme « l'aptitude d'une structure à résister à des événements tels que les incendies, les explosions, les chocs ou les conséquences d'une erreur humaine, sans présenter de dégâts disproportionnés par rapport à la cause d'origine ». Cette définition fait clairement ressortir les notions de dommage initial (défaillance locale) et de dommage disproportionné (défaillance globale). Cette thèse propose une approche de la quantification de la robustesse structurale en contexte probabiliste pour mesurer l'impact d'une défaillance localisée sur la défaillance globale de la structure. L'objectif majeur de la thèse est de quantifier l'écart entre une défaillance locale et une défaillance globale, en introduisant différents indices de robustesse selon que la structure soit intègre ou initialement endommagée. Pour cela, dans le but de caractériser et quantifier les liens existant entre la performance des différents éléments d'une structure et la performance globale de la structure, il est nécessaire d'introduire une étude en système qui intègre de manière concomitante des notions de défaillance locale (modes de défaillance) et des notions de défaillance globale. Une recherche « par l'intérieur » des chemins de défaillance dominants est présentée. Le terme « par l'intérieur » est utilisé car c'est le cheminement interne de la défaillance dans la structure qui est recherché. Des méthodes de parcours d'arbre d'évènements sont introduites telles que la méthode des « branches et bornes », du β-unzipping, ou encore du β-unzipping avec bornage. Ces méthodes permettent d'identifier les chemins de défaillance dominants avec des temps de calcul raisonnables. En particulier, il est possible de déterminer le chemin de défaillance associé à la plus grande probabilité de défaillance, appelé encore chemin de référence. Une approche « par l'extérieur » est également proposée, qui consiste à identifier la défaillance globale sans parcourir un arbre d'évènement (et donc sans s'intéresser à l'ordre avec lequel la défaillance survient). Le terme « par l'extérieur » correspond donc à regarder la défaillance de manière globale sans chercher à déterminer la chronologie de la défaillance. Dans les deux cas, l'enjeu est au final de développer une démarche globale permettant d'apprécier et de quantifier la robustesse des structures neuves ou existantes au travers de méthodes et d'indices pouvant s'appliquer à une large variété de problèmes / Structural robustness is associated with several definitions depending on context. In the field of structural engineering, the Eurocodes define structural robustness as “the ability of a structure to withstand events like fire, explosions, impact or the consequences of human error, without being damaged to an extent disproportionate to the original cause”. Such a definition clearly involves concepts of local and global failures. This PhD work proposes a methodology to quantify structural robustness in a probabilistic way and to assess the impact of local failures on global failures. The main objective of this PhD is to quantify the gap between local and global failures by introducing several robustness indices proposed for undamaged and damaged structures. To qualify and quantify the relationships between the performance of the different structural components and the overall structural performance, it is necessary to introduce a system-level analysis which simultaneously considers concepts of local failure modes and global failure events. An inner approach is introduced to determine significant failure sequences and to characterize stochastically dominant failure paths identified by using branch-and-bound, β-unzipping, and mixed β-unzipping with bounding methods. These methods enable to determine significant failure paths with reasonable computational times. In particular, the path with the largest probability of occurrence is considered as the reference failure path. An outer approach is also proposed which identifies global failure without using an event-tree search (and, consequently, without analyzing the order in the failure sequence). This concept characterizes an overall and simultaneous failure of different components without determining the chronology in the failure event. In both cases, the goal is to provide a general and widely applicable framework for qualifying and quantifying the robustness level of new and existing structures through the introduction of methodologies and indices

La statistique des valeurs extrêmes est une question majeure dans divers contextes scientifiques. Cependant, bien que la description de la statistique d'un extremum global soit certainement une caractéristique importante, celle-ci ne se concentre que sur une seule variable parmi un grand nombre de variables aléatoires. Une question naturelle qui se pose alors est la suivante: ces valeurs extrêmes sont-elles isolées, loin des autres variables ou bien au contraire existe-t-il un grand nombre d'autres variables proches de ces valeurs extrêmes ? Ces questions ont suscité l'étude de la densité d'état de ces événements quasi-extrêmes. Il existe pour cette quantité peu de résultats pour des variables fortement corrélées, qui est pourtant le cas rencontré dans de nombreux modèles fondamentaux. Deux pistes de modèles physiques de variables fortement corrélées pouvant être étudiés analytiquement se démarquent alors: les positions d’une marche aléatoire et les valeurs propres de matrice aléatoire. Cette thèse est ainsi consacrée à l’étude de statistique d’extrêmes pour ces deux modèles de variables fortement corrélées. Dans une première partie, j’étudie le cas où la collection de variables aléatoires est la position au cours du temps d’un mouvement brownien, qui peut être contraint à être périodique, positif... Ce mouvement brownien est vu comme la limite d’un marcheur aléatoire classique après un grand nombre de pas. Il est alors possible d’interprèter ce problème comme celui d’une particule quantique dans un potentiel ce qui permet d’utiliser des méthodes puissantes issues de la mécanique quantique comme l’utilisation de propagateurs et de l’intégrale de chemin. Ces outils permettent de calculer la densité moyenne à partir du maximum pour les différents mouvements browniens contraints et même la distribution complète de cette quantité pour certains cas. Il est également possible de généraliser cette démarche à l’étude de plusieurs marches aléatoires indépendantes ou avec interaction. Cette démarche permet également d’effectuer une étude temporelle, ainsi que de généraliser à l’étude d’autres fonctionnelle du maximum. Dans la seconde partie, j’étudie le cas où la collection de variables aléatoires est composée des valeurs propres d’une matrice aléatoire. Ce travail se concentre sur l’études des matrices des ensembles gaussiens (GOE, GUE et GSE) ainsi qu’à l’étude des matrices de Wishart. L’étude du voisinage de la valeur propre maximale pour ces deux modèles est faite en utilisant une méthode fondée sur les propriétés des polynômes orthogonaux. Dans le cas des matrices gaussiennes unitaires GUE, j’ai obtenu une formule analytique pour la distribution à partir du maximum ainsi qu’une nouvelle expression de la statistique du gap entre les deux plus grandes valeurs propres en termes d’une fonction transcendante de Painlevé. Ces résultats, et plus particulièrement leurs généralisations aux cas GOE, sont alors appliqués à un modèle de verre de spin sphérique en champs moyen. Dans le cas des matrices de Wishart, l’analyse des polynômes orthogonaux dans le régime de double échelle m’a permis de retrouver les différentes statistiques de la valeur propre minimale et également de prouver une conjecture sur la première correction de taille finie pour des grandes matrices de la distribution de la valeur propre minimale dans la limite dite de «hard edge». / Extreme value statistics plays a keyrole in various scientific contexts. Although the description of the statistics of a global extremum is certainly an important feature, it focuses on the fluctuations of a single variable among many others. A natural question that arises is then the following: is this extreme value lonely at the top or, on the contrary, are there many other variables close to it ? A natural and useful quantity to characterize the crowding is the density of states near extremes. For this quantity, there exist very few exact results for strongly correlated variables, which is however the case encountered in many situations. Two physical models of strongly correlated variables have attracted much attention because they can be studied analytically : the positions of a random walker and the eigenvalues of a random matrix. This thesis is devoted to the study of the statistics near the maximum of these two ensembles of strongly correlated variables. In the first part, I study the case where the collection of random variables is the position of a Brownian motion, which may be constrained to be periodic or positive. This Brownian motion is seen as the limit of a classical random walker after a large number of steps. It is then possible to interpret this problem as a quantum particle in a potential which allows us to use powerful methods from quantum mechanics as propagators and path integral. These tools are used to calculate the average density from the maximum for different constrained Brownian motions and the complete distribution of this observable in certain cases. It is also possible to generalize this approach to the study of several random walks, independent or with interaction, as well as to the study of other functional of the maximum. In the second part, I study the case of the eigenvalues of random matrices, belonging to both Gaussian and Wishart ensembles. The study near the maximal eigenvalues for both models is performed using a method based on semi-classical orthogonal polynomials. In the case of Gaussian unitary matrices, I have obtained an analytical formula for the density near the maximum as well as a new expression for the distribution of the gap between the two largest eigenvalues. These results, and in particular their generalizations to different Gaussian ensembles, are then applied to the relaxational dynamics of a mean-field spin glass model. Finally, for the case of Wishart matrices I proposed a new derivation of the distribution of the smallest eigenvalue using orthogonal polynomials. In addition, I proved a conjecture on the first finite size correction of this distribution in the «hard edge» limit.

Le besoin de se déplacer est un besoin fondamental dans la vie de tous les jours. Avec l’extension continue des zones urbaines, l’augmentation de la population et l’amélioration du niveau de vie des citoyens, le nombre de voitures ne cesse d’augmenter. Ceci étant, la plupart des transports publics proposés aujourd’hui obéissent à des règles qui manquent de souplesse et qui incluent rarement le caractère dynamique, en temps et en espace, de la demande. Cela réduit ainsi l’attractivité de ces services et les rendant même parfois difficilement supportables. De ce fait, la majorité des usagers utilisent encore leur propre véhicule. Ce grand nombre de véhicules, qui est en augmentation continue sur les réseaux routiers, provoque de nombreux phénomènes de congestion induisant une surconsommation de carburant, des émissions inutiles de gaz à effet de serre et une perte de temps importante. Pour y remédier, nous proposons dans cette thèse de nouveaux systèmes de déplacement des usagers avec différents modèles d’optimisation pour la mobilité partagée (covoiturage et taxis-partagés) ainsi que la combinaison de la mobilité partagée avec les transports publics. Les expérimentations sont réalisées sur de vrais réseaux routiers ainsi que sur des données réelles. Ces nouveaux systèmes améliorent considérablement la qualité de service des systèmes classiques existants en termes de coût et de flexibilité tout en ayant un temps de calcul raisonnable. / The travelling is a fundamental part of everyday life. The continuous expansion of urban areas combined with the population increasing and the improvement of life standards increases the need of mobility and the use of private cars. Furthermore, the majority of public transportations are subject to rules lacking of flexibility and rarely taking into account the dynamic context. The attractiveness of public transportation is therefore reduced and, as a consequence, its financial support, resulting in a further deterioration of the public services quality and flexibility. Therefore, the majority of users still use their own vehicles. The number of vehicles is continuously increasing on road networks causing important phenomena of congestion, high fuel consumption and emissions of greenhouse gases, time loss. This unpleasant situation forces communities to consider alternative solutions for the mobility such as ride-sharing, an interesting alternative to solo car use. The overall objective of this thesis is to propose new travel systems for users through the introduction of optimization models for shared mobility (ride-sharing and taxi-sharing) and the combination of shared mobility and public transportation. The computational experiments are carried out on real road networks and real data. Our numerical results show the effectiveness of our approach, which improves the quality of service compared to the traditional systems in terms of cost and flexibility. The running time remains reasonable to allow using our framework in real-time transportation applications.

Ma thèse porte sur la compilation des langages de requêtes orientés web des données. Plus particulièrement, ma thèse s'intéresse à l'analyse, l'optimisation et l'évaluation distribuée d'un tel langage : SPARQL. Ma contribution principale est l'élaboration d'une méthode nouvelle particulièrement intéressante pour des requêtes contenant de la récursion ou dans le cadre d'une évaluation distribuée. Cette nouvelle méthode s'appuie sur un nouvel outil que nous introduisons : la μ-algèbre. C'est une variation de l'algèbre relationnelle équipée d'un opérateur de point fixe. Nous présentons sa syntaxe et sémantique ainsi qu'une traduction vers la μ-algèbre depuis SPARQL avec Property Paths (une fonctionnalité introduite dans le dernier standard SPARQL qui autorise une forme de récursion).Nous présentons ensuite un système de types et nous montrons comment les termes de la μ-algèbre peuvent être réécrits en d'autres termes (de sémantique équivalente) en utilisant soit des règles de réécriture provenant de l'algèbre relationnelle soit des règles nouvelles, spécifiques à la μ-algèbre. Nous démontrons la correction des nouvelles règles qui sont introduites pour réécrire les points fixes : elles permettent de pousser les filtres, les jointures ou les projections à l'intérieur des points fixes (dépendant des certaines conditions sur le terme).Nous présentons ensuite comment ces termes peuvent être évalués, d'abord de manière générale, puis en considérant le cas particulier d'une évaluation sur une plateforme distribuée. Nous présentons aussi un modèle de coût pour l'évaluation des termes. À l'aide du modèle de coût et de l'évaluateur, plusieurs termes qui sont équivalents d'un point de vue sémantiques peuvent maintenant être vus comme différentes manières d'évaluer les termes avec différents coûts estimés. Nous montrons alors que les termes qui sont considérés grâce aux nouvelles règles de réécritures que nous avons introduites, permettent une exécution plus efficace que ce qui était possible dans les autres approches existantes. Nous confirmons ce résultat théorique par une expérimentation comparant plusieurs exécuteurs sur des requêtes SPARQL contenant de la récursion.Nous avons investigué comment utiliser une plateforme de calcul distribuée (Apache Spark) pour produire un évaluateur efficace de requêtes SPARQL. Cet évaluateur s'appuie sur un fragment de la μ-algèbre, limité aux opérateurs qui ont une traduction en code Spark efficace. Le résultat de ces investigations à résultat en l'implémentation de SPARQLGX, un évaluateur SPARQL distribué en pointe par rapport à l'état de l'art.Pour finir, ma dernière contribution concerne l'estimation de la cardinalité des solutions à un terme de la μ-algèbre. Ces estimateurs sont particulièrement utiles pour l'optimisation. En effet, les modèles de coût reposent généralement sur de telles estimations pour choisir quel sera le terme le plus efficace parmi plusieurs termes équivalents. Pour cette estimation nous nous intéressons tout particulièrement au fragment conjonctif de la μ-algèbre (ce qui correspond au fragment bien connu Basic Graph Pattern de SPARQL). Notre nouvelle estimation de cardinalité s'appuie sur des statistiques sur les données et a été implémenté dans SPARQLGX. Nos expériences montrent que cette méthode permet de grandement accélérer l'évaluation de SPARQL sur SPARQLGX. / The topic of my PhD is the compilation of web data query languages. More particularly, the analysisand the distributed evaluation of a such language: SPARQL. My main contributions concern theevaluation of web data queries especially for recursive queries or for distributed settings.In this thesis, I introduce μ-algebra: it is a kind of relational algebra equipped with a fixpointoperator. I present its syntax, semantics, and a translation from SPARQL with Property Paths (anew feature of SPARQL allowing some form of recursion) to this μ-algebra.I then present a type system and show how μ-algebra terms can be rewritten to terms withequivalent semantics using either classical rewrite rules of the relational world or new rules that arespecific to this μ-algebra. We demonstrate the correctness of these new rules that are introduced tohandle the rewriting of fixpoints: they allow to push filters, joins and projections inside fixpointsor to combine several fixpoints (when some condition holds).I demonstrate how these terms could be evaluated both from a general perspective and in thespecific case of a distributed evaluation. I devise a cost model for μ-algebra terms inspired by thisevaluation. With this cost model and this evaluator, several terms that are semantically equivalentcan be seen as various Query Execution Plans (QEP) for a given query. I show that the μ-algebraand its rewrite rules allow the reach of QEP that are more efficient than all QEP considered in otherexisting approaches and confirm this by an experimental comparison of several query evaluators onSPARQL queries with recursion.I investigate the use of an efficient distributed framework (Spark) to build a fast SPARQL dis-tributed query evaluator. It is based on a fragment of μ-algebra, limited to operators that havea translation into fast Spark code. The result of this has been used to implement SPARQLGX, astate of the art distributed SPARQL query evaluator.Finally, my last contribution concerns the estimation of the cardinality of solutions to a μ-algebraterm. Such estimators are key in the optimization. Indeed, most cost models for QEP rely on suchestimators and are therefore necessary to determine the most efficient QEP. I specifically considerthe conjunctive query fragment of μ-algebra (which corresponds to the well-known Basic GraphPattern fragment of SPARQL). I propose a new cardinality estimation based on statistics about thedata and implemented the method into SPARQLGX. Experiments show that this method improvesthe performance of SPARQLGX.

Les êtres vivants sont caractérisés par leur rapport avec l'environnement dans lequel ils évoluent. Ils sont dotés de capacités de perception, d'action et de décision. L'animation comportementale s'inspire de cette architecture pour peupler des environnements virtuels avec des entités autonomes à l'image des organismes vivants. Dans ce domaine, il est un être vivant qui retient particulièrement l'attention : l'être humain. Dans cette thèse, nous proposons une architecture pour la description du comportement des humanoïdes virtuels. Dans un premier temps, nous étudions la relation entre l'humanoïde et son environnement dans le cadre de la navigation. Nous proposons un système de subdivision spatiale permettant d'extraire des propriétés topologiques à partir d'un environnement géométrique. Ces informations sont ensuite utilisées pour créer un algorithme de planification de chemin hiérarchique. Nous proposons, dans la continuité, un algorithme de navigation s'inspirant d'études sur le comportement piétonnier et permettant de simuler, en temps réel, des foules composées de plusieurs centaines de piétons. Dans un second temps, nous étudions les composantes réactives et cognitives du comportement. Nous proposons un modèle réactif dont la propriété est de synchroniser et d'adapter automatiquement le déroulement simultané de plusieurs comportements. Le modèle cognitif peut alors exploiter cette propriété pour choisir des actions permettant à l'humanoïde de réaliser un but. Ce modèle se base sur un langage orienté objet permettant de décrire le monde sous la forme des interactions qu'il offre aux humanoïdes. Différentes applications ont validé les travaux réalisés dans cette thèse : simulation de foule, fiction interactive et cinématographie virtuelle.

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette thèse présente la conception et la réalisation en VLSI d'un processeur programmable pour une nouvelle architecture MIMD massivement parallèle, intermédiaire entre la connection machine et les hypercubes de processeurs 32 bits. Elle est composée d'une grille 2d de cellules asynchrones communiquant par échanges de messages. Chaque cellule intégré une partie de traitement qui consiste en un petit microprocesseur 8 bits dote d'une mémoire (données et programme), et une partie de routage permettant l'acheminement des messages. A l'issue de l'étude des différents problèmes de communication dans les machines parallèles, nous proposons un routeur original utilisant le principe du Wormhole, et permettant d'acheminer jusqu'à cinq messages en parallèle. Nous décrivons ensuite l'architecture de la partie de traitement, en partant de la définition du jeu d'instructions, du chemin de données et de la partie contrôle jusqu'à la conception au bas niveau. Un premier prototype d'un circuit VLSI de ce processeur a été réalise sur silicium et a permis d'obtenir les mesures des surfaces et des performances