Les jeux des gendarmes et du voleur dans les graphes traitent de la<br />capture d'un voleur qui se déplace dans un réseau par une équipe de<br />gendarmes. Ces jeux trouvent leurs motivations en informatique<br />fondamentale, notamment dans le cadre de la théorie de la complexité<br />et dans celui de la théorie des mineurs de graphes. Ces jeux ont<br />également des applications en intelligence artificielle et en<br />robotique. Quel que soit le contexte, le nombre de gendarmes utilisés<br />a un coût et doit être minimisé. Dans cette thèse, nous étudions<br />diverses contraintes auxquelles les stratégies de capture sont<br />soumises, ainsi que le coût de ces contraintes en terme de nombre de<br />gendarmes. Nous distinguons principalement trois cadres d'étude.<br /><br />Dans la première partie de cette thèse, nous définissons une variante<br />de stratégie de capture qui établit un pont entre la largeur<br />arborescente et la largeur linéaire des graphes. En particulier, nous<br />prouvons la monotonie de cette variante générale et donnons un<br />algorithme exponentiel exact pour calculer de telles stratégies.<br /><br />Dans la seconde partie de cette thèse, nous nous intéressons aux<br />stratégies dites connexes qui doivent assurer que la partie propre du<br />réseau est constamment connexe. Nous prouvons plusieurs bornes<br />supérieures et inférieures du coût de cette contrainte en terme de<br />nombre de gendarmes. Nous étudions également la propriété de monotonie<br />des stratégies de capture connexe.<br /><br />Dans la troisième partie de cette thèse, nous étudions les stratégies<br />de capture dans un contexte décentralisé. Nous proposons plusieurs<br />algorithmes décentralisés qui permettent aux gendarmes de calculer<br />eux-mêmes la stratégie qu'ils doivent réaliser.

Les exigences croissantes sur l'efficacité énergétique des bâtiments, l'évolution du {marché} énergétique, le développement technique récent ainsi que les particularités du poste de chauffage ont fait du MPC le meilleur candidat pour la régulation thermique des bâtiments à occupation intermittente. Cette thèse présente une méthodologie basée sur la commande prédictive distribuée visant un compromis entre l'optimalité, la simplicité et la flexibilité de l'implantation de la solution proposée. Le développement de l'approche est progressif : à partir du cas d'une seule zone, la démarche est ensuite étendue au cas multizone et / ou multisource, avec la prise en compte des couplages thermiques entre les zones adjacentes. Après une formulation quadratique du critère MPC pour mieux satisfaire les objectifs économiques du contrôle, la formulation linéaire est retenue. Pour répartir la charge de calcul, des méthodes de décomposition linéaire (comme Dantzig-Wolfe et Benders) sont employées. L'efficacité des algorithmes distribués proposés est illustrée par diverses simulations.

Les exigences croissantes sur l'efficacité énergétique des bâtiments, l'évolution du {marché} énergétique, le développement technique récent ainsi que les particularités du poste de chauffage ont fait du MPC le meilleur candidat pour la régulation thermique des bâtiments à occupation intermittente. Cette thèse présente une méthodologie basée sur la commande prédictive distribuée visant un compromis entre l'optimalité, la simplicité et la flexibilité de l'implantation de la solution proposée. Le développement de l'approche est progressif : à partir du cas d'une seule zone, la démarche est ensuite étendue au cas multizone et / ou multisource, avec la prise en compte des couplages thermiques entre les zones adjacentes. Après une formulation quadratique du critère MPC pour mieux satisfaire les objectifs économiques du contrôle, la formulation linéaire est retenue. Pour répartir la charge de calcul, des méthodes de décomposition linéaire (comme Dantzig-Wolfe et Benders) sont employées. L'efficacité des algorithmes distribués proposés est illustrée par diverses simulations. / The increasing requirements on energy efficiency of buildings, the evolution of the energy market, the technical developments and the characteristics of the heating systems made of MPC the best candidate for thermal control of intermittently occupied buildings. This thesis presents a methodology based on distributed model predictive control, aiming a compromise between optimality, on the one hand, and simplicity and flexibility of the implementation of the proposed solution, on the other hand. The development of the approach is gradually. The mono-zone case is initially considered, then the basic ideas of the solution are extended to the multi-zone and / or multi-source case, including the thermal coupling between adjacent zones. Firstly we consider the quadratic formulation of the MPC cost function, then we pass towards a linear criterion, in order to better satisfy the economic control objectives. Thus, linear decomposition methods (such as Dantzig-Wolfe and Benders) represent the mathematical tools used to distribute the computational charge among the local controllers. The efficiency of the distributed algorithms is illustrated by simulations.