La géométrie de l’information est la théorie mathématique qui applique les méthodes de la géométrie différentielle dans le domaine des statistiques et de la théorie de l’information. C’est une technique très prometteuse pour l’analyse et l’illustration des algorithmes itératifs utilisés en communications numériques. Cette thèse porte sur l’application de cette technique ainsi que d’autre technique d’optimisation bien connue, l’algorithme itératif du point proximal, sur les algorithmes itératifs en général. Nous avons ainsi trouvé des interprétations géométriques (basée sur la géométrie de l’information) et proximales (basée sur l’algorithme du point proximal)intéressantes dans le cas d’un algorithme itératif de calcul de la capacité des canaux discrets sans mémoire, l’algorithme de Blahut-Arimoto. L’idée étant d’étendre cette application sur une classe d’algorithmes itératifs plus complexes. Nous avons ainsi choisi d’analyser l’algorithme de décodage itératif des modulations codées à bits entrelacés afin de trouver quelques interprétations et essayer de proposer des liens existant avec le critère optimal de maximum de vraisemblance et d’autres algorithmes bien connus dans le but d’apporter certaines améliorations par rapport au cas classique de cet algorithme, en particulier l’étude de la convergence.Mots-clefs : Géométrie de l’information, algorithme du point proximal, algorithme de Blahut-Arimoto, décodage itératif, Modulations codées à bits entrelacés, maximum de vraisemblance. / Information geometry is a mathematical theory that applies methods of differential geometryin the fields of statistics and information theory. It is a very promising technique foranalyzing iterative algorithms used in digital communications. In this thesis, we apply this technique, in addition to the proximal point algorithm, to iterative algorithms. First, we have found some geometrical and proximal point interpretations in the case of an iterative algorithmfor computing the capacity of discrete and memoryless channel, the Blahut-Arimoto algorithm.Interesting results obtained motivated us to extend this application to a larger class of iterative algorithms. Then, we have studied in details iterative decoding algorithm of Bit Interleaved Coded Modulation (BICM) in order to analyse and propose some ameliorations of the classical decoding case. We propose a proximal point interpretation of this iterative process and find the link with some well known decoding algorithms, the Maximum likelihood decoding.

L'évaluation des systèmes répartis est habituellement fondée sur des critères numériques relatifs à la quantité d'information échangée au cours des calculs. Nous montrons que ces critères ne sont pas suffisants pour évaluer le degré de répartition des algorithmes répartis usuels. Des critères qualitatifs, spécifiques de la répartition, sont nécessaires.<br /><br />La modularité exprime que les processeurs du système n'ont initialement aucune connaissance concernant globalement le réseau dans lequel ils sont plongés. La symétrie exprime que les processeurs avec des positions topologiquement équivalentes dans le réseau ont aussi des rôles équivalents dans les calculs.<br /><br />Nous définissons ces propriétés dans le cadre du langage CSP des processus séquentiels communicants de Hoare. Nous proposons une définition syntaxique pour la modularité. Nous montrons qu'une définition syntaxique de la symétrie n'est pas suffisante. Nous en proposons une définition sémantique. Cette définition se réfère implicitement à une sémantique partiellement ordonnée de CSP. <br /><br />Nous étudions l'existence d'algorithmes de diffusion et d'élection dans les réseaux de processus communicants, qui soient modulaires et symétriques. Nous obtenons de nombreux résultats positifs et négatifs. Ceci conduit en particulier à une évaluation précise du pouvoir expressif de CSP. Nous montrons par exemple qu'il n'existe pas d'implantation des gardes d'émission par des gardes de réception seulement, si la symétrie doit être préservée.<br /><br />Ces résultats sont enfin utilisés pour proposer une solution modulaire, symétrique et bornée au problème de la détection de la terminaison répartie proposé par Francez.

Après une description de la méthode de Karmarkar, il est montré que la valeur du pas de déplacement peut être largement améliorée. Les principales difficultés pratiques de la méthode sont discutées. Plus particulièrement, l'hypothèse de connaitre, au départ, la valeur optimale de l'objectif. Diverses extensions et variantes sont étudiées dans le but de relaxer l'hypothèse ci-dessus

L'isomorphisme inexact de graphes est un problème crucial pour la définition d'une distance entre graphes, préalable nécessaire à une multitude d'applications allant de l'analyse d'images à des applications biomédicales en passant par la reconnaissance optique de caractères. Ce problème est encore plus complexe que celui de l'isomorphisme exact. Alors que ce dernier est un problème de décision de complexité au moins de classe P et qui ne s'applique qu'à des graphes exactement identiques, l'isomorphisme inexact est un problème combinatoire de complexité de classe NP qui permet de prendre en compte des perturbations dues au bruit, qui apparaissent fréquemment dans les applications réelles. Dans ce cadre, nous choisissons d'étudier une solution basée sur les algorithmes génétiques pouvant être appliquée à l'isomorphisme exact et inexact. Nous proposons des opérateurs de croisement généraux pour tout problème représenté par un codage de permutation, ainsi que des opérateurs spécifiques à l'isomorphisme de graphes qui exploitent une heuristique gloutonne. Nous réalisons une étude exhaustive pour comparer ces opérateurs avec les opérateurs existants, soulignant leurs propriétés, avantages et inconvénients respectifs. Nous étudions par ailleurs plusieurs pistes d'amélioration de l'algorithme, en théorie ou en pratique, considérant successivement les objectifs d'accélération de l'exécution, d'augmentation de la précision et de garantie de résultat optimal. Nous proposons pour cela de combiner l'approche proposée avec d'autres techniques telles que des heuristiques générales comme la recherche locale, des heuristiques dédiées comme l'algorithme A*, et des outils pratiques comme la parallélisation. Ces travaux conduisent à la définition d'une méthode générique pour la résolution de tous les problèmes d'isomorphismes de graphes, qu'il s'agisse d'isomorphismes exact ou inexact, d'isomorphismes de graphes de même taille ou d'isomorphismes de sous-graphes. Nous illustrons enfin la validité de cette solution générale par trois applications concrètes issues de domaines différents, la recherche d'images et la chimie, qui présentent chacune des caractéristiques spécifiques, utilisant des graphes attribués ou non, soumis aux perturbations plutôt structurelles ou au niveau d'attributs.

Cette thèse présente une contribution à l'amélioration de certains résultats concernant les algorithmes en Algèbre linéaire et plus particulièrement les algorithmes sur les matrices structurées. Nous présentons un nouvel algorithme de diagonalisation par blocs des matrices de Hankel, particulièrement efficace. Dans le cas où la matrice de Hankel correspond à une suite récurrente linéaire, nous retrouvons ainsi l'algorithme de Berlekamp-Massey, mais dans une version simplifiée (plus facile à expliquer et à programmer) et accélérée par des troncatures. En outre notre version permet une gestion dynamique des données. Notre diagonalisation par blocs, qui s'applique sur un corps arbitraire, nous permet de donner une démonstration purement algébrique et simple d'un délicat théorème de Frobenius pour la signature d'une forme de Hankel réelle. Nous donnons également une étude approfondie de l'algorithme d'Euclide signé et de ses versions matricielles pour les matrices de Hankel et de Bezout associées à un couple de polynômes. Nous expliquons les rapports existants entre différents algorithmes connus dans la littérature.

Dans ce travail je présente une étude unifiée basée sur l'estimation du maximum de vraisemblance pour des modèles markoviens, semi-markoviens et semi-markoviens cachés. Il s'agit d'une étude théorique des propriétés asymptotiques de l'EMV des modèles mentionnés ainsi que une étude algorithmique. D'abord, nous construisons l'estimateur du maximum de vraisemblance (EMV) de la loi stationnaire et de la variance asymptotique du théorème de la limite centrale (TLC) pour des fonctionnelles additives des chaînes de Markov ergodiques et nous démontrons sa convergence forte et sa normalité asymptotique. Ensuite, nous considérons un modèle semi-markovien non paramétrique. Nous présentons l'EMV exact du noyau semi-markovien qui gouverne l'évolution de la chaîne semi-markovienne (CSM) et démontrons la convergence forte, ainsi que la normalité asymptotique de chaque sous-vecteur fini de cet estimateur en obtenant des formes explicites pour les matrices de covariance asymptotiques. Ceci a été appliqué pour une observation de longue durée d'une seule trajectoire d'une CSM, ainsi que pour une suite des trajectoires i.i.d. d'une CSM censurée à un instant fixe. Nous introduisons un modèle semi-markovien caché (MSMC) général avec dépendance des temps de récurrence en arrière. Nous donnons des propriétés asymptotiques de l'EMV qui correspond à ce modèle. Nous déduisons également des expressions explicites pour les matrices de covariance asymptotiques qui apparaissent dans le TLC pour l'EMV des principales caractéristiques des CSM. Enfin, nous proposons une version améliorée de l'algorithme EM (Estimation-Maximisation) et une version stochastique de cet algorithme (SAEM) afin de trouver l'EMV pour les MSMC non paramétriques. Des exemples numériques sont présentés pour ces deux algorithmes.

Ce travail de thèse sur les problèmes de ré-ordonnancement dans un système de transport de bus concerne la mise en oeuvre d'un système d'aide (SAD) pour les régulateurs des exploitants dans leurs tâches de prise de décision lorsque se produisent des perturbations dans le fonctionnement du réseau de transport. Dans ce contexte, nous avons développé un SAD qui repose sur un module de dimensionnement et un module des stratégies de régulation pour aider les régulateurs dans le processus de planification en temps réel et pour diminuer les influences des perturbations. Les approches par l'algorithme génétique et l'algorithme du recuit simulé sont utilisées pour la régulation en tenant compte des diverses contraintes imposées au système et en particulier des contraintes de capacité des autobus. Un nouveau codage et de nouveaux opérateurs de croisement et de mutation ont été proposés pour permettre de respecter les contraintes du problème. Ainsi, nous avons construit une application en Visual C Sharp du SAD proposé afin de prouver son efficacité en cas de perturbation sur le réseau de transport public d'autobus.

Les métaheuristiques sont une famille d'algorithmes stochastiques destinés à résoudre des problèmes d 'optimisation difficile . Utilisées dans de nombreux domaines, ces méthodes présentent l'avantage d'être généralement efficaces, sans pour autant que l'utilisateur ait à modifier la structure de base de l'algorithme qu'il utilise. Parmi celles-ci, l'Optimisation par Essaim Particulaire (OEP) est une nouvelle classe d'algorithmes proposée pour résoudre les problèmes à variables continues. Les algorithmes d'OEP s'inspirent du comportement social des animaux évoluant en essaim, tels que les oiseaux migrateurs ou les poissons. Les particules d'un même essaim communiquent de manière directe entre elles tout au long de la recherche pour construire une solution au problème posé, en s'appuyant sur leur expérience collective. Reconnues depuis de nombreuses années pour leur efficacité, les métaheuristiques présentent des défauts qui rebutent encore certains utilisateurs. Le réglage des paramètres des algorithmes est un de ceux-ci. Il est important, pour chaque problème posé, de trouver le jeu de paramètres qui conduise à des performances optimales de l'algorithme. Cependant, cette tâche est fastidieuse et coûteuse en temps, surtout pour les utilisateurs novices. Pour s'affranchir de ce type de réglage, des recherches ont été menées pour proposer des algorithmes dits adaptatifs . Avec ces algorithmes, les valeurs des paramètres ne sont plus figées, mais sont modifiées, en fonction des résultats collectés durant le processus de recherche. Dans cette optique-là, Maurice Clerc a proposé TRIBES, qui est un algorithme d'OEP mono-objectif sans aucun paramètre de contrôle. Cet algorithme fonctionne comme une boîte noire , pour laquelle l'utilisateur n'a qu'à définir le problème à traiter et le critère d'arrêt de l'algorithme. Nous proposons dans cette thèse une étude comportementale de TRIBES, qui permet d'en dégager les principales qualités et les principaux défauts. Afin de corriger certains de ces défauts, deux modules ont été ajoutés à TRIBES. Une phase d'initialisation régulière est insérée, afin d'assurer, dès le départ de l'algorithme, une bonne couverture de l'espace de recherche par les particules. Une nouvelle stratégie de déplacement, basée sur une hybridation avec un algorithme à estimation de distribution, est aussi définie, afin de maintenir la diversité au sein de l'essaim, tout au long du traitement. Le besoin croissant de méthodes de résolution de problèmes multiobjectifs a conduit les concepteurs à adapter leurs méthodes pour résoudre ce type de problème. La complexité de cette opération provient du fait que les objectifs à optimiser sont souvent contradictoires. Nous avons élaboré une version multiobjectif de TRIBES, dénommée MO-TRIBES. Nos algorithmes ont été enfin appliqués à la résolution de problèmes de seuillage d'images médicales et au problème de dimensionnement de composants de circuits analogiques

Le transport de marchandises dans les zones urbaines est un sujet important de nos jours. Le transport est une activité vitale pour les villes, mais implique pollution, congestion, accidents. La logistique urbaine vise à optimiser les processus logistiques et de transports urbains en tenant compte des aspects environnementaux et sociaux. Cette thèse traite de cette thématique et fait partie du projet MODUM.MODUM vise à étudier un système de livraison basé sur des centres de distribution urbains. Nous présentons une classification et une analyse des mouvements de marchandises et des problèmes de tournées de véhicules (VRP) associés.La deuxième partie propose une revue complète des travaux de recherche traitant des problème VRP avec excursions multiples (MTVRP). Le MTVRP est une extension du VRP où les véhicules sont autorisés à effectuer plusieurs tournées. Nous proposons une heuristique pour le MTVRP qui est par la suite adaptée pour un problème plus riche, le MTVRP avec fenêtres de temps et dates de disponibilité. Il s'agit d'une variante du MTVRP où à chaque client est associée une fenêtre de temps et à chaque marchandise une date de disponibilité qui représente l'instant où elle devient disponible au dépôt.Par la suite, nous étudions une variante du MTVRP où les marchandises sont classées par types de produits qui ne peuvent pas être transportés dans le même véhicule. Une analyse est effectuée pour montrer l’avantage des tournées multiples pour le problème de dimensionnement des flottes.Enfin, nous décrivons le problème de tournées qui se pose dans MODUM et le simulateur qui est développé pour évaluation du système. / Transportation of merchandise in urban areas has become an important nowadays topic. In fact, transportation is a vital activity for each city, but entail pollution, congestion, accidents.City logistics aims at optimizing the whole urban logistics and transportation process, taking into account environmental and social aspects. This thesis, that is part of the MODUM project, finds its location in this area of research. In particular, MODUM aims at studying a delivery system based on City Distribution Centers.We first present a classification and an analysis of urban good movements and routing problems peculiar to metropolitan areas. A second survey proposes a complete collection of articles that has been done on the Multi Trip Vehicle Routing Problem (MTVRP). The MTVRP is an extension of the Vehicle Routing Problem (VRP) where vehicles are allowed to perform several trips.We propose an efficient heuristic for the MTVRP that is, in a subsequent step, adapted to a new routing problem, the MTVRP with Time Windows and Release Dates (MTVRPTWR). It is a variant of the MTVRP where each customer is associated with a time window and each merchandise is associated with a release date that represents the instant it becomes available at the depot.We, then, study a variant of the MTVRP where goods belong to different commodities that cannot be transported at the same time by the same vehicle. An analysis is conducted on the benefits of the multi-trip aspect in fleet dimensioning problems.Finally we describe the complex routing problem that arises in MODUM and the simulator that is developed to evaluate the performances of the system.

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés. / In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V \S] is the set of edges with exactly one end in S. A sensor network topology based on weakly connected sets is partition into three groups, slaves, masters and bridges. The first performs the measurements, the second gathers the collected data and the later provides the inter-group communications. We first give some properties of this combinatorial structure when the undirected graph G is connected. Then we provide complexity results for the problem of finding the minimum weakly connected independent set problem (MWCISP). We also describe an exact enumeration algorithm of complexity O∗(1.4655|V |) (for the (MWCISP)). Numerical tests of this exact procedure are also presented. We then present an integer programming formulation for the minimum weakly connected independent set problem and discuss its associated polytope. Some classical graph operations are also used for defining new polyhedra from pieces. We give valid inequalities and describe heuristical separation algorithms for them. Finally, we develop a branch-and-cut algorithm and test it on two classes of graphs.