De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Les systèmes multiprocesseurs sur puce électronique (On-Chip Multiprocessor [OCM]) sont considérés comme les meilleures structures pour occuper l'espace disponible sur les circuits intégrés actuels. Dans nos travaux, nous nous intéressons à un modèle architectural, appelé architecture isométrique de systèmes multiprocesseurs sur puce, qui permet d'évaluer, de prédire et d'optimiser les systèmes OCM en misant sur une organisation efficace des nœuds (processeurs et mémoires), et à des méthodologies qui permettent d'utiliser efficacement ces architectures. Dans la première partie de la thèse, nous nous intéressons à la topologie du modèle et nous proposons une architecture qui permet d'utiliser efficacement et massivement les mémoires sur la puce. Les processeurs et les mémoires sont organisés selon une approche isométrique qui consiste à rapprocher les données des processus plutôt que d'optimiser les transferts entre les processeurs et les mémoires disposés de manière conventionnelle. L'architecture est un modèle maillé en trois dimensions. La disposition des unités sur ce modèle est inspirée de la structure cristalline du chlorure de sodium (NaCl), où chaque processeur peut accéder à six mémoires à la fois et où chaque mémoire peut communiquer avec autant de processeurs à la fois. Dans la deuxième partie de notre travail, nous nous intéressons à une méthodologie de décomposition où le nombre de nœuds du modèle est idéal et peut être déterminé à partir d'une spécification matricielle de l'application qui est traitée par le modèle proposé. Sachant que la performance d'un modèle dépend de la quantité de flot de données échangées entre ses unités, en l'occurrence leur nombre, et notre but étant de garantir une bonne performance de calcul en fonction de l'application traitée, nous proposons de trouver le nombre idéal de processeurs et de mémoires du système à construire. Aussi, considérons-nous la décomposition de la spécification du modèle à construire ou de l'application à traiter en fonction de l'équilibre de charge des unités. Nous proposons ainsi une approche de décomposition sur trois points : la transformation de la spécification ou de l'application en une matrice d'incidence dont les éléments sont les flots de données entre les processus et les données, une nouvelle méthodologie basée sur le problème de la formation des cellules (Cell Formation Problem [CFP]), et un équilibre de charge de processus dans les processeurs et de données dans les mémoires. Dans la troisième partie, toujours dans le souci de concevoir un système efficace et performant, nous nous intéressons à l'affectation des processeurs et des mémoires par une méthodologie en deux étapes. Dans un premier temps, nous affectons des unités aux nœuds du système, considéré ici comme un graphe non orienté, et dans un deuxième temps, nous affectons des valeurs aux arcs de ce graphe. Pour l'affectation, nous proposons une modélisation des applications décomposées en utilisant une approche matricielle et l'utilisation du problème d'affectation quadratique (Quadratic Assignment Problem [QAP]). Pour l'affectation de valeurs aux arcs, nous proposons une approche de perturbation graduelle, afin de chercher la meilleure combinaison du coût de l'affectation, ceci en respectant certains paramètres comme la température, la dissipation de chaleur, la consommation d'énergie et la surface occupée par la puce. Le but ultime de ce travail est de proposer aux architectes de systèmes multiprocesseurs sur puce une méthodologie non traditionnelle et un outil systématique et efficace d'aide à la conception dès la phase de la spécification fonctionnelle du système. / On-Chip Multiprocessor (OCM) systems are considered to be the best structures to occupy the abundant space available on today integrated circuits (IC). In our thesis, we are interested on an architectural model, called Isometric on-Chip Multiprocessor Architecture (ICMA), that optimizes the OCM systems by focusing on an effective organization of cores (processors and memories) and on methodologies that optimize the use of these architectures. In the first part of this work, we study the topology of ICMA and propose an architecture that enables efficient and massive use of on-chip memories. ICMA organizes processors and memories in an isometric structure with the objective to get processed data close to the processors that use them rather than to optimize transfers between processors and memories, arranged in a conventional manner. ICMA is a mesh model in three dimensions. The organization of our architecture is inspired by the crystal structure of sodium chloride (NaCl), where each processor can access six different memories and where each memory can communicate with six processors at once. In the second part of our work, we focus on a methodology of decomposition. This methodology is used to find the optimal number of nodes for a given application or specification. The approach we use is to transform an application or a specification into an incidence matrix, where the entries of this matrix are the interactions between processors and memories as entries. In other words, knowing that the performance of a model depends on the intensity of the data flow exchanged between its units, namely their number, we aim to guarantee a good computing performance by finding the optimal number of processors and memories that are suitable for the application computation. We also consider the load balancing of the units of ICMA during the specification phase of the design. Our proposed decomposition is on three points: the transformation of the specification or application into an incidence matrix, a new methodology based on the Cell Formation Problem (CFP), and load balancing processes in the processors and data in memories. In the third part, we focus on the allocation of processor and memory by a two-step methodology. Initially, we allocate units to the nodes of the system structure, considered here as an undirected graph, and subsequently we assign values to the arcs of this graph. For the assignment, we propose modeling of the decomposed application using a matrix approach and the Quadratic Assignment Problem (QAP). For the assignment of the values to the arcs, we propose an approach of gradual changes of these values in order to seek the best combination of cost allocation, this under certain metric constraints such as temperature, heat dissipation, power consumption and surface occupied by the chip. The ultimate goal of this work is to propose a methodology for non-traditional, systematic and effective decision support design tools for multiprocessor system architects, from the phase of functional specification.

Le problème inverse en électroencéphalographie (EEG) est la localisation de sources de courant dans le cerveau utilisant les potentiels de surface sur le cuir chevelu générés par ces sources. Une solution inverse implique typiquement de multiples calculs de potentiels de surface sur le cuir chevelu, soit le problème direct en EEG. Pour résoudre le problème direct, des modèles sont requis à la fois pour la configuration de source sous-jacente, soit le modèle de source, et pour les tissues environnants, soit le modèle de la tête. Cette thèse traite deux approches bien distinctes pour la résolution du problème direct et inverse en EEG en utilisant la méthode des éléments de frontières (BEM): l’approche conventionnelle et l’approche réciproque. L’approche conventionnelle pour le problème direct comporte le calcul des potentiels de surface en partant de sources de courant dipolaires. D’un autre côté, l’approche réciproque détermine d’abord le champ électrique aux sites des sources dipolaires quand les électrodes de surfaces sont utilisées pour injecter et retirer un courant unitaire. Le produit scalaire de ce champ électrique avec les sources dipolaires donne ensuite les potentiels de surface. L’approche réciproque promet un nombre d’avantages par rapport à l’approche conventionnelle dont la possibilité d’augmenter la précision des potentiels de surface et de réduire les exigences informatiques pour les solutions inverses. Dans cette thèse, les équations BEM pour les approches conventionnelle et réciproque sont développées en utilisant une formulation courante, la méthode des résidus pondérés. La réalisation numérique des deux approches pour le problème direct est décrite pour un seul modèle de source dipolaire. Un modèle de tête de trois sphères concentriques pour lequel des solutions analytiques sont disponibles est utilisé. Les potentiels de surfaces sont calculés aux centroïdes ou aux sommets des éléments de discrétisation BEM utilisés. La performance des approches conventionnelle et réciproque pour le problème direct est évaluée pour des dipôles radiaux et tangentiels d’excentricité variable et deux valeurs très différentes pour la conductivité du crâne. On détermine ensuite si les avantages potentiels de l’approche réciproquesuggérés par les simulations du problème direct peuvent êtres exploités pour donner des solutions inverses plus précises. Des solutions inverses à un seul dipôle sont obtenues en utilisant la minimisation par méthode du simplexe pour à la fois l’approche conventionnelle et réciproque, chacun avec des versions aux centroïdes et aux sommets. Encore une fois, les simulations numériques sont effectuées sur un modèle à trois sphères concentriques pour des dipôles radiaux et tangentiels d’excentricité variable. La précision des solutions inverses des deux approches est comparée pour les deux conductivités différentes du crâne, et leurs sensibilités relatives aux erreurs de conductivité du crâne et au bruit sont évaluées. Tandis que l’approche conventionnelle aux sommets donne les solutions directes les plus précises pour une conductivité du crâne supposément plus réaliste, les deux approches, conventionnelle et réciproque, produisent de grandes erreurs dans les potentiels du cuir chevelu pour des dipôles très excentriques. Les approches réciproques produisent le moins de variations en précision des solutions directes pour différentes valeurs de conductivité du crâne. En termes de solutions inverses pour un seul dipôle, les approches conventionnelle et réciproque sont de précision semblable. Les erreurs de localisation sont petites, même pour des dipôles très excentriques qui produisent des grandes erreurs dans les potentiels du cuir chevelu, à cause de la nature non linéaire des solutions inverses pour un dipôle. Les deux approches se sont démontrées également robustes aux erreurs de conductivité du crâne quand du bruit est présent. Finalement, un modèle plus réaliste de la tête est obtenu en utilisant des images par resonace magnétique (IRM) à partir desquelles les surfaces du cuir chevelu, du crâne et du cerveau/liquide céphalorachidien (LCR) sont extraites. Les deux approches sont validées sur ce type de modèle en utilisant des véritables potentiels évoqués somatosensoriels enregistrés à la suite de stimulation du nerf médian chez des sujets sains. La précision des solutions inverses pour les approches conventionnelle et réciproque et leurs variantes, en les comparant à des sites anatomiques connus sur IRM, est encore une fois évaluée pour les deux conductivités différentes du crâne. Leurs avantages et inconvénients incluant leurs exigences informatiques sont également évalués. Encore une fois, les approches conventionnelle et réciproque produisent des petites erreurs de position dipolaire. En effet, les erreurs de position pour des solutions inverses à un seul dipôle sont robustes de manière inhérente au manque de précision dans les solutions directes, mais dépendent de l’activité superposée d’autres sources neurales. Contrairement aux attentes, les approches réciproques n’améliorent pas la précision des positions dipolaires comparativement aux approches conventionnelles. Cependant, des exigences informatiques réduites en temps et en espace sont les avantages principaux des approches réciproques. Ce type de localisation est potentiellement utile dans la planification d’interventions neurochirurgicales, par exemple, chez des patients souffrant d’épilepsie focale réfractaire qui ont souvent déjà fait un EEG et IRM. / The inverse problem of electroencephalography (EEG) is the localization of current sources within the brain using surface potentials on the scalp generated by these sources. An inverse solution typically involves multiple calculations of scalp surface potentials, i.e., the EEG forward problem. To solve the forward problem, models are needed for both the underlying source configuration, the source model, and the surrounding tissues, the head model. This thesis treats two distinct approaches for the resolution of the EEG forward and inverse problems using the boundary-element method (BEM): the conventional approach and the reciprocal approach. The conventional approach to the forward problem entails calculating the surface potentials starting from source current dipoles. The reciprocal approach, on the other hand, first solves for the electric field at the source dipole locations when the surface electrodes are reciprocally energized with a unit current. A scalar product of this electric field with the source dipoles then yields the surface potentials. The reciprocal approach promises a number of advantages over the conventional approach, including the possibility of increased surface potential accuracy and decreased computational requirements for inverse solutions. In this thesis, the BEM equations for the conventional and reciprocal approaches are developed using a common weighted-residual formulation. The numerical implementation of both approaches to the forward problem is described for a single-dipole source model. A three-concentric-spheres head model is used for which analytic solutions are available. Scalp potentials are calculated at either the centroids or the vertices of the BEM discretization elements used. The performance of the conventional and reciprocal approaches to the forward problem is evaluated for radial and tangential dipoles of varying eccentricities and two widely different skull conductivities. We then determine whether the potential advantages of the reciprocal approach suggested by forward problem simulations can be exploited to yield more accurate inverse solutions. Single-dipole inverse solutions are obtained using simplex minimization for both the conventional and reciprocal approaches, each with centroid and vertex options. Again, numerical simulations are performed on a three-concentric-spheres model for radial and tangential dipoles of varying eccentricities. The inverse solution accuracy of both approaches is compared for the two different skull conductivities and their relative sensitivity to skull conductivity errors and noise is assessed. While the conventional vertex approach yields the most accurate forward solutions for a presumably more realistic skull conductivity value, both conventional and reciprocal approaches exhibit large errors in scalp potentials for highly eccentric dipoles. The reciprocal approaches produce the least variation in forward solution accuracy for different skull conductivity values. In terms of single-dipole inverse solutions, conventional and reciprocal approaches demonstrate comparable accuracy. Localization errors are low even for highly eccentric dipoles that produce large errors in scalp potentials on account of the nonlinear nature of the single-dipole inverse solution. Both approaches are also found to be equally robust to skull conductivity errors in the presence of noise. Finally, a more realistic head model is obtained using magnetic resonance imaging (MRI) from which the scalp, skull, and brain/cerebrospinal fluid (CSF) surfaces are extracted. The two approaches are validated on this type of model using actual somatosensory evoked potentials (SEPs) recorded following median nerve stimulation in healthy subjects. The inverse solution accuracy of the conventional and reciprocal approaches and their variants, when compared to known anatomical landmarks on MRI, is again evaluated for the two different skull conductivities. Their respective advantages and disadvantages including computational requirements are also assessed. Once again, conventional and reciprocal approaches produce similarly small dipole position errors. Indeed, position errors for single-dipole inverse solutions are inherently robust to inaccuracies in forward solutions, but dependent on the overlapping activity of other neural sources. Against expectations, the reciprocal approaches do not improve dipole position accuracy when compared to the conventional approaches. However, significantly smaller time and storage requirements are the principal advantages of the reciprocal approaches. This type of localization is potentially useful in the planning of neurosurgical interventions, for example, in patients with refractory focal epilepsy in whom EEG and MRI are often already performed.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Réalisé en cotutelle avec l'École normale supérieure de Cachan – Université Paris-Saclay / L'un des aspects fondamentaux des systèmes informatiques modernes, et en particulier des systèmes critiques, est la possibilité d'exécuter plusieurs processus, partageant des ressources communes, de façon simultanée. De par leur nature concurrentielle, le bon fonctionnement de ces systèmes n'est assuré que lorsque leurs comportements ne dépendent pas d'un ordre d'exécution prédéterminé. En raison de cette caractéristique, il est particulièrement difficile de s'assurer qu'un système concurrent ne possède pas de faille. Dans cette thèse, nous étudions la vérification formelle, une approche algorithmique qui vise à automatiser la vérification du bon fonctionnement de systèmes concurrents en procédant par une abstraction vers des modèles mathématiques. Nous considérons deux de ces modèles, les réseaux de Petri et les systèmes d'addition de vecteurs, et les problèmes de vérification qui leur sont associés. Nous montrons que le problème d'accessibilité pour les systèmes d'addition de vecteurs (avec états) à deux compteurs est PSPACE-complet, c'est-à-dire complet pour la classe des problèmes solubles à l'aide d'une quantité polynomiale de mémoire. Nous établissons ainsi la complexité calculatoire précise de ce problème, répondant à une question demeurée ouverte depuis plus de trente ans. Nous proposons une nouvelle approche au problème de couverture pour les réseaux de Petri, basée sur un algorithme arrière guidé par une caractérisation logique de l'accessibilité dans les réseaux de Petri continus. Cette approche nous a permis de mettre au point un nouvel algorithme qui s'avère particulièrement efficace en pratique, tel que démontré par notre implémentation logicielle nommée QCover. Nous complétons ces résultats par une étude des systèmes de transitions bien structurés qui constituent une abstraction générale des systèmes d'addition de vecteurs et des réseaux de Petri. Nous considérons le cas des systèmes de transitions bien structurés à branchement infini, une classe qui inclut les réseaux de Petri possédant des arcs pouvant consommer ou produire un nombre arbitraire de jetons. Nous développons des outils mathématiques facilitant l'étude de ces systèmes et nous délimitons les frontières au-delà desquelles la décidabilité des problèmes de terminaison, de finitude, de maintenabilité et de couverture est perdue. / One fundamental aspect of computer systems, and in particular of critical systems, is the ability to run simultaneously many processes sharing resources. Such concurrent systems only work correctly when their behaviours are independent of any execution ordering. For this reason, it is particularly difficult to ensure the correctness of concurrent systems. In this thesis, we study formal verification, an algorithmic approach to the verification of concurrent systems based on mathematical modeling. We consider two of the most prominent models, Petri nets and vector addition systems, and their usual verification problems considered in the literature. We show that the reachability problem for vector addition systems (with states) restricted to two counters is PSPACE-complete, that is, it is complete for the class of problems solvable with a polynomial amount of memory. Hence, we establish the precise computational complexity of this problem, left open for more than thirty years. We develop a new approach to the coverability problem for Petri nets which is primarily based on applying forward coverability in continuous Petri nets as a pruning criterion inside a backward coverability framework. We demonstrate the effectiveness of our approach by implementing it in a tool named QCover. We complement these results with a study of well-structured transition systems which form a general abstraction of vector addition systems and Petri nets. We consider infinitely branching well-structured transition systems, a class that includes Petri nets with special transitions that may consume or produce arbitrarily many tokens. We develop mathematical tools in order to study these systems and we delineate the decidability frontier for the termination, boundedness, maintainability and coverability problems.

Cette thèse s'inscrit dans l'étude des modèles asymptotiques aux équations des ondes de surface dans le régime modulationnel. Le problème des ondes de surface consiste à décrire le mouvement - sous l'influence de la gravitation et éventuellement de tension de surface - d'un fluide dans un domaine délimité par la surface libre du fluide et par un fond fixe. Dans l'étude de ce problème, on s'intéresse en particulier aux ondes se propageant à la surface du fluide.Dans le régime modulationnel, on considère l'évolution des ondes de surface sous forme de paquets d'ondes de faible amplitude se propageant dans une direction. Il est bien connu que la motion de l'enveloppe du paquet d'onde sur une échelle de temps d'ordre t = O(1/ϵ²), où ϵ est un petit paramètre désignant l'amplitude, est décrite approximativement par des systèmes d'équations appelés systèmes de Benney-Roskes (BR) / Davey-Stewartson (DS). Ces systèmes sont donnés par une équation de type Schrödinger cubique couplée à une équation d'ondes. L'approximation classique de BR / DS est bien établie et a été largement étudiée au cours des dernières décennies. Récemment, David Lannes a introduit une version à "dispersion exacte" de ces systèmes. Contrairement aux équations de BR / DS standard, les systèmes à dispersion exacte préservent la relation de dispersion des équations des ondes de surface. On devrait obtenir ainsi une description plus riche du vrai comportement dynamique des ondes de surface que dans le cas de l'approximation classique.Le systèmes de BR / DS à dispersion exacte sont étudiés dans cette thèse. La première partie est consacrée à la déduction formelle des systèmes de BR / DS en tant que modèles asymptotiques aux équations des ondes de surface. Nous donnons en outre un résultat sur la consistance de cette approximation.Ensuite, nous étudions le problème de Cauchy pour le système de BR à dispersion exacte. En fait, afin de justifier la consistance de l'approximation de BR avec les équations exactes, on doit prouver que ce système est bien posé (en espace de Sobolev) sur une échelle de temps d'ordre O(1/ϵ). Ceci est un problème ouvert même dans le cas classique, du moins pour le système de dimension 1 + 2. De même, nous ne pouvons pas démontrer l'existence de solutions en temps long pour le système de BR à dispersion exacte, mais nous obtenons un théorème d'existence locale (t = O(1)) à condition que la tension de surface soit assez forte. Si nous nous restreignons au système de dimension 1+1, nous pouvons enlever la contrainte sur la tension de surface. L'idée de la preuve d'existence locale, qui est inspirée par un travail de Schochet-Weinstein, est d'écrire le système de BR comme un système symétrique hyperbolique quasi-linéaire perturbé par un terme dispersif ne contribuant pas à l'énergie du système. Ainsi, nous pouvons appliquer les méthodes standard de résolution des systèmes hyperboliques.En modifiant le terme non-linéaire du système de BR de dimension 1+1 sans changer l'ordre de consistance, nous obtenons un système qui est bien posé sur l'échelle de temps appropriée O(1/ϵ). Cependant, cette démarche ne peut pas être généralisée au cas de dimension 1+2.Dans le dernier chapitre de cette thèse, nous donnons quelques résultats sur les systèmes de Davey-Stewartson à dispersion exacte. Pour les systèmes de DS, il est suffisant de démontrer qu'ils sont bien posés localement afin de justifier leur consistance avec les équations des ondes de surface. La théorie d'existence de solutions est assez complète pour le système de DS classique. Dans le cas de dispersion exacte cependant, les équations paraissent mal posées généralement, si bien que l'existence locale ne peut être démontrée pour l'instant que pour quelques cas particuliers simples. / This thesis is concerned with asymptotic models to the water wave equations in the modulational regime. The water wave equations describe the motion - under the influence of gravity and possibly surface tension - of an inviscid fluid in a domain which is bounded by a fixed bottom from below and the free surface of the fluid from above. In the study of the water wave problem, one is in particular interested by waves propagating on the surface of the fluid.In the modulational regime, one considers the evolution of surface waves under the form of small amplitude wave packets traveling in one direction. It is well known that the evolution of the wave packet envelope on the long time scale t = O(1/ϵ²), where ϵ is a small parameter denoting the amplitude of the wave, is approximately governed by a set of equations known as the Benney-Roskes (BR) / Davey-Stewartson (DS) systems. These systems are essentially given by a cubic Schrödinger-type equation coupled to a wave equation. The classical BR / DS approximation is well established and has been largely studied in the past decades. Recently, David Lannes has introduced a "full dispersion" version of these systems. In contrast to the standard BR / DS equations, the full dispersion systems preserve the linear dispersion relation of the full water wave equations, and should therefore give a richer description of the original wave dynamics than the classical approximation.The full dispersion BR / DS systems are studied in this thesis. In the first part, we formally derive the full dispersion BR / DS approximation from the water wave equations both in the case of zero and positive surface tension. The formal derivation is completed by a consistency result.We then study well-posedness in Sobolev space of the full dispersion BR system. In order to justify consistency of the BR approximation with the full water wave equations, one needs to show that the BR system is well posed on a time scale of order O(1/ϵ). This is an open problem even in the classical case, at least for the 1 + 2 dimensional system. We also do not obtain well-posedness on the long time scale for the full dispersion BR system, but we can show that it is locally well-posed in the case of sufficiently strong surface tension, and additionally in the zero surface tension case if we restrict ourselves to the 1+1 dimensional system. The proof is inspired by a paper of Schochet-Weinstein, and is based on writing the full dispersion BR system as a quasilinear symmetric hyperbolic system with dispersive perturbation, where the dispersive terms do not contribute to the energy. We can therefore apply classical solution methods for hyperbolic systems.By modifying the nonlinear part of the 1+1 dimensional full dispersion BR system without changing consistency, we obtain a system that is well-posed on the appropriate O(1/ϵ) time scale. This approach however does not generalize to the 1+2 dimensional case.In the last chapter of the thesis, we give some results on the full dispersion DS systems, which are obtained as special limits of the full dispersion BR system. For these systems, it is sufficient to prove local well-posedness in order to show consistency with the water wave equations. For the standard DS systems, local well-posedness theory is quite complete. For the full dispersion systems, the analysis is complicated by some nonlocal operators and the equations seem to be generally ill-posed. There are however some simple cases where local well-posedness can be shown. We also discuss some modifications of the full dispersion DS system that might allow to solve it for a larger range of parameters.

Cette thèse est consacrée à l’étude des monoïdes plaxiques par une nouvelle approche utilisant des méthodes issues de la réécriture. Ces méthodes sont appliquées à des présentations de monoïdes plaxiques décrites en termes de tableaux de Young, de bases cristallines de Kashiwara et de modèle des chemins de Littelmann. On étudie le problème des syzygies pour la présentation de Knuth des monoïdes plaxiques. En utilisant la procédure de complétion homotopique basée sur les procédures de complétion de Squier et de Knuth–Bendix, on construit des présentations cohérentes de monoïdes plaxiques de type A. Une telle présentation cohérente étend la notion de présentation convergente d’un monoïde par une famille génératrice de syzygies, décrivant toutes les relations entre les relations. On explicite une présentation cohérente finie des monoïdes plaxiques de type A avec les générateurs colonnes. Cependant, cette présentation n’est pas minimale dans le sens que plusieurs de ses générateurs sont superflus. En appliquant la procédure de réduction homotopique, on réduit cette présentation en une présentation cohérente finie qui étend la présentation de Knuth, donnantainsi toutes les syzygies des relations de Knuth. D’une manière plus générale, on étudie des présentations de monoïdes plaxiques généralisés du point de vue de la réécriture. On construit des présentations convergentes finies de ces monoïdes en utilisant les chemins de Littelmann. De plus, on étudie ces présentations pour le type C en termes de bases cristallines de Kashiwara. En introduisant les générateurs colonnes admissibles, on construit une présentation convergente finie du monoïde plaxique de type C avec des relations explicites. Cette approche nous permettrait d’étudier le problème des syzygies des présentations de monoïdes plaxiques en tout type / This thesis focuses on the study of plactic monoids by a new approach using methods issued from rewriting theory. These methods are applied on presentations of plactic monoids given in terms of Young tableaux, Kashiwara’s crystal bases and Littelmann path model. We study the syzygy problem for the Knuth presentation of the plactic monoids. Using the homotopical completion procedure that extends Squier’s and Knuth–Bendix’s completions procedure, we construct coherent presentations of plactic monoids of type A. Such a coherent presentation extends the notion of a presentation of a monoid by a family of generating syzygies, taking into account all the relations among the relations. We make explicit a finite coherent presentation of plactic monoids of type A with the column generators. However, this presentation is not minimal in the sense that many of its generators are superfluous. After applying the homotopical reduction procedure on this presentation, we reduce it to a finite coherent one that extends the Knuth presentation, giving then all the syzygies of the Knuth relations. More generally, we deal with presentations of plactic monoids of any type from the rewriting theory perspective. We construct finite convergent presentations for these monoids in a general way using Littelmann paths. Moreover, we study the latter presentations in terms of Kashiwara’s crystal graphs for type C. By introducing the admissible column generators, we obtain a finite convergent presentation of the plactic monoid of type C with explicit relations. This approach should allow us to study the syzygy problem for the presentations of plactic monoids for any type

La caractérisation d’objets enfouis à partir de mesures d’ondes diffractées est un problème présent dans de nombreuses applications comme l’exploration géophysique, le contrôle non-destructif, l’imagerie médicale, etc. Elle peut être obtenue numériquement par la résolution d’un problème inverse. Néanmoins, c’est un problème non linéaire et mal posé, ce qui rend la tâche difficile. Une reconstruction précise nécessite un choix judicieux de plusieurs paramètres très différents, dépendant des données de la méthode numérique d’optimisation choisie.La contribution principale de cette thèse est une étude de la reconstruction complète d’obstacles élastiques immergés à partir de mesures du champ lointain diffracté. Les paramètres à reconstruire sont la frontière, les coefficients de Lamé, la densité et la position de l’obstacle. On établit tout d’abord des résultats d’existence et d’unicité pour un problème aux limites généralisé englobant le problème direct d’élasto-acoustique. On analyse la sensibilité du champ diffracté par rapport aux différents paramètres du solide, ce qui nous conduit à caractériser les dérivées partielles de Fréchet comme des solutions du problème direct avec des seconds membres modifiés. Les dérivées sont calculées numériquement grâce à la méthode de Galerkine discontinue avec pénalité intérieure et le code est validé par des comparaisons avec des solutions analytiques. Ensuite, deux méthodologies sont introduites pour résoudre le problème inverse. Toutes deux reposent sur une méthode itérative de type Newton généralisée et la première consiste à retrouver les paramètres de nature différente indépendamment, alors que la seconde reconstruit tous les paramètre en même temps. À cause du comportement différent des paramètres, on réalise des tests de sensibilité pour évaluer l’influence de ces paramètres sur les mesures. On conclut que les paramètres matériels ont une influence plus faible sur les mesures que les paramètres de forme et, ainsi, qu’une stratégie efficace pour retrouver des paramètres de nature distincte doit prendre en compte ces différents niveaux de sensibilité. On a effectué de nombreuses expériences à différents niveaux de bruit, avec des données partielles ou complètes pour retrouver certains paramètres, par exemple les coefficients de Lamé et les paramètres de forme, la densité, les paramètres de forme et la localisation. Cet ensemble de tests contribue à la mise en place d’une stratégie pour la reconstruction complète des conditions plus proches de la réalité. Dans la dernière partie de la thèse, on étend ces résultats à des matériaux plus complexes, en particulier élastiques anisotropes. / The characterization of hidden objects from scattered wave measurements arises in many applications such as geophysical exploration, non destructive testing, medical imaging, etc. It can be achieved numerically by solving an Inverse Problem. However, this is a nonlinear and ill-posed problem, thus a difficult task. A successful reconstruction requires careful selection of very different parameters depending on the data and the chosen optimization numerical method.The main contribution of this thesis is an investigation of the full reconstruction of immersed elastic scatterers from far-field pattern measurements. The sought-after parameters are the boundary, the Lamé coefficients, the density and the location of the obstacle. First, existence and uniqueness results of a generalized Boundary Value Problem including the direct elasto-acoustic problem are established. The sensitivity of the scattered field with respect to the different parametersdescribing the solid is analyzed and we end up with the characterization of the corresponding partial Fréchet derivatives as solutions to the direct problem with modified right-hand sides. These Fréchet derivatives are computed numerically thanks to the Interior Penalty Discontinuous Galerkin method and the code is validated thanks to comparison with analytical solutions. Then, two solution methodologies are introduced for solving the inverse problem. Both are based on an iterative regularized Newton-type methodology and the first one consists in retrieving the parameters of different nature independently, while the second one reconstructs all parameters together. Due to the different behavior of the parameters, sensitivity tests are performed to assess the impact of the parameters on the measurements. We conclude that material parameters have a weaker influence on the measurements than shape parameters, and therefore, a successful strategy to retrieve parameters of distinct nature should take into account these different levels of sensitivity. Various experiments at different noise levels and with full or limited aperture data are carried out to retrieve some of the physical properties, e.g. Lamé coefficients with shape parameters, density with shape parameters a, density, shape and location. This set of tests contributes to a final strategy for the full reconstruction and in more realistic conditions. In the final part of the thesis, we extend the results to more complex material parameters, in particular anisotropic elastic.

Dans cette thèse, nous nous intéressons à résoudre certains problèmes inverses pour des équations différentielles aux dérivées fractionnaires. Un problème inverse est généralement mal posé. Un problème mal posé est un problème qui ne répond pas à l’un des trois critères de Hadamard pour être bien posé, c’est-à-dire, soit l’existence, l’unicité ou une dépendance continue aux données n'est plus vraie, à savoir, des petits changements dans les données de mesure entraînent des changements indéfiniment importants dans la solution. La plupart des difficultés à résoudre des problèmes mal posés sont causées par l’instabilité de la solution. D’autre part, les équations différentielles fractionnaires deviennent un outil important dans la modélisation de nombreux problèmes de la vie réelle et il y a eu donc un intérêt croissant pour l’étude des problèmes inverses avec des équations différentielles fractionnaires. Le calcul fractionnaire est une branche des mathématiques qui fait référence à l’extension du concept de dérivation classique à la dérivation d’ordre non entier. Calculer une dérivée fractionnaire à un certain moment exige tous les processus précédents avec des propriétés de mémoire. C’est l’avantage principal du calcul fractionnaire d’expliquer les processus associés aux systèmes physiques complexes qui ont une mémoire à long terme et / ou des interactions spatiales à longue distance. De plus, les équations différentielles fractionnaires peuvent nous aider à réduire les erreurs découlant de paramètres négligés dans la modélisation des phénomènes physiques. / In this thesis, we are interested in solving some inverse problems for fractional differential equations. An inverse problem is usually ill-posed. The concept of an ill-posed problem is not new. While there is no universal formal definition for inverse problems, Hadamard [1923] defined a problem as being ill-posed if it violates the criteria of a well-posed problem, that is, either existence, uniqueness or continuous dependence on data is no longer true, i.e., arbitrarily small changes in the measurement data lead to indefinitely large changes in the solution. Most difficulties in solving ill-posed problems are caused by solution instability. Inverse problems come into various types, for example, inverse initial problems where initial data are unknown and inverse source problems where the source term is unknown. These unknown terms are to be determined using extra boundary data. Fractional differential equations, on the other hand, become an important tool in modeling many real-life problems and hence there has been growing interest in studying inverse problems of time fractional differential equations. The Non-Integer Order Calculus, traditionally known as Fractional Calculus is the branch of mathematics that tries to interpolate the classical derivatives and integrals and generalizes them for any orders, not necessarily integer order. The advantages of fractional derivatives are that they have a greater degree of flexibility in the model and provide an excellent instrument for the description of the reality. This is because of the fact that the realistic modeling of a physical phenomenon does not depend only on the instant time, but also on the history of the previous time, i.e., calculating timefractional derivative at some time requires all the previous processes with memory and hereditary properties.

Cette thèse porte sur une méthode cartésienne parallèle pour résoudre des problèmes elliptiques avec interfaces complexes et sur son application aux problèmes elliptiques en domaine irrégulier dans le cadre d'un modèle de croissance tumorale. La méthode est basée sur un schéma aux différences fi nies et sa précision est d'ordre deux sur tout le domaine. L'originalité de la méthode consiste en l'utilisation d'inconnues additionnelles situées sur l'interface et qui permettent d'exprimer les conditions de transmission à l'interface. La méthode est décrite et les détails sur la parallélisation, réalisée avec la bibliothèque PETSc, sont donnés. La méthode est validée et les résultats sont comparés avec ceux d'autres méthodes du même type disponibles dans la littérature. Une étude numérique de la méthode parallélisée est fournie. La méthode est appliquée aux problèmes elliptiques dans un domaine irrégulier apparaissant dans un modèle continue et tridimensionnel de croissance tumorale, le modèle à deux espèces du type Darcy . L'approche utilisée dans cette application est basée sur la pénalisation des conditions de transmission a l'interface, afin de imposer des conditions de Neumann homogènes sur le bord d'un domaine irrégulier. Les simulations du modèle sont fournies et montrent la capacité de la méthode à imposer une bonne approximation de conditions au bord considérées.