Le but de cette thèse est l'étude et l'implémentation de routines de base pour aider l'utilisateur de machines parallèles à mémoire distribuée à obtenir les meilleures performances avec un coût de développement moindre. Trois ensembles de routines sont étudiés. Le premier concerne des routines de communication sur réseau réconfigurable. La seconde bibliothèque fournit à l'utilisateur des routines portables de recouvrements calculs/communications transparents. Enfin, le dernier ensemble concerne des routines de calcul comme le produit de matrices, la factorisation LU et la transformée de Fourier bidimensionnelle. Une attention toute particulière est portée aux recouvrements calculs/communications. Enfin, une application des principes présentés tout au long de la thèse est donnée. Elle concerne la simulation d'un front de combustion

Cette thèse présente des méthodes et des algorithmes pour l'évaluation de performance de systèmes à grand espace d'états décrits par des formalismes de haut niveau. Parmi les différents formalismes de haut niveau normalement utilisés, nous nous sommes intéressés au formalisme des Réseaux d'Automates Stochastiques (SAN). Le formalisme SAN se caractérise par la modélisation de systèmes complexes, où un système est représenté par la composition de sous-systèmes (automates) qui interagissent entre eux. Cette interaction se réalise par l'occurrence des événements synchronisants ou des taux fonctionnels. Lorsqu'on calcule l'espace d'états atteignables de systèmes complexes, le principal problème qui surgit est l'explosion combinatoire de l'espace d'états du modèle. Dans la première partie de cette thèse, nous proposons des méthodes pour la génération de l'espace d'états atteignables de modèles compositionnels qui utilisent des taux fonctionnels. Nous utilisons les Diagrammes de Décision Multi-valués (MDD) pour représenter et manipuler les espaces d'états et le formalisme SAN pour la modélisation de systèmes. Un MDD est une structure de donnée arborescente qui permet de représenter et de manipuler de façon performante un très grand espace d'états. L'avancée par rapport à l'état de l'art a été de proposer de méthodes qui prennent en compte ces fonctions qui expriment des relations entre les composants des modèles. Des études d'exemples sont présentées afin d'illustrer les apports de ces méthodes. Dans la deuxième partie de cette thèse, nous nous sommes intéressés à la résolution d'un modèle SAN à temps discret dont la matrice de transition est représentée par une formule tensorielle (appelée descripteur discret). A cet effet, nous présentons l'Algèbre Tensorielle compleXe (ATX) adaptée à la composition parallèle des SAN à temps discret pour la représentation du descripteur et nous démontrons des propriétés qui servent de base aux méthodes itératives pour la résolution de la chaîne de Markov associée au modèle SAN. Un des avantages de représenter un modèle SAN par un descripteur est la façon compacte par laquelle on peut représenter les transitions du modèle: on remplace une description dans un espace produit par un unique produit tensoriel portant sur des facteurs qui décrivent ce qui se passe sur une seule dimension (une composante du modèle SAN). Afin de profiter de cette représentation, nous présentons une méthode de multiplication d'un vecteur de probabilité par un descripteur discret adaptée à cette algèbre. Cette méthode vise à exploiter des propriétés du produit tensoriel complexe de façon à ce que la multiplication par un opérateur sur l'espace produit soit remplacée par une suite d'opérations qui manipulent des données de la taille d'une composante (et pour toutes les composantes).

Les travaux présentés dans cette thèse constituent une contribution à la modélisation, à l'analyse et à la commande des systèmes de transport public par l'adaptation des réseaux de Petri (RdP) et algèbre des dioïdes. Nous étudions en particulier la gestion optimisée des correspondances par une planification des horaires d'un réseau de transport en commun. Nous développons dans ce sens des modèles capables d'apporter des solutions aux problèmes d'amélioration de la qualité de service de transport en commun, par les minimisations des temps de correspondance et des ressources matérielles utilisées. Notre travail est effectué en considérant deux études de cas de fonctionnement des bus au niveau des arrêts de correspondance où des échanges de passagers sont susceptibles de se produire. Un fonctionnement synchronisé pour lequel nous utilisons un modèle graphe d'événements temporisés (GET) et un modèle (max, +) linéaire stationnaire qui lui est associé. Un fonctionnement non-synchronisé modélisé par un graphe d'événements temporisés avec retrait dynamique de jetons (GETRDJ). Ce dernier modèle graphique, possédant des conflits structurels, a une description analytique dans l'algèbre (max, +) de forme linéaire non-stationnaire. La résolution mathématique du modèle obtenu passe par une politique de résolution des conflits associés au modèle graphique. Nous proposons dans ce sens une politique de routage déterminée a priori prenant en compte les caractéristiques du système. Cette politique permet d'une part, d'arbitrer les conflits sur le modèle graphique, et d'autre part, de résoudre le modèle mathématique. L'analyse des solutions obtenues ainsi que les éléments propres de la matrice caractéristique du modèle (max, +) permet de déterminer les différents temps de correspondance des voyageurs et d'estimer ainsi les performances du système étudié. Dans le souci de minimiser les temps de correspondance des voyageurs et améliorer la qualité de service, nous proposons une politique de commande de ces réseaux de bus. Deux approches sont alors proposées. La première permet de synthétiser une commande basée sur les techniques développées dans le cadre de la théorie de la résiduation dans les dioïdes. La seconde est fondée sur des résultats de simulation qui permettent d'obtenir une commande à partir des optima globaux des fonctions objectifs. Les résultats obtenus sont validés sur une partie du réseau de transport en commun de la ville de Montbéliard.

Contrairement aux données traditionnelles, les données semi-structurées sont irrégulières : des données peuvent manquer, des concepts similaires peuvent être représentés par différents types de données, et les structures même peuvent être mal connues. Cette absence de schéma prédéfini, permettant de tenir compte de toutes les données du monde extérieur, présente l'inconvénient de complexifier les algorithmes d'intégration des données de différentes sources. Nous proposons une architecture de médiation basée entièrement sur XML. L'objectif de cette architecture de médiation est de fédérer des sources de données distribuées de différents types. Elle s'appuie sur le langage XQuery, un langage fonctionnel conçu pour formuler des requêtes sur des documents XML. Le médiateur analyse les requêtes exprimées en XQuery et répartit l'exécution de la requête sur les différentes sources avant de recomposer les résultats. L'évaluation des requêtes doit se faire en exploitant au maximum les spécificités des données et permettre une optimisation efficace. Nous décrivons l'algèbre XAlgebre à base d'opérateurs conçus pour XML. Cette algèbre a pour but de construire des plans d'exécution pour l'évaluation de requêtes XQuery et traiter des tuples d'arbres XML. Ces plans d'exécution doivent pouvoir être modélisés par un modèle de coût et celui de coût minimum sera sélectionné pour l'exécution. Dans cette thèse, nous définissons un modèle de coût pour les données semi-structurées adapté à notre algèbre. Les sources de données (SGBD, serveurs Web, moteur de recherche) peuvent être très hétérogènes, elles peuvent avoir des capacités de traitement de données très différentes, mais aussi avoir des modèles de coût plus ou moins définis. Pour intégrer ces différentes informations dans l'architecture de médiation, nous devons déterminer comment communiquer ces informations entre le médiateur et les sources, et comment les intégrer. Pour cela, nous utilisons des langages basés sur XML comme XML-Schema et MathML pour exporter les informations de métadonnées, de formules de coûts et de capacité de sources. Ces informations exportées sont communiquées par l'intermédiaire d'une interface applicative nommée XML/DBC. Enfin, des optimisations diverses spécifiques à l'architecture de médiation doivent être considérées. Nous introduisons pour cela un cache sémantique basé sur un prototype de SGBD stockant efficacement des données XML en natif.

Notre recherche vise à répondre aux difficultés des enseignants à gérer l'hétérogénéité des apprentissages des élèves en algèbre élémentaire en fin de scolarité obligatoire en France (15 ans). La thèse, qui s'inscrit dans le projet de recherche PepiMeP, porte sur la modélisation didactique de parcours d'enseignement différencié appuyés par un logiciel de diagnostic et sur leur implémentation informatique dans des systèmes de ressources en ligne. Nous la situons dans le cadre de la théorie anthropologique du didactique pour étudier et comprendre les conditions de production et de circulation des savoirs dans les institutions. Tirant parti de recherches antérieures en didactique de l'algèbre, nous définissons une organisation mathématique épistémologique de référence. Elle sert de fondement pour, d'une part, analyser le savoir à enseigner et formuler des hypothèses sur la présence de savoirs et savoir-faire implicites dans les institutions considérées et, d'autre part, mettre en relation les rapports personnels des élèves, caractérisés par le diagnostic, avec les rapports institutionnels en algèbre. Ces analyses éclairent sur les questions génératrices à aborder dans les parcours et fournissent des éléments pour sélectionner des types de tâches, souvent rarement présents en classe, et pour organiser leur gestion didactique. L'analyse d'expérimentations, menées dans le cadre d'un travail collaboratif avec des enseignants du secondaire, des chercheurs en informatique et l'association de professeurs de mathématique Sésamath, nous permet d'évaluer la pertinence cognitive et épistémologique du modèle et d'envisager son écologie possible dans l'enseignement secondaire actuel.

L'inégalité de Hausdorff-Young a été généralisée aux groupes localement compacts par R. Kunze dans le cas unimodulaire puis par M. Terp dans le cas général. Une version de cette inégalité a été donnée par B. Russo pour les opérateurs intégraux. Dans cette thèse, on établit une inégalité de Hausdorff-Young pour les groupoïdes mesurés qui recouvre ces résultats. Comme dans les cas des groupes non commutatifs, on utilise la théorie non commutative de l'intégration. La majeure partie de ce travail est l'identification des espaces Lp de l'algèbre de von Neumann du groupoïde dans les cas p=1, 2 comme espaces de fonctions et aussi comme espaces d'opérateurs aléatoires.

Les SIG, systèmes d'information géographiques, stockent des données<br /> géo-référencées dans des bases de données géographiques, ouvrant<br /> ainsi de grandes potentialités en terme d'exploitation. Une<br /> utilisation fréquente des SIG concerne la prise de décision à<br /> référence spatiale. Néanmoins, la technologie SIG actuelle souffre<br /> encore de plusieurs lacunes, dues en grande partie à un manque de<br /> capacités analytiques capables de supporter la nature multicritère<br /> des problèmes spatiaux. La solution la plus diffusée pour faire<br /> évoluer les SIG vers un vrai outil d'aide à la décision à référence<br /> spatiale est l'analyse multicritère (AMC). De nombreux travaux<br /> d'intégration SIG-AMC ont été publiés depuis le début des années<br /> 1990. Cependant, ces travaux présentent plusieurs limites qui les<br /> empêchent à être diffusés au delà du cadre académique : (i)<br /> utilisation du mode d'intégration indirecte ou encastrée, (ii)<br /> intégration d'une seule méthode ou d'un nombre limité de méthodes,<br /> (iii) absence d'une méthodologie pour le choix de la méthode à<br /> appliquer dans un problème donné, (iv) intégration des méthodes du<br /> critère unique de synthèse, et (v) nécessité d'une connaissance<br /> approfondie du SIG et de l'AMC. Dans ce travail de thèse, notre<br /> contribution a porté sur la proposition de solutions conceptuelles,<br /> méthodologiques et informatiques pour surpasser ces différentes<br /> lacunes. Plus précisément, nous proposons : (i) une stratégie<br /> d'intégration SIG-AMC, (ii) un module à base de règles pour le choix<br /> de la procédure d'agrégation, (iii) une méthodologie pour la<br /> cartographie décisionnelle multicritère facilitant l'utilisation des<br /> méthodes de surclassement de synthèse, et (iv) une algèbre destinée<br /> à la modélisation spatiale multicritère. Pour valider les solutions<br /> proposées, nous avons développé un prototype et nous l'avons<br /> appliqué à un problème de génération des corridors en utilisant des<br /> données réelles, relatives à l'Ile-de-France. Les résultats obtenus<br /> sont satisfaisants.

Cette thèse traite principalement des contreparties combinatoires et constructives de certains théorèmes d'optimisation combinatoire qui font appel à des outils de topologie algébrique. Des généralisations des lemmes de Sperner et des formules combinatoires de Ky Fan sont proposées, ainsi que des applications à la coloration des graphes de Kneser et au célèbre problème du partage équitable du collier. Un problème d'ordonnancement lié à ce dernier problème est également abordé. Enfin, le dernier chapitre contient des résultats nouveaux pour les sigma-jeux (jeux de lampes) sur la grille.

Les systèmes de commande en réseau (SCR) sont de plus en plus répandus dans le milieu industriel. Ils procurent en effet de nombreux avantages en termes de coût, de flexibilité, de maintenance, etc. Cependant,l'introduction d'un réseau, qui par nature est composé de ressources partagées, impacte considérablement les performances temporelles des systèmes de commande. Un signal de commande par exemple n'arrive à destination qu'après un certain délai. Pour s'assurer que ce délai soit inférieur à un certain seuil de sécurité ou du respect d'autres contraintes temps réels de ces systèmes, une évaluation au préalable, avant la mise en service d'un SCR, s'avère donc nécessaire. Dans nos travaux de recherche, nous nous intéressons à la réactivité des SCR client/serveur et évaluons leur temps de réponse.Notre contribution dans ces travaux est d'adopter une approche analytique à base de l'algèbre (Max,+) et remédier aux problèmes des méthodes existantes comme l'explosion combinatoire de la vérification formelle ou de la non exhaustivité des approches par simulation. Après modélisation des SCR client/serveur à l'aide de Graphe d'Evénements Temporisés puis représentation de leurs dynamiques à l'aides d'équations (Max,+) linéaires, nous obtenons des formules de calcul direct du temps de réponse. Plus précisément, nous adoptons une analyse déterministe pour calculer les bornes, minimale et maximale, du temps de réponse puis une analyse stochastique pour calculer la fonction de sa distribution. De plus, nous prenons en compte dans nos travaux tous les délais élémentaires qui composent le temps de réponse, y compris les délais de bout-en-bout, dus à la traversée du seul réseau de communication. Ce dernier étant naturellement composé de ressources partagées, rendant l'utilisation des modèles (Max,+) classiques impossibles, nous introduisons une nouvelle approche de modélisation à base du formalisme (Max,+) mais prenant en compte le concept de conflit ou ressource partagée.L'exemple d'un réseau de type Ethernet est considéré pour évaluer ces délais de bout-en-bout. Par ailleurs, cette nouvelle méthode (Max,+) est assez générique et reste applicable à de nombreux systèmes impliquant des ressources partagées, au delà des seuls réseaux de communication. Enfin, pour vérifier la validité des résultats obtenus dans nos travaux, notamment la formule de la borne maximale du temps de réponse, une compagne de mesures expérimentales sont menées sur une plateforme dédiée. Différentes configurations et conditions de trafic dans un réseau Ethernet sont considérées.

Un défi toujours actuel dans le domaine des systèmes intégrables quantiques est le calcul exact et explicite des fonctions de corrélation. Dans le cas de modèles simples tels que la chaîne de Heisenberg XXZ de spins 1/2, des progrès significatifs ont été réalisés ces dernières années. Les méthodes développées utilisent les symétries des modèles en volume infini (algèbre quantique affine) ou fini (algèbre de Yang-Baxter). L'objet de cette thèse est d'étendre le champ d'application de ce dernier type d'approche dans le cas où l'algèbre de Yang-Baxter sous-jacente est de type dynamique. C'est typiquement le cas du modèle de physique statistique solid-on-solid (SOS) qui décrit les interactions d'un paramètre de hauteur autour des faces d'un réseau bidimensionnel, avec des poids statistiques donnés par une matrice R elliptique solution de l'équation de Yang-Baxter dynamique.L'étude des fonctions de corrélation du modèle SOS est abordée dans le cadre de l'ansatz de Bethe algébrique et de la méthode de séparation des variables. Des représentations en termes de déterminants de fonctions usuelles sont obtenues par les deux méthodes pour les produits scalaires entre états et pour les facteurs de forme des opérateurs locaux en volume fini. Les formules obtenues dans le cadre de l'ansatz de Bethe algébrique sont ensuite utilisées pour représenter la fonction de corrélation à deux points sous la forme d'intégrales multiples, ainsi que pour le calcul de diverses quantités physiques à la limite thermodynamique, telles que les polarisations spontanées ou les probabilités de hauteurs locales. Ces dernières s'expriment sous forme d'intégrales multiples similaires à celles du modèle XXZ.