Dissertations / Theses on the topic 'Paramétrée'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Paramétrée.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
Chamseddine, Najla. "Analyse quantitative paramétrée d'automates temporisés probabilistes." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2009. http://tel.archives-ouvertes.fr/tel-00626062.
Fradin, Julien. "Graphes complexes en biologie : problèmes, algorithmes et évaluations." Thesis, Nantes, 2018. http://www.theses.fr/2018NANT4093/document.
Ln order to better understand how a biological system works, it is necessary to study the interactions between the different entities that compose it. To this aim, these biological interactions can be modelled in the form of graphs. ln some of these graphs, the vertices are colored in order to provide additional information on the entity which is associated with them. ln this context, a common subproblem consists in searching for a subgraph of interest, called a motif, in these graphs. ln the first part of this manuscript, we present a state of the art from an algorithmical point of view of the GRAPH MOTIF problem, which consists in searching for so-called functional motifs in vertex-colored graphs. The modeling of biological systems in graphs form can also be applied in mass spectrometry. Thus, we introduce the MAXIMUM COLORFUL ARBORESCENCE problem (MCA) in order to de novo determine the molecular formula of unknown metabolites. ln the second part of this manuscript, we carry out an algorithmic study of the MCA problem. While MCA is algorithmically difficult to solve even in very constrained graph classes, our modeling allows us to obtain new approximation algorithms in these same classes, as well as to determine a new graph class in which MCA is solved in polynomial time. Parameterized complexity results for this problem are also shown, which are then compared to those in the literature on instances from biological data
Dailler, Sylvain. "Extension paramétrée de compilateur certifié pour la programmation parallèle." Thesis, Orléans, 2015. http://www.theses.fr/2015ORLE2071/document.
Nowadays, we are using an increasing number of computer applications. Errors in critical applications (medicine, transport, . . .) may carry serious health or financial issues. Avoiding errors in programs is a challenge and may be achieved by deductive verification. Deductive verification applies to program written in a high-level languages, which are transformed into machine language by compilers. These compilers must be correct to ensure the nonpropagation of errors to machine code. Since 2005, multicore processors have spread in all electronic devices. So, these architectures need adapted compilers and proofs of correctness. Our work is the modular extension of a verified compiler for parallel languages targeting multicore architectures. Specifications of these languages (and their operational semantics) needed at all levels of the compiler and proofs of correctness of this compiler are parameterized by modules specifying elements of parallelism such as a relaxed memory model and notions of synchronization and scheduling between threads. This work is the first step in the conception of a certified compiler for high-level parallel languages such as algorithmic skeletons
Bonnet, Edouard. "Résultats Positifs et Négatifs en Approximation et Complexité Paramétrée." Thesis, Paris 9, 2014. http://www.theses.fr/2014PA090040/document.
Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah
Chopin, Morgan. "Problèmes d'optimisation avec propagation dans les graphes : complexité paramétrée et approximation." Phd thesis, Université Paris Dauphine - Paris IX, 2013. http://tel.archives-ouvertes.fr/tel-00933769.
Rinaudo, Philippe. "Algorithmique de l'alignement structure-séquence d'ARN : une approche générale et paramétrée." Phd thesis, Université Paris Sud - Paris XI, 2012. http://tel.archives-ouvertes.fr/tel-00847745.
Morançay, Lionel. "Représentation paramétrée et modélisation des systèmes physiques pour la conception optimale." Compiègne, 1993. http://www.theses.fr/1993COMP582S.
Duvillié, Guillerme. "Approximation, complexité paramétrée et stratégies de résolution de problèmes d'affectation multidimensionnelle." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT321/document.
In this thesis, we focused in the Wafer-to-Wafer integration problems. These problems come from IC manufacturing. During the production of three-dimensional processors, dies have to be superimposed. Until recent, the dies were engraved on a silicon disk called wafer, then were cut, tested and sorted to suppress faulty dies and lastly superimposed one to each other.However superimposing wafers instead of dies presents several technical and financial advantages. Since faulty dies can only be dismissed when cutting the wafer, superimpose two wafers can lead to superimpose a faulty die with a viable one. In this case, the resulting stack of dies is considered as faulty. It follows that a bad assignment between the wafers can lead to a disastrous yield.In order to minimize the number of faulty dies stacks, a "failure map" of each wafer is generated during a test phase. This map gives location of the faulty dies on the wafers. The objective is then to take advantage of this map to define an assignment of the wafers to each other in order to match as many failures as possible.This problem can be modelized with Multidimensional Assignment problems. Each wafer can be seen as a vector with as many dimensions as the number of dies engraved on it. A coordinate set to zero marks a faulty die while a coordinate set to one indicates a viable one. Each seat of wafers is represented by a set of vector. Formally, an instance of a Wafer-to-Wafer integration problem is represented by m sets of n p-dimensional vectors. The objective is then to partition the vectors into n disjoint m-tuples, each tuple containing exactly one vector per set. An m-tuple represents a stack of wafers. Every m-tuple can be represented by a p-dimensional vector. Each coordinate is computed by performing the bitwise AND between the corresponding coordinates of the vectors that compose the m-tuple. In other words, a coordinate of the representative vector is equal to one if and only if this coordinate is equal to one in every vector composing the tuple. It follows that a dies stack is viable if and only if all the dies composing the stack are viable. The objective is then to maximize the overall number of ones of to minimize the overall number of zeros.The first part of the thesis is a theoretical one. We study the complexity of the considered versions of the problem with regards to natural parameters such as m, n, p or the number of zeros per vector. We show that these problems can encode more classical problems such as Maximum Clique, Minimum Vertex Cover or k-Dimensional Matching. This leads to several negative results from computational complexity, approximability or even parameterized complexity point of view. We also provide several positive results for some specific cases of the problem.In a second part, we focus on the practical solving of the problem. We provide and compare several Integer Linear Programming formulations. We also focus on performances of some approximation algorithms that we detailed in the theoretical part
Efremov, Semen. "Croissance paramétrée et bruit procédural pour la conception de métamatériaux mécaniques." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0046.
With constant development of technologies, computational and manufacturing capabilities increase, production methods evolve, and new techniques appear. As a result, the need for new materials with tailored, optimized properties for different applications arises. Periodic composites with tailored microstructure topology, called cellular metamaterials are extensively studied in this context. These structures are known for their remarkable mechanical properties, including high strength, lower weight, and increased energy absorption. The use of these materials allows to achieve improved physical properties or specific functional features and provides economical gain and ecological benefit.This thesis is dedicated to the development and analysis of methods for computer-aided design of materials with tailored mechanical properties. The mechanical metamaterials were studied through two different approaches: modelling periodic structures through a parameterized growth model and procedural noise functions. To tackle the challenge of obtaining near-regular microstructures with progressively varying properties, I proposed and studied a cellular material spawned by a growth process. The growth is parameterized by a 3D star-shaped set at each lattice point, defining the geometry that will appear around it. Individual tiles may be computed and used in a periodic lattice, or a global structure may be produced under spatial gradations, changing the parametric star-shaped set at each lattice location. Beyond free spatial gradation, an important advantage of this approach is that elastic symmetries can be intrinsically enforced. It is shown in this work how shared symmetries between the lattice and the star-shaped set directly translate into symmetries of the periodic structures' elastic response. Thus, the approach enables restricting the symmetry of the elastic responses -- monoclinic, orthorhombic, trigonal, and so on -- while freely exploring a wide space of possible geometries and topologies. I provide a comprehensive study of the space of symmetries and broad combinations of growth process parameters. Furthermore, I demonstrate through numerical and experimental results the expected responses triggered by the obtained structures.The second contribution of this thesis is a novel procedural pattern synthesis technique. This approach exhibits desirable properties for modeling highly contrasted patterns, that are well suited to produce surface and microstructure details. This approach defines a stochastic smooth phase field –- a phasor noise –- that is then fed into a periodic function (e.g. a sine wave), producing an oscillating field with prescribed main frequencies and preserved contrast oscillations. I present in this thesis a mathematical model, that builds upon a reformulation of Gabor noise in terms of a phasor field that affords for a clear separation between local intensity and phase. In particular, I study the behavior of phasor noise in terms of its power spectrum. Hence, a comparative theoretical study of phasor noise was performed in order to gain understanding of links between its properties and parameters
Andami, Ovono Armel. "Equations de diffusion paramétrée par la portée des interactions à longue distance." Phd thesis, Université de Poitiers, 2009. http://tel.archives-ouvertes.fr/tel-00365445.
Andami, Ovono Armel. "Équations de diffusion paramétrée par la portée des interactions à longue distance." Poitiers, 2009. http://theses.edel.univ-poitiers.fr/theses/2009/Andami-Ovono-Armel/2009-Andami-Ovono-Armel-These.pdf.
This thesis is devoted to a quasilinear parabolic equation in which the diffusion is defined by the length of different non local interactions. As regards stationary problem, having shown the results of existence, uniqueness and continuity. We introduce a general criterion of inversibility later depending on parameter, this very important criterion is going to allow us in example of application to find well known results when parameter will be equal to the diameter of domain. We give then a fundamental result of comparison of solutions in the case of radial symmetrical solutions and a general implementation of count of solutions. Finally we give some numerical applications using a method of fixed point and Newton’s method to illustrate these results. As regards parabolic problem having shown existence of global attractor associated to our problem, we show an estimate L∞ of solution according to estimate Lq, q >1 by using Moser’s iteration
Zimmermann, Jakub. "Détection d'intrusions paramétrée par la politique par contrôle de flux de références." Rennes 1, 2003. http://www.theses.fr/2003REN10155.
Labbé, Sébastien. "Réduction paramétrée de spécifications formées d'automates communicants : algorithmes polynomiaux pour la réduction de modèles." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2007. http://tel.archives-ouvertes.fr/tel-00180174.
L'idée que nous proposons consiste à contourner ce phénomène en appliquant des techniques de réduction paramétrée, pouvant être désignées sous le terme anglo-saxon "slicing'', en amont d'une analyse complexe. Cette analyse peut ainsi être effectuée a posteriori sur une spécification réduite, donc potentiellement moins sujette à l'explosion combinatoire. Notre méthode de réduction paramétrée est basée sur des relations de dépendances dans la spécification sous analyse, et est fondée principalement sur les travaux effectués par les communautés de la compilation et du slicing de programmes. Dans cette thèse nous établissons un cadre théorique pour les analyses statiques de spécifications formées d'automates communicants, dans lequel nous définissons formellement les relations de dépendances mentionnées ci-dessus, ainsi que le concept de "tranche" de spécification par rapport à un "critère" de réduction. Ensuite, nous décrivons et démontrons les algorithmes efficaces que nous avons mis au point pour calculer les relations de dépendances et les tranches de spécifications, et enfin nous décrivons notre mise en oeuvre de ces algorithmes dans l'outil "Carver", pour la réduction paramétrée de spécifications formées d'automates communicants.
Watrigant, Rémi. "Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20100/document.
The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms
Magos, Rivera Miguel. "Sur la modélisation des systèmes dynamiques à topologie variable : une formulation Hamiltonienne à ports paramétrée." Lyon 1, 2005. http://www.theses.fr/2005LYO10016.
Sebeloue, Martine. "Modélisation comportementale paramétrée de fonctions analogiques pour la simulation des systèmes de transmission, en technologie bipolaire." Toulouse, INPT, 2000. http://www.theses.fr/2000INPT014H.
Fournier, Paulin. "Parameterized verification of networks of many identical processesVérification paramétrée de réseaux composés d'une multitude de processus identiques." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S170/document.
This thesis deals with formal verification of distributed systems. Model checking is a technique for verifying that the model of a system under study fulfills a given property. This PhD investigates the parameterized verification of networks composed of many identical processes for which the number of processes is the parameter. Considering networks of probabilistic timed protocols, we show that the parameterized reachability and synchronization problems are undecidable when the communication topology is a clique. However, assuming probabilistic creation and deletion of processes, the problems become decidable. Regarding selective networks, where the messages only reach a subset of the components, we show decidability of the parameterized reachability problem thanks to reduction to a new model of distributed two-player games for which we prove decidability in coNP of the game problem. Finally, we consider local strategies that enforce all processes to resolve the non-determinism only according to their own local knowledge. Under this assumption of local strategy, we were able to show that the parameterized reachability and synchronization problems are NP-complete
Potier, Jean-Claude. "Contribution à la notion de programmation par démonstration : conception sur exemple, mise au point et génération de programmes portables de géométrie paramétrée dans le système EBP." Poitiers, 1995. http://www.theses.fr/1995POIT2299.
Daligault, Jean. "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00804206.
Toubiana, meyer Rivka. "Contribution à l’évaluation objective du confort en posture assise par le développement d’un modèle biomécanique paramétrable du tronc." Thesis, Paris, ENSAM, 2016. http://www.theses.fr/2016ENAM0016/document.
The comfort of motor vehicles is a strategic and economic element in their developments. One of the future challenges is the individual comfort, which can only be achieved with original digital models. Indeed, we should be able to take into account the diversity of anthropometric occupants in the worldwide. In this context, Faurecia, automotive seating manufacturer and leader in this field, wishes to optimize its design process through digital tools to analyze comfort in the early design steps. However, at present, no digital tool is available to validate the comfort of the backrest. The purpose of this study is to develop a numerical assessment tool for the comfort of the backrest design taking into account individual differences. This tool is based on the development of a biomechanical trunk model. Firstly, a test campaign allowed identifying the sitting reproducibility of a volunteer in a standardized position (position, pressure distribution). A parametric finite element model of the trunk was developed and will allow simulating these experimental conditions. The model was validated from a geometrical point of view and the mesh was analyzed. To fully validate the model and allow its use by OEMs, sitting positions which the spine curvature is known will be simulated. Then the model will be evaluated for the comfort analysis by comparison of the pressure maps to the human/seat interface
Garnero, Valentin. "(Méta)-noyaux constructifs et linéaires dans les graphes peu denses." Thesis, Montpellier, 2016. http://www.theses.fr/2016MONTT328/document.
In the fields of Algorithmic and Complexity, a large area of research is based on the assumption that P ≠ NP(Polynomial time and Non deterministic Polynomial time), which means that there are problems for which a solution can be verified but not constructed in polynomial time. Many natural problems are not in P, which means, that they have no efficient algorithm. In order to tackle such problems, many different branches of Algorithmic have been developed. One of them is called Parametric Complexity. It consists in developing exact algorithms whose complexity is measured as a function of the size of the instance and of a parameter. Such a parameter allows a more precise analysis of the complexity. In this context, an algorithm will be considered to be efficient if it is fixed parameter tractable (fpt), that is, if it has a complexity which is exponential in the parameter and polynomial in the size of the instance. Problems that can be solved by such an algorithm form the FPT class.Kernelisation is a technical that produces fpt algorithms, among others. It can be viewed as a preprocessing of the instance, with a guarantee on the compression of the data. More formally, a kernelisation is a polynomial reduction from a problem to itself, with the additional constraint that the size of the kernel, the reduced instance, is bounded by a function of the parameter. In order to obtain an fpt algorithm, it is sufficient to solve the problem in the reduced instance, by brute-force for example (which has exponential complexity, in the parameter). Hence, the existence of a kernelisiation implies the existence of an fpt algorithm. It holds that the converse is true also. Nevertheless, the existence of an efficient fpt algorithm does not imply a small kernel, meaning a kernel with a linear or polynomial size. Under certain hypotheses, it can be proved that some problems can not have a kernel (that is, are not in FPT) and that some problems in FPT do not have a polynomial kernel.One of the main results in the field of Kernelisation is the construction of a linear kernel for the Dominating Set problem on planar graphs, by Alber, Fellows and Niedermeier.To begin with, the region decomposition method proposed by Alber, Fellows and Niedermeier has been reused many times to develop kernels for variants of Dominating Set on planar graphs. Nevertheless, this method had quite a few inaccuracies, which has invalidated the proofs. In the first part of our thesis, we present a more thorough version of this method and we illustrate it with two examples: Red Blue Dominating Set and Total Dominating Set.Next, the method has been generalised to larger classes of graphs (bounded genus, minor-free, topological-minor-free), and to larger families of problems. These meta-results prove the existence of a linear or polynomial kernel for all problems verifying some generic conditions, on a class of sparse graphs. As a price of generality, the proofs do not provide constructive algorithms and the bound on the size of the kernel is not explicit. In the second part of our thesis, we make a first step to constructive meta-results. We propose a framework to build linear kernels based on principles of dynamic programming and a meta-result of Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh and Thilikos
Ammour, Samir. "Support des patrons de conception dans les outils UML." Paris 6, 2006. http://www.theses.fr/2006PA066592.
Hiet, Guillaume. "Détection d'intrusions paramétrée par la politique de sécurité grâce au contrôle collaboratif des flux d'informations au sein du système d'exploitation et des applications : mise en œuvre sous Linux pour les programmes Java." Phd thesis, Université Rennes 1, 2008. http://tel.archives-ouvertes.fr/tel-00355089.
Hiet, Guillaume. "Détection d'intrusions paramétrée par la politique de sécurité grâce au contrôle collaboratif des flux d'information au sein du système d'exploitation et des applications : mise en oeuvre sous Linux pour les programmes Java." Rennes 1, 2008. http://www.theses.fr/2008REN1S171.
Computer security is now a crucial issue. We are convinced that policy-based intrusion detection is a promising approach. This kind of detection is only based on both a model of the system state evolution and a model of the security policy. We aim at using policy-based intrusion detection systems (IDS) to monitor a system with OS running COTS software and web applications. We propose a detection model that can monitor information flow between information containers. We define a generic IDS architecture implementing the proposed model. This architecture is based on the collaboration between several IDS monitoring information flows at different granularity levels. We present an implementation of this architecture and the results of the experiments we realized on realistic Java applications
Watel, Dimitri. "Approximation de l'arborescence de Steiner." Thesis, Versailles-St Quentin en Yvelines, 2014. http://www.theses.fr/2014VERS0025/document.
The directed Steiner tree problem (DST) asks, considering a directed weighted graph, a node r called root and a set of nodes X called terminals, for a minimum cost directed tree rooted in r spanning X. DST is an NP-complete problem. We are interested in the search for polynomial approximations for DST. Unless P = NP, DST can not be approximated neither within a constant ratio nor a logarithmic ratio with respected to k, where k is the number of terminals. The smallest known approximation ratio is O(kԑ)$ where ԑ is a positive real.In the first part, we provide three new approximation algorithms : a practical greedy algorithm merging two of the main approximation techniques for DST, an algorithm for the case where the graph is layered and where the distance between the terminals and the root is high, and an exponential approximation algorithm combining an approximation algorithm and an exact algorithm, parameterized with the number of terminals the exact algorithm must cover.In the last part we study DST with two branching constraints. With this technique, we are able to reduce the number of feasible solutions, and possibly facilitate the search for an optimal solution of the constraint problem. We study how it is possible to build such a solution in polynomial time and if this solution is a good approximation of an optimal solution of the non-constraint problem
Chane-Yack-Fa, Raphaël. "Vérification formelle de systèmes d'information." Thèse, Université de Sherbrooke, 2018. http://hdl.handle.net/11143/11630.
Khosravian, Ghadikolaei Mehdi. "Extension of NP Optimization Problems." Thesis, Paris Sciences et Lettres (ComUE), 2019. http://www.theses.fr/2019PSLED064.
The problem of determining the quality of a partial solution occurs in almost every algorithmic approach that gradually computes a global solution. Pruning search trees, proving approximation guarantees, or the efficiency of enumeration strategies usually require a suitable way to decide if a given partial solution is a reasonable candidate to pursue for extension to a global one, of assured quality. In this thesis, we study a special type of optimization problems, called extension problems for a large number of optimization problems on graphs. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimization problem can be solved in polynomial time. We present many positive/negative hardness and approximation results for different input scenarios. Moreover, the parameterized complexity of extension problems with respect to size of partial solutions, as well as the optimality of some exact algorithms under the Exponential-Time Hypothesis (ETH) are studied
Laug, Patrick. "Contribution à la génération automatique de maillages de qualité pour la simulation numérique." Habilitation à diriger des recherches, Université Pierre et Marie Curie - Paris VI, 2006. http://tel.archives-ouvertes.fr/tel-00012000.
Ce mémoire constitue une synthèse de mes contributions concernant la génération automatique de maillages respectant le mieux possible ces critères de qualité. Ces différents travaux de recherche ont été réalisés au sein du projet Gamma de l'INRIA.
Dans ce document, les thèmes suivants sont abordés successivement :
- la discrétisation de courbes du plan ou de l'espace 3D,
- le maillage de domaines plans de contours fixes ou variables,
- le maillage de surfaces gauches paramétrées ou discrètes.
Au cours de ces opérations de discrétisation et de maillage, la taille et la forme des éléments sont contrôlées par un champ de métriques traduisant des contraintes géométriques et/ou physiques. Les méthodes présentées ont toutes été validées sur de nombreux exemples académiques ou industriels, notamment en mécanique des solides et en mécanique des fluides.
Sikora, Florian. "Aspects algorithmiques de la comparaison d'éléments biologiques." Phd thesis, Université Paris-Est, 2011. http://pastel.archives-ouvertes.fr/pastel-00667797.
Charlet, Célina. "Raffiner pour vérifier des systèmes paramétrés." Besançon, 2003. http://www.theses.fr/2003BESA2054.
Sérée, Bastien. "Problèmes d'optimisation des les graphes paramétrés." Electronic Thesis or Diss., Ecole centrale de Nantes, 2022. http://www.theses.fr/2022ECDN0066.
We are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We alsoprove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study paritygames on parametrized graphs with one and two players whose objective is the conjunction of a qualitative condition on the parity andquantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searchinga winning strategy in both cases with one and two players
Laville, Aurélien. "Modélisation géométrique et mécanique du complexe musculo-squelettique du rachis cervical sous facteur de charge." Phd thesis, Paris, ENSAM, 2010. http://pastel.archives-ouvertes.fr/pastel-00553250.
Carbonnel, Clément. "Harnessing tractability in constraint satisfaction problems." Thesis, Toulouse, INPT, 2016. http://www.theses.fr/2016INPT0118/document.
The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results
Pham, Thi Ngoc Diem. "Spécification et conception de services d'analyse de l'utilisation d'un environnement informatique pour l'apprentissage humain." Phd thesis, Université du Maine, 2011. http://tel.archives-ouvertes.fr/tel-00689025.
Couchot, Jean-François. "Vérification d'invariants de systèmes paramétrés par superposition." Besançon, 2006. http://www.theses.fr/2006BESA2100.
Apprato, Dominique. "Approximation de surfaces paramétrées par éléments finis." Pau, 1987. http://www.theses.fr/1987PAUU3012.
Bennouna, Jaouad. "Approximation de courbes paramétrées par éléments finis." Pau, 1987. http://www.theses.fr/1987PAUU3009.
Ayad, Ali. "Complexité de résolution de systèmes algébriques paramétrés." Rennes 1, 2006. https://tel.archives-ouvertes.fr/tel-00127383.
Diallo, Madiagne. "Réseaux de flots : flots paramétrés et tarification." Versailles-St Quentin en Yvelines, 2003. http://www.theses.fr/2003VERS0030.
La thèse se focalise sur des applications des problèmes de flots dans des réseaux modélisant, d'une part des réseaux de distribution de fluide ou d'énergie et d'autre part des réseaux de télécommunication. Nous nous sommes intéressés à deux aspects :Le premier aspect consiste en une analyse de sensibilité des flots sur les réseaux de distribution, c'est à dire, l'étude de l'impact de la variation de la capacité d'une ou de plusieurs arêtes sur l'ensemble des valeurs de flot maximum entre toutes les paires de sommets du réseau. En outre, nous nous sommes intéressés à la rentabilité d'une arête donnée dans un réseau. Nous avons d'abord apporté des corrections à l'unique méthode qui existait dans le cas d'une capacité d'arête qui varie et nous avons proposé des algorithmes simples et efficaces pour résoudre le cas de plusieurs capacités qui varient. Nos méthodes sont basées sur les arbres de coupes de Gomory et Hu. 'Etant donné un réseau non orienté ayant capacités qui peuvent varier avec des paramètres lambda_1,\lambda_2, \lambda_3, \ldots \lambda_k, nous avons montré que 2^k calculs d'un arbre de coupes de Gomory et Hu étaient suffisants pour déterminer les valeurs de flot maximum entre toutes les paires de sommets dans le réseau. En ce qui concerne le problème de la rentabilité d'un lien, nous avons montré que juste 2 calculs d'un arbre de coupes de Gomory et Hu suffisaient pour déterminer l'ensemble des paires de sommets pour lesquelles tout flot maximum sature le lien cible. Le second aspect concerne l'allocation de ressources dans un réseau de télécommunication pour la satisfaction de requêtes d'utilisateurs. Pour ce faire, nous avons étudié ce problème par le biais de la tarification pour gérer la congestion tout en tenant compte du comportement des utilisateurs et de la volonté de profit del'opérateur. Nous avons utilisé une approche bi-niveaux pour résoudre le problème. Avec la méthode du Lagragien augmenté, nous résolvons le problème d'allocation de ressources en associant les multiplicateurs de Lagrange aux prix sur les liens du réseaux. Nous utilisons ensuite les conditions d'optimalité de Karush-Kuhn-Tucker pour vérifier si les ultiplicateurs (prix) sont uniques ou pas. Au cas de non unicité nous montrons comment on peut résoudre un deuxième problème d'optimisation sur ces multiplicateurs (prix) afin d'améliorer le revenu sur le réseau
Bergé, Pierre. "Algorithmes pour voyager sur un graphe contenant des blocages." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLS480.
We study NP-hard problems on graphs with blockages seen as models of networks which are exposed to risk of failures.We treat cut problems via the parameterized complexity framework. The cutset size p is taken as a parameter. Given a set of sources {s1,...,sk} and a target $t, we propose an algorithm which builds a small edge cut of size p separating at least r sources from t. This NP-complete problem is called Partial One-Target Cut. It belongs to the family of multiterminal cut problems. Our algorithm is fixed-parameter tractable (FPT) as its execution takes $2^{O(p^2)}n^{O(1)}$. We prove that the vertex version of this problem, which imposes cuts to contain vertices instead of edges, is W[1]-hard. Then, we design an FPT algorithm which counts the minimum vertex (S,T)-cuts of an undirected graph in time $2^{O(plog p)}n^{O(1)}$.We provide numerous results on the competitive ratio of both deterministic and randomized strategies for the Canadian Traveller Problem. The optimal ratio obtained for the deterministic strategies on general graphs is 2k+1, where k is a given upper bound on the number of blockages. We show that randomized strategies which do not use memory cannot improve the bound 2k+1. In addition, we discuss the tightness of lower bounds on the competitiveness of randomized strategies. The distance competitive ratio for a group of travellers possibly equipped with telecommunication devices is studied. Eventually, a strategy dedicated to equal-weight chordal graphs is proposed while another one is built for graphs with small maximum (s,t)-cuts. Both strategies outperform the ratio 2k+1
Perez, Anthony. "Algorithmes de noyau pour des problèmes d'édition de graphes et autres structures." Phd thesis, Université Montpellier II - Sciences et Techniques du Languedoc, 2011. http://tel.archives-ouvertes.fr/tel-00660089.
Chapelle, Mathieu. "Décompositions de graphes : quelques limites et obstructions." Phd thesis, Université d'Orléans, 2011. http://tel.archives-ouvertes.fr/tel-00659666.
Vignola, Emanuele. "A Theoretical Perspective on Hydrogenation and Oligomerization of Acetylene over Pd Based Catalysts." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN054/document.
Selective hydrogenation of acetylene in ethylene-rich flows is a fundamental process in the petrochemical industry since it allows the purification of ethylene for polymer applications. The reaction is catalyzed by Pd, which features acceptable selectivity towards ethylene compared to the total hydrogenation product, ethane. Pure Pd is, however, deactivated by oligomeric byproducts, known as ”green oil” in the literature. Therefore, most industrial catalysts are Pd-Ag alloys, where Ag helps to suppress the secondary reactions. This work addresses the formation of initial oligomers on Pd and Ag-Pd catalysts. A mean field based theoretical model was built to efficiently screen the topology of the topper most layer of the alloy catalyst under relevant conditions. This model gave evidence for strongly favored Pd island formation. To confirm this result, the system was then re-investigated by means of Monte Carlo simulations including the effect of segregation. Emergence of large domains of Pd were confirmed over large ratios of Ag to Pd. Green oil is expected to form on these catalytically active islands. To obtain a detailed view on the oligomerization process, activation energies were computed both for hydrogenation and oligomerization steps by periodic density functional theory on Pd(111). Oligomerization was found to be competitive with hydrogenation, with the hydrogenation of the oligomers being among the fastest processes. The role of Pd domains to green oil formation is still to be clarified under realistic conditions, where the surface is covered by many different species. A step forward to this goal was taken by developing a machine-learning tool which automatically interpolates model Hamiltonians on graphical lattices based on DFT computations, accounting for lateral interactions and distorted adsorption modes on crowded surfaces
Muller, Alexis. "Construction de systèmes par application de modèles paramétrés." Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2006. http://tel.archives-ouvertes.fr/tel-00459025.
Netto, Mariana Schiavo. "La commande adaptative de systèmes non-linéairement paramétrés." Paris 11, 2001. http://www.theses.fr/2001PA112320.
The contents of the thesis are divided into three main parts as follows. The first part treats the visual servoing problem, consisting of the control of the motion of a two-links planar robot manipulator by a fixed TV camera. We propose two different solutions to solve the problem. The second main part is devoted to the study of the use of the convexity property in the adaptive control of nonlinearly parametrized plants. We first treat a class of plants considered by Boskovic. We propose a reparametrization that convexifies the nonlinearity. We then apply a known controller to the convexly-parametrized system. We provide then a comparison between the controller applied to the reparametrized plant and the controller by Boskovic. The next step was to extend this convexifying reparametrization to a more general class of nonlinear parametrizations. This new result is used for the adaptative control of fed-batch fermentation processes. .
Traonouez, Louis-Marie. "Vérification et dépliages de réseaux de Petri temporels paramétrés." Phd thesis, Université de Nantes, 2009. http://tel.archives-ouvertes.fr/tel-00466429.
Les travaux présentés portent sur l'étude de méthodes de vérification paramétrée des systèmes temps réels. La motivation pour ces recherches est de proposer des méthodes formelles à appliquer sur des systèmes dont les spécifications ne sont pas encore complètes. Des paramètres sont donc introduits dans les modèles utilisés afin de donner des degrés de liberté à la modélisation. Le but est alors de guider la conception du système en déterminant des valeurs satisfaisantes pour les paramètres.
Nous nous sommes focalisé sur les paramètres temporels qui sont en général parmi les plus complexes à définir. Nous avons ainsi défini le modèle des réseaux de Petri à chronomètres paramétrés.
Dans une première approche, nous étendons les méthodes d'analyse classiquement utilisées dans les réseaux de Petri temporels. L'espace d'états du modèle paramétré est ainsi représenté par le graphe des classes d'états paramétrées. Cela nous permet de proposer des semi-algorithmes de model-checking paramétré avec lesquels nous vérifions des formules de logique TCTL paramétrées.
Dans une seconde approche, nous étudions les méthodes qui préservent le parallélisme des réseaux de Petri. L'intérêt est de limiter l'explosion combinatoire qui apparaît lors de l'analyse de systèmes distribués, en particulier avec des modèles paramétrés. Nous proposons pour cela une méthode de dépliage temporel paramétré. Ce dépliage est a priori infini, mais nous proposons de l'utiliser pour résoudre un problème de supervision. La construction du dépliage est alors guidée par des observations finies, et nous extrayons les explications de ces observations, ainsi que les contraintes sur les paramètres qu'elles induisent.
Malaval, Jean-Louis. "Outils de CAO paramétrés pour la conduite de processus." Montpellier 2, 1987. http://www.theses.fr/1987MON20239.
Mebsout, Alain. "Inférence d'invariants pour le model checking de systèmes paramétrés." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112188/document.
This thesis tackles the problem of automatically verifying complexparameterized systems. This approach is important because it can guarantee thatsome properties hold without knowing a priori the number of components in thesystem. We focus in particular on the safety of such systems and we handle theparameterized aspect with symbolic methods. This work is set in the theoreticalframework of the model checking modulo theories and resulted in a new modelchecker: Cubicle.One of the main contribution of this thesis is a novel technique forautomatically inferring invariants. The process of invariant generation isintegrated with the model checking algorithm and allows the verification inpractice of systems which are out of reach for traditional symbolicapproaches. One successful application of this algorithm is the safety analysisof industrial size parameterized cache coherence protocols.Finally, to address the problem of trusting the answer given by the modelchecker, we present two techniques for certifying our tool Cubicle based on theframework Why3. The first consists in producing certificates whose validity canbe assessed independently while the second is an approach by deductiveverification of the heart of Cubicle
Conversy, Stéphane. "Conception d'icones auditives paramétrées pour les interfaces homme-machine." Paris 11, 2000. http://www.theses.fr/2000PA112174.
Du, Cauzé De Nazelle Paul. "Paramétrage de formes surfaciques pour l'optimisation." Thesis, Ecully, Ecole centrale de Lyon, 2013. http://www.theses.fr/2013ECDL0008/document.
To improve optimized solutions quality in the design process, it is important to provide the optimizer tools to navigate the design space as much as possible. The purpose of this thesis is to analyze different parametrization methods for automotive surface shapes, in order to offer Renault an efficient optimization process. Three methods are analyzed in this thesis. The first two are closed to the existing ones, and propose to blend shapes to create diversity. Thus, we are able to maximize the exploration of the design space, while minimizing the effort for CAD setting. We show their high potential, but they involve the use of optimization methods difficult to implement today. The third method is designed to exploit the formulation of Koiter shell equations, which integrates mechanical and shape parameters, and to use it to perform shape optimization with respect to different mechanical criteria. This method also has the advantage of allowing the gradients calculation. On the other hand, we show that it is possible to use the Bezier’s control points as optimization parameters, and thus control the minimum number of variables necessary for the optimization problem, while allowing a broad exploration of the design space. However, this method is non-standard in the industry and involves specific developments that have been made in the context of this thesis. Finally, we implement in this thesis essentials elements of an optimization process for surface shapes