Дисертації з теми "Jeux sur les graphes"
Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями
Ознайомтеся з топ-50 дисертацій для дослідження на тему "Jeux sur les graphes".
Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.
Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.
Переглядайте дисертації для різних дисциплін та оформлюйте правильно вашу бібліографію.
Duchêne, Eric. "Jeux combinatoires sur les graphes." Université Joseph Fourier (Grenoble), 2006. http://www.theses.fr/2006GRE10100.
Повний текст джерелаEveryone has ever played a combinatorial game, such as chess or checkers. The interest of mathematicians about this subject is often related to the search of a winning strategy for one of both players. From the game of Nim to chess, the complexity of this search is very variable. In this manuscript, we firstly give a short view of the main stages of the topic, who really started in the beginning of the XXth century. Besides, we emphasize the correlation between combinatorial games and number theory, error-correcting codes, or graph theory. We then investigate some variations of « classical » combinatorial games : Wythoff's game and Dots and Boxes. We detail the strategy and « good » game positions for the first and the second player. We then consider a solitaire variation of a recent two-player game : Clobber. It is a one-player game, where stones are placed on the vertices of a given graph. A move consisting in removing a stone (under some conditions), the goal is to minimize the number of remaining stones at the end. We give structural and algorithmic results about this game played on grids, trees or hypercubes
Schmidt, Simon. "Jeux à objectif compétitif sur les graphes." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM085/document.
Повний текст джерелаIn this thesis, we study three competitive optimization graph games. These games allow a dynamic approach to discrete optimization problems, which is an advantageous alternative way to consider these questions. The global idea consists in defining a combinatorial partisan game, associated to the original optimization problem, like coloring, domination, etc. Two players alternatively build the structure related to the optimization problem. One of them tries to obtain a structure as optimal as possible, whereas his opponent wants to prevent him from doing it. Under the hypothesis that both players play optimally, the size of the obtained structure defines a game invariant of the graph.We start by studying a 1-improper variation of the coloring game, which is the first and the most studied competitive optimization graph game. In this game, the players colors the vertices of a graph, such that two adjacent vertices do not share the same color. In the 1-improper version, we allow a vertex to have at most one neighbor with the same color as it. Then, we study the domination game, in which the players have to build a domination set, that is a sub-set of vertices such that any other vertex is adjacent to one of the vertex in this set. Finally, we define a new game, related to the distinguishing coloring problem. This game is about building a vertex-coloring which is preserved by none of the graph automorphisms. We raise some challenging open questions about this new game, especially concerning the characterization of graphs with infinite game invariant, by the existence of order two automorphisms
Cachat, Thierry. "Jeux sur des graphes d'automates à pile et leurs extensions." Rennes 1, 2004. http://www.theses.fr/2004REN10048.
Повний текст джерелаSerre, Olivier. "Contribution à l'étude des jeux sur des graphes de processus à pile." Phd thesis, Université Paris VIII Vincennes-Saint Denis, 2004. http://tel.archives-ouvertes.fr/tel-00011326.
Повний текст джерелаDans cette thèse, les graphes de jeu considérés sont des graphes de processus à pile qui offrent une représentation finie simple de systèmes infinis relativement complexes. Sur de tels graphes, on peut considérer des conditions de gain classiques (accessibilité, Büchi ou parité) mais aussi des conditions plus spécifiques au modèle comme celles portant sur le bornage de la pile. On peut également combiner ces dernières entre elles.
Une première contribution a été de fournir une représentation des ensembles de positions gagnantes pour les jeux de parité ainsi qu'une nouvelle présentation des résultats connus pour ces derniers. On a alors pu étendre de façon naturelle les techniques de preuves à d'autres conditions de gain, notamment à celles portant sur le bornage de la pile.
Une autre contribution a été la description d'une famille de conditions de gain de complexité borélienne arbitraire finie pour lesquelles les jeux (sur des graphes finis ou sur des graphes de processus à pile) restent décidables.
L'étude des jeux sur les graphes de BPA et sur les graphes de processus à compteur a permis de proposer des techniques propres à ces modèles qui fournissent alors des bornes de complexité meilleures que celles obtenues dans le cas général des graphes de processus à pile.
Enfin, une dernière contribution a été de proposer une solution pour les jeux sur des graphes de processus à pile munis de conditions combinant des conditions régulières et des conditions sur la hauteur de pile et pour des conditions décrites par des automates à pile avec visibilité.
GONZáLEZ, GóMEZ Mauricio. "Jeux stochastiques sur des graphes avec des applications à l’optimisation des smart-grids." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLN064.
Повний текст джерелаWithin the research community, there is a great interest in exploring many applications of energy grids since these become more and more important in our modern world. To properly design and implement these networks, advanced and complex mathematical tools are necessary. Two key features for their design are correctness and optimality. While these last two properties are in the core of formal methods, their effective application to energy networks remains largely unexploited. This constitutes one strong motivation for the work developed in this thesis. A special emphasis is made on the generic problem of scheduling power consumption. This is a scenario in which the consumers have a certain energy demand and want to have this demand fulfilled before a set deadline (e.g., an Electric Vehicle (EV) has to be recharged within a given time window set by the EV owner). Therefore, each consumer has to choose at each time the consumption power (by a computerized system) so that the final accumulated energy reaches a desired level. The way in which the power levels are chosen is according to a ``strategy’’ mapping at any time the relevant information of a consumer (e.g., the current accumulated energy for EV-charging) to a suitable power consumption level. The design of such strategies may be either centralized (in which there is a single decision-maker controlling all strategies of consumers), or decentralized (in which there are several decision-makers, each of them representing a consumer). We analyze both scenarios by exploiting ideas originating from formal methods, game theory and optimization. More specifically, the power consumption scheduling problem can be modelled using Markov decision processes and stochastic games. For instance, probabilities provide a way to model the environment of the electrical system, namely: the noncontrollable part of the total consumption (e.g., the non-EV consumption). The controllable consumption can be adapted to the constraints of the distribution network (e.g., to the maximum shutdown temperature of the electrical transformer), and to their objectives (e.g., all EVs are recharged). At first glance, this can be seen as a stochastic system with multi-constraints objectives. Therefore, the contributions of this thesis also concern the area of multi-criteria objective models, which allows one to pursue several objectives at a time such as having strategy designs functionally correct and robust against changes of the environment
Comin, Carlo. "Complexité dans les Jeux Infinis sur les Graphes et les Réseaux de Contraintes Temporelles." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1061/document.
Повний текст джерелаThis dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games
Marcoux, Héli. "Jeux de poursuite policier-voleur sur un graphe - Le cas du voleur rapide." Thesis, Université Laval, 2014. http://www.theses.ulaval.ca/2014/30386/30386.pdf.
Повний текст джерелаGraph searching problems can be expressed as a game where a group of searchers is trying to capture a group of fugitives on a graph. When players move alternately in such a game, we are then referring to games of Cops and Robbers. Nowakowski and Winkler [28], and independently Quilliot [45], introduced the very first version of cops and robbers games in which a single cop tries to capture a single robber, both players moving alternately from their current positions to neighboring vertices. They notably proposed a very nice characterization of graphs that are winning for the cop, which is based on a particular dismantling scheme of the graph’s vertices; a dismantling scheme consisting in removing one by one each vertex of the graph by following a given rule. This dismantling-like characterization is furthermore interesting since it directly yields a divide-and-conquer algorithm that is polynomial, to solve the cop and robber problem. In this master thesis, we propose a new version of cops and robbers games in which the robber is able to move arbitrarily fast in the graph and in which the cop has a watching area that limits the robber’s moving capabilities. We characterize the cop-winning graphs for this new game by using some dismantling scheme similar to the one given by Nowakowski and Winkler [28], Quilliot [45], but that better fits our new game’s conditions. To obtain this dismantling-like characterization, we particularly need to generalize the definition of a classical graph to an undergrounded graph, whose vertices are split in a set of light vertices and a set of dark vertices. We also give an algorithm that provides a monotonous cop-winning strategy by making sure the cop is securing more and more vertices at each turn.
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
Hagenbach, Jeanne. "Communication stratégique et réseaux." Phd thesis, Université Panthéon-Sorbonne - Paris I, 2009. http://tel.archives-ouvertes.fr/tel-00450632.
Повний текст джерелаDavid, Vincent. "Algorithmique parallèle sur les arbres de décision et raisonnement en temps contraint : étude et application au minimax." Toulouse, ENSAE, 1993. http://www.theses.fr/1993ESAE0008.
Повний текст джерелаDorbec, Paul. "Jeux, graphes et propagation." Habilitation à diriger des recherches, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00975898.
Повний текст джерелаRenault, Gabriel. "Jeux combinatoires dans les graphes." Phd thesis, Université Sciences et Technologies - Bordeaux I, 2013. http://tel.archives-ouvertes.fr/tel-00919998.
Повний текст джерелаGuignard, Adrien. "Jeux de coloration de graphes." Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14391/document.
Повний текст джерелаPart 1: Domination Game and its variantsDomination game is a combinatorial game that consists in marking vertices of a graph so that a marked vertex has no marked neighbors. The first player unable to mark a vertex loses the game.Since the computing of winning strategies is an NP-hard problem for any graphs, we examine some specific families of graphs such as complete k-partite graphs, paths or saws. For these families, we establish the set of losing elements. For other families, such as caterpillars, we prove that exists a polynomial algorithm for the computation of outcome and winning strategies. No polynomial algorithm has been found to date for more general families, such as trees.We also study 28 variants of Domination game, including the 12 variants defined by J. Conway for any combinatorial game. Using game functions, we find the set of losing paths for 10 of these 12 variants. We also investigate 16 variants called diameter, for instance when rules require to play on the component that has the largest diameter.Part 2: The game chromatic number of treesThis parameter is computed from a coloring game: Alice and Bob alternatively color the vertices of a graph G, using one of the k colors in the color set. Alice has to achieve the coloring of the entire graph whereas Bob has to prevent this. Faigle and al. proved that the game chromatic number of a tree is at most 4. We undertake characterization of trees with a game chromatic number of 3. Since this problem seems difficult for general trees, we focus on sub-families: 1-caterpillars and caterpillars without holes.For these families we provide the characterization and also compute winning strategies for Alice and Bob. In order to do so, we are led to define a new notion, the bitype, that for a partially-colored graph G associates two letters indicating who has a winning strategy respectively on G and G with an isolated vertex. Bitypes allow us to demonstrate several properties, in particular to compute the game chromatic number of a graph from the bitypes of its connected components
Charpentier, Clément. "Coloration, jeux et marquages dans les graphes." Thesis, Bordeaux, 2014. http://www.theses.fr/2014BORD0023/document.
Повний текст джерелаWe study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems
Mc, Inerney Fionn. "Jeux de domination et d’identification dans les graphes." Thesis, Université Côte d'Azur (ComUE), 2019. http://www.theses.fr/2019AZUR4049.
Повний текст джерелаIn this thesis, 2-player games on graphs and their algorithmic and structural aspects are studied. First, we investigate two dynamic dominating set games: the eternal domination game and its generalization, the spy game. In these two games, a team of guards pursue a fast attacker or spy in a graph with the objective of staying close to him eternally and one wants to calculate the eternal domination number (guard number in the spy game) which is the minimum number of guards needed to do this. Secondly, the metric dimension of digraphs and a sequential version of the metric dimension of graphs are then studied. These two problems are those of finding a minimum subset of vertices that uniquely identify all the vertices of the graph by their distances from the vertices in the subset. In particular, in the latter, one can probe a certain number of vertices per turn which return their distances to a hidden target and the goal is to minimize the number of turns in order to ensure locating the target. These games and problems are studied in particular graph classes and their computational complexities are also studied. Precisely, in Chapter 3, the NP-hardness of the spy game and the guard numbers of paths and cycles are first presented. Then, results for the spy game on trees and grids are presented. Notably, we show an equivalence between the fractional variant and the "integral" version of the spy game in trees which allowed us to use Linear Programming to come up with what we believe to be the first exact algorithm using the fractional variant of a game to solve the "integral" version. In Chapter 4, asymptotic bounds on the eternal domination number of strong grids are presented. In Chapter 5, results on the NP-completeness of the Localization game under different conditions (and a variant of it) and the game in trees are presented. Notably, we show that the problem is NP-complete in trees, but despite this, we come up with a polynomial-time (+1)-approximation algorithm in trees. We consider such an approximation to be rare as we are not aware of any other such approximation in games on graphs. Lastly, in Chapter 6, results on the metric dimension of oriented graphs are presented. In particular, the orientations which maximize the metric dimension are investigated for graphs of bounded degree, tori, and grids
Dailly, Antoine. "Criticalité, identification et jeux de suppression de sommets dans les graphes : Des étoiles plein les jeux." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSE1163/document.
Повний текст джерелаIn this thesis, we study both graphs and combinatorial games. There are several links betweenthose two domains : games are useful for modeling an opponent in optimization problems on graphs,and in the other direction several classical games are played on graphs. We will study two graphproblems and adapt some classical combinatorial games to be played on graphs.In a first chapter, we study a criticality problem. A graph that verifies some property, and suchthat any modification (vertex or edge addition or deletion) breaks the property is called critical forthis property. We focus on the critical graphs for the property "having diameter 2", called D2Cgraphs. The Murty-Simon conjecture gives an upper bound on the number of edges in a D2C graphwith a given number of vertices. However, recent research suggests that this bound can be improvedfor non-bipartite D2C graphs. We show the validity of this approach by proving a smaller upperbound for a subfamily of non-bipartite D2C graphs.In a second chapter, we consider an identification problem. Identification consists in assigningsome data to every edge or vertex of a graph, such that this assignment induces a label to everyvertex with the added condition that two distinct vertices must have a different label. We definean edge-coloring using sets of integers inducing an identification of the vertices, and prove that thiscoloring requires at most a logarithmic number of integers (with respect to the order of the graph)in order to successfully identify the vertices. This result is compared with other identifying colorings,for which the number of colors required to successfully identify the vertices can be linear with respectto the order of the graph.In order to show the link between graphs and games, we adapt a well-known family of games tobe played on graphs. We propose a general framework for the study of many vertex deletion games(which are games in which the players delete vertices from a graph under predefined rules) such asArc-Kayles. This framework is a generalization of subtraction and octal games on graphs. In theirclassical definition, those games exhibit a high regularity : all finite subtraction games are ultimatelyperiodic, and Guy conjectured that this is also true for all finite octal games.We specifically study the connected subtraction games CSG(S) (with S being a finite set). Inthose games, the players can remove k vertices from a graph if and only if they induce a connectedsubgraph, the graph remains connected after their deletion, and k ∈ S. We prove that those gamesare all ultimately periodic, in the sense that for a given graph and vertex, a path attached to thisvertex can be reduced (after a certain preperiod) without changing the Grundy value of the graph forthe game. We also prove pure periodicity results, mostly on subdivided stars : for some sets S, thepaths of a subdivided star can be reduced to their length modulo a certain period without changingthe outcome of the game.Finally, we define a weighted version of Arc-Kayles, called Weighted Arc-Kayles (WAKfor short). In this game, the players select an edge and reduce the weight of its endpoints. Verticeswith weight 0 are removed from the graph. We show a reduction between WAK and Arc-Kayles,then we prove that the Grundy values of WAK are unbounded, which answers an open question onArc-Kayles. We also prove that the Grundy values of WAK are ultimately periodic if we fix allbut one of the weights in the graph
Pardo, Soares Ronan. "Jeux de poursuite-évasion, décompositions et convexité dans les graphes." Phd thesis, Université Nice Sophia Antipolis, 2013. http://tel.archives-ouvertes.fr/tel-00908227.
Повний текст джерелаNisse, Nicolas. "Jeux des gendarmes et du voleur dans les graphes. Mineurs de graphes, stratgies connexes, et approche distribue." Phd thesis, Université Paris Sud - Paris XI, 2007. http://tel.archives-ouvertes.fr/tel-00168818.
Повний текст джерелаcapture d'un voleur qui se déplace dans un réseau par une équipe de
gendarmes. Ces jeux trouvent leurs motivations en informatique
fondamentale, notamment dans le cadre de la théorie de la complexité
et dans celui de la théorie des mineurs de graphes. Ces jeux ont
également des applications en intelligence artificielle et en
robotique. Quel que soit le contexte, le nombre de gendarmes utilisés
a un coût et doit être minimisé. Dans cette thèse, nous étudions
diverses contraintes auxquelles les stratégies de capture sont
soumises, ainsi que le coût de ces contraintes en terme de nombre de
gendarmes. Nous distinguons principalement trois cadres d'étude.
Dans la première partie de cette thèse, nous définissons une variante
de stratégie de capture qui établit un pont entre la largeur
arborescente et la largeur linéaire des graphes. En particulier, nous
prouvons la monotonie de cette variante générale et donnons un
algorithme exponentiel exact pour calculer de telles stratégies.
Dans la seconde partie de cette thèse, nous nous intéressons aux
stratégies dites connexes qui doivent assurer que la partie propre du
réseau est constamment connexe. Nous prouvons plusieurs bornes
supérieures et inférieures du coût de cette contrainte en terme de
nombre de gendarmes. Nous étudions également la propriété de monotonie
des stratégies de capture connexe.
Dans la troisième partie de cette thèse, nous étudions les stratégies
de capture dans un contexte décentralisé. Nous proposons plusieurs
algorithmes décentralisés qui permettent aux gendarmes de calculer
eux-mêmes la stratégie qu'ils doivent réaliser.
Nisse, Nicolas. "Jeux des gendarmes et du voleur dans les graphes : Mineurs de graphes, stratégies connexes, et approche distribuée." Paris 11, 2007. http://www.theses.fr/2007PA112088.
Повний текст джерелаIn graph searching problems, a team of searchers is aiming at catching a fugitive running in a network. These problems are motivated by several aspects of theoretical computer science, including computational complexity and minor graph theory. They have also numerous practical applications in artificial intelligence and robotics. In all these contexts, the number of searchers implied in the capture of the fugitive has a cost and must be minimized. In this thesis, we study several constraints of search strategie and their cost in terms of number of searchers. The thesis is divided in three parts. In the first part of the thesis, we introduce a new variant of search strategy that establishs a link between the treewidth and the pathwidth of a graph. In particular, we prove that this kind of strategy satisfies the monotonicity property, and we propose a exponential exact algorithm computing such a strategy. In the second part of the thesis, we focus on the so-called connected search strategy that must insure that the clear part of the network remains permanently connected. We prove several upper and lower bounds related to the cost of this constraint in terms of number of searchers. We also study the monotonicity property of the connected search strategies. In the third part of the thesis, we study the search strategy in a decentralized context. We propose several decentralized algorithms allowing searchers to compute by themselves the strategy that must be performed
Coupechoux, Pierre. "Codes et jeux de soustraction et de poursuite dans les graphes." Thesis, Toulouse, INSA, 2018. http://www.theses.fr/2018ISAT0016/document.
Повний текст джерелаIdentifying codes were introduced in 1998 by Karpovsky, Chakrabarty and Levitin. An identifying code is a subgraph such that each vertex is uniquely identified by the vertices in its neighborhood. There are several variants of these codes, including a colored version where the vertices are identified by the colors in their neighborhood. In this phd, we want to build an identifying coloring of a large cycle, given a fixed number of colors. We also studied identified codes in a certain class of oriented graphs: tournaments. We have also studied some topics in the game theory. The first one is a generalization of octal games, where we play on a graph instead of a heap. More precisely, the 0.33 game; each player can remove one or two vertices in a graph, with no disconnection allowed. The first player who cannot play loses. We studied this game in some graph classes: subdivided stars and subdivided bistars. The other game is called the Firefighter game. It's a one player game, where this one wants to contain a spreading fire in a graph. We solved a conjecture about this game, and introduced the online version of the game, for which we found some approximation results
Belkhir, Walid. "Algèbre et combinatoire des jeux de parité." Aix-Marseille 1, 2008. http://www.theses.fr/2008AIX11065.
Повний текст джерелаGarrec, Tristan. "Sur les jeux dynamiques : jeux stochastiques, recherche-dissimulation et transmission d'information." Thesis, Toulouse 1, 2019. http://www.theses.fr/2019TOU10019.
Повний текст джерелаIn this thesis, we study various models of dynamic games. These model decision-making processes taken by rational agents in strategic interactions and whose situation changes over time. The first chapter is devoted to stochastic games. In these, the current game depends on a state of nature, which evolves randomly from one stage to the next depending on the current state as well as the actions of the players, who observe these elements. We study communication properties between states, when the state space is in the form of a product X × Y, and players control the dynamics on their components of the state space. The existence of optimal strategies in any long enough repeated game, i.e., the existence of the uniform value, is proved under the assumption of strong communication on one side. We prove the non-convergence of the value of the discounted game, which implies the non-existence of the asymptotic value, under the assumption of weak communication on both sides. The next two chapters are devoted to models of search games. A searcher and a hider act on a search space. The searcher’s objective is typically to find the hider as quickly as possible, or to maximize the probability of finding him in a given time. The challenge is then to calculate the value and optimal strategies of the players according to the geometry of the search space. In a patrolling game, an attacker chooses a time and place to attack, while a patroller walks continuously. When the attack occurs, the patroller has a fixed amount of time to locate the attacker. In a stochastic search game, players act on a graph. The novelty of the model is that due to various events, at each stage, some edges may not be available, so the graph evolves randomly over time. Finally, the last chapter is devoted to a model of repeated games with incomplete information called dynamic control of information. An advisor has a private knowledge of the state of nature, which changes randomly over time. Every day, the advisor chooses the amount of information he discloses to an investor through messages. In turn, the investor chooses whether or not to invest in order to maximize her daily expected payoff. In the event of an investment, the advisor receives a fixed commission from the investor. His objective is then to maximize the discounted frequency of days on which investment takes place. We are interested in a specific information disclosure strategy of the advisor called the greedy strategy. It is a stationary strategy with the property of minimizing the amount of information disclosed under the constraint of maximizing the advisor’s current payoff
Hajri, Hatem. "Flots stochastiques sur les graphes." Phd thesis, Université Paris Sud - Paris XI, 2011. http://tel.archives-ouvertes.fr/tel-00660596.
Повний текст джерелаMAHEO, MEHEUST MARYVONNE. "Sur quelques parametres de graphes." Paris 11, 1994. http://www.theses.fr/1994PA112200.
Повний текст джерелаIssartel, Yann. "Inférence sur des graphes aléatoires." Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM019.
Повний текст джерелаThis thesis lies at the intersection of the theories of non-parametric statistics and statistical learning. Its goal is to provide an understanding of statistical problems in latent space random graphs. Latent space models have emerged as useful probabilistic tools for modeling large networks in various fields such as biology, marketing or social sciences. We first define an identifiable index of the dimension of the latent space and then a consistent estimator of this index. More generally, such identifiable and interpretable quantities alleviate the absence of identifiability of the latent space itself. We then introduce the pair-matching problem. From a non-observed graph, a strategy sequentially queries pairs of nodes and observes the presence/absence of edges. Its goal is to discover as many edges as possible with a fixed budget of queries. For this bandit type problem, we study optimal regrets in stochastic block models and random geometric graphs. Finally, we are interested in estimating the positions of the nodes in the latent space, in the particular situation where the space is a circle in the Euclidean plane. For each of the three problems, we obtain procedures that achieve the statistical optimal performance, as well as efficient procedures with theoretical guarantees. These algorithms are analysed from a non-asymptotic viewpoint, relying in particular on concentration inequalities
Caucal, Didier. "Sur des graphes infinis réguliers." [S.l.] : [s.n.], 1998. ftp://ftp.irisa.fr/techreports/habilitations/caucal.pdf.
Повний текст джерелаAnglès, d'Auriac Jean-Alexandre. "Jeux de défense et ensembles tropicaux." Thesis, Paris 11, 2015. http://www.theses.fr/2015PA112235/document.
Повний текст джерелаThe first pane of this thesis is on the study of vertex-colored graphs. We look at the tractability of asserting the existence of particular sets of vertices on a graph with the added constraint that the sets must be tropical, i.e. they must contain at least one vertex of each of the colors in the graph.This additional constraint tends to make the problems way less tractable. For instance, finding a minimum tropical dominating set, or a minimum tropical vertex cover, are APX-complete problems even when restricted to paths. Finding the smallest tropical connected subgraph is also NP-complete even when restricted to trees. However, restricting the number of colors will usually make problems more tractable. For instance, finding a connected tropical subgraph (on any graph) can be done in polynomial time as long as the number of colors is logarithmic in the size of the graph. Moreover, we show some structural results that links the size of a minimum connected subgraph to parameters such as the number of colors, the number of edges, the minimum degree…The second pane is on the study of some games on graphs, called defense games, in which multiple attackers target vertices and multiple defenders protect subgraphs.We focus on the existence of a Nash equilibrium when defenders protect paths of size at most p.When each defender protects exactly one edge, we show among other results that the game on a graph G with n defenders and k attackers admits a Nash equilibrium if and only if there exists a dominating set of size at most k in G, which is NP-complete in the general case.Similarly, when each defender protects a path of size at most p, the existence of a Nash equilibrium is linked to the notion of p-independent, i.e. a set of vertices such that every pair of elements of the set is at distance greater than p.Determining the existence of a maximal p-independent of size at most k is NP-complete, but our Min2stablemax algorithm can compute the minimum size of a maximal 2-independent set in a tree
Cristau, Julien. "Jeux et automates sur les ordres." Phd thesis, Université Paris-Diderot - Paris VII, 2010. http://tel.archives-ouvertes.fr/tel-00554026.
Повний текст джерелаBigot, de Morogues Francis. "Sur les jeux stratégiques de marché." Aix-Marseille 2, 1997. http://www.theses.fr/1997AIX24010.
Повний текст джерелаHaji, Mirsadeghi Mir Omid. "Routage sur les graphes géométriques aléatoires." Paris 6, 2012. http://www.theses.fr/2012PA066204.
Повний текст джерелаThe two first chapters are focused on preliminaries. In Chapter 3 of this thesis, we analyze a class of “Signal to Interference and Noise Ratio” (SINR) random graphs. These random graphs arise in the modeling of packet transmissions in wireless networks. In contrast to previous studies on SINR graphs, we consider both a space and a time dimension. We study optimal paths in such wireless networks in terms of first passage percolation on this random graph. We establish both positive and negative results on the associated time constant. The main negative result states that this time constant is infinite on the random graph associated with a Poisson point process under natural assumptions on the wireless channels. The main positive result states that when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson point process, the time constant is positive and finite. In the second part, we develop a framework for studying point-map invariant measures. We focus on the case of a not necessarily bijective point-map f. We introduce the notion of Point-map Palm version of the point process Φ, which satisfies the desired invariance property when it exists and we give sufficient conditions for it to exist. Chapter 5, explains the connection between Chapters 3 and 4. It generalizes the notion of point-map Palm measures for stochastic point-maps and time dependent point-maps. As we will see in the end of the Chapter 3, the optimal path in the time- space SINR graph is not computable locally in time. This fact leads us to considering suboptimal local algorithms
Hahn, Gena. "Sur des graphes finis et infinis." Paris 11, 1986. http://www.theses.fr/1986PA112166.
Повний текст джерелаThis work describes the dependence of microstructural features on rapid solidification processing for the melt spun Al-8% Fe alloy. The inspected parameters are: - ejection pressure and substrate velocity, - nature and rugosity of susbtrate, - ejection temperature. The resultant microstructures of the chill block melt spun ribbons is classified into three families: micro-cellular and dendritic structures, and equiaxed grains containing precipitates. It is possible to avoid the occurrence of the coarse dendritic structure corresponding to the slowest cooling conditions however, uniformity of the ribbon morphologic characteristics and good thermal contact between the ribbon and the weel have to be insured. So, improvement of wetting is the major point. The influence of process parameters on wetting is discussed and particular attention is paid to the sticking distance between the ribbon and the substrate. The planar flow casting method has been developed and microstructural results are compared to those given by the C. B. M. S. Technique
Caron-Aparicio, Jean-Xavier. "Problèmes isopérimétriques sur les graphes quantiques." Master's thesis, Université Laval, 2020. http://hdl.handle.net/20.500.11794/66416.
Повний текст джерелаRoka, Zsuzsanna. "Automates cellulaires sur graphes de Cayley." Lyon 1, 1994. http://www.theses.fr/1994LYO10180.
Повний текст джерелаVialatte, Jean-Charles. "Convolution et apprentissage profond sur graphes." Thesis, Ecole nationale supérieure Mines-Télécom Atlantique Bretagne Pays de la Loire, 2018. http://www.theses.fr/2018IMTA0118/document.
Повний текст джерелаConvolutional neural networks have proven to be the deep learning model that performs best on regularly structured datasets like images or sounds. However, they cannot be applied on datasets with an irregular structure (e.g. sensor networks, citation networks, MRIs). In this thesis, we develop an algebraic theory of convolutions on irregular domains. We construct a family of convolutions that are based on group actions (or, more generally, groupoid actions) that acts on the vertex domain and that have properties that depend on the edges. With the help of these convolutions, we propose extensions of convolutional neural netowrks to graph domains. Our researches lead us to propose a generic formulation of the propagation between layers, that we call the neural contraction. From this formulation, we derive many novel neural network models that can be applied on irregular domains. Through benchmarks and experiments, we show that they attain state-of-the-art performances, and beat them in some cases
Zuk, Andrzej. "Sur certaines propriétés spectrales du Laplacien sur les graphes." Toulouse 3, 1996. http://www.theses.fr/1996TOU30272.
Повний текст джерелаLardon, Aymeric. "Cinq essais sur les jeux d'oligopoles coopératifs." Phd thesis, Université Jean Monnet - Saint-Etienne, 2011. http://tel.archives-ouvertes.fr/tel-00743703.
Повний текст джерелаRosenberg, Dinah. "Sur les jeux répétés à somme nulle." Paris 10, 1998. http://www.theses.fr/1998PA100079.
Повний текст джерелаTurek, Ondrej. "Opérateurs de Schrödinger sur des graphes métriques." Phd thesis, Université du Sud Toulon Var, 2009. http://tel.archives-ouvertes.fr/tel-00527790.
Повний текст джерелаCan, Van Hao. "Processus de contact sur des graphes aléatoires." Thesis, Aix-Marseille, 2016. http://www.theses.fr/2016AIXM4709/document.
Повний текст джерелаThe contact process is one of the most studied interacting particle systems and is also often interpreted as a model for the spread of a virus in a population or a network. The aim of this thesis is to study the relationship of the local structure of the network and the global behavior of the contact process (the virus) on the whole network. Let $(G_n)$ be a sequence of random graphs converging weakly to a graph $G$. Then we study $tau_n$, the extinction time of the contact process on $G_n$ starting from full occupancy. We prove in some examples that there is a phase transition of $tau_n$ when $lambda$ - the infection rate of the contact process crosses a critical value $lambda_c(G)$ depending only on $G$. More precisely, for some models of random graphs, such as the configuration model, preferential attachment graph, random geometric graph, inhomogeneous graph, we show that $tau_n$ is of logarithmic (resp. exponential) order when $lambda < lambda_c(G)$ (resp. $lambda < lambda_c(G)$). Moreover, in some cases we also prove metastable results: in the super-critical regime, $tau_n$ divided by its expectation converges in law to an exponential random variable with mean $1$, and the density of the infected sites is stable for a long time
VANMERPE, JEAN-MARIE. "Decomposition et algorithmes efficaces sur les graphes." Amiens, 1999. http://www.theses.fr/1999AMIE0111.
Повний текст джерелаCournier, Alain. "Sur quelques algorithmes de décomposition de graphes." Montpellier 2, 1993. http://www.theses.fr/1993MON20034.
Повний текст джерелаTurek, Ondřej. "Opérateurs de Schrödinger sur des graphes métriques." Toulon, 2009. http://tel.archives-ouvertes.fr/tel-00527790/fr/.
Повний текст джерелаThis thesis is devoted to investigation of quantum graphs, in other words, quantum systems in which a nonrelativistic particle is confined to a graph. We propose a new way to represent the boundary conditions, and with the help of this result we solve the longstanding open problemof approximating by regular graphs all singular vertex couplings in quantum graph vertices. We present a construction in which the edges are disjunct and the pairs of the so obtained endpoints are joined by additional connecting edges of lengths 2d. Each connecting edge carries a delta potential and a vector potential. It is shown that when the lengths 2d of the connecting edges shrink to zero and the added potentials properly depend on d, the limit can yield any requested singular vertex coupling. This type of boundary conditions is used to examine scattering properties of singular vertices of degrees 2 and 3. We show thar the couplings between each pair of the outgoing edges are individually tunable, which could enable the design of quantum spectral junctions filters. We also study Schrödinger operators on an infinite quantum graph of a chain form which consists of identical rings connected at the touching points by delta-couplings. If the graph is periodic, the Hamiltonian has a band spectrum. We consid a "bending" deformation of the chain consisting in changing the position of the point of contact between two rings. We show that this deformation gives rive to eigenvalues and analyze their dependence on the "bending angle"
Buron, Maxime. "Raisonnement efficace sur des grands graphes hétérogènes." Thesis, Institut polytechnique de Paris, 2020. http://www.theses.fr/2020IPPAX061.
Повний текст джерелаThe Semantic Web offers knowledge representations, which allow to integrate heterogeneous data from several sources into a unified knowledge base. In this thesis, we investigate techniques for querying such knowledge bases.The first part is devoted to query answering techniques on a knowledge base, represented by an RDF graph subject to ontological constraints. Implicit information entailed by the reasoning, enabled by the set of RDFS entailment rules, has to be taken into account to correctly answer such queries. First, we present a sound and complete query reformulation algorithm for Basic Graph Pattern queries, which exploits a partition of RDFS entailment rules into assertion and constraint rules. Second, we introduce a novel RDF storage layout, which combines two well-known layouts. For both contributions, our experiments assess our theoretical and algorithmic results.The second part considers the issue of querying heterogeneous data sources integrated into an RDF graph, using BGP queries. Following the Ontology-Based Data Access paradigm, we introduce a framework of data integration under an RDFS ontology, using the Global-Local-As-View mappings, rarely considered in the literature.We present several query answering strategies, which may materialize the integrated RDF graph or leave it virtual, and differ on how and when RDFS reasoning is handled. We implement these strategies in a platform, in order to conduct experiments, which demonstrate the particular interest of one of the strategies based on mapping saturation. Finally, we show that mapping saturation can be extended to reasoning defined by a subset of existential rules
Heinrich, Marc. "Reconfiguration and combinatorial games." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1102/document.
Повний текст джерелаThis thesis explores problems related to games. The games that we consider in this study are games for which there is no hidden information: all the players have access to all the information related to the game; there is also no randomness and everything is deterministic. A few well-known board games (such as chess or go) fall in this category and are representative of the kinds of games that we consider here. Central to the study of these games is the notion of strategy, which roughly speaking, is a way of playing which ensures a certain objective. The main question of interest, when both playing and studying a game, is the problem of finding the 'best' strategy, which secures the victory for the player following it. In this thesis, we consider both one-player games, also called combinatorial puzzles, and two-player games. Examples of combinatorial puzzles include Rubik's cube, Rush-Hour, Sokoban, the 15 puzzle, or peg solitaire. Recently, some types of one-player games in particular have received a strong regain of interest as part of the larger area of reconfiguration problems. The puzzles we described above can all be described in the following way: there is a set of configurations, which represents all the possible states of the game; and the player is allowed to transform a configuration using a prescribed set of moves. Starting from an initial configuration, the goal is to reach a target configuration by a succession of valid moves. Reconfiguration extends this definition to any search problem: the set of configuration becomes the set of solutions to an instance of a given problem, and we ask whether we can transform one given solution to another using only a prescribed set of moves. Hence, in addition to the combinatorial puzzles, reconfiguration problems also include many `games' which are not played by humans anymore but are instead mathematical problems sharing a lot of similarities with combinatorial puzzles. The study of reconfiguration problems has been driven by many different motivations. It has algorithmic applications: it can be seen as a way to adapt a current solution already in place to reach a new one by only making small local changes. It is also connected to other problems such as random sampling, approximate counting or problems coming from statistical physics. It can also be used as a tool for understanding the performance of some heuristic algorithms based on local modifications of solutions such as local search. Two-player games, which are also called combinatorial games, have been studied since the beginning of the twentieth century, with the works of Bouton which were continued with the development of a nice theory by Berlekamp, Conway, and Guy, unifying a certain number of classical games. We focus in this study on perfect strategies (i.e., players always choosing the best possible move), and try to characterize who wins under perfect play for various games. This approach is at the heart of what is called Combinatorial Game Theory. Most of the research in this area is focused on `math games' which are games invented by mathematicians, often with simple rules and almost never played by humans. The main motivation for studying these games comes from the nice, and sometimes unexpected connections these games have with other areas of mathematics, such as for example number theory, automatons, or dynamical systems. In this thesis, we study one- and two-player games. The questions we consider are often related to complexity. Complexity theory consists in trying to classify problems depending on their hardness. By hardness we mean to quantify how much time it would take for a computer to solve the problem. An other aspect of this research consists in investigating structural properties that these games can satisfy. Finally, one of our main tools is the notion of graph, and we use in particular methods and techniques from graph theory to answer the different questions we just mentioned
Xie, Lijue. "Le coeur des jeux sur des ensembles ordonnés." Paris 1, 2009. http://www.theses.fr/2009PA010019.
Повний текст джерелаLaval, Marion. "Essai sur les contrats de jeux et paris." Toulouse 1, 2012. http://www.theses.fr/2012TOU10034.
Повний текст джерелаGambling has always been a controversial activity. Some consider it fun and attractive other find it devious and dangerous. This activity has been regulated by the Government because of this paradox. Therefore a system based on administrative authorizations was implemented giving exclusive rights to the three main actors of the sector : the ‘Pari mutual urbain’, the ‘Française des Jeux’ and casinos. As a result, the French gambling system is a monopolistic one. Because it is considered as a specific activity, the Government chose to limit legal actions by restricted civil right and to severely condemn infractions by a binding penal right. The recent evolution of gambling, mainly driven by the Internet usage, added to the European commission pressure, forced the legislator to intervene. In order to limit the proliferation of illegal gambling websites, he moved away from its initial politic and opened the gambling market to competition. The n°2010-476 law from the 12 of may 2010 appeared as a renewal of ancient rights whose rules were not adapted to modern times. Taking into consideration both players’ wishes and government’s interest, this law has a double ambition : to promote a secure and diversified market and to fight against illegal market players’ offer. If the law n°2010-476 from the 12 of may, relating to the gambling market opening to competition and its regulation, appears to mix new and past decisions, it is also giving us an opportunity, two yeas after its implementation, to analyze this sector before and after this law in order to appraise its benefits and its limits
Coron, Jean-Luc. "Quelques exemples de jeux à champ moyen." Thesis, Paris Sciences et Lettres (ComUE), 2017. http://www.theses.fr/2017PSLED032/document.
Повний текст джерелаThe mean field game theory was introduced in 2006 by Jean-Michel Lasry and Pierre-Louis Lions. It allows us to study the game theory in some situations where the number of players is too high to be able to be solved in practice. We will study the mean field game theory on graphs by learning from the studies of Oliver Guéant which we will extend to more generalized forms of Hilbertian. We will also study the links between the K-means and the mean field game theory. In principle, this will offer us new algorithms for solving the K-means thanks to the techniques of numerical resolutions of the mean field games. Findly, we will study a mean field game called the "starting time of a meeting". We will extend it to situations where the players can choose between two meetings. We will study analytically and numerically the existence and multiplicity of the solutions to this problem
BRASSEUR, HOUDARD ANNE. "Jeux de mains, jeux de vilains. . . Ou une reflexion sur l'abord des enfants sourds en difficulte." Angers, 1991. http://www.theses.fr/1991ANGE1025.
Повний текст джерелаAllard, Antoine. "Percolation sur graphes aléatoires - modélisation et description analytique -." Thesis, Université Laval, 2014. http://www.theses.ulaval.ca/2014/30822/30822.pdf.
Повний текст джерелаGraphs are abstract mathematical objects used to model the interactions between the elements of complex systems. Their use is motivated by the fact that there exists a fundamental relationship between the structure of these interactions and the macroscopic properties of these systems. The structure of these graphs is analyzed within the paradigm of percolation theory whose tools and concepts contribute to a better understanding of the conditions for which these emergent properties appear. The underlying interactions of a wide variety of complex systems share many universal structural properties, and including these properties in a unified theoretical framework is one of the main challenges of the science of complex systems. Capitalizing on a multitype approach, a simple yet powerful idea, we have unified the models of percolation on random graphs published to this day in a single framework, hence yielding the most general and realistic framework to date. More than a mere compilation, this framework significantly increases the structural complexity of the graphs that can now be mathematically handled, and, as such, opens the way to many new research opportunities. We illustrate this assertion by using our framework to validate hypotheses hinted at by empirical results. First, we investigate how the network structure of some complex systems (e.g., power grids, social networks) enhances our ability to monitor them, and ultimately to control them. Second, we test the hypothesis that the “k-core” decomposition can act as an effective structure of graphs extracted from real complex systems. Third, we use our framework to identify the conditions for which a new immunization strategy against infectious diseases is optimal.
Copros, Guillaume. "Stationnarité forte sur des graphes discrets ou quantiques." Thesis, Toulouse 3, 2018. http://www.theses.fr/2018TOU30088/document.
Повний текст джерелаIn this thesis, we are interested in the notion of strong stationary time, and in that, strongly connected, of strong stationary dual. These tools allow to study the convergence of ergodic processes, by determining a random time when the equilibrium is reached. The state space of the considered processes are discrete or continuous graphs. In the first part, we consider the discrete case, and we explicit a necessary and sufficient condition to the existence, for any initial distribution, of a finite strong stationary time. To do so, we construct explicitly a strong stationary dual, with values in the set of connected subsets of the graph, which evolves at each step by adding or removing some points at its border. Whenever this operation separates the dual set in several parts, in order not to disconnect it, one of these parts is chosen randomly, with a probability proportionnal to its weight relative to the invariant distribution. We also study the general behaviour of any dual process,2 and we give some other examples. In the second part, we deal with the continuous case, and the studied process is then a diffuion. We caracterize its invariant distribution, and we explicit an infinitesimal generator, which is expected to be that of a dual process. Nevertheless, this case turns out to be a little more involved that the discrete one. The dual process is thus constructed only for a brownian motion on a particular graph, as the unique solution of a martingale problem. Some leads are given to solve the case of diffusions on more general graphs, especially by using the convergence of a sequence of jump processes such as those presented in the first part