No description available.

This thesis focuses on range searching data structures, an elementary problem in computational geometry with research spanning decades. These problems often involve very large data sets. Processor speeds increase faster than memory speeds, thus the gap between the rate at which CPUs can process data and the rate at which it can be retrieved is increasing. To bridge this gap, various levels of cache are used. Since cache misses are costly, algorithms should be cache-friendly. The input-output (I/O) model was the first model for constructing cache-efficient algorithms, focusing on a two-level memory hierarchy. Algorithms for this model require manual tuning to determine optimal values for hardware dependent parameters, and are only optimal at a single level of a memory hierarchy. Cache-oblivious (CO) algorithms are built without knowledge of the hierarchy, allowing them to be optimal across all levels at once. There exist strong theoretical and practical results for I/O-efficient range searching. Recently, the CO model has received attention, but range searching remains poorly understood. This thesis explores data structures for CO range counting and reporting. It presents the first space and worst-case query-time optimal approximate range counting structure for a family of related problems, and associated O(N log N)-space query-optimal reporting structures. The approximate counting structure is the first of its kind in internal memory, I/O and CO models. Researchers have been trying to create linear-space query-optimal CO reporting structures. This thesis shows that for a variety of problems, linear space is in fact impossible. Heuristics are also used for building cache-friendly algorithms. Space-filling curves are continuous functions mapping multi-dimensional sets into one-dimensional ones. They are used to build search structures in the hopes that objects that were close in the original space remain close in the resulting ordering. This results in queries incurring fewer page swaps when traversing the structure. The Hilbert curve is notably good at this, but often imposes a space or time penalty. This thesis introduces compact Hilbert indices, which remove the ineffiency inherent for input point sets with bounding boxes smaller than their bounding hypercubes.

L'équation de Weinstein á coefficients complexes est une équation régissant les Potentiels á Symétrie Axiale (PSA) qui s'écrit $L_m[u]=\Delta u+\left(m/x\right)\d_x u =0$, oú $m\in\C$. Cette équation intervient notamment pour la modélisation du bord du plasma dans un Tokamak pour $m=-1$, ou encore elle est, lorsque $m=1$, appelée équation de Ernst linéarisée (équation permettant de donner explicitement des solutions aux équations d'Einstein). Ici, on généralise des résultats connus pour $m\in \R$ au cas $m\in\C$ (on donne des expressions explicites de solutions fondamentales aux opérateurs de Weinstein et leurs estimations au voisinage des singularités, puis on démontre une formule de Green pour les PSA dans le demi-plan droit $\H^+$ pour Re $m< 1$). On prouve un nouveau théoréme de décomposition des PSA dans des domaines annulaires quelconques pour $m\in\C$ et dans une géométrie annulaire particuliére faisant intervenir les coordonnées bipolaires, on prouve toujours pour $m\in\C$ qu'une famille de solutions des PSA en termes de fonctions de Legendre Associées de premiére et seconde espéce forme une famille compléte (par une méthode de quasi-séparabilité des variables et par une analyse de Fourier) permettant d'exprimer les PSA sous forme de série et lorsque $m\in \R$, on montre que cette famille est même une base de Riesz dans certains anneaux á bord circulaire non concentrique. Dans une deuxiéme partie, par une méthode qui est due á A. S. Fokas, on donne, sous forme intégrale explicite, des formules des PSA dans un domaine circulaire du demi-plan droit $\H^+$, dans le cas oú le paramétre $m$ est un entier relatif. Ces représentations sont obtenues par la résolution d'un probléme de Riemann-Hilbert sur le plan complexe ou sur une surface de Riemann á deux feuillets selon la parité du coefficient $m$. Ces formules font intervenir de façon explicites les données Dirichlet et Neumann des PSA. On montre aussi que cette méthode s'applique á tous les domaines simlement connexe de $\H^+$ á bord régulier. Dans la derniére partie, on étudie une classe de fonctions qui englobe les PSA, ce sont les fonctions pseudo-holomorphes, {\it i. e.} les solutions de l'équation $\bar\d w=\alpha\overline{w}$. avec $\alpha\in L^r$, $2\leq r<\infty$. Un résultat qui semble être le tout premier de son genre a été obtenu, c'est une extension de la régularité du principe de similarité (décomposition des fonction pseudo-holomorphe sous la forme $e^s F$ sous certaines hypothéses de régularités et oú $F$ est une fonction holomorphe) et une réciproque de ce principe qui conduit á un paramétrage analytique de cette classe de fonctions dans le cas critique $r=2$. Puis en utilisant la connexion entre les fonctions pseudo-holomorphes et les solutions de l'équation de Beltrami conjuguée, on résoud un probléme de Dirichlet á données $L^p$ pondérées sur des domaines lisses pour des équations du type conductivité á coefficient dont le log appartient á l'espace de Sobolev $W^{1,2}$.

Le contrôle de santé structural ou Structural Health Monitoring (SHM) des matériaux constitue une démarche fondamentale pour la maîtrise de la durabilité et de la fiabilité des structures en service. Au-delà des enjeux industriels et humains qui ne cessent de s'accroître en termes de sécurité et de fiabilité, le contrôle de santé doit faire face à des exigences de plus en plus élaborées. Les nouvelles stratégies de contrôle de santé doivent non seulement détecter et identifier l'endommagement mais aussi quantifier les différents phénomènes qui en sont responsables. Pour atteindre cet objectif, il est nécessaire d'accéder à une meilleure connaissance des processus d'endommagement. Par ailleurs, ceux-ci surviennent fréquemment sous l'effet de sollicitations mécaniques et environnementales. Ainsi, il est indispensable, d'une part, d'élaborer des méthodes de traitement des signaux permettant d'estimer les effets des conditions environnementales et opérationnelles, dans un contexte de l'analyse des événements précurseurs des mécanismes d'endommagement, et, d'autre part, de définir les descripteurs d'endommagement les plus adaptés à cette analyse. Cette étude propose donc des méthodes de traitement du signal permettant d'atteindre cet objectif, dans un premier temps, pour l'estimation des effets externes sur les ondes multidiffusées dans un contexte de contrôle de santé actif et, dans un second temps, pour l'extraction d'un indicateur d'endommagement à partir de l'analyse des signaux d'émission acoustique dans un contexte de contrôle de santé passif. Dans la première partie de ce travail, quatre méthodes de traitement du signal sont proposées. Celles-ci permettent de prendre en compte les variations des conditions environnementales dans la structure, qui dans le cadre de cette thèse, se sont limitées au cas particulier du changement de la température. En effet, les variations de température ont pour effet de modifier les propriétés mécaniques du matériau et par conséquent la vitesse de propagation des ondes ultrasonores. Ce phénomène entraîne alors une dilatation temporelle des signaux acoustiques qu'il convient d'estimer afin de suivre les variations de température. Quatre estimateurs de coefficients de dilatation sont alors étudiés : Il s'agit de l'intercorrélation à fenêtre glissante, utilisée comme méthode de référence, la méthode du stretching, l'estimateur à variance minimale et la transformée exponentielle. Les deux premières méthodes ont été déjà validées dans la littérature alors que les deux dernières ont été développées spécifiquement dans le cadre de cette étude. Par la suite, une évaluation statistique de la qualité des estimations est menée grâce à des simulations de Monte-Carlo utilisant des signaux de synthèse. Ces signaux sont basés sur un modèle de signal multidiffusé prenant en compte l'influence de la température. Une estimation sommaire de la complexité algorithmique des méthodes de traitement du signal complète également cette phase d'évaluation. Enfin, la validation expérimentale des méthodes d'estimation est réalisée sur deux types de matériaux : Tout d'abord, dans une plaque d'aluminium, milieu homogène dont les caractéristiques sont connues, puis, dans un second temps dans un milieu fortement hétérogène prenant la forme d'une plaque composite en verre/epoxy. Dans ces expériences, les plaques sont soumises à différentes températures dans un environnement thermique contrôlé. Les estimations de température sont alors confrontées à un modèle analytique décrivant le comportement du matériau. La seconde partie de ce travail concerne la caractérisation in situ des mécanismes d'endommagement par émission acoustique dans des matériaux hétérogènes. Les sources d'émission acoustique génèrent des signaux non stationnaires...

Cette thèse présente quelques résultats sur la théorie locale pour les espaces de Banach et d'opérateurs. La première partie consiste en l'étude de la propriété $\text{OUMD}$ pour l'espace colonne $C$. La deuxième partie traite de la propriété $\text{UMD}$ classique pour les espaces $L_p(L_q)$ itérés. Le résultat principal donne une construction nouvelle et très naturelle de treillis de Banach qui sont super-réflexifs et non-$\text{UMD}$: L'espace $L_p(L_q(L_p(L_q(\cdots$ itéré une infinité de fois est super-réflexif si $1 < p, q < \infty$ mais n'est pas $\text{UMD}$ si $p \ne q$.

Pour toute variété affine W munie d'une opération d'un groupe réductif G, le schéma de Hilbert invariant est un espace de modules qui classifie les sous-schémas fermés de W, stables par l'opération de G, et dont l'algèbre affine est somme directe de G-modules simples avec des multiplicités finies préalablement fixées. Dans cette thèse , on étudie d'abord le schéma de Hilbert invariant, noté H, qui paramètre les sous-schémas fermés GL(V)-stables Z de W=n1 V oplus n2 V^* tels que k[Z] est isomorphe à la représentation régulière de GL(V) comme GL(V)-module. Si dim(V)<3,on montre que H est une variété lisse, et donc que le morphisme de Hilbert-Chow gamma: H -> W//G est une résolution des singularités du quotient W//G. En revanche, si dim(V)=3, on montre que H est singulier. Lorsque dim(V)<3, on décrit H par des équations et aussi comme l'espace total d'un fibré vectoriel homogène au dessus d'un produit de deux grassmanniennes. On se place ensuite dans le cadre symplectique en prenant n1=n2 et en remplaçant W par la fibre en 0 de l'application moment mu: W -> End(V). On considère alors le schéma de Hilbert invariant H' qui paramètre les sous-schémas contenus dans mu^{-1}(0). On montre que H' est toujours réductible, mais que sa composante principale Hp' est lisse lorsque dim(V)<3. Dans ce cas, le morphisme de Hilbert-Chow est une résolution (parfois symplectique) des singularités du quotient mu^{-1}(0)//G. Lorsque dim(V)<3, on décrit Hp' comme l'espace total d'un fibré vectoriel homogène au dessus d'une variété de drapeaux. Enfin, on obtient des résultats similaires lorsque l'on remplace GL(V) par un autre groupe classique (SL(V), SO(V), O(V), Sp(V)) que l'on fait opérer d'abord dans W=nV, puis dans la fibre en 0 de l'application moment.

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-10T18:13:32Z No. of bitstreams: 1 ROMERO ALVES DE MELO - DISSERTAÇÃO PPGMAT 2006..pdf: 1038740 bytes, checksum: d9fd10d289c6cf822fe688e743b58356 (MD5) / Made available in DSpace on 2018-07-10T18:13:32Z (GMT). No. of bitstreams: 1 ROMERO ALVES DE MELO - DISSERTAÇÃO PPGMAT 2006..pdf: 1038740 bytes, checksum: d9fd10d289c6cf822fe688e743b58356 (MD5) Previous issue date: 2006-12 / Capes / Neste trabalho usaremos a Teoria de Semigrupos para demonstrar resultados de existência e unicidade de solução para Equações Diferenciais Ordinárias, em espaços de Banach. Usando esta teoria resolvemos problemas de valor inicial, com relação a equação do calor e a equação da onda. (Para visualizar a equação ou fórmula deste resumo recomendamos o download do arquivo). / In this work we use semigroup theory to prove some results of existence and unicity for a class Ordinary Differential Equation, on Banach spaces. Using this tool, we show the existence of solutions for wave and heat equations. (To visualize the equation or formula of this summary we recommend downloading the file).

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.

Neste trabalho estudamos os homomorfismos entre anéis de polinômios do ponto de vista da teoria de bases de Groebner. Em particular, determinamos o núcleo de um tal homomorfismo e desenvolvemos um método para determinar quando este é sobrejetivo. Estes resultados são então generalizados para anéis quocientes. O estudo de tais homomorfismos nos permite determinar os polinômos minimais de elementos em extensões de corpos, bem como encontrar soluções para um problema de programação inteira. / In this work we study the homomorphisms between polynomial rings as an application of the Groebner basis theory. In particular, we determine generators for the kemel of such a homomorphism and we give a method to determine whether it is onto. We then generalize these results to the case of quocient rings. The study of these homomorphisms allows us to determine mini mal polynomials of elements in field extensions, as well as to find solutions to an integer programming problem.