Dans ce mémoire on s'intéresse à quelques problèmes de similarités ainsi qu'au spectre étendu d'un opérateur. Dans la première partie, on donne des critères de similarité à certaines classes d'isométries partielles et on obtient par exemple le résultat suivant. Soit T un opérateur sur H un espace de Hilbert. T est similaire à la somme directe d'un opérateur de Jordan et d'une isométrie si et seulement si T est à puissances bornées, T a une ascente finie et il existe un opérateur S E [appartenant à] B(H) à puissances bornées tel que Tn Sn Tn =Tn , pour tout n de N . Ces résultats peuvent être vus comme des résultats partiels pour un problème ouvert posé par Badea et Mbekhta en 2005. Dans la seconde partie, on obtient un critère de similarité conjointe à deux contractions qu'on applique pour obtenir des résultats de perturbation d'opérateurs conjointement similaires à des contractions. Le spectre étendu d'un opérateur est traité dans le dernier chapitre. Quelques liens avec d'autres spectres d'un opérateur sont proposés avant d'étudier le comportement du spectre étendu de certaines classes d'opérateurs. Enfin, on utilise le spectre étendu pour donner des critères d'hypercyclicité qu'on comparera à celui de Godefroy-Shapiro. / Ln this thesis, we study some similarity problems and the extended spectrum of an operator. ln the first part, we give criteria of similarity to some classes of partial isometries. For example, we obtain the following result. Let T be an operator on H an Hilbert space. T is similar to the direct sum of a Jordan operator and an isometry if and only if T is power-bounded, T has a finite as cent and there exists a power~bounded operator S E B(H) so that TnsnTn = Tn, for all n of No This results can be seen as partial results to an open problem of Badea and Mbekhta (2005) . ln the second part, we obtain a criterion of joint similarity to two contractions that we apply to have results of pertubation of operators jointly similar to contractions. The extended spectrum is the subject of the last part. Some of its links with other spectra of an operator are proposed before studying the behaviour of the extended spectrum of sorne classes of operators. Finally we use the extended spectrum to give criteria of hypercyclicity that we will compare to a criterion of Godefroy and Shapiro

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse a pour objectif d’étudier l’influence du caractère statique ou dynamique des problèmes arithmétiques à énoncés verbaux sur les procédures correctes de résolution, ainsi que sur la nature des erreurs. 772 enfants de Cours Moyen ont résolus des problèmes complexes de deux types, des problèmes de complément et de transformation, dont la particularité tient aux deux procédures permettant d’accéder à la solution : la procédure par différence-complément, consistant à faire les calculs pas à pas, et la procédure par différence-comparaison, consistant à comparer les deux ensembles et à déduire que la différence entre les touts est la même que celles entre les parties. L’hypothèse testée et confirmée par la première expérimentation est que la nature statique des problèmes de complément favorise une procédure par différence-complément, alors que la nature dynamique des problèmes de transformation favorise une procédure par différence-comparaison. Une seconde expérimentation confirme ces résultats, et montre que lorsque les enfants doivent deviner la question aux énoncés privés de leur question initiale, ils privilégient les questions sur le tout, notamment pour les problèmes de transformation. Les procédures erronées relevées dans les protocoles ont permis d’établir une typologie des erreurs. Des protocoles d’élèves de SEGPA ont été analysés à leur tour, afin de classer les erreurs relevées dans la typologie. Cette étude a révélé que la production de certaines erreurs semble être fonction du type de problème. Les résultats mettent en évidence l’influence des aspects statiques et dynamiques des énoncés sur les procédures de résolution qu’elles soient correctes ou erronées. / This thesis studies the arithmetic word problems dynamic or static nature influence on solving procedures, as well as on errors. 772 children from 4th and 5th grades solved complex problems of two different types, combination problems and change problems. Their specificity is they can be solved by two different procedures: the complementation procedure consisting in a step by step computation, and the matching procedure, consisting in the computation of the difference between homologous quantities. The first experiment results support the hypothesis that the combination problem static nature leads to a complementation procedure, whereas the change problem dynamic nature leads to a matching procedure. The second experiment results are consistent with the first experiment, in addition, they show that when children are asked to guess the question to a problem, they give their preference to a question related to the whole rather than to the part, especially for change problems. The errors extracted from the protocols enabled us to build a typology of errors. Protocols from pupils with learning difficulties and attending an adapted Junior High School class were studied, and their errors were classified in our typology. This study revealed that some types of errors occurred more often in one or the other type of problems. The results pointed out that the statement static or dynamic nature influences the solving procedures, either correct or erroneous.

Les premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variables / The first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible powers

Les problèmes d'allocation de ressources suscitent un intérêt croissant aussi bien en Économie qu'en Informatique. Ordinairement, ils sont résolus par des techniques centralisées, dans lesquelles une entité omnisciente détermine comment allouer les ressources de manière optimale. Cependant, ces approches font des hypothèses qui ne sont pas toujours réaliste. Or, il n'est souvent pas possible d'avoir une entité omnisciente. Certaines applications sont dynamiques et nécessitent une méthode de résolution adaptative qui puisse prendre en compte de nouvelles informations durant la résolution. Ces approches considèrent toujours que les communications entre les participants ne sont pas restreintes, ce qui n'est évidemment pas le cas dans la plupart des cas, comme dans les réseaux pair-à-pair par exemple où un pair ne peut communiquer qu'à un ensemble restreint du système.Dans cette thèse, nous nous focalisons sur les méthodes de ré-allocation distribuées, basée sur des systèmes multi-agents, qui transforment une allocation initiale par des séquences de transactions locales entre agents. Nous cherchons à concevoir des comportements d'agents menant un processus de négociation à une allocation socialement optimale. Cette allocation peut alors être vue comme un phénomène émergent. Nous voulons également identifier les paramètres favorisant l'efficacité des négociations ainsi que ceux qui la restreignent. Nous considérons différentes mesures de bien-être social et nous fournissons les comportements à implémenter pour négocier efficacement dans chaque cas. Nous proposons une méthode adaptative et ``anytime'' où n'importe quel type de réseau d'accointances peut être considéré. / Resource allocation problems have been widely studied according to various scenarios in the literature. They are usually solved by means of centralized techniques, where an omniscient entity determines how to optimally allocate resources. However, these solving methods are not well-adapted for applications where privacy is required. Moreover, several assumptions made are not always plausible, which may prevent their use in practice, especially in the context of agent societies. For instance, dynamic applications require adaptive solving processes, which can handle the evolution of initial data. Such techniques never consider restricted communication possibilities whereas many applications are based on. For instance, in peer-to-peer networks, a peer can only communicate to a small subset of the systems.In this thesis, we focus on distributed methods to solve resource allocation problems. Initial allocations evolves step by step thanks to local agent negotiations. We seek to provide agent behaviors leading negotiation processes to socially optimal allocations. In this work, resulting resource allocations can be viewed as emergent phenomena. We also identify parameters favoring the negotiation efficiency. We provide the agent behavior to implement when four different social welfare notions are considered. The original method proposed in thesis is adaptive, anytime and can handle any restriction on agent communication possibilities.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Titre de l'écran-titre (visionné le 2 octobre 2023) / Dans l'environnement commercial mondial concurrentiel d'aujourd'hui, les chaînes d'approvisionnement sont devenues plus complexes et plus sensibles en raison de leur dépendance vis-à-vis des demandes des clients en constante évolution. La création de valeur pour les clients ne réfère pas toujours à la qualité ou à la quantité du produit, elle réfère également à la disponibilité du produit à temps à l'endroit demandé. Tirer parti d'une chaîne d'approvisionnement pour fournir une valeur élevée aux clients ne peut être possible sans un transport organisé de manière efficace. Les professionnels considèrent qu'un service de livraison amélioré est crucial pour répondre à la demande des clients et augmenter la disponibilité des produits. En effet, un tel service est considéré comme un facteur clé dans la création de valeur pour les clients dans le monde des affaires. Le transport est l'un des éléments clés de la chaîne d'approvisionnement, car il joue un rôle essentiel dans le maintien d'une chaîne d'approvisionnement robuste et résiliente. De plus, un réseau de transport efficace aide les entreprises à réduire leurs coûts d'exploitation, à augmenter les niveaux de service et à obtenir un avantage sur la concurrence. Cela augmente l'intérêt de la recherche axée sur la gestion des opérations de transport et de la distribution. Tout au long de cette recherche, nous nous intéressons aux problèmes de cueillettes et de livraisons (ou Pickup and Delivery problems (PDPs)) qui sont une généralisation du problème classique de tournées de véhicules (Vehicle Routing Problem). En général, les PDPs impliquent la conception d'itinéraires à coût minimum pour un ensemble de véhicules afin de satisfaire toutes les requêtes de cueillettes et de livraisons. Les relations d'appariement et de précédence entre les lieux de cueillette et de livraison doivent être respectées. Plusieurs variantes de PDPs sont créées en ajoutant différents types de contraintes telles que les fenêtres de temps, la capacité des véhicules, etc. Cette classe de problèmes d'optimisation trouve des applications dans plusieurs contextes réels, tels que le transport de passagers porte-à-porte, les services de courrier urbain, le transport maritime et le transport de marchandises. Les PDPs ont été largement abordés dans la littérature. Cependant, les réseaux de distribution modernes avec des opérations de plus en plus complexes et des caractéristiques spéciales rendent les méthodes conventionnelles limitées et/ou inefficaces. Par conséquent, il est essentiel de développer de nouvelles méthodes et des solutions innovantes pour relever les nouveaux défis de l'industrie des transports. Dans ce projet de recherche, nous aborderons des PDPs réels issus de différents contextes tels que la livraison du dernier kilomètre et les services de santé. Tout d'abord, nous étudions un nouveau PDP dans le contexte de la livraison du dernier kilomètre connu sous le nom multi-pickup and delivery problem with time windows (MPDPTW), c'est un problème de cueillettes multiples et de livraison avec fenêtres de temps. Ce problème trouve de nombreuses applications concrètes, comme dans le domaine de l'économie du partage avec les services UBER EAT, où un client est autorisé à commander de la nourriture de différents restaurants; l'entreprise doit ensuite effectuer des cueillettes à différents endroits, avant de livrer tous les repas au client. Nous avons conçu de nouveaux algorithmes exacts pour le MPDPTW, fournissant les premières bornes inférieures et obtenant des solutions optimales pour les grandes instances. Dans ce travail, deux nouvelles formulations pour le problème sont introduites, une formulation à deux indices et la formulation des représentants asymétriques (asymmetric representatives formulation). Une transformation du MPDPTW en PDPTW est également proposée et testée. Les formulations mathématiques sont ensuite comparées pour trouver le meilleur algorithme pour le problème. Le deuxième problème abordé dans ce projet de recherche est une application liée au PDP dans le contexte de la logistique des soins de santé. Les activités de transport dans les hôpitaux sont de plus en plus complexes en raison de la grande variété de fournitures et d'équipements utilisés, tels que les articles jetables qui sont utilisés plus fréquemment. Cela se traduit par une augmentation du volume de transport dans les hôpitaux. Ces facteurs justifient le besoin de plus d'efficacité et de productivité des systèmes de transport dans les hôpitaux afin de répondre au niveau de service attendu par les patients sans augmenter les coûts. Un moyen efficace pour atteindre ces objectifs est l'automatisation des processus logistiques à l'aide de véhicules autoguidés (automated guided vehicles). Nous étudions le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands (FSRPS-AGV), c'est un problème de dimensionnement de flotte de véhicules autoguidés dans un environnement dynamique avec des contraintes de synchronization. Ce problème est dans le cadre d'une application réelle avec un partenaire de l'industrie de la santé à la ville de Québec. Nous décrivons le problème, nous introduisons une formulation mathématique et proposons une matheuristique pour le résoudre. Les tests sont menés sur des instances petites et grandes générées à partir de données réelles fournies par notre partenaire industriel. La troisième problématique étudiée dans ce projet est une application dans le contexte de la livraison de béton prêt à l'emploi (BPE). De nombreux problèmes opérationnels difficiles sont rencontrés par les fournisseurs du BPE, tels que la planification des opérations de production dans les usines de production, la planification des horaires quotidiens et hebdomadaires des chauffeurs, la planification des opérations de chargement, et la livraison du béton sur les chantiers de construction. Dans un environnement commercial caractérisé par une concurrence féroce, des solutions innovantes sont nécessaires pour résoudre ces problèmes afin d'atteindre l'exellence opérationnelle et de garantir un avantage concurrentiel. Bien que l'optimisation des opérations de livraison de béton soit essentielle pour les entreprises de béton, la satisfaction des chauffeurs et des clients ne doit pas être négligée. Nous étudions le personnel scheduling problem for ready-mixed concrete delivery (PSP-RMC) dans le contexte d'une application réelle avec une entreprise de béton au Québec, Canada. L'objectif est d'aider les fournisseurs de BPE à planifier des horaires de chauffeurs rentables et consistents (heures de début de travail similaires au cours de la semaine) sur un large horizon de planification sous des contraintes opérationnelles et réglementaires strictes. Des problèmes de PDPs sont résolus à l'intérieur même du PSP-RMC pour obtenir des routes pour les chauffeurs. Nous décrivons le problème et proposons un algorithme métaheuristique en deux étapes pour le résoudre. Les tests sont menées sur des instances artificielles et sur des instances générées à partir de données réelles fournies par notre partenaire industriel. Cette thèse est structurée comme suit. Une revue de la littérature sur les problèmes de cueillettes et de livraisons est présentée après un chapitre d'introduction. Le chapitre 2 est consacré au multi-pickup and delivery problem with time windows, et le chapitre 3 présente le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Le chapitre 4 présente le personnel scheduling problem for ready-mixed concrete delivery. La conclusion suit et résume les principales contributions de cette thèse dans le dernier chapitre. / In today's challenging and competitive global business environment, supply chains have become more complex and sensitive due to their dependence on constantly changing customer demands. Creating value for customers does not always refer to the quality or quantity of the product, it also refers to the availability of the product on time at the requested location. Leveraging a supply chain to provide high value to customers cannot be possible without effectively organized transportation. A better delivery service increases the availability of products to fulfill the demand of customers. Therefore, business practitioners consider it a very important factor in creating value for customers. Transportation is one of the key components in the entire supply chain, it has a critical role in maintaining a robust and resilient supply chain. Moreover, an efficient transportation network helps businesses to reduce operating costs, increase service levels, and gain a clear advantage over the competition. This increases research interest focused on transportation operations management. Throughout this research, we are interested in pickup and delivery problems (PDPs) which are a generalization of the classical vehicle routing problem (VRP). In general, the PDPs involve designing minimum-cost routes for a set of vehicles to satisfy all the pickup-delivery requests. Pairing and precedence relations of pickup and delivery locations must be respected. Variants of PDPs are found by adding side constraints such as time windows, vehicle capacity, etc. This class of optimization problems has applications in several real-life contexts, such as door-to-door passenger transportation, urban courier services, maritime shipping and freight transportation. PDPs have been widely addressed in the literature. However, modern delivery networks with more and more complex operations and special characteristics make conventional methods limited and/or inefficient. Hence, developing new innovative solution methods to tackle the new challenges of the transportation industry is crucial. In this research project, we tackle real-life PDPs arising from different contexts, such as last mile delivery and healthcare services. First, we study a new rich PDP in the context of last mile delivery known as the multi-pickup and delivery problem with time windows (MPDPTW). This problem finds many real-life applications, some of them are in the context of shared economy such as UBER EAT services, where a client is allowed to order food from different restaurants; the company must then perform all pickups at different places, before delivering all meals to the client location. We designed a new branch-and-cut algorithm for the MPDPTW providing the first dual bounds for the problem and obtaining tight solutions for large instances. In this work, two new formulations for the problem are introduced, a two-index formulation and the asymmetric representatives formulation (ARF). A transformation of the MPDPTW into a PDPTW is also proposed and tested. The mathematical formulations are then compared to define the best one for the problem. The second problem tackled in this research project is a PDP-related application in the context of healthcare logistics. Transportation activities in hospitals are now becoming more complex due to the wide variety of supplies and equipment used such as disposable items which are being used more frequently. This results in the expansion of the volume of transportation in hospitals. These factors justify the need for more efficiency and productivity of transportation systems in hospitals in order to meet the service level expected by patients without increasing costs. One of the most powerful ways of achieving these goals is the automation of logistics processes by using automated guided vehicles. We study the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands in the context of a real-life application with an industrial partner from the healthcare industry in Quebec City, Canada. We describe the problem, introduce a mathematical formulation for it, and propose a powerful matheuristic to solve it. Computational experiments are conducted on large and small instances generated based on real-data provided by our industrial partner. The third problem studied in this project is another application, this time in the context of ready-mixed concrete (RMC) delivery. Many challenging operational problems are faced by RMC suppliers such as scheduling production operations at production plants, creating daily and weekly drivers' schedules, loading operations scheduling, and delivering concrete to construction sites. In a business environment characterized by a fierce competition, innovative solutions are needed to tackle these problems in order to achieve operational efficiency and guarantee a competitive advantage. Although optimizing concrete delivery operations is essential for concrete companies, drivers' and customers' satisfaction should not be neglected. We study the personnel scheduling problem for RMC delivery in the context of a real-life application with a concrete company in Quebec, Canada. The goal is to help RMC suppliers build cost-effective and consistent (similar starting times over the week) drivers' schedules over a large planning horizon, under tight operational and regulatory constraints. The PSP-RMC embeds a PDP which is solved to create routes for drivers. We describe the problem and propose a two-stage metaheuristic algorithm to solve it. Computational experiments are conducted on artificial instances, and on instances generated based on real-data provided by our industrial partner. This thesis is structured as follows. A literature review on the pickup and delivery problems is presented after an introductory chapter. Chapter 2 is devoted to the multi-pickup and delivery problem with time windows, and Chapter 3 presents the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Chapter 4 presents the personnel scheduling problem for ready-mixed concrete delivery. The conclusion follows and summarizes the main contributions of this thesis in the last Chapter.