Les méthodes de traitement d'images fondées sur les équations aux dérivées partielles (EDP) bénéficient d'une attention particulière de la part de la communauté scientifique. Le nombre d'applications a considérablement augmenté après la formulation du problème sous forme d'ensembles de niveaux. Les EDPs s'appliquent dans de nombreux domaines tels le filtrage des images (diffusion non-linéaire), les contours actifs utilisés pour la segmentation des images statiques (graphe de Voronoï, Ligne de Partage des Eaux, plus court chemin, détection d'objets), aussi bien que des séquences d'images (suivi d'objets) ou encore des méthodes plus récentes tel le shape-from-shading. Les applications industrielles de ces méthodes sont néanmoins très limitées, d'une part par une complexité considérable de calculs (nombre d'itérations très élevé, par ex.), d'autre part par des difficultés rencontrées lors d'implantation embarquées (consommation d'énergie, exigences mémoire). Quelques expériences temps-réel ont été publiées avec des super-calculateurs ou des accélérateurs graphiques. Quant aux applications embarquées, elles sont à notre connaissance quasi-inexistantes. Notre but est de proposer une architecture dédiée, facilitant tant l'implantation temps-réel qu'embarquée. En vue de cet objectif nous proposons un nouvel algorithme de solution de l'équation Eikonale/calcul de fonction distance qui procède en parallèle, élimine l'usage des files d'attente hiérarchiques et permet d'obtenir la solution sur la totalité ou seulement sur une partie de l'image (le narrow band). La complexité de cet algorithme, nommé Massive Marching, est linéaire. Nous estimons que l'impact de Massive Marching est d'autant plus important pour la communauté de Morphologie Mathématique, qu'il s'agit du premier algorithme permettant d'obtenir en parallèle la ligne de partage des eaux non-biaisée. Ensuite, nous proposons deux types d'architecture (i) SIMD et (ii) plusieurs coeurs de processeurs embarqués implantant Massive Marching en parallèle ou semi-parallèle. Ces mêmes types d'architecture peuvent être utilisés pour implanter un filtrage aussi bien que des méthodes à évolution d'interface. La même architecture peut donc être utilisée pour implanter une application complète, composée de différents types d'algorithmes comme par exemple filtrage suivi par segmentation.

Cette thèse vise à développer des algorithmes de simulation conditionnelle de fonctions aléatoires à lois bivariables isofactorielles, c'est-à-dire telles qu'il existe une base de fonctions (facteurs) sans corrélations spatiales croisées. Les lois isofactorielles réalisent un compromis entre deux exigences souvent difficiles à concilier: d'une part, elles forment une vaste classe de modèles et permettent de s'adapter à la description de nombreux phénomènes; d'autre part, l'inférence statistique du modèle repose sur un faible nombre de paramètres. La première partie de la thèse met en relief les limitations et les approximations commises par une technique réputée "passe-partout": l'algorithme séquentiel, qui consiste à simuler les sites de l'espace les uns après les autres dans un ordre aléatoire, en estimant en chaque site la distribution de probabilité conditionnelle de la valeur inconnue par un krigeage d'indicatrices ou par un krigeage disjonctif. La seconde partie propose des modèles nouveaux et des algorithmes adaptés à leur simulation et au conditionnement à des données expérimentales. Plusieurs outils structuraux sont introduits et étudiés pour mener l'inférence des lois bivariables, notamment le madogramme, les variogrammes d'ordre inférieur à deux et les variogrammes d'indicatrices. Les concepts et méthodes sont finalement appliqués à un ensemble de données minières (accumulations en or et argent dans un gisement chilien en veine) caractérisées par une très forte dissymétrie des histogrammes.

Ce travail a pour motivation une meilleure compréhension des graphes parfaits. La preuve en 2002 de la conjecture des graphes parfaits de Claude Berge par Chudnovsky, Robertson, Seymour et Thomas a jeté une lumière nouvelle sur ce domaine de la combinatoire, mais a laissé plusieurs questions en suspens, notamment l'existence d'un algorithme combinatoire de coloration des graphes parfaits. Une paire d'amis d'un graphe est une paire de sommets telle que tous les chemins les reliant sont de longueur paire. Comme l'ont montré Fonlupt et Urhy, la contraction d'une paire amis préserve le nombre chromatique du graphe, et appliquée récursivement, permet dans certains cas de colorier optimalement le graphe. Nous prouvons une conjecture de Everett et Reed affirmant que cette approche fonctionne pour une classe de graphes parfaits: les graphes d'Artémis. Nous en déduisons un algorithme de coloration des graphes Artémis de complexité O(mn^2). Nous donnons un algorithme de complexité O(n^9) pour la reconnaissance des graphes d'Artémis. D'autres algorithmes de reconnaissance sont donnés, tous fondés sur des routines de détection de sous-graphes dans des graphes de Berge. Nous montrons que ces problèmes de détection sont NP-complets si on cherche à les étendre aux graphes quelconques.

Le théorème d'irréductibilité de Hilbert assure l'existence d'une spécialisation conservant l'irréductibilité d'un polynôme à plusieurs variables et à coefficients rationnels. Des versions effectives ont été données par P. Dèbes (1993) puis par U. Zannier et A. Schinzel (1995). Nous proposons ici diverses tentatives d'améliorer ces résultats effectifs : méthode de Dörge, méthode des congruences inspirée par un article de M. Fried et enfin une utilisation des résultats récents de R. Heath-Brown sur les points entiers d'une courbe algébrique. Cette dernière voie va nous permettre d'améliorer significativement les résultats connus. On finira par une application à la recherche d'un algorithme polynomial pour la factorisation d'un polynôme à deux indéterminées.

Je définis tout d'abord les polynômes vectoriels orthogonaux relativement à une matrice r x s de mesures ou de poids et je rappelle les propriétés habituelles : la récurrence à r+s+1 termes, le théorème de Shohat-Favard ou l'égalité de Christoffel-Darboux. Ces polynômes permettent, par l'utilisation d'approximants de Padé, de caractériser l'ensemble résolvant de l'opérateur aux différences associé aux récurrences. Cette caractérisation a déjà été donnée par Duren mais la démonstration utilisée ici est novatrice. Je définis ensuite des fonctions homographiques sur l'ensemble des matrices $r\times s$. J'uniformise ainsi tous les cas connus de fractions continues: scalaire, vectoriel ou matriciel. Elles permettent aussi de démontrer un théorème d'accélération de convergence de fractions continues matricielles, généralisation d'un théorème similaire pour les fractions généralisées donné par de Bruin et Jacobsen. J'utilise alors les polynômes vectoriels pour calculer les coefficients de récurrence d'autres polynômes par l'algorithme de Chebyshev modifié vectoriel, généralisation du cas scalaire pour lequel nous démontrons des critères de stabilité. Finalement, l'algorithme de Chebyshev modifié est utilisé pour étudier l'évolution temporelle du système dynamique semi-infini de Toda-Langmuir. Dans ce système, les particules sont sur le semi-axe réel et elles interagissent suivant une loi exponentielle décroissante. L'approche utilisée pour résoudre le problème est, encore une fois, innovante. En effet, j'étudie seulement les n premières particules et je m'intéresse à l'erreur commise sur l'évolution lorsque l'on tronque le système à N>>n quantités c'est-à-dire que l'on travaille avec un système fini. Je présente l'étude théorique de l'erreur, où je réutilise nos résultats sur la stabilité de l'algorithme de Chebyshev modifié, ainsi que des exemples numériques.

Le sujet de la thèse se situe dans le cadre de l'étude des équations différentielles ordinaires et des systèmes dynamiques non linéaires. La thèse présente une étude des attracteurs des systèmes dynamiques dissipatifs. En particulier, l'attracteur chaotique de Lorenz et les cycles limites des systèmes de Liénard. La première partie est dédiée au système de Lorenz. Ce système est obtenu par simplication des équations de Boussinesq fourmulées dans la cadre de la convection de Rayleigh-Bénard. Le système de Lorenz est important car il est le premier à avoir exhibé un comportement chaotique. On utilise des sections transverses (courbes ou surfaces qui ne sont traversées par le flot que dans un seul sens sur toute leur étendue) pour acquerir de l'information sur l'attracteur chaotique du système. Pour cela, on utilise les formes algébriques des intégrales du mouvement pour trouver des équations de sections tranverses. L'existance des ces sections transverses pour des plages de valeurs des paramètres nous permet de donner des limites algébriques à l'attracteur chaotique du systeme quand celui ci existe mais aussi de donner des plages de valeur des paramètres pour lesquelles il n'y a pas de comportement chaotique possible. La deuxième partie de la thèse présente un algorithme formel qui donne accès au nombre de cycles limites des systèmes de Liénard. En plus du nombre, on obtient une approximation algébrique de l'equation ainsi que la multiplicité de chacun de ces cycles. Le grand intérêt de cet algorithme est qu'il ne repose pas sur l'existence d'un petit paramètre (l'algorithme n'est pas perturbatif) et qu'il change le problème initial de résoudre une équation differentielle nonlinéaire en un problème algébrique de compter les racines d'un polynôme à une variable. On obtient aussi grâce à cet algorithme des approximations algébriques des courbes de bifurcations (de Hopf, saddle-node, hétérocline) des systèmes de Liénard.

Le problème de la gestion de la diversité est défini sur un ensemble partiellement ordonné d'élements possédant des demandes et des coûts unitaires de production. L'objectif est de produire un sous-ensemble de $k$ éléments références, $k$ étant un nombre donné, minimisant les coûts. Chaque élément non produit doit être remplacé par une référence qui lui est supérieure, ce qui implique un sur-coût. Après une étude théorique de complexité, nous modélisons ce problème grâce à un programme linéaire en nombres entiers, proche de ceux des problèmes de localisation $k$-médians. Pour résoudre ce programme, nous présentons un algorithme lagrangien, ainsi que de nombreux critères de fixation de variables permettant de réduire la taille du problème. Nous exploitons ensuite cet algorithme pour construire des solutions de bonne qualité. Nous développons enfin un algorithme exact de Séparation et Coupe. Nous étudions un certain type de coupes ainsi qu'une heuristique permettant de les générer. Nous concluons par des tests numériques effectués sur des instances réelles.

En zone méditerranéenne, d'intenses précipitations automnales sont responsables de crues particulièrement violentes : les crues " éclair ". L'intensité et la variabilité des précipitations ainsi que la complexité des processus hydrologiques responsables de la production des écoulements sur ces bassins limitent la prédictibilité de ces phénomènes. Une meilleure compréhension des processus impliqués dans les réponses hydrologiques des bassins versants et responsables de la variabilité spatio-temporelle des chemins de l'eau peut permettre d'améliorer les modélisations de ce type d'évènement. S'insérant dans le cadre de l'hydrologie spatialisée, cette thèse se propose d'étudier l'apport des potentialités satellitales, et notamment des produits 3D à très haute résolution pour la caractérisation spatiale des bassins et de leurs réseaux hydrographiques, afin d'étudier les origines géomorphologiques des variations spatio-temporelles des réponses hydrologiques et en vue d'améliorer la compréhension des mécanismes responsables des épisodes de crue. Pour cela, ce travail s'articule autour de deux axes. Le premier consiste à caractériser, à partir de données spatiales, le drain " potentiel " représentant le réseau géomorphologique sec formé par la suite continue des lignes de thalweg des bassins. Un algorithme original utilisant une structure de MNT sous forme triangulaire (TIN) a été développé spécifiquement dans ce but, afin d'obtenir un tracé des réseaux fidèle à leur tracé réel et de fournir des éléments sur leur géomorphologie ainsi que sur celle des bassins. Le deuxième axe concerne l'étude de la dynamique drain en eau ou " réel ". Il s'agit d'améliorer la compréhension des dynamiques spatiales de mise en eau des drains à travers différents épisodes de crue. Dans ce cadre, un réseau spatialisé de capteurs légers a été distribué sur deux bassins expérimentaux (< 1Km²) situés sur le Gardon d'Anduze afin de suivre les variations spatio-temporelles des dynamiques hydrologiques au sein des réseaux en eau. La confrontation des caractéristiques géomorphologiques et des réponses hydrologiques observées a permis de confirmer la prédominance des écoulements sub-surfaciques sur les bassins étudiés, de mettre en évidence deux types de réseaux aux fonctionnements différenciés (le réseau principal et le réseau secondaire), l'importante influence des pentes et de leur changement sur l'initiation et la pérennité des écoulements au sein des réseaux, et de proposer des hypothèses de fonctionnements différenciés en fonction des épisodes.

Les réseaux de télécommunications évoluent vers des modèles qui consistent en un certain nombre de routeurs IP interconnectés par un réseau optique intelligent. Cette nouvelle infrastructure multicouche nécessite un haut niveau de fiabilité, de telle manière que les services du réseau puissent être rétablis en cas de panne. Dans cette thèse, nous considérons différents problèmes de sécurisation et de dimensionnement liés à cette infrastructure multicouche. Nous donnons des formulations en terme de programmes linéaires mixtes , et nous discutons des polytopes associés. Nous décrivons plusieurs classes d'inégalités valides et étudions les conditions pour qu'elles définissent des facettes. Nous discutons de procédures de séparation pour ces inégalités et induisons des opérations de réduction. Nous développons des algorithmes de coupes et branchements et de coupes génération de colonnes et branchements et présentons une étude expérimentales sur des instances aléatoires et réelles.

Les travaux de recherche effectués dans le cadre de cette thèse concernent un problème delotissement et de séquencement pour une ligne de production imparfaite. Deux types d'aléas sont prisen compte : le rendement aléatoire (à cause des rebuts) et le temps d'exécution aléatoire (à cause despannes machines). Les temps de changement de série dépendant de la séquence des produits sontégalement pris en compte.Le problème est issu de d'une fabrication automatisée (usine-automate) des circuits impriméset il a été posé lors de la conception du système de gestion de production de l'atelier fabriquant lespartons conducteurs de plusieurs types. Étant donné que l'usine était complètement automatisée,l'atelier (comme le reste de l'usine) travaillait la plupart de la journée sans personnel autre que celui demaintenance, alors il fallait construire un planning de production pour les 24 heures suivantes. Ceplanning devait être répété chaque jour. Le problème consistait à définir les quantités optimales deproduits à traiter (tailles de lots) et l'ordre de passage des lots dans une ligne de production afind'optimiser un critère.Le problème traité appartient à trois domaines de recherche: 1) lotissement optimale pour lessystèmes de production imparfaits (ou lotissement sous incertitudes); 2) ordonnancement etlotissement déterministe; 3) ordonnancement avec des temps ou (et) coût de changement de série (setup).Dans la littérature scientifique nous trouvons beaucoup d'exemples de problèmes appartenant auun ou à l'intersection de deux de ces domaines. Par contre, nous n'avons pas trouvé les travaux quitraites de problèmes identiques au notre.Etant donné que le problème est trop compliqué tel qu'il est, nous avons cherché des façonsde son modélisation qui nous permettrons le résoudre. Nous avons trouvé trois cas où le problèmeinitial peut être décomposé en plusieurs parties, chacune entre lesquelles peut être transformé dans unproblème connu de la Recherche Opérationnelle. Ensuite nous avons travaillé que sur la partielotissement du problème décomposé tout en montrant comment les autres partis peuvent être résolus.Les problèmes de ce type sont très importants pour l'optimisation d'une chaine logistique.Ces résolutions aident d'organiser la production à la manière efficace, que permet aux entreprises defaire des gains financiers importants.