Les schémas de subdivisions ont été initialement introduits pour construire par itération, des courbes ou des surfaces à partir de points de contrôle. Ils sont apparus comme étant un ingrédient de base dans la définition d'analyses multirésolutions, avec comme application<br />l'approximation et la compression des images. Dans la construction de courbes ou dans la compression d'images, la convergence du schéma de subdivision vers une fonction continue, la régularité de cette fonction, la stabilité et l'ordre du schéma sont des propriétés cruciales. Les schémas linéaires présentant une importante limitation (ils créent des oscillations au voisinage de forts gradients ou de discontinuité qui se traduit par des zones de flous près des contours dans la compression d'images), on s'est alors intéressé à des schémas non-linéaires.<br />S'inscrivant dans la lignée des théories concernant les schémas non- linéaires, on a développé dans ce travail des théorèmes de convergence, de régularité, de stabilité et d'ordre pour une classe de<br />schémas non-linéaires s'écrivant sous la forme d'une somme d'un schéma linéaire et d'une perturbation non-linéaire. <br />Nous avons ensuite appliqué ces résultats à l'étude de propriétés de schémas non-linéaires existants, ou que nous avons contruits pour répondre au problème d'oscillations ou aux problèmes de régularité.<br />Une première application concerne la compression d'images. On s'est proposé d'étudier la stabilité de l'analyse multirésolution bidimensionnelle associée à cette classe de schémas non-linéaires,<br />puis d'appliquer les théorèmes établis et d'observer numériquement, les bénifices obtenus par rapport à des analyses multirésolutions linéaires.<br />Enfin, une deuxième application concerne la construction d'opérateurs aux différences finies ayant une erreur homogène sur des grilles non-uniformes, à partir un opérateur donné et d'un schéma de subdivision.

En imagerie du petit animal par tomographie d'émission monophotonique (TEMP), la modélisation de la réponse physique du détecteur demande beaucoup de soin pour en contrebalancer la faible résolution intrinsèque. Les coupes du volume à reconstruire s'obtiennent ainsi à partir des projections, à la fois par une opération de rétroprojection et une déconvolution de la réponse impulsionnelle du détecteur. Nous optons dès lors pour des méthodes itératives de résolution d'un grand système linéaire qui fonctionnent indépendamment de la complexité du modèle.<br />Pour parvenir à des résultats exploitables, tant en terme de résolution spatiale que de temps de calcul chez le rat ou la souris, nous décrivons dans ce travail les choix de notre modélisation par une réponse impulsionnelle gaussienne, ajustée suivant des paramètres physiques et géométriques. Nous utilisons ensuite la symétrie de rotation inhérente au dispositif pour ramener le calcul de P opérateurs de projections au calcul d'un seul d'entre eux, par une discrétisation de l'espace compatible avec cette symétrie, tout en contrôlant la densité angulaire de voxels pour éviter un suréchantillonnage au centre du volume.<br />Enfin, nous proposons une nouvelle classe d'algorithmes adaptés à la fréquence qui permettent d'optimiser la reconstruction d'une gamme de fréquence spatiale donnée, évitant ainsi d'avoir à calculer de nombreuses itérations lorsque le spectre à reconstruire se retrouve surtout dans les hautes fréquences.

Cette thèse, fruit d'un contrat de recherche avec Générale des Eaux,<br />porte sur le problème de tournées de service multi-périodes avec fenêtres de temps et flotte limitée. Nous proposons plusieurs méthodes de résolution approchées, ainsi qu'une méthode optimale. La méthode optimale est basée sur la génération de colonnes. Une des méthodes approchées est un algorithme mémétique basé sur une heuristique également développée dans cette thèse. Enfin, la méthode optimale est dérivée en méthode approchée par l'utilisation d'une heuristique pour la résolution du sous-problème.<br />Les algorithmes proposés permettent d'apporter des solutions efficaces à des problèmes comportant jusqu'à 300 clients, dans des temps variant de quelques secondes à quelques dizaines de minutes. Dans un second temps, nous appliquons ces méthodes à des scénarios issus de problématiques réelles, dans une logique d'aide à la décision.

L'objet de cette thèse est l'étude des aspects algorithmiques de l'effet petit monde dans les grands réseaux d'interaction.Les observations expérimentales ont montré que les grands réseaux d'interactions (sociales, informatiques, biologiques), présentaient des propriétés macroscopiques communes. Une d'elles est l'effet petit monde qui consiste en l'existence de chemins très courts entre toutes les paires de noeuds qui peuvent être découverts en n'utilisant qu'une vue locale du réseau. Nous nous intéressons à cette caractéristique algorithmique de l'effet petit monde, à son application au routage informatique décentralisé, et à son émergence dans les réseaux réels.Nous proposons un nouvel algorithme de routage décentralisé sur le modèle aléatoire de petit monde de Kleinberg, qui calcule des chemins de longueur O(log n.(loglog n)^2), asymptotiquement plus courts que ceux des algorithmes existants (en O((log n)^2)). Cet algorithme pourrait également s'appliquer aux réseaux pair-à-pair. Nous précisons cette étude en comparant les charges induites pas les différents algorithmes proposés sur ce modèle.En tentant d'exhiber les caractéristiques minimales d'un graphe qui permettent de l'augmenter en un petit monde par l'ajout de raccourcis aléatoires, nous proposons un nouveau modèle de petit monde qui généralise celui de Kleinberg. Il s'agit d'ajouter une distribution de liens dépendant de la taille des boules de la métrique des distance sous-jacente. Ce modèle peut par ailleurs être étendu simplement pour produire toute distribution des degrés, dont en particulier la fameuse loi de puissance. Enfin, nous proposons le premier schéma distribué qui permette de transformer un réseau de diamètre quelconque en petit monde en ajoutant un seul nouveau lien par noeud, il s'agit d'un premier pas vers la compréhension de l'émergence naturelle du phénomène dans les réseaux réels.

Les travaux présentés dans ce mémoire ont pour objectif d'apporter une contribution au domaine de l'élastodynamique linéaire et plus particulièrement aux méthodes dites de recalage chargées de réconcilier le modèle analytique d'une structure avec les données expérimentales. Les techniques proposées, en matière de réanalyse et d'identification paramétrique, sont susceptibles d'être appliquées à des modèles industriels de grande taille.<br /><br />Première partie : Étude de méthodes de réanalyse approchée de structures mécaniques modifiées<br />Lorsque les paramètres de conception du modèle varient, il est nécessaire d'effectuer une réanalyse afin d'obtenir les solutions propres (modes et fréquences) du système modifié. Une stratégie de réanalyse approchée de type Rayleigh-Ritz est présentée : elle est plus rapide et moins coûteuse qu'une réanalyse exacte, tout en offrant une précision satisfaisante grâce à l'apport des vecteurs de résidus statiques.<br /><br />Deuxième partie : Application d'une méthode évolutionnaire d'optimisation au recalage de modèles<br />Dans cette partie, on propose d'adapter une méthode évolutionnaire au problème de l'identification paramétrique. Inspiré par les principes d'évolution des algorithmes génétiques, son fonctionnement repose sur l'information fournie par une fonction coût représentant la distance entre un modèle recalé et la structure réelle. Des opérateurs heuristiques sont introduits afin de favoriser la recherche des solutions qui minimisent la fonction.<br /><br />Troisième partie : Logiciel Proto–Dynamique<br />Cette partie vise à présenter l'environnement de travail qui a servi à programmer les techniques formulées dans le mémoire et à réaliser les tests numériques. Proto, écrit en langage Matlab, est une plate-forme de développement regroupant des outils d'analyse et des méthodes de recalage.

Dans cette thèse,nous proposons de nouvelles techniques de réduction de variance, pourles simultions Monté Carlo. Par un simple changement de variable, nous modifions la loi de simulation de façon paramétrique. L'idée consiste ensuite à utiliser une version convenablement projetée des algorithmes de Robbins-Monro pour déterminer le paramètre optimal qui "minimise" la variance de l'estimation. Nous avons d'abord développé une implémentation séquentielle dans laquelle la variance est réduite dynamiquement au cours des itératons Monte Carlo. Enfin, dans la dernière partie de notre travail, l'idée principale a été d'interpréter la réduction de variance en termes de minimisation d'entropie relative entre une mesure de probabilité optimale donnée, et une famille paramétrique de mesures de probabilité. Nous avons prouvé des résultats théoriques généraux qui définissent un cadre rigoureux d'utilisation de ces méthodes, puis nous avons effectué plusieurs expérimentations en finance et en fiabilité qui justifient de leur efficacité réelle.

Ce travail est relatif à la contribution d'un modèle théorique pour représenter un PSTM. L'approche est globale et veut pouvoir prendre en considération des objets de tailles inférieures à la longueur d'onde mis en présence de sondes de tailles réalistes. Le modèle développé est bi-dimensionnel et dans cette thèse son application est limité à la polarisation S (TE) en diffraction normale et à hauteur constante. Nous exposons d'abord les bases du modèle mis en oeuvre qui repose sur la méthode différentielle à laquelle sont combinés des algorithmes matriciels. Pour éviter tout problème numérique lorsque le système sonde-objet a des dimensions réalistes (beaucoup supérieure à la longueur d'onde) nous avons utilisé l'algorithme matriciel S. Après avoir défini les critères à satisfaire strictement pour obtenir des performances sûres nous avons appliqué ce modèle aux différents cas suivant : - Sonde monomodes - Sondes multimodes - Sondes structurées (gaine, coeur et éventuellement revêtement métallique externe sont pris en compte). - Spectroscopie d'un objet absorbant inséré dans un couche diélectrique uniforme en proche IR. Tous nos résultats sont cohérents et ouvrent des voies sûres pour l'interprétation des images puisque nous avons montrés que nos calculs étaient en accord qualitatif correct avec des résultats expérimentaux obtenus antérieurement sur des systèmes tests. Dans tous les cas étudiés nous avons montré que la présence de la sonde, quelle que soit sa nature et sa structure, perturbait la distribution du champ électromagnétique rayonné par l'objet. Ceci nous conduit à définir une nouvelles approche de la fonction de transfert en microscopie de champ proche. L'étude encore limitée aux sondes monomodes, montre que la fonction de transfert n'est pas définie dans le cas général. Ce premier travail ouvre des perspectives intéressantes puisque pour la première fois des sondes de formes réelles (incluant apex et taper) et de grandes tailles (jusqu'à 70µm pour la partie guidante) éventuellement métallisées, ont été prises en compte dans un modèle numérique. Il permet aussi d'aborder de façon nouvelle le problème de la fonction de transfert et des images spectroscopiques, y compris en IR. Il est aussi adaptable à la polarisation P (TM)

Cette thèse s'intéresse à des méthodes de points intérieurs et de quasi-Newton en optimisation non linéaire et à leurs mises en oeuvre. On présente le code NOPTIQ utilisant les formules de BFGS à mémoire limitée pour résoudre des problèmes de grande taille. L'originalité de cette approche est l'emploi de ces formules dans le cadre des méthodes de points intérieurs. L'espace mémoire et le coût en opérations du calcul d'une itération sont alors faibles. Le code NOPTIQ est robuste et a des performances comparables avec les codes de références l-BFGS-B et LANCELOT. On présente aussi un algorithme non réalisable utilisant les méthodes précédentes pour résoudre un problème non linéaire avec contraintes d'inégalité et contraintes d'égalité linéaire. L'idée est de pénaliser le problème à l'aide de variables de décalage et d'une variante de la méthode big-M. La convergence q-superlinéaire des itérés internes et la convergence globale des itérés externes sont démontrées.

L'approximation des convexes lisses par des polytopes pour la distance de Hausdorff a connu de nombreux résultats théoriques grâce à l'apport de la géométrie riemannienne. Nous rappelons ces résultats portant principalement sur le comportement asymptotique et montrons leur utilité pour certains cas pratiques. Puis nous établissons notre résultat principal, à savoir que ce problème d'approximation d'un convexe est, en un sens bien précis, équivalent à celui de l'approximation d'une norme par une autre. Nous établissons ensuite les propriétés d'un produit d'approximations de normes, ce qui nous permet de construire par récurrence sur la dimension des polytopes approchant certains convexes lisses, ainsi que des approximations optimales des normes Lp. Enfin nous montrons à travers différentes applications à la géométrie algorithmique en quoi une approximation de norme permet de transformer un algorithme de résolution exacte en un algorithme de résolution approchée mais moins coûteux.

Le but de l'expérience Virgo est la détection des ondes gravitationnelles. L'objet de cette thèse est l'étude de méthodes pour la recherche de signaux émis par des étoiles à neutrons ainsi que l'étalonnage du détecteur.<br> Dans une première partie, l'étoile à neutrons et son émission d'ondes gravitationnelles, sont présentées. Ensuite le détecteur, les principales sources de bruits, ainsi que la solution adoptée pour l'étalonnage sont décrits.<br> Puis dans une seconde partie la modélisation des effets dus aux mouvements de la terre (effet Doppler, modulation d'amplitude) est décrite. Leurs conséquences sur le rapport signal sur bruit sont déterminées.<br> Les deux derniers chapitres sont consacrés aux algorithmes de recherche de signaux périodiques. Tout d'abord le cas où la position de la source est connue est présenté. Le ralentissement de la rotation de la source et la correction de cet effet sont décrits. La correction de l'effet Doppler est aussi détaillée. De même, le problème de la gestion du gigantesque flot de données à traiter est abordé, et une solution y est apportée. Finalement la difficulté de recherche multidirectionnelle est présentée. Des prototypes d'algorithmes hiérarchiques sont aussi évalués.