L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

L'objet de cette thèse est l'étude d'un problème d'ordonnancement, dont le critère d'optimisation est la minimisation du nombre total de changements d'outils sur une machine flexible. Différents problèmes liés à l'outillage et pouvant constituer un obstacle au fonctionnement d'un atelier flexible sont brièvement examinés, (de la gestion de l'inventaire aux changements d'outils). Nous nous concentrons ensuite sur le problème d'ordonnancement avec gestion d'outils sur une seule machine: ce problème est NP-complet. Un premier aspect qui est la gestion off-line des outils est étudié: différents modèles sont proposés pour la minimisation des changements en fonction d'une séquence des tâches donnée. Dans ce cas, le problème est polynomial. Nous revenons ensuite au problème d'ordonnancement proprement dit, pour lequel plusieurs types de méthodes heuristiques sont décrites et comparées. La seconde partie du travail est consacrée à la gestion on-line des changements d'outils; elle se compose de deux chapitres: dans le premier, le modèle que nous allons utiliser est décrit en détail. Il s'agit de la modélisation des problèmes de k-serveurs. Le principe peut être résumé comme suit: sur un réseau de n clients potentiels, on dispose de k serveurs mobiles, avec lesquels on doit répondre on-line aux demandes unitaires et successives des clients, tout en optimisant les déplacements des serveurs. Ce problème est en étroite relation avec la gestion des mémoires en informatique. Dans le dernier chapitre, le modèle des k-serveurs «classique» est généralisé aux problèmes avec service par blocs de demandes, ce qui permet d'adapter l'algorithme de partitionnement, (fortement compétitif pour le service unitaire), au cas plus général des demandes groupées. Cet algorithme dont nous étudions les propriétés et la compétitivité est applicable à la gestion on-line des changements d'outils. Il sert de base à la construction d'une heuristique d'ordonnancement avec gestion d'outils. Cette dernière méthode se révèle très efficace comparée aux précédentes

Le problème de la recherche d'un élément dans un ensemble donne est un des problèmes fondamentaux en informatique non numérique, lie, par exemple, aux bases de données, a la compilation, a l'optimisation combinatoire, etc... Dans cette thèse nous abordons le problème de la recherche dans des ensembles ordonnes et quelques problèmes qui lui sont lies. Une matrice est dite triée si elle possédé une relation d'ordre total sur chaque ligne et chaque colonne. Un cas particulier est l'ensemble des matrices définies par x+y, la somme cartésienne de deux vecteurs tries. Après un tour d'horizon des problèmes de la sélection, de la recherche et du tri sur des ensembles de la forme x=y, nous démontrons des bornes inférieures et introduisons des bornes supérieures pour les problèmes de la recherche et de la sélection. Nous proposons, en outre, plusieurs algorithmes parallèles pour la recherche dans x+y. Ensuite nous montrons comment appliquer ces résultats a la resolution en parallèle du problème de décision du sac-a-dos, ou, étant donnes plusieurs objets et un sac de capacité définie a remplir, on veut décider s'il existe une combinaison des objets qui remplit exactement le sac. Des algorithmes avec une accélération optimale sont introduits pour divers modèles de machines parallèles a mémoire partagée et distribuée. Pour ce problème les approches existantes se ramènent soit a la recherche dans x+y, soit a la traversée d'un espace combinatoire a l'aide de la technique du Branch & Bound. Cette dernière technique est aussi discutée dans ce travail, ou nous présentons un algorithme de Branch & Bound en vue de la resolution de problèmes d'optimisation combinatoire sur la connexion machine. Enfin, toujours dans le domaine de l'optimisation combinatoire, nous étudions le comportement de l'algorithme de recuit simule. Nous prouvons que, malgré la confiance qu'il inspire et sa grande utilisation pour des application

Les "équations de Schrödinger stochastiques" sont des équations différentielles stochastiques de type non classique qui apparaissent dans le domaine de la mesure en mécanique quantique. Leurs solutions sont appelées "trajectoires quantiques" et décrivent l'évolution de petits systèmes quantiques ouverts soumis à une mesure continue de type indirecte (on mesure l'environnement qui interagit avec le petit système).<br /><br />Habituellement, les justifications mathématiques et physiques de ces modèles sont loin d'être intuitives et évidentes. Soit elles manquent de rigueur car basées sur des arguments heuristiques, soit elles uilisent des outils mathématiques lourds et très abstraits (Filtrage quantique, espérance conditionnelle dans les algèbres de Von Neumann...).<br /><br />Dans cette thèse, on met en place un modèle discret de mesure en mécanique quantique. Ce modèle est basé sur celui des "interactions quantiques répétées" développé par Stéphane ATTAL et Yan PAUTRAT. Le cadre est le suivant. On considère un petit système en contact avec une chaine infinie de petits systèmes (tous notés H) identiques et indépedants entre eux. Chaque copie H interagit avec le petit système pendant un temps h. Après chaque interaction, on effectue une mesure sur H. Cette série de mesures entraine une série de modifications aléatoires de l'état du petit système. Cette série de modifications est alors décrite à l'aide d'une chaine de Markov dépendante du paramètre h. On montre alors que l'on peut obtenir les trajectoires quantiques, solutions des équations de Schrödinger stochastiques, comme limite continue (h tend vers 0) à partir de ces chaines de Markov. Ce résultat de convergence nécessite, au préalable, une étude complète des problèmes d'existence et d'uncité des solutions.<br /><br />Grâce à ce résultat de convergence, à partir d'un modèle physique discret, on justifie de façon rigoureuse et intuive l'utilisation des équations de Schrödinger stochastiques. On étend ensuite ces résultats dans le cas de modèles en dimension finie quelconque et on introduit la notion de controle.

.

Étude de certains problèmes d'optimisation combinatoire. Le premier concerne un problème de régulation de trafic pour lequel on donne une formulation mathématique et on propose une méthode permettant de le résoudre. Le deuxième problème traité est un des problèmes de la physique statistique qui relève de la combinatoire et de l'optimisation, celui du fondamental d'un verre de spins (modèle d'Ising). Enfin on étudie, deux autres problèmes d'optimisation combinatoire: l'absorbant et le Ki-recouvrement de poids minimum

Introduction. Couvertures des graphes par des cycles. Couverture par des circuits d'un matroïde régulier qui admet un Z.5- flot non nul. Flots de Fulkerson. Flots de Petersen. Constructions locales. Annexe. Bibliographie

.

.

On étudie dans cette thèse certains aspects de la régularité de l'ensemble singulier d'un minimiseur pour la fonctionnelle de Mumford-Shah. On se place principalement en dimension 3 même si certains résultats fonctionnent encore en dimension supérieure. Dans une première partie on étudie les minimiseurs globaux dans R^N et on montre que si (u;K) est un minimiseur global et que si K est un cône assez régulier, alors u (modulo les constantes) est une fonction homogène de degré 1/2 dans R^N\K. Ceci nous permet de lier l'existence d'un minimiseur global et le spectre du laplacien sphérique dans la sphère unité privée de K. Une conséquence est qu'un secteur angulaire stricte ne peut pas être l'ensemble singulier d'un minimiseur global de Mumford-Shah dans R^3. Dans la deuxième partie on montre un théorème de régularité au voisinage des cônes minimaux P, Y et T. On montre que si K est proche (en distance) d'un Y ou d'un T dans une certaine boule, alors K est l'image C^1,alpha d'un P, Y ou d'un T dans une boule légèrement plus petite, ce qui généralise un théorème de L. Ambrosio, N. Fusco et D. Pallara [AFP07]. Les techniques employées ne sont pas exclusives à la dimension 3 et devraient permettre de démontrer des résultats analogues en toute dimension pour un minimiseur de Mumford-Shah, dès lors qu'un résultat de régularité sur les ensembles presque minimaux existerait.