.

.

Les objets étudiés dans cette thèse sont des algorithmes de calcul de pgcd. Nous effectuons dans cette thèse des analyses probabilistes de plusieurs de ces algorithmes : les algorithmes alpha-euclidiens, l'algorithme LSB et l'algorithme de Lehmer-Euclide. Nous obtenons des résultats précis sur le comportement moyen de toute une gamme de paramètres, entre autres le nombre d'itérations et la complexité en bits. Les techniques employées sont celles de l'analyse dynamique d'algorithmes, et les analyses effectuées dans cette thèse permettent d'élargir le champ d'application de cette méthodologie. En particulier, nous étudions des systèmes dynamiques à branches non surjectives, des systèmes dynamiques définis sur l'ensemble des nombres p-adiques ou encore des systèmes de fonctions itérées. Ces analyses impliquent une étude très précise des opérateurs de Perron-Frobenius et des opérateurs de transfert associés à ces systèmes. En particulier, le comportement probabiliste des algorithmes est relié aux propriétés spectrales de ces opérateurs. Nous analysons également l'évolution des principaux paramètres des algorithmes au cours de leur execution.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse comporte deux parties. La première est consacrée à l'étude de quelques problèmes inverses de détection et de localisation d'obstacles ou de sources à l'aide d'un miroir à retournement temporel (MRT), appareil pouvant rétro-propager des ondes sur la source qui les a émises. Nous commençons par la méthode DORT qui permet de focaliser sélectivement des ondes sur des petits obstacles. Nous étudions numériquement en acoustique les résultats mathématiques obtenus par C. Hazard et K. Ramdani et étendons mathématiquement ces résultats au cas de l'électromagnétisme. Puis, nous nous intéressons à la reconstruction d'une source acoustique ponctuelle avec un MRT. Dans un contexte déterministe, nous proposons des simulations numériques attestant du phénomène de super-résolution, c'est-à-dire l'amélioration en moyenne de la qualité de la focalisation dans un milieu hétérogène plutôt qu'homogène. La deuxième partie a pour objet la résolution numérique par équations intégrales du problème de diffraction multiple en acoustique, c'est-à-dire en présence de nombreux obstacles. D'une part, nous montrons que le préconditionneur prenant en compte les effets de la diffraction simple (interaction d'un objet avec lui-même) a la propriété intéressante de rendre toutes les équations intégrales semblables. D'autre part, pour des obstacles circulaires, nous calculons explicitement les coefficients de Fourier des quatre opérateurs intégraux usuels. Ceci nous permet de proposer une méthode de résolution numérique robuste et efficace et, de plus, d'étudier numériquement le spectre de l'opérateur intégral de simple couche en régime basse fréquence dans un milieu dilué et dans un milieu dense. / This thesis is divided into two parts. The first one deals with some inverse problems related to the detection and localization of targets using a Time Reversal Mirror (TRM), which can back-propagate a signal on the source that emitted it. We first study the DORT method, a technique used to focus waves selectively on small scatterers. In the context of acoustic scattering, a numerical investigation of the mathematical results obtained by C. Hazard and K. Ramdani is proposed. These results are then mathematically extended to the electromagnetic case. To conclude this part, we investigate numerically the reconstruction of an acoustic point source with a TRM. By using a deterministic model, we provide numerical examples that illustrate the super-resolution phenomena, that is, the enhancement in average of the quality of focusing in an heterogeneous medium compared to an homogeneous one. The second part is devoted to the numerical solution of acoustic multiple scattering problems using integral equations. Multiple scattering means that the medium contains at least two scatterers. We first study the preconditioner which takes into account the single scattering (self-interaction) effects. Then, we show that all the so-preconditioned integral equations are identical, up to an invertible operator. Afterwards, for circular scatterers, we analytically compute the Fourier coefficients of the four classical boundary integral operators. Thus, we propose on the one hand an efficient and robust numerical method and on the other hand a numerical investigation of the spectrum of the single-layer boundary integral operator in the low frequency regime for a dense medium and a dilute one.

Le renouveau actuel du vocabulaire formel dans l’univers des architectures dites « non standards » s’appuie largement sur l’utilisation de modeleurs tridimensionnels. Dans cette démarche de conception, la stratégie de modélisation d’objets relève moins de l’utilisation directe de la géométrie que de la formalisation d’une idée. En effet, le travail de recherche morphologique, de la forme idée à la forme visée, nécessite de nombreux ajustements incompatibles avec une démarche linéaire de modélisation géométrique. Nous émettons l’hypothèse que la genèse des formes résulte d’opérations successives de transformation de forme fondées sur des objectifs sémantiques et guidées par une ou plusieurs images mentales. Ce cheminement se fait par des variations importantes entre différents états de la forme et par de nombreux ajustements de cette forme. Pour répondre à ce processus itératif nous proposons une approche paramétrique de la modélisation qui s’appuie sur des modificateurs de forme de haut niveau. Nous nommons opérateurs morphologiques ces outils d’action sur la forme qui permettent à partir d’une fonction de transformation morphologique (bomber, torsader, plisser…) de trouver par différentes solutions alternatives et par ajustement une forme satisfaisante. Notre travail aborde plus spécifiquement les opérateurs plier, plisser, froisser / The current renewal of formal vocabulary in the world of architecture, so-called “non-standard”, relies heavily on the use of three-dimensional modelers. In this design strategy, object modeling falls under the direct use of geometry as the formalization of an idea. Indeed work with such forms requires many adjustments incompatible with linear geometric modeling. We assume that the genesis of forms results from successive operations processing form that are founded on semantic objectives and guided by one or more mental images. This semantic path is a variation between different states of the form and numerous adjustments to the form. To formalize this iterative process, we propose a parametric approach based on high level modifiers of form. Morphological operators are action tools that allow finding a satisfactory form through a morphological transformation (bulging, twisting, pleating…) and adjustment. Keywords : morphological operator, 3D design, architectural conception

Ce mémoire présente plusieurs résultats d'analyse spectrale, qui s'appuient pour la plupart sur le principe variationnel du min-max. L'objectif principal est d'établir une formule de type Weyl pour certains opérateurs de Schrôdinger . Cette formule, emblématique de l'analyse semi-classique , établit une correspondance entre la fonction de comptage du spectre et le volume dans l'espace des phases des trajectoires du système classique sous-jacent. Les cas considérés concernent des opérateurs pour lesquels ce volume est infini, de sorte qu'il est nécessaire de trouver une alternative à cette formule. Il est fait également mention d'un problème classique de bouteille magnétique , qui est à la source des travaux ultérieurs.

Cette thèse porte sur la résolution numérique de systèmes d'équations non-linéaires. Elle présente des contributions dans trois sous-domaines utilisant le calcul par intervalles : l'analyse par intervalles, les intervalles modaux et la programmation par contraintes. Le traitement des systèmes linéaires est au centre de plusieurs des travaux. Il sert notamment de base à la résolution dans le cas non-linéaire. En analyse par intervalles, nous proposons une extension de la méthode de Hansen-Bliek pour l'approximation extérieure optimale de l'ensemble des solutions d'un système linéaire dont les coefficients varient dans des intervalles. L'extension proposée prend en compte la possibilité de choisir le quanticateur (existentiel ou universel) associé à certains coefficients du système. Cette liberté permet de modéliser un plus large éventail de problèmes linéaires, notamment ceux obtenus itérativement à partir de l'opérateur de Newton (intervalle) généralisé. Une généralisation de la décomposition LU exploitant l'arithmétique de Kaucher est également proposée. Sur les intervalles modaux, nous proposons une construction originale de la théorie qui s'articule autour de la notion d'image quantiée, généralisation naturelle de la notion d'image d'une fonction. La construction proposée présente certains avantages, comme celui de pouvoir donner un sens plus concret à l'arithmétique de Kaucher. En programmation par contraintes, nous étudions de nouvelles cohérences partielles reposant sur la structure d'unions d'intervalles. Cette structure peut être utilisée pour représenter plus nement le domaine des variables dans des systèmes de contraintes numériques. Nous montrons notamment dans quelle mesure, et à quel coût, la propriété d'arc-cohérence peut ainsi être obtenue grâce à cette nouvelle représentation.

Le modèle de dimères est un système de mécanique statistique qui modélise l'adsorption de molécules diatomiques sur la surface d'un cristal, représenté par un réseau périodique plan biparti. On attribue à chaque type d'arête une énergie. Pour une telle distribution d'énergie, il existe une famille à deux paramètres de mesures de Gibbs, dont les comportements sont classifiés en trois phases : gazeuse, liquide, solide.<br /><br />Dans la première partie, on étudie le comportement d'un tel système près de la transition liquide-solide. En examinant le cas du réseau hexagonal, nous exhibons deux types de comportements limites. Le premier est une collection de chemins aléatoires conditionnés à s'éviter. Le deuxième, le modèle du collier de perles, est un processus ponctuel sur ZxR. Ces deux modèles limites ont pour marginales le processus déterminantal sur R avec noyau sinus, décrivant aussi les valeurs propres des grandes matrices aléatoires de l'ensemble GUE. Le modèle du collier de perles est universel : on montre qu'il est la limite de tout modèle de dimères sur un graphe planaire biparti périodique.<br /><br />Dans une deuxième partie, on étudie la statistique des motifs dessinés par des dimères. Les fluctuations de densité d'un motif convergent à la limite d'échelle vers un champ gaussien. Dans le cas liquide, l'objet limite est la somme d'une dérivée du champ libre et d'un bruit blanc indépendant. Pour une mesure gazeuse, la limite est juste un bruit blanc.<br /><br />Enfin, on aborde un problème de dénombrement de chemins sur le graphe-échelle, lié à l'étude du noyau de la chaleur sur le groupe de l'allumeur de réverbères, ainsi qu'à celle des opérateurs de Schrödinger aléatoires.

Dans la première partie, nous nous intéressons à des opérateurs dont le spectre est inclus dans le cercle unité $\bbt$. Nous obtenons des résultats concernant certaines propriétés de croissance des normes $\| T^{-n} \| \, (n \geq 0)$ pour des opérateurs $T$ dont le spectre est dénombrable ou vérifie certaines conditions géométriques. Pour obtenir ces résultats, nous sommes amenés à travailler dans les espaces de fonctions<br />$$<br />A_{\omega}(\bbt) = \Big\{ f \textrm{ continue sur } \bbt : \, \big\| f \big\|_{\omega} = \sum_{n = -\infty}^{+\infty} | \widehat{f}(n) | \omega(n) < +\infty \Big\},<br />$$<br />où $\omega = \big( \omega(n) \big)_{n \in \bbz}$ est une suite de réels strictement positifs, et $\widehat{f}(n)$ désigne le $\textrm{n}^{\textrm{ième}}$ coefficient de Fourier de $f$. Lorsque la suite $\omega = \big( \omega(n) \big)_{n \in \bbz}$ est un poids, $\big( A_{\omega}(\bbt), \| \, \|_{\omega} \big)$ est une algèbre de Banach. Nous obtenons alors la caractérisation de certains idéaux fermés de $A_{\omega}(\bbt)$ pour une famille de poids. <br /><br />Dans la seconde partie, nous nous intéressons à des fermés de $\bbt$ qui sont (ou non) des ensembles d'unicité pour des espaces $\dsp A_{\omega}^{+}(\bbt) = \Big\{ f \in A_{\omega}(\bbt): \, \widehat{f}(n) = 0 \quad (n < 0) \Big\}$, où $\omega = \big( \omega(n) \big)_{n \in \bbz}$ est une suite de réels strictement positifs. Un fermé $E$ de $\bbt$ étant d'unicité pour un espace $X $ de fonctions continues sur $\bbt$, si la seule fonction dans $X$ s'annulant sur $E$ est la fonction nulle. Plus précisément, nous étudions le lien qu'il y a entre le fait qu'un fermé de $\bbt$ satisfait une condition géométrique donnée et le fait qu'il soit ou non un ensemble d'unicité pour $A_{\omega}^{+}(\bbt)$.