Inhaltsverzeichnis
Auswahl der wissenschaftlichen Literatur zum Thema „Jeux sur graphes“
Geben Sie eine Quelle nach APA, MLA, Chicago, Harvard und anderen Zitierweisen an
Machen Sie sich mit den Listen der aktuellen Artikel, Bücher, Dissertationen, Berichten und anderer wissenschaftlichen Quellen zum Thema "Jeux sur graphes" bekannt.
Neben jedem Werk im Literaturverzeichnis ist die Option "Zur Bibliographie hinzufügen" verfügbar. Nutzen Sie sie, wird Ihre bibliographische Angabe des gewählten Werkes nach der nötigen Zitierweise (APA, MLA, Harvard, Chicago, Vancouver usw.) automatisch gestaltet.
Sie können auch den vollen Text der wissenschaftlichen Publikation im PDF-Format herunterladen und eine Online-Annotation der Arbeit lesen, wenn die relevanten Parameter in den Metadaten verfügbar sind.
Zeitschriftenartikel zum Thema "Jeux sur graphes"
BESNIER, Jean-Baptiste, Frédéric CHERQUI, Gilles CHUZEVILLE und Aurélie LAPLANCHE. „Amélioration de la connaissance patrimoniale des réseaux d’assainissement de la métropole de Lyon“. TSM 12 2023, TSM 12 2023 (20.12.2023): 169–77. http://dx.doi.org/10.36904/tsm/202312169.
Der volle Inhalt der QuelleMessi Nguélé, Thomas, Maurice Tchuente und Jean-François Méhaut. „Social network ordering based on communities to reduce cache misses“. Revue Africaine de la Recherche en Informatique et Mathématiques Appliquées Volume 24 - 2017 - Special... (10.05.2017). http://dx.doi.org/10.46298/arima.1448.
Der volle Inhalt der QuelleStange, Madison, Dan G. Brown, Kevin Harrigan und Michael Dixon. „Built-in bad luck: Evidence of near-miss outcomes by design in scratch cards“. Journal of Gambling Issues, Nr. 36 (02.08.2017). http://dx.doi.org/10.4309/jgi.2017.36.3.
Der volle Inhalt der QuelleStange, Madison, Dan G. Brown, Kevin Harrigan und Michael Dixon. „Built-in bad luck: Evidence of near-miss outcomes by design in scratch cards“. Journal of Gambling Issues, Nr. 36 (02.08.2017). http://dx.doi.org/10.4309/jgi.v0i36.3977.
Der volle Inhalt der QuelleLenart, Cristian, und Arthur Lubovsky. „A uniform realization of the combinatorial $R$-matrix“. Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (01.01.2015). http://dx.doi.org/10.46298/dmtcs.2491.
Der volle Inhalt der QuelleScully, Ziv, Tian-Yi Jiang und Yan Zhang. „Firing Patterns in the Parallel Chip-Firing Game“. Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AT,..., Proceedings (01.01.2014). http://dx.doi.org/10.46298/dmtcs.2421.
Der volle Inhalt der QuelleNabias, Laurent. „Constellations of kinship in the medieval nobility of Île-de-France (1000-1440)“. Analyse de réseaux pour les sciences sociales, Papers (11.06.2018). http://dx.doi.org/10.46298/arcs.9234.
Der volle Inhalt der QuelleDissertationen zum Thema "Jeux sur graphes"
Duchêne, Eric. „Jeux combinatoires sur les graphes“. Université Joseph Fourier (Grenoble), 2006. http://www.theses.fr/2006GRE10100.
Der volle Inhalt der QuelleEveryone 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.
Der volle Inhalt der QuelleIn 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.
Der volle Inhalt der QuelleSerre, 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.
Der volle Inhalt der QuelleDans 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.
Der volle Inhalt der QuelleWithin 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.
Der volle Inhalt der QuelleThis 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.
Der volle Inhalt der QuelleGraph 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.
Der volle Inhalt der QuelleWe 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
Vandenhove, Pierre. „Strategy complexity of zero-sum games on graphs“. Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG029.
Der volle Inhalt der QuelleWe study two-player zero-sum turn-based games on graphs, a framework of choice in theoretical computer science. Such games model the possibly infinite interaction between a computer system (often called reactive) and its environment. The system, seen as a player, wants to guarantee a specification (translated to a game objective) based on the interaction; its environment is seen as an antagonistic opponent. The aim is to automatically synthesize a controller for the system that guarantees the specification no matter what happens in the environment, that is, a winning strategy in the derived game.A crucial question in this synthesis quest is the complexity of strategies: when winning strategies exist for a game objective, how simple can they be, and how complex must they be? A standard measure of strategy complexity is the amount of memory needed to implement winning strategies for a given game objective. In other words, how much information should be remembered about the past to make optimal decisions about the future? Proving the existence of bounds on memory requirements has historically had a significant impact. Such bounds were, for instance, used to show the decidability of monadic second-order theories, and they are at the core of state-of-the-art synthesis algorithms. Particularly relevant are the finite-memory-determined objectives (for which winning strategies can be implemented with finite memory), as they allow for implementable controllers. In this thesis, we seek to further the understanding of finite-memory determinacy. We divide our contributions into two axes.First, we introduce arena-independent finite-memory determinacy, describing the objectives for which a single automatic memory structure suffices to implement winning strategies in all games. We characterize this property through language-theoretic and algebraic properties of objectives in multiple contexts (games played on finite or infinite graphs). We show in particular that understanding the memory requirements in one-player game graphs (i.e., the simpler situation of games where the same player controls all the actions) usually leads to bounds on memory requirements in two-player zero-sum games. We also show that if we consider games played on infinite game graphs, the arena-independent-finite-memory-determined objectives are exactly the omega-regular objectives, providing a converse to the landmark result on finite-memory determinacy of omega-regular objectives. These results generalize previous works about the class of objectives requiring no memory to implement winning strategies.Second, we identify natural classes of objectives for which precise memory requirements are surprisingly not fully understood. We introduce regular objectives (a subclass of the omega-regular objectives), which are simple objectives derived from regular languages. We effectively characterize their memory requirements for each player, and we study the computational complexity of deciding the existence of a small memory structure. We then move a step up in the complexity of the objectives and consider objectives definable with deterministic Büchi automata. We characterize the ones for which the first player needs no memory to implement winning strategies (a property called half-positionality). Thanks to this characterization, we show that half-positionality is decidable in polynomial time for this class of objectives. These results complement seminal results about memory requirements of classes of omega-regular objectives
Hagenbach, Jeanne. „Communication stratégique et réseaux“. Phd thesis, Université Panthéon-Sorbonne - Paris I, 2009. http://tel.archives-ouvertes.fr/tel-00450632.
Der volle Inhalt der Quelle