Nous présentons dans cette thèse une étude sur des<br />algorithmes distribués asynchrones et déterministes de<br />contröle. Un système distribué consiste en un réseau<br />de sites (processeurs, ordinateurs ou réseaux locaux). Dans cette<br />thèse, nous ne considérons que des réseaux de sites<br />communicants n'ayant ni mémoire partagée ni horloge globale.<br />De nombreux problèmes de l'algorithmique distribuée sont<br />réductibles à la construction d'un Arbre Couvrant qui est la<br />structure de contrôle qui nous intéresse.<br /><br />Nous étudions deux types d'algorithmes~: ceux utilisant<br />la notion de phase logique et les autres qui ne considèrent aucun<br />mécanisme de synchronisation. Ces derniers ont des comportements<br />imprévisibles améliorant la tolérance aux fautes. Nous<br />présentons un nouvel algorithme de ce type associé à une<br />élection qui n'est pas une recherche d'extremum contrairement<br />à l'usage. Cet algorithme est comparable au meilleur<br />algorithme connu qui utilise des jetons et des phases logiques<br />induisant un comportement plus "séquentiel".<br /><br />D'autres algorithmes, construisant des AC contraints, sont<br />considérés. En particulier l'AC de Diamètre Minimum qui<br />est, à notre connaissance, un problème qui n'a jamais<br />été étudié dans ce domaine. Le diamètre d'un<br />graphe est la somme des poids des arêtes du plus long des plus<br />courts chemins. Si nous considérons la complexité temporelle,<br />cette contrainte est d'un intérêt &vident. Nous proposons<br />différents algorithmes suivant que la tolérance aux fautes est<br />nécessaire ou non.<br /><br />Finalement, l'étude pratique des algorithmes distribués sur<br />des réseaux de grande taille nous a conduit à la construction<br />d'un simulateur. Il permet l'exécution d'un même code source<br />sur des machines séquentielles ou parallèles.

Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.

Le problème de placement sur deux dimensions consiste à décider s'il existe un rangement d'objets rectangulaires dans une boîte donnée. C'est un problème combinatoire difficile (à la complexité du respect des capacités s'ajoute celle du positionnement des objets). Nous considérons les variantes sans rotation des objets et avec ou sans optimisation de la valeur des objets placés. Nous menons une étude exploratoire des méthodologies qui peuvent être développées à l'interface de la programmation mathématique, de l'optimisation combinatoire et de la théorie des graphes. Nous comparons les formulations de la littérature et en proposons de nouvelles. Nous développons et testons deux approches de résolution innovantes. L'une est basée sur la décomposition de Dantzig-Wolfe (avec un branchement sur les contraintes disjonctives de non recouvrement des objets). L'autre constitue en une approche combinatoire basée sur diverses caractérisations des graphes d'intervalles (modélisant le chevauchement des objets selon chaque axe).

L'espace et le temps sont des concepts indissociables et nécessaires à l'analyse de l'évolution d'entités spatio-temporelles. Modéliser ces évolutions passe par la détection des changements et des relations qui modifient et caractérisent ces entités. Ces changements sont en particulier caractérisés par des modifications liées à la position, à l'empreinte spatiale de ces entités, ou même à leur identité. Une modélisation spatio-temporelle nécessite le développement de solutions de représentation qui permettent d'identifier et d'étudier les processus mis en jeu, leurs causes et leurs conséquences. Le fait que la représentation formelle et informatique d'un phénomène entraîne une description plus ou moins simplifiée de la réalité, implique qu'une telle modélisation retienne le niveau de détail disponible et/ou souhaité de cette description. Idéalement, il devrait être possible d'étudier un phénomène à plusieurs niveaux de granularité dans l'espace et dans le temps. Si de nombreux modèles et approches ont été proposés pour modéliser des évolutions d'entités au sein de phénomènes spatio-temporels, aucun ne permet de disposer d'une structure de représentation permettant de saisir complètement la sémantique de ces applications. Cette recherche propose un modèle de graphe spatio-temporel qui permet de caractériser les principales propriétés de l'évolution d'entités spatiales. Nous distinguons dans ce cadre plusieurs concepts structurants comme les notions d'identité et de relations à travers les dimensions spatiales et temporelles. Pour un temps donné, nous catégorisons les relations spatiales et de filiation et, à travers le temps, les filiations temporelles et les relations spatio-temporelles. Les structures de graphe émergeantes permettent non seulement de caractériser l'évolution d'un ensemble d'entités spatiales, mais aussi de découvrir de nouvelles propriétés. Des fonctions de manipulation de graphe sont développées et appliquées au modèle de graphe spatiotemporel. Ces fonctions identifient des processus génériques ( e.g. vie et mort d'une entité) ou liés à une application spécifique et à sa sémantique. Afin de combiner plusieurs sources d'informations au sein d'un même graphe, des fonctions de jointure permettent l'intégration de plusieurs graphes au sein d'une représentation unifiée. Les propriétés des graphes ainsi constitués et le rôle des différentes entités présentes au sein de ces graphes sont étudiés par une qualification des différents types de routes les reliant. La consistance du modèle de graphe spatio-temporel est abordée à partir d'un algorithme de vérification de contraintes. Nous faisons la différence entre les contraintes de domaine intrinsèques au modèle de graphe, et les contraintes sémantiques dépendantes d'une application en particulier. Une extension de la démarche de modélisation est réalisée à partir d'une structure basée sur les bigraphes qui permet de représenter explicitement un phénomène spatio-temporel selon plusieurs niveaux de granularité spatiale.

Cette thèse s'inscrit dans l'étude des graphes infinis de présentation finie. Nous nous intéressons à la fois à leurs propriétés logiques et aux langages qui leur sont associés. Nous nous concentrons sur l'étude des graphes infinis associés aux automates à pile d'ordre supérieur. Notre première contribution est la définition d'une notion de rationalité pour les piles d'ordre supérieur. Nous montrons que cette notion partage de nombreuses propriétés de la rationalité sur les mots : clôture par complémentaire, accepteurs déterministes et complets, et caractérisation en logique du second ordre monadique. Nous établissons un lien étroit entre les automates à pile d'ordre supérieur et les ensembles rationnels de piles d'ordre supérieur. Notre seconde contribution est l'étude structurelle des graphes associés à ces automates. Nous en donnons différentes caractérisations qui montrent la robustesse de ces familles de graphes infinis.

Dénes Kőnig est connu comme mathématicien avec ses œuvres importants sur la théorie des graphes. Avant de commencer son travail professionnel, en 1902 et en 1905 quand il était étudiant, il a successivement publié deux livres sur les récréations mathématiques en hongrois, mais ces livres ne sont pas encore beaucoup examinés par des historiens. Dans la présente thèse, j'ai traduit ces livres en anglais, et comparé le contenu avec sa monographie sur la théorie des graphes publiée en 1936. J'ai trouvé que beaucoup de problèmes traités dans le second livre sur les récréations mathématiques de 1905 ont été traités à nouveau dans la monographie de 1936, et que beaucoup de problèmes traités dans la monographie de 1936 ont déjà été traités dans le second livre de 1905. Dans ces deux publications, des mêmes problèmes étaient traités de manières différentes. Pour clarifier les rapports entre les récréations mathématiques et la théorie des graphes, j'ai analysé comment des éléments des diagrammes de la théorie des graphes et des concepts de celle-ci ont été formés dans le contexte de récréations mathématiques. J'ai trouvé que Tarry, dans sa conférence sur la géométrie de situation lors d'un congrès en 1886, a intégré certains concepts de sujets différents de récréations mathématiques, et qu'il a utilisé la même sorte de diagrammes pour examiner des problèmes des sujets différents. Les éléments des diagrammes de Tarry sont similaires à ceux utilisés dans la monographie de Kőnig de 1936, et les concepts qui y correspondent peuvent être considérés comme certaines représentations des concepts de la théorie des graphes définis dans la monographie de Kőnig de 1936.

Depuis 1995, l'Union européenne cherche à trouver des solutions pour impulser le cabotage afin de rééquilibrer la distribution modale des transports en Europe. Les "autoroutes de la mer" sont une alternative de transport moins polluante que le mode routier, ainsi qu'une solution pour éviter la congestion des autoroutes. Mais en raison des caractéristiques du transport maritime international, le développement du cabotage n'est pas seulement une alternative écologique, il est aussi une nécessité économique pour le développement ou le maintien des activités maritimes et portuaires. Le cabotage pourrait être une source de trafic de fret non négligeable. L'auteur a analysé les flux routiers entre 112 villes de la péninsule ibérique et de l'Europe du nord-ouest, qui seront la source éventuelle du fret à transférer vers le cabotage. Il a identifié trois principaux pôles d'expédition et de réception du fret routier qui devront fournir les principaux volumes. Ensuite, l'auteur a développé un modèle de choix modal multicritère qui permet la comparaison directe entre les alternatives unimodales de transport combiné. Ce modèle a été utilisé dans le cas de la concurrence entre le mode routier et le mode maritime du cabotage, en fonction du critère du coût de transport. La concentration des liaisons compétitives de cabotage sur les ports permet de définir un potentiel de développement du cabotage pour 57 ports. L'auteur utilise la distribution des flux routiers pour définir les lignes de cabotage les plus "porteuse", en touchant les ports à plus fort potentiel. Finalement, en supposant un transfert de fret routier de 30 pour cent et en ayant connaissance de la distribution spatiale qui devra suivre, l'auteur attribue des volumes de fret aux lignes identifiées afin de construire un scénario de transfert. Mais il faut une volonté politique de l'Union européenne pour impulser ces lignes de cabotage maritime.

Le concept de radio logicielle (SDR) est une solution pertinente pour concevoir des équipements multi-standards. Une façon de réaliser de tels équipements est d'identifier les fonctions et opérateurs communs entre les standards. Cette approche s'appelle la paramétrisation et est divisée en deux catégories : l'approche pragmatique qui est une version pratique pour créer et développer des opérateurs communs à partir d'opérateurs existants, et l'approche théorique dont l'objectif est de réaliser une exploration graphique d'un équipement multi-standards selon différents niveaux de granularité, accompagnée d'un problème d'optimisation. C'est cette dernière approche qui a constitué le sujet de base de cette thèse. Ainsi, une fonction de coût doit être optimisée afin de sélectionner les opérateurs communs entre les différentes normes, ce qui permet de proposer une configuration optimale à partir de laquelle sont déduits les opérateurs communs. Dans notre travail, nous avons dans un premier temps modélisé théoriquement la structure graphique d'un système multi-standards par un hypergraphe orienté. En outre, nous avons fourni une expression mathématique alternative de la fonction de coût suggérée, en utilisant des définitions propres à la théorie des graphes. Ensuite, nous avons montré que le problème d'optimisation associé était un problème NP sous une certaine contrainte, ce qui a entraîné une preuve d'exclusion de certaines configurations dont les coûts ne peuvent être minimaux. Ceci a constitué la deuxième contribution de cette thèse. Enfin, nous avons proposé un nouvel algorithme permettant de résoudre le problème d'optimisation donné, et dont l'intérêt est de donner une solution optimale du problème au lieu d'une solution approchée fournie par les méthodes heuristiques classiques. Un programme associé à cet algorithme a été développé en langage C, puis appliqué à plusieurs exemples de cas génériques afin d'en étudier les performances.

Un système de communication sans fil MIMO-CDMA combine l'utilisation de plusieurs antennes (au niveau de la station de base et/ou des usagers), avec la technique d'accès multiple à répartition par codes. Afin de tirer profit des avantages de cette combinaison, la conception d'un algorithme efficace qui permet l'allocation des ressources devient une tache indispensable. Ce travail propose deux algorithmes d'ordonnancement permettant d'allouer les ressources réseau aux différents usagers dans les systèmes MIMO-CDMA. Vu que le problème d'ordonnancement est dans ce cas NP-difficile, nous avons adopté une approche basée sur la théorie des graphes. Ainsi, nous avons obtenu le bon compromis entre performances et complexité algorithmique. Les simulations présentées démontrent l'efficacité des algorithmes proposés. Ces derniers donnent des résultats très proches de l'optimal tout en réduisant largement la complexité de l'algorithme exacte. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Algorithmes d'ordonnancement, Théorie des graphes, Systèmes de communication sans fil MIMO-CDMA, Simulation des réseaux.

Dans cette thèse, nous étudions deux problèmes de théorie des graphes largement étudiés ces trois dernières décennies: les codes correcteurs d'erreur et la domination.<br />Nous étudions d'abord deux généralisations des codes correcteurs d'erreurs : les codes parfaits sur des alphabets mixtes et les codes pondérés de rayon un. Ces problèmes ont beaucoup été étudiés sur la métrique de Hamming.<br />Nous les étudions dans la métrique de Lee, et nous montrons des résultats aussi bien d'existence que d'inexistence.<br />Nous montrons aussi que le rapport de dualité entre la domination et les codes est fort pour la grille carrée lorsque l'on considère des boules sans le centre.<br />Puis, nous étudions la domination dans les produits de graphes. Depuis que Vizing a conjecturé en 1968 que la domination est surmultiplicative pour le produit cartésien de graphes, les relations entre des variantes du nombre de domination d'un produit de graphes et ses facteurs ont attiré beaucoup d'attention. Après avoir donné quelques bornes sur le nombre de domination totale du produit direct de graphes, nous déterminons le nombre de domination de puissance des produits de chemins.<br />Puis, nous montrons une conjecture ``à la Vizing'' pour le nombre de domination totale supérieure du produit cartésien.<br />Ensuite, nous étudions la domination avec une approche structurelle. En continuation de l'étude de Favaron et Henning, nous fournissons plusieurs bornes supérieures sur le nombre de paire-domination des graphes sans étoiles, pour chaque nombre de branches, et des graphes sans P_5. Nous proposons aussi des familles infinies de graphes pour lesquels ces bornes sont atteintes.<br />Enfin, nous comparons la domination totale supérieure et la paire-domination supérieure, deux variantes de la domination qui ont attiré l'attention récemment, et nous donnons des bornes précises pour les arbres.