Academic literature on the topic 'Algorithmes de mariage'

Nous proposons une alternative à l’approche prévalente dans les algorithmes de mariage en ligne. Basés sur le choix d’un critère de mariage, nous construisons des algorithmes dits locaux. Ces algorithmes sont locaux dans le sens où chacun des individus est tour à tour soumis au critère de mariage choisi. Ce qui nous amène à démontrer que le nombre de sommets qui finissent mariés lorsque chaque individu adopte une stratégie prédéfinie est solution d’une équation différentielle ordinaire. Grâce à cette approche nous prédisons les performances et comparons deux algorithmes/stratégies. Pour émuler l'asymptotique des graphes, nous utilisons le modèle de configuration basé sur un échantillonnage de la distribution de degré du graphe d'intérêt. Et globalement notre méthode peut être vue comme une généralisation de la Differential Equation Method de Wormald. Il est à noter que l’approche en ligne se concentre principalement sur les graphes bipartis<br>The present thesis constructs an alternative framework to online matching algorithms on large graphs. Using the configuration model to mimic the degree distributions of large networks, we are able to build algorithms based on local matching policies for nodes. Thus, we are allowed to predict and approximate the performances of a class of matching policies given the degree distributions of the initial network. Towards this goal, we use a generalization of the differential equation method to measure valued processes. Through-out the text, we provide simulations and a comparison to the seminal work of Karp, Vazirani and Vazirani based on the prevailing viewpoint in online bipartite matching

Le Problème du Mariage Stable (SMP) est un problème d'appariement où les participants ont des préférences à propos de leurs partenaires potentiels.L'objectif est de trouver un appariement optimal (stable dans un sens) au regard des préférences. Ce type d'appariement a de très nombreuses applications comme les affectations d'étudiants à des universités (APB ou ParcourSup), celles des internes en médecine aux hôpitaux, les choix des donneurs pour les patients en attente d'organe, la mise en rapport des taxis et de leurs clients ou encore la diffusion de contenu sur Internet.Certaines de ces applications peuvent être traitées de manière centralisée tandis que d'autres, de par leur nature distribuée et la complexité de leurs données, nécessitent un traitement différent. Par exemple, dans le contexte du Cloud-Computing, des machines virtuelles sont émulées par des machines réelles situées sur la terre entière.Un algorithme centralisé causerait des délais considérables dans les prises de décision tout en étant sensible aux défaillances, ce qui est inconcevable pour un service supposé disponible à tout moment. D'un autre côté, chaque fois que des personnes sont impliquées dans un appariement, elles ont le droit de garder privées leurs données personnelles et en particulier leur liste de préférences, qui peut contenir des informations sensibles.Par conséquent, il est souhaitable que les listes de préférence des personnes ne soient jamais transmises sur Internet, et encore moins rassemblées pour un traitement centralisé.C'est pourquoi la distribution, la tolérance aux défaillances (par auto-stabilisation) et la confidentialité sont les trois principaux mots-clés de cette thèse.Dans ce contexte, nous proposons deux solutions distribuées auto-stabilisantes. De telles solutions tolèrent les défaillances (e.g., corruptions de mémoire ou de messages) transitoires (ou de courte durée) de n'importe quels noeuds.La confidentialité des listes de préférences est garantie par les deux algorithmes que nous proposons : les listes ne sont pas partagées et seules des queries binaires et leurs réponses sont échangés.Une différence entre ces algorithmes est le modèle de communication : le premier algorithme utilise le modèle à état tandis que le second algorithme utilise le modèle à registre plus général.Dans les deux modèles, les exécutions se déroulent par pas atomiques et un démon (démon distribué inéquitable) exprime la notion d'asynchronisme.Avec ce démon, le temps de stabilisation peut être borné en terme de moves (pas locaux).Cette mesure de complexité permet d'évaluer avec précision la puissance de calcul nécessaire ou l'énergie dissipée par les exécutions de l'algorithme.Ce n'est pas le cas quand la complexité est évaluée en rounds, puisque le nombre de moves effectués dans un round n'est pas nécessairement borné.Le premier algorithme, basé sur la méthode centralisée de Ackermann et al. (SICOMP' 2011), résout le SMP en O(n⁴) moves.Il permet également de résoudre certaines variantes du SMP telles que le mariage stable avec indifférence, avec partenaires inacceptables, etc.Le point de départ du deuxième algorithme est le schéma de détection locale/correction globale de Awerbuch et al. (DA' 1994) : un algorithme non auto-stabilisant (devant être initialisé) mais avec la propriété d'être vérifiable localement peut être combiné avec un détecteur et un algorithme de réinitialisation.De cette combinaison résulte un algorithme auto-stabilisant.Malheureusement, la définition de la vérifiabilité locale de DA '1994 ne s'applique pas à notre cas (en particulier en raison du démon inéquitable).Nous proposons donc une nouvelle définition.De plus, nous concevons un algorithme de réinitialisation (reset) asynchrone, distribué et auto-stabilisant.L'algorithme résultant résout le SMP en θ(n)² moves<br>The Stable Marriage Problem (SMP) is a matching problem where participants have preferences over their potential partners.The objective is to find a matching that is optimal (stable in certain sens) with regard to these preferences.This type of matching has a lot of widely used applications such as the assignment of children to schools, interns to hospitals, kidney transplant patients to donors, as well as taxi scheduling or content delivery on the Internet.Some applications can be solved in a centralized way while others, due to their distributed nature and their complex data, need a different treatment.For example, when applying this problem to the Cloud-Computing context, virtual machines are emulated by real machines located all over the world.A centralized algorithm would cause unbearable delays and be sensible to failures, which is inconceivable for a service meant to be available at any time.On the other hand, when humans are to be matched or involved in a matching, they have the right to keep their personal data private and in particular their list of preferences.Consequently, the preference lists should not be transmitted on the Internet, and even less gathered for a centralized treatment.This is why, distribution, fault-tolerance (by self-stabilization) and privacy are the three main keywords of this thesis.In order to handle these challenges, we provide two distributed self-stabilizing solutions.Such solutions tolerate transient (or short-lived) failures (e.g., memory or message corruptions) of any nodes.The privacy of the preference lists is guaranteed by the two proposed algorithms: lists are not shared, only some binary queries and responses are transmitted.One of the differences between the two algorithms is the communication model: the first algorithm uses the state model while the second algorithm uses the more general register model.In both models, executions proceed in atomic steps and a daemon (distributed unfair daemon) conveys the notion of asynchrony.Under this daemon, the stabilization time can be bounded in term of moves (local computations).This complexity metrics allows to evaluate the necessary computational power or the energy consumption of the algorithm's executions.This is not the case when the stabilization time is measured in rounds since an unbounded number of moves may be executed during a round.The first algorithm, based on the centralized method of Ackermann et al. (SICOMP' 2011), solves the problem in O(n⁴) moves.It also solves some variants of SMP such as the Stable Marriage with indifference, with unacceptable partners, etc.The starting point of the second algorithm is the local detection/global correction scheme of Awerbuch et al. (DA' 1994): a non-self-stabilizing algorithm (with initialization) that satisfies the property of local checkability can be combined with a detector and a reset algorithms.The result of this composition is a self-stabilizing version of the given algorithm.Unfortunately, local checkability definition of DA '1994 does not apply to our case (in particular due to the unfair daemon).Consequently, we propose a new definition.Furthermore, we design a distributed self-stabilizing asynchronous reset algorithm. Using it, the resulting composed algorithm solves SMP in θ(n)² moves in a self-stabilizing way

Includes bibliographical references (leaves 69-74).<br>Includes abstract.<br>Long-term ecosystem changes, such as regime shifts, have occurred in several marine ecosystems worldwide. Multivariate statistical methods have been used to detect such changes, but they have to date not been applied to the southern Benguela ecosystem. A weakness of many of the methods is that they require long time series data and do not provide robust results at the end of time series. A new method known as the sequential t-test algorithm for analysing regime shifts (STARS) is applied to a set of biological state variables and environmental and anthropogenic forcing variables in the southern Benguela.

Composite materials (herein means Fibre Reinforced Plastic, FRP) are increasingly usedin the construction of marine vehicles because of their outstanding strength, stiffness and light weight properties. However, the use of FRP comes with difficulties in the design process as a result of the large number of design variables involved: composite material design, topologies and laminate schemes. All variables are related to each other leading to a high dimensional and flexible design space. It is hard to use traditional design methods in order to gain solutions for an initial design stage in a short time. Hence, this thesis deals with the presentation of a structural synthesis (optimisation framework) for plate components of composite ship structures. The framework broadly consists of an optimisation technique and structural analytical methods. To make the framework compatible with the nature of composite ship structural design problems, the Genetic Algorithm (GA) is selected as the optimisation tool because of its robustness, its ability in dealing with both continuous and discrete variables and its excellent searching for a global optimum. The typical plate types in a ship structure are the stiffened and unstiffened plates. For a stiffened plate, the combination of the grillage analysis of energy method based on Navier solution and an equivalent elastic properties approach are introduced. Using this, it is possible to produce layer by layer optimisation results for the base plate, web and crown of the stiffened plate. Unfortunately, solutions of the adopted grillage analysis do not cover the mechanical behaviour of the plate between stiffeners so the Higher-Order Shear Deformation Theory (HSDT) must be employed. This method provides accurate solutions for thin to moderately thick plates with a compromised computational time. Then stiffness, strength and stability can be considered in the design problem. In addition, to achieve the program of the structural synthesis, various computational modules are implemented according to the evaluation of composite micromechanics properties, maximum stress failure criteria and structural weight function. Then the main modules are validated with available resources. The usefulness of the program has been proved by comparing it with the optimal solutions from finite element software. Finally, many application examples of secondary and tertiary composite ship structures are presented. The optimal results prove the success of the optimisation framework. This could be evidence for further improvement to obtain a valuable structural optimisation tool.

On assiste au développement des activités humaines liées au monde océanique, mais aucune norme n'a encore émergé pour l'Internet des objets appliqué aux objets autonomes marins. Bien qu'elle possède une bande passante limitée, l'onde acoustique est le seul moyen de communiquer sur des distances importantes et elle est donc utilisée par de nombreux systèmes sous-marins pour communiquer, naviguer ou déduire des informations sur l'environnement. Cela a conduit à une forte demande de réseaux sans fil qui nécessitent à la fois une bonne efficacité spectrale et énergétique avec la faible complexité des algorithmes associés. Par conséquent, au cours de ce doctorat, nous avons proposé plusieurs solutions originales pour relever le défi de développer des techniques numériques, capables de faire face au canal acoustique.En raison d’une diversité inhérente d'espace du signal (SSD), les constellations tournées permettent de meilleures performances théoriques que les constellations conventionnelles et ce, sans détérioration spectrale. Nous passons en revue les propriétés structurelles des constellations tournées M-QAM uniformément projetées, afin de proposer une technique de demapping souple à faible complexité pour les canaux à fading. Puis, nous proposons une technique originale de réduction du PAPR pour les systèmes OFDM utilisant les constellations tournées. Afin de réduire la complexité du décodage aveugle, nous nous appuyons sur les propriétés des constellations tournées M-QAM uniformément projetées, pour concevoir un estimateur de faible complexité. De plus, pour faire face à la sélectivité du canal acoustique, nous avons proposé un turbo-détecteur parcimonieux adaptatif avec seulement quelques coefficients à mettre à jour afin de réduire la complexité. Enfin, nous avons proposé un algorithme original auto-optimisé pour lequel les tailles de pas de l'égaliseur sont mises à jour de manière adaptative et assistées par des informations souples de manière itérative, afin de répondre à l'exigence de convergence rapide et de faible erreur quadratique sur des canaux variant rapidement dans le temps<br>There has been recently a large development of human activities associated to the ocean world, where no standard has emerged for the Internet of Things (IoT) linked to marine autonomous objects. Though it has a limited bandwidth, the acoustic wave is the only way to communicate over average to large distances and it is thus used by many underwater systems to communicate, navigate, or infer information about the environment. This led to a high demand for wireless networks that require both spectral efficiency and energy efficiency with the associated low-complexity algorithms. Therefore, in this Ph.D. thesis, we proposed several original solutions to face this challenge.Indeed, due to the inherent Signal Space Diversity (SSD), rotated constellations allow better theoretical performance than conventional constellations with no spectral spoilage. We review the structural properties of uniformly projected rotated M-QAM constellations, so as to propose a low complexity soft demapping technique for fading channels. Then, we present an original blind technique for the reduction of the PAPR for OFDM systems using the rotated constellations with SSD. In order to reduce the complexity of blind decoding for this technique, we again rely on the properties of uniformly projected M-QAM rotated constellations to design a low-complexity estimator. Moreover, to face the selectivity of the acoustic channel, we suggest a sparse adaptive turbo detector with only a few taps to be updated in order to lower down the complexity burden. Finally, we have proposed an original self-optimized algorithm for which the step-sizes of both the equalizer and the phase estimator are updated adaptively and assisted by soft-information in an iterative manner, so as to meet the requirement of fast convergence and low MSE over time-varying channels

Dans ce travail, l’optimisation de la propulsion et de la commande des AUV (Autonomous Underwater Vehicles en anglais) est développée. Le modèle hydrodynamique de l’AUV est examiné. Egalement, son système de propulsion est étudié et des modèles pour des solutions de propulsion différentes (fixe et vectorielle) sont développés dans le cadre de la mobilité autonome.Le modèle et l’identification de la technologie de propulsion dite fixe sont basés sur un propulseur disponible commercialement. Le système de propulsion vectoriel est basé sur un prototype de propulseur magneto-couplé reconfigurable (PMCR) développé à l’IRDL-ENIB.Une méthode de commande non linéaire utilisant le modèle hydrodynamique de l’AUV est développée et son adaptation à deux systèmes de propulsion est présentée. Des analyses portant sur la commandabilité du robot et l’application de cette commande à différents systèmes sont proposées. L’optimisation globale est utilisée pour trouver des topologies propulsives et des paramètres de commande adaptés à la réalisation de tâches robotiques spécifiques. L’optimisation réalisée permet de trouver des solutions capables d’assurer le suivi de trajectoire et de minimiser la consommation énergétique du robot. L’optimisation utilise un algorithme génétique (algorithme évolutionnaire), une méthode d’optimisation stochastique appliquée ici à la conception orientée tâche de l’AUV. Les résultats de cette optimisation peuvent être utilisés comme une étape préliminaire dans la conception des AUVs, afin de donner des pistes pour améliorer les capacités de la propulsion.La technique d’optimisation est également appliquée au robot RSM (fabriqué au sein de l’IRDL-ENIB) en modifiant seulement quelques paramètres de sa topologie propulsive. Cela afin d’obtenir des configurations de propulsion adaptées au cours d’une seule et même mission aux spécificités locomotrices des tâches rencontrées : reconfiguration dynamique de la propulsion de l’AUV<br>In this PhD thesis, the optimization of the propulsion and control of AUVs is developed. The hydrodynamic model of the AUVs is examined. Additionally, AUV propulsion topologies are studied and models for fixed and vectorial technology are developed. The fixed technology model is based on an off the shelf device, while the modeled vectorial propulsive system is based on a magnetic coupling thruster prototype developed in IRDL (Institut de Recherche Dupuy de Lôme) at ENI Brest. A control method using the hydrodynamic model is studied, its adaptation to two AUV topologies is presented and considerations about its applicability will be discussed. The optimization is used to find suitable propulsive topologies and control parameters in order to execute given robotic tasks, speeding up the convergence and minimizing the energy consumption. This is done using a genetic algorithm, which is a stochastic optimization method used for task-based design.The results of the optimization can be used as a preliminary stage in the design process of an AUV, giving ideas for enhanced propulsive configurations. The optimization technique is also applied to an IRDL existing robot, modifying only some of the propulsive topology parameters in order to readily adapt it to different tasks, making the AUV dynamically reconfigurable

A novel video observational method for the space-time stereoscopic reconstruction of dynamic surfaces representable as graphs, such as ocean waves, is developed. Variational optimization algorithms combining image processing, computer vision and partial differential equations are designed to address the problem of the recovery of the shape of an object's surface from sequences of synchronized multi-view images. Several theoretical and numerical paths are discussed to solve the problem. The variational stereo method developed in this thesis has several advantages over existing 3-D reconstruction algorithms. Our method follows a top-down approach or object-centered philosophy in which an explicit model of the target object in the scene is devised and then related to image measurements. The key advantages of our method are the coherence (smoothness) of the reconstructed surface caused by a coherent object-centered design, the robustness to noise due to a generative model of the observed images, the ability to handle surfaces with smooth textures where other methods typically fail to provide a solution, and the higher resolution achieved due to a suitable graph representation of the object's surface. The method provides competitive results with respect to existing variational reconstruction algorithms. However, our method is based upon a simplified but complete physical model of the scene that allows the reconstruction process to include physical properties of the object's surface that are otherwise difficult to take into account with existing reconstruction algorithms. Some initial steps are taken toward incorporating the physics of ocean waves in the stereo reconstruction process. The developed method is applied to empirical data of ocean waves collected at an off-shore oceanographic platform located off the coast of Crimea, Ukraine. An empirically-based physical model founded upon current ocean engineering standards is used to validate the results. Our findings suggest that this remote sensing observational method has a broad impact on off-shore engineering to enrich the understanding of sea states, enabling improved design of off-shore structures. The exploration of ways to incorporate dynamical properties, such as the wave equation, in the reconstruction process is discussed for future research.