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.

A partir de l'identification des 3 hypothèses que sont l'information imparfaite, l'asymétrie informationnelle et la rationalité limitée, la science économique a du profondément modifier la représentation et l'explication des phénomènes économiques du modèle standard. Ce mouvement a concerné à la fois la vision des marchés et celle de la firme. A partir de la notion de « firme processeur d'information » qui est celle largement retenue dans l'orthodoxie néo-classique ou apparentée, cette thèse propose de penser l'articulation entre organisation, information et pouvoir. Afin de dépasser la double tradition en économie qui consiste soit à postuler le pouvoir (approche des radicaux), soit à le nier (courant néo-classique), une démarche pragmatique essaie d'aller chercher en dehors des frontières de l'économie des modèles susceptibles de donner des pistes de représentation du pouvoir intra-organisationnel. Ce choix est renforcé par les travaux de micro-économie contemporain qui mobilisent eux-mêmes des travaux d'inspiration « sociologique » et qui permettent de penser l'introduction du pouvoir dans les modèles de al théorie standard. Cette démarche aboutit au choix d'une définition opérationnelle du pouvoir ouvrant la voie à une quantification de l'organisation. Celle-ci est menée en utilisant la théorie des graphes d'influence, qui allie la représentation topologique de la théorie des graphes au calcul matriciel de la méthodologie input-output. Les indicateurs qu'elle fournit sont calculés dans le cadre de l'étude d'une organisation concrète. La base de données est construite à partir des flux d'échange de mails. Ils fournissent une caractérisation assez fine de l'organisation en distinguant notamment le niveau global du niveau local. Ils permettent également de discuter de l'articulation entre la structure formelle et la structure informelle. <br />Finalement sur la base de trois définitions des notions d'organisation, d'information et de pouvoir, élaborées à partir d'une large revue de la littérature en économie des organisations, cette thèse propose des indicateurs permettant de déterminer qui a le pouvoir dans une organisation concrète définie comme une structure d'échanges d'informations.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.

Un fasciagraphe de taille n et de fibre F est constitué de n copies consécutives du graphe F, chaque copie étant reliée à la suivante selon le même schéma. Les rotagraphes sont définis similairement, mais selon une structure circulaire. Dans cette thèse nous caractérisons un ensemble de problèmes combinatoires qui peuvent être résolus de façon efficace dans la classe des fasciagraphes et rotagraphes. Dans ce contexte, nous définissons les (d,q,w)-propriétés closes et stables, et présentons pour de telles propriétés un algorithme pour calculer une solution optimale en temps constant pour l'ensemble des fasciagraphes ou rotagraphes de fibre fixée. Nous montrons que plusieurs problèmes communément étudiés dans la théorie des graphes et NP-complets dans le cas général sont caractérisés par des (d,q,w)-propriétés closes ou stables. Dans une seconde partie de la thèse, nous adaptons cet algorithme générique à trois problèmes spécifiques caractérisés par des (d,q,w)-propriétés stables : le problème du code identifiant minimum, et deux problèmes proches, celui de dominant-localisateur minimum et celui du dominant-total-localisateur minimum. Nous présentons alors une implémentation de l'algorithme qui nous a permis de répondre à des questions ouvertes dans certains rotagraphes particuliers : les bandes circulaires de hauteur bornée. Nous en déduisons d'autres résultats sur les bandes infinies de hauteur bornée. Enfin, nous explorons le problème du code identifiant dans une autre classe de graphes à structure répétitive : les graphes fractals de cycle.

La décomposition modulaire apparait naturellement dans différents domaines de la combinatoire (et en particulier les graphes). Cette décomposition se révèle être un puissant outil de description d'objets discrets. Elle est aussi utilisée comme étape préliminaire à nombreux d'algorithmes.<br /><br />Dans ce mémoire, nous nous intéressons au calcul de la décomposition modulaire. Malgré la publication d'algorithmes linéaires au milieu des années 90, la recherche sur ce problème n'a pas cessée. Nous faisons le point sur les différentes avancées et techniques utilisées.

Cette thèse traite deux types de problèmes algorithmiques : des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes et des problèmes de découverte de structures secondaires d'ARN. Nous étudions des problèmes de triangularisation de matrices booléennes par permutation des lignes et des colonnes. Ce problème apparaît, par exemple, lorsque l'on souhaite calculer "en place" un système d'équations. Une façon naturelle d'aborder ce problème est de se placer dans le cadre général de la théorie des graphes et des graphes bipartis en particulier. Nous présentons de nombreux résultats de complexité - essentiellement de NP-complétude - liés à ce problème et introduisons quelques extensions dont nous précisons toujours la complexité. Certaines familles d'ARN sont très précisément définies par des motifs de séquence, et des contraintes structurelles secondaires et tertiaires. La plupart des outils ne sont pas adaptés puisqu'ils n'intègrent pas toutes les connaissances sur la molécule lors de l'exploration des banques de séquences. D'où l'intérêt d'algorithmes de recherche assurant une recherche en séquence et structure par le biais d'un descripteur défini par l'utilisateur intégrant l'ensemble des connaissances caractérisant l'ARN à détecter. Une nouvelle façon d'aborder ce problème consiste en l'étude de problèmes algorithmiques sur les graphes d'intersection d'un ensemble de 2-intervalles. Cette notion de 2-intervalles se trouve dans la lignée des études actuelles en matière d'algorithmique de graphes où l'on étudie de plus en plus les structures des graphes issues de modèles géométriques. Nous présentons plusieurs résultats de complexité et montrons en particulier que la recherche de motifs dans un ensemble de 2-intervalles est un problème NP-complet. Nous nous intéressons, plus particulièrement, à appliquer ces travaux pour la prédiction de motifs biologiques structurés. Plus spécifiquement, nous avons mis au point l'algorithme ORANGE pour la prédiction des introns auto-catalytiques de groupe 1 dans de grandes séquences génomiques. Cet algorithme est une amélioration de l'algorithme CITRON mis au point par F. Lisacek et F. Michel du point de vue de la rapidité d'exécution. De plus, une mise-en-œuvre de l'algorithme ORANGE est accessible en ligne sur Internet.