L'étude présentée dans ce travail de thèse aborde deux aspects du problème de Cauchy caractéristique en relativité générale. D'une part, une formule intégrale pour le problème de Cauchy caractéristique pour l'équation de Dirac est établie, généralisant les travaux de Penrose en espace-temps courbe. Ayant adapté le cadre fonctionnel pour obtenir une théorie des distributions adaptée à la structure algébriques des spineurs, le formalisme Geroch-Held-Penrose est utilisé pour décrire de la manière la plus précise possible la formule intégrale. La formule de Penrose en spin arbitraire sur l'espace-temps de Minkowski est retrouvée. D'autre part, une théorie de scattering conforme pour une équation des ondes non linéaire conformément invariante sur un espace asymptotiquement simple est construite. En effectuant un rééchelonnement conforme, l'espace-temps est complété en lui ajoutant une frontière constituée de deux hypersurfaces caractéristiques représentant respectivement les extrémités passées et futures des géodésiques de type lumière. Le comportement asymptotique des champs s'obtient alors en considérant les traces des solutions de l'équation conforme sur ces bords. L'inversibilité des opérateurs de trace s'obtient alors en résolvant un problème de Cauchy caractéristique sur ce bord et l'opérateur de scattering conforme par composition de ces opérateurs de trace.

Dans cette thèse, on construit puis on étudie une classe d'exemples de variations de structure de Hodge (VSH) sur des variétés complexes compactes. Dans la première partie, on construit des variétés projectives lisses munies de VSH à partir de certaines familles de sections hyperplanes à singularités simples. Les deux parties suivantes correspondent à l'étude de ces VSH de deux points de vue différents: on montre d'abord que leur application des périodes est génériquement immersive, puis on utilise le théorème décomposition de M. Saito pour calculer certains invariants cohomologiques.

Cette thèse propose une étude de trois grands problèmes de mathématiques financières dans les marchés financiers avec coûts de transactions proportionnels. La première partie est consacrée à l'étude des conditions de non arbitrage dans un marché avec information incomplete. La seconde partie résoud le problème de recouvrement d'option américaine dans le cas continue et introduit le concept de système de prix cohérent. Enfin, la troisième partie traite du problème de consommation - investissement de Merton dans un marché où le processus des prix est dirigé par un processus de Lévy.

De nombreux problèmes d'optimisation issus du monde réel, notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés. En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte. Les métaheuristiques sont des candidates naturelles pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques. Toutefois, le développement de métaheuristiques efficaces découle d'un processus de recherche complexe. Le cœur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif, ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO. Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées. Enfin, la question de la prise en compte l'incertitude est abordée dans le contexte de l'optimisation multiobjectif.

This work studies new algorithms and data structures that are useful in the context of program verification. As computers have become more and more ubiquitous in our modern societies, an increasingly large number of computer-based systems are considered safety-critical. Such systems are characterized by the fact that a failure or a bug (computer error in the computing jargon) could potentially cause large damage, whether in loss of life, environmental damage, or economic damage. For safety-critical systems, the industrial software engineering community increasingly calls for using techniques which provide some formal assurance that a certain piece of software is correct. One of the most successful program verification techniques is model checking, in which programs are typically abstracted by a finite-state machine. After this abstraction step, properties (typically in the form of some temporal logic formula) can be checked against the finite-state abstraction, with the help of automated tools. Alternating automata play an important role in this context, since many temporal logics on words and trees can be efficiently translated into those automata. This property allows for the reduction of model checking to automata-theoretic questions and is called the automata-theoretic approach to model checking. In this work, we provide three novel approaches for the analysis (emptiness checking) of alternating automata over finite and infinite words. First, we build on the successful framework of antichains to devise new algorithms for LTL satisfiability and model checking, using alternating automata. These algorithms combine antichains with reduced ordered binary decision diagrams in order to handle the exponentially large alphabets of the automata generated by the LTL translation. Second, we develop new abstraction and refinement algorithms for alternating automata, which combine the use of antichains with abstract interpretation, in order to handle ever larger instances of alternating automata. Finally, we define a new symbolic data structure, coined lattice-valued binary decision diagrams that is particularly well-suited for the encoding of transition functions of alternating automata over symbolic alphabets. All of these works are supported with empirical evaluations that confirm the practical usefulness of our approaches. / Ce travail traite de l'étude de nouveaux algorithmes et structures de données dont l'usage est destiné à la vérification de programmes. Les ordinateurs sont de plus en plus présents dans notre vie quotidienne et, de plus en plus souvent, ils se voient confiés des tâches de nature critique pour la sécurité. Ces systèmes sont caractérisés par le fait qu'une panne ou un bug (erreur en jargon informatique) peut avoir des effets potentiellement désastreux, que ce soit en pertes humaines, dégâts environnementaux, ou économiques. Pour ces systèmes critiques, les concepteurs de systèmes industriels prônent de plus en plus l'usage de techniques permettant d'obtenir une assurance formelle de correction. Une des techniques de vérification de programmes les plus utilisées est le model checking, avec laquelle les programmes sont typiquement abstraits par une machine a états finis. Après cette phase d'abstraction, des propriétés (typiquement sous la forme d'une formule de logique temporelle) peuvent êtres vérifiées sur l'abstraction à espace d'états fini, à l'aide d'outils de vérification automatisés. Les automates alternants jouent un rôle important dans ce contexte, principalement parce que plusieurs logiques temporelle peuvent êtres traduites efficacement vers ces automates. Cette caractéristique des automates alternants permet de réduire le model checking des logiques temporelles à des questions sur les automates, ce qui est appelé l'approche par automates du model checking. Dans ce travail, nous étudions trois nouvelles approches pour l'analyse (le test du vide) desautomates alternants sur mots finis et infinis. Premièrement, nous appliquons l'approche par antichaînes (utilisée précédemment avec succès pour l'analyse d'automates) pour obtenir de nouveaux algorithmes pour les problèmes de satisfaisabilité et du model checking de la logique temporelle linéaire, via les automates alternants.Ces algorithmes combinent l'approche par antichaînes avec l'usage des ROBDD, dans le but de gérer efficacement la combinatoire induite par la taille exponentielle des alphabets d'automates générés à partir de LTL. Deuxièmement, nous développons de nouveaux algorithmes d'abstraction et raffinement pour les automates alternants, combinant l'usage des antichaînes et de l'interprétation abstraite, dans le but de pouvoir traiter efficacement des automates de grande taille. Enfin, nous définissons une nouvelle structure de données, appelée LVBDD (Lattice-Valued Binary Decision Diagrams), qui permet un encodage efficace des fonctions de transition des automates alternants sur alphabets symboliques. Tous ces travaux ont fait l'objet d'implémentations et ont été validés expérimentalement.

Cette thèse est consacrée à l'étude de plusieurs problèmes d'équations aux dérivées partielles non-linéaires. La première partie (chapitres 1-2-3) traite d'un problème trouvant son origine en biologie mathématique, à savoir l'étude de la survie à long terme d'une population dont l'évolution est gouvernée par une équation parabolique non-linéaire. Dans le modèle considéré, le mécanisme de diffusion est contrôlé par le p-Laplacien, la non-linéarité est de type logistique et fait intervenir un poids m pouvant changer de signe, et les conditions aux limites sont de flux nul. Le poids m correspond à une répartition des ressources devant permettre la survie de la population. Dans le chapitre 1, nous déterminons entre autres un critère de survie à long terme faisant intervenir la valeur propre principale du p-Laplacien avec poids m. Cette valeur propre apparait, plus précisément, comme la valeur limite d'un paramètre en-dessous de laquelle toute solution positive de l'équation converge vers zéro lorsque t tend vers l'infini. Ceci nous conduit naturellement au problème de minimiser la valeur propre en question lorsque m varie dans une classe adéquate de poids. Dans le chapitre 2, nous prouvons l'existence de minimiseurs et montrons que ces derniers satisfont une propriété de type “bang-bang”. Plusieurs propriétés de montonie sont aussi étudiées dans des situations géométriques particulières, et une caractérisation complète est donnée en dimension 1. Le chapitre 3 est consacré à l'élaboration de simulations numériques, où l'algorithme utilisé combine un méthode de plus grande pente avec une représentation de certains ensembles comme ensembles de niveaux. La deuxième sujet de cette thèse (chapitre 4) est un problème elliptique faisant intervenir l'opérateur de courbure moyenne. Nous nous intéressons à l'existence et à la multiplicité de solutions nodales de ce problème. Nous montrons que, si un certain paramètre de l'équation est suffisamment grand, il existe une solution nodale qui change de signe exactement deux fois. Nous établissons également l'existence d'un nombre arbitrairement grand de solutions nodales. Enfin, dans le cas particulier où le domaine est une boule, un résultat de brisure de symétrie est obtenu, résultat qui induit l'existence d'au moins deux solutions à deux domaines nodaux.

Notre problème consiste à déterminer le nombre de grands rectangles identiques nécessaires pour ranger une liste de rectangles sans modifier leur orientation. Nous proposons des méthodes pour calculer des bornes inférieures pour ce problème, essentiellement basée sur le concept de fonctions dual-réalisables. Nous proposons aussi deux méthodes exactes de type énumératives. L'une permet de déterminer si un ensemble de rectangles peut être contenu dans un rectangle unique. Elle repose sur une nouvelle relaxation du problème. La deuxième méthode permet de résoudre le problème général de bin packing en deux dimensions. Elle calcule pour cela une décomposition itérative de l'ensemble des rectangles à placer.

L'imagerie électrique est un outil de plus en plus important pour un large domaine d'applications relatives à la caractérisation de la subsurface proche. D'importants développements ont été réalisés au cours des vingt dernières années pour l'amélioration des systèmes d'acquisitions et des algorithmes d'inversions. L'acquisition et le traitement de gros jeux de données reste toutefois une tâche délicate, en particulier en présence de topographie. Afin d'améliorer la gestion de la topographie, nous avons développé un nouvel algorithme d'inversion électrique 2.5D et 3D. Nous avons proposé deux nouvelles formulations pour supprimer la singularité à la source. Le problème direct est résolu en utilisant la méthode des Différences Finies Généralisées et des maillages non structurés, permettant une représentation précise de la topographie. Le code d'inversion utilise la méthode de l'état adjoint pour calculer le gradient de la fonction objective de manière économique. Cette approche a donné de bons résultats avec des données synthétiques. Les premiers résultats sur des données réelles ont permis de retrouver les principales structures de la subsurface, ainsi que plusieurs zones de faibles résistivités pouvant correspondre à des zones fracturées.

Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états.

La littérature scientifique propose une grande variété de stratégies pour la résolution des problèmes d'optimisation combinatoire (POC). Ces problèmes sont d'une grande complexité et demandent des méthodes évoluées pour les résoudre. Les algorithmes exacts, comme la programmation linéaire en nombres entiers (PLNE) à l'aide de l'algorithme Branch and Bound (B&B), arrivent à trouver une solution optimale pour certaines instances de problèmes. Par contre, plus la taille du problème à résoudre est grande, plus ces algorithmes ont de la difficulté à en venir à bout. Les métaheuristiques représentent alors une alternative intéressante pour trouver une solution de qualité acceptable dans des délais très courts. Toutefois, il est impossible de garantir qu'une métaheuristique trouvera la solution optimale d'un problème. Parmi ces méthodes, on retrouve l'optimisation par colonies de fourmis (OCF), qui a su faire ses preuves pendant les dernières années pour la résolution de différents problèmes d'optimisation combinatoire. Une autre avenue consiste à créer des algorithmes hybrides. L'objectif principal de ce mémoire est de proposer trois algorithmes hybridant un OCF et la PLNE pour résoudre le problème d'ordonnancement de voitures (POV). Le POV est un POC qui consiste à déterminer dans quel ordre placer un ensemble de voitures à produire sur une chaîne d'assemblage en se soumettant à un ensemble de contraintes. On cherche parfois la séquence minimisant le nombre de conflits, où un conflit représente une surcharge de travail occasionnée à un poste particulier de l'atelier de montage par l'arrivée successive de plusieurs voitures similaires, ou encore minimisant le nombre de changements de couleurs à l'atelier de peinture. Pour simplifier le problème, on ne s'attardera qu'aux contraintes liées à l'atelier de montage où sont installées les différentes options des voitures. Cette version théorique du POV que l'on retrouve dans la littérature est une simplification du problème industriel. Différentes méthodes ont été proposées pour solutionner ce problème. Celles qui attirent notre attention sont l'OCF et la PLNE. On cherchera, dans ce mémoire, à concevoir des approches hybrides exploitant les forces de ces deux approches. Il sera également possible de comparer la performance des algorithmes hybrides avec les résultats obtenus avec l'OCF pour établir l'apport de telles hybridations. Le premier algorithme hybride proposé consiste à créer un sous-problème à partir de la meilleure solution de chaque cycle de l'OCF et de résoudre ce sous-problème avec le B&B. Cette méthode ne s'est pas avérée très performante, car aucune intensification n'est effectuée sur une solution. Le second algorithme tente de combler cette lacune en appelant le B&B de manière répétitive à un intervalle régulier de cycles de l'OCF. Cet appel répété du B&B représente, en fait, une recherche locale exacte (RLE). Pour l'ensemble des problèmes utilisés pour tester cette hybridation, des résultats de qualité légèrement supérieure ou égale à l'OCF, intégrant une recherche locale, ont été obtenus pour environ deux problèmes sur trois. On peut en dire autant de la troisième hybridation proposée, qui consiste, dans un premier temps, à exécuter l'OCF et à fournir la meilleure solution trouvée comme solution de départ à la RLE. Les objectifs fixés dans cette recherche ont été atteints en concevant des méthodes de résolution hybrides, adaptées au POV, combinant une métaheuristique et une méthode exacte. On avait aussi pour but d'établir la performance des méthodes hybrides face à leurs contreparties singulières. En règle générale, les hybridations parviennent à donner des résultats de qualité équivalente à celle des résultats de l'OCF avec recherche locale mais avec un coût en temps d'exécution. Il s'agit tout de même d'une conclusion réjouissante puisque des améliorations pourraient être apportées à ces algorithmes pour les rendre encore plus performants. On a aussi exploré quelques façons de créer des sous-problèmes plus faciles à résoudre par un algorithme exact. Ceci ouvre donc une porte à une autre approche de la résolution de POC.