Afin de pouvoir subvenir aux futurs besoins en matière de transport aérien il est nécessaire d'augmenter la capacité de l'espace aérien. Les contrôleurs aériens, qui occupent une place centrale dans la gestion du trafic, doivent quotidiennement faire face à des situations conflictuelles (conflits) lors desquelles deux vols risquent de violer les normes de séparation en vigueur si aucune modification de trajectoire n'est envisagée. La détection et la résolution des conflits potentiels contribuent à augmenter la charge de travail des contrôleurs et peuvent potentiellement les conduire à diriger les vols vers des zones moins denses de l'espace aérien, induisant a posteriori un retard pour les vols. Le problème de la capacité de l'espace aérien peut donc être abordé en régulant les flux de trafic de façon réduire la quantité de conflits aériens. L'objectif de cette thèse est de mettre au point une méthodologie destinée à minimiser les risques de conflits aériens en modifiant légèrement les vitesses des appareils. Cette approche est principalement motivée par les conclusions du projet ERASMUS portant sur la régulation de vitesse subliminale. Ce type de régulation a été conçu de façon à ne pas perturber les contrôleurs aériens dans leur tâche. En utilisant de faibles modulations de vitesse, imperceptibles par les contrôleurs aériens, les trajectoires des vols peuvent être modifiées pour minimiser la quantité totale de conflits et ainsi faciliter l'écoulement du trafic dans le réseau aérien. La méthode retenue pour mettre en œuvre ce type de régulation est l'optimisation sous contrainte. Dans cette thèse, nous développons un modèle d'optimisation déterministe pour traiter les conflits à deux avions. Ce modèle est par la suite adapté à la résolution de grandes instances de trafic en formulant le modèle comme un Programme Linéaire en Nombres Entiers. Pour reproduire des conditions de trafic réalistes, nous introduisons une perturbation sur la vitesse des vols, destinée à représenter l'impact de l'incertitude en prévision de trajectoire dans la gestion du trafic aérien. Pour valider notre approche, nous utilisons un outil de simulation capable de rejouer des journées entières de trafic au dessus de l'espace aérien européen. Les principaux résultats de ce travail démontrent les performances du modèle de détection et de résolution de conflits et soulignent la robustesse de la formulation face à l'incertitude en prévision de trajectoire. Enfin, l'impact de notre approche est évalué à travers divers indicateurs propres à la gestion du trafic aérien et valide la méthodologie développée.

This thesis is concerned with Monte Carlo methods for sampling high-dimensional binary vectors from complex distributions of interest. If the state space is too large for exhaustive enumeration, these methods provide a mean of estimating the expected value with respect to some function of interest. Standard approaches are mostly based on random walk type Markov chain Monte Carlo, where the equilibrium distribution of the chain is the distribution of interest and its ergodic mean converges to the expected value. We propose a novel sampling algorithm based on sequential Monte Carlo methodology which copes well with multi-modal problems by virtue of an annealing schedule. The performance of the proposed sequential Monte Carlo sampler depends on the ability to sample proposals from auxiliary distributions which are, in a certain sense, close to the current distribution of interest. The core work of this thesis discusses strategies to construct parametric families for sampling binary vectors with dependencies. The usefulness of this approach is demonstrated in the context of Bayesian variable selection and combinatorial optimization of pseudo-Boolean objective functions.

Ha Minh Lam et M. Morales ont introduit une classe d'idéaux binomiaux qui est une extension binomiale d'idéaux monomiaux libres de carrés.Étant donné I un idéal monomial quadratique de k[x] libre de carrés et J une somme d'idéaux de scroll de k[z] qui satisfont certaines conditions, nous définissons l'extension binomiale de I comme B=I+J. Le sujet de cette thèse est d'étudier le nombre p plus grand tel que les sizygies de B son linéaires jusqu'au pas p-1. Sous certaines conditions d'ordre imposées sur les facettes du complexe de Stanley-Reisner de I nous obtiendrons un ordre > pour les variables de l'anneau de polynomes k[z]. Ensuite nous prouvons pour un calcul des bases de Gröbner que l'idéal initial in(B), sous l'ordre lexicographique induit par l'ordre de variables >, est quadratique libre de carrés. Nous montrerons que B est régulier si et seulement si I est 2-régulier. Dans le cas géneral, lorsque I n'est pas 2-régulier nous trouverons une borne pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En outre, en supossant que J est un idéal torique et en imposant des conditions supplémentaires, nous trouveron une borne supérieure pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En imposant des conditions supplémentaires, nous prouverons que les deux bornes sont égaux.

Dans la première partie, on s'intéresse à la multi-diffusion d'une onde acoustique avec une matrice homogène 2D contenant N inclusions. Dans le cas particulier de deux inclusions, on met alors en évidence l'importance du contraste matrice/inclusion dans les termes d'interactions entre inclusions. Le cas général de la multi-diffusion, pour distribution aléatoire de N inclusions, est ensuite développé dans l'esprit de Foldy-Lax basé sur des moyennes d'ensembles. Ainsi on cherche à déterminer le nombre d'onde effectif de l'onde effective, définie comme la moyenne du champ total, dans le cas d'une onde incidente émise par un point source. La deuxième partie est consacrée au cloaking actif dans une plaque. On détermine ainsi les amplitudes modales des sources multipolaires afin d'éteindre une onde plane ou émise par un point source, dans une région donnée. En outre, cette méthode peut s'appliquer pour éteindre l'onde diffractée par un défaut. Enfin dans la dernière partie, on se propose d'étudier la propagation d'onde au sein d'un milieu comportant des dislocations. On utilise la géométrie de Riemann-Cartan afin de modéliser ce milieu continu. Afin d'illustrer les différences que peuvent induire deux définitions possibles de la déformation (spatiale et matérielle), nous étudions la propagation d'ondes 3D dans l'exemple simple d'un milieu continu avec une densité uniforme et stationnaire de défauts. L'anisotropie et l'atténuation sont présentes dans les deux modèles mais sous forme différente. Enfin la déformation matérielle induit des modes de respiration et, en régime haute fréquence, des ondes transverses qui suivent l'escalier en spirale de Cartan.

Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet.

Dans cette thèse, nous étudions des problèmes d'identification des sommets dans les graphes. Identifier les sommets d'un graphe consiste à attribuer à chaque sommet un objet qui rend le sommet unique par rapport aux autres. Nous nous intéressons particulièrement aux codes identifiants : sous-ensembles de sommets d'un graphe, dominants, tels que le voisinage fermé de chaque sommet du graphe a une intersection unique avec l'ensemble. Les sommets du code identifiant peuvent être considérés comme des capteurs et chaque sommet du graphe comme un lieu possible pour une défaillance. Nous caractérisons tout d'abord l'ensemble des graphes pour lesquels tous les sommets sauf un sont nécessaires dans tout code identifiant. Le problème consistant à trouver un code identifiant optimal, c'est-'a-dire de taille minimale, étant NP-difficile, nous l'étudions sur quatre classes restreintes de graphes. Suivant les cas, nous pouvons résoudre complètement le problème (pour les graphes de Sierpinski), améliorer les bornes générales (pour les graphes d'intervalles, les graphes adjoints, la grille du roi) ou montrer que le problème reste difficile même restreint (pour les graphes adjoints). Nous considérons ensuite des variations autour des codes identifiants permettant plus de flexibilité pour les capteurs. Nous étudions par exemple des capteurs du plan capables de détecter des défaillances 'a un rayon connu avec une erreur tolérée. Nous donnons des constructions de tels codes et bornons leur taille pour des valeurs de rayons et d'erreurs fixés ou asymptotiques. Nous introduisons enfin la notion de coloration identifiante d'un graphe, permettant d'identifier les sommets d'un graphe avec les couleurs présentes dans son voisinage. Nous comparons cette coloration avec la coloration propre des graphes et donnons des bornes sur le nombre de couleurs nécessaires pour identifier un graphe, pour plusieurs classes de graphes.

Cette thèse explore l'utilisation des modèles bayésiens dans les IA de jeux vidéo multi-joueurs, particulièrement l'IA des jeux de stratégie en temps réel (STR). Les jeux vidéo se situent entre la robotique et la simulation totale, car les autres joueurs ne sont pas simulés, et l'IA n'a pas de contrôle sur la simulation. Les jeux de STR demandent simultanément d'effectuer des actions reactives (contrôle d'unités) et de prendre des décisions stratégiques (technologiques, économiques) et tactiques (spatiales, temporelles). Nous avons utilisé la modélisation bayésienne comme une alternative à la logique (booléenne), étant capable de travailler avec des informations incomplètes, et donc incertaines. En effet, la spécification incomplète des comportement "scriptés", ou la spécification incomplète des états possibles dans la recherche de plans, demandent une solution qui peut gérer cette incertitude. L'apprentissage artificiel aide à réduire la complexité de spécifier de tels modèles. Nous montrons que la programmation bayésienne peut intégrer toutes sortes de sources d'incertitudes (états cachés, intentions, stochasticité) par la réalisation d'un joueur de StarCraft complètement robotique. Les distributions de probabilité sont un moyen de transporter, sans perte, l'information que l'on a et qui peut représenter au choix: des contraintes, une connaissance partielle, une estimation de l'espace des états et l'incomplétude du modèle lui-même. Dans la première partie de cette thèse, nous détaillons les solutions actuelles aux problèmes qui se posent lors de la réalisation d'une IA de jeu multi-joueur, en donnant un aperçu des caractéristiques calculatoires et cognitives complexes des principaux types de jeux. En partant de ce constat, nous résumons les catégories transversales de problèmes, et nous introduisons comment elles peuvent être résolues par la modélisation bayésienne. Nous expliquons alors comment construire un programme bayésien en partant de connaissances et d'observations du domaine à travers un exemple simple de jeu de rôle. Dans la deuxième partie de la thèse, nous détaillons l'application de cette approche à l'IA de STR, ainsi que les modèles auxquels nous sommes parvenus. Pour le comportement réactif (micro-management), nous présentons un controleur multi-agent décentralisé et temps réel inspiré de la fusion sensori-motrice. Ensuite, nous accomplissons les adaptation dynamiques de nos stratégies et tactiques à celles de l'adversaire en le modélisant à l'aide de l'apprentissage artificiel (supervisé et non supervisé) depuis des traces de joueurs de haut niveau. Ces modèles probabilistes de joueurs peuvent être utilisés à la fois pour la prédiction des décisions/actions de l'adversaire, mais aussi à nous-même pour la prise de décision si on substitue les entrées par les notres. Enfin, nous expliquons l'architecture de notre joueur robotique de StarCraft, et nous précisions quelques détails techniques d'implémentation. Au delà des modèles et de leurs implémentations, il y a trois contributions principales: la reconnaissance de plan et la modélisation de l'adversaire par apprentissage artificiel, en tirant partie de la structure du jeu, la prise de décision multi-échelles en présence d'informations incertaines, et l'intégration des modèles bayésiens au contrôle temps réel d'un joueur artificiel.

Blasius et Rogawski ont formulé une conjecture qui prévoit que l'action du Frobenius sur la cohomologie d'une variété de Shimura est annulée par un certain polynôme, à coefficients dans l'algèbre de Hecke. C'est l'analogue de la célèbre relation d'Eichler-Shimura pour la courbe modulaire. Dans cette thèse, on démontre cette conjecture pour les variétés de Shimura associées aux groupes unitaires en signature (n-1,1) quand n est impair. Par ailleurs, on étudie certains aspects dans le cas particulier n=3. On montre explicitement la relation de congruence sur le lieu ordinaire. De plus, on étudie le graphe des cristaux supersinguliers et les relèvements d'isogénies en caractéristique nulle.

Depuis Ruelle, puis Rugh, Baladi, Tsujii, Liverani et d'autres, on sait que la fuite vers l'équilibre statistique dans de nombreux systèmes dynamiques chaotiques est gouvernée par le spectre de résonances de Ruelle de l'opérateur de transfert. A la suite de récents travaux de Faure, Sjöstrand et Roy, cette thèse propose une approche semiclassique de systèmes dynamiques chaotiques de type partiellement expansifs. Une partie du mémoire est consacrée aux extensions d'applications expansives vers des groupes de Lie compacts, en se reistreignant essentiellement aux extensions vers le groupe spécial unitaire SU(2). On se sert de la théorie des états cohérents pour les groupes de Lie, développée dans les années 70 par Perelomov et Gilmore, pour mettre en oeuvre les outils semiclassiques et la théorie des résonances de Helfer et Sjöstrand. On en déduira une estimation de Weyl et un gap spectral pour les résonances de Ruelle prouvant que la fuite vers l'équilibre statistique dans ces modèles est gouvernée par un opérateur de rang fini (en accord avec les résultats obtenus par Tsujii pour les semi-flots partiellement expansifs). On étend ensuite cette approche aux modèles "ouverts" pour lesquels la dynamique présente un ensemble captif de Cantor. On montrera l'existence d'un spectre discret de résonances de Ruelle et on prouve une loi de Weyl fractale, analogue classique du théorème de Lin-Guillopé-Zworski pour les résonances du laplacien hyperbolique sur les surfaces à courbure négative constante. On montre aussi un gap spectral asymptotique. On expliquera pourquoi ces modèles semblent être des objets d'étude adaptés pour approcher des questions importantes et difficiles du chaos classique ou quantique. On pense en particulier au problème de la minoration du nombre de résonances, étudié dans le contexte des applications quantiques par Nonnenmacher et Zworski.

Un système intégrable semi-torique sur une variété symplectique de dimension 2n est un système intégrable dont le flot de n − 1 composantes de l'application moment est 2 -périodique. On obtient donc une action hamiltonienne du tore Tn−1. En outre, on demande que tous les points critiques du système soient non-dégénérés et sans composante hyperbolique. En dimension 4, San V˜u Ngo.c et Álvaro Pelayo ont étendu à ces systèmes semi-toriques les résultats célèbres d'Atiyah, Guillemin, Sternberg et Delzant concernant la classification des systèmes toriques. Dans cette thèse nous proposons une extension de ces résultats en dimension quelconque, à commencer par la dimension 6. Les techniques utilisées relèvent de l'analyse comme de la géométrie symplectique, ainsi que de la théorie de Morse dans des espaces différentiels stratifiés. Nous donnons d'abord une description de l'image de l'application moment d'un point de vue local, en étudiant les asymptotiques des coordonnées actionangle au voisinage d'une singularité foyer-foyer, avec le phénomène de monodromie du feuilletage qui en résulte. Nous passons ensuite à une description plus globale dans la veine des polytopes d'Atiyah, Guillemin et Sternberg. Ces résultats sont basés sur une étude systématique de la stratification donnée par les fibres de l'application moment. Avec ces résultats, nous établissons la connexité des fibres des systèmes intégrables semi-toriques de dimension 6 et indiquons comment nous comptons démontrer ce résultat en dimension quelconque.