Les polynômes orthogonaux sont introduits par la théorie de Sturm-Liouville, puis les équivalences existantes entre leurs définitions classiques sont montrées. Certains résultats de base de la théorie sont ensuite décortiqués. On termine en introduisant des résultats préliminaires de la théorie analytique des polynômes, qui étudie les liens entre les coefficients d'un polynôme, ses zéros et ses points critiques.

Déterminer le groupe de Galois d’un polynôme rationnel ou encore d’une extension de corps n’est pas, en général, un travail de tout repos s’il est effectué manuellement. La difficulté de ce problème nous amène donc à vouloir automatiser le processus à l’aide d’algorithmes qui prennent le polynôme en entrée et ressortent son groupe de Galois en un temps raisonnable. Le présent mémoire a pour but de mettre la lumière sur deux algorithmes connus tout en présentant les résultats nécessaires pour les comprendre et les reproduire. Le tout est ensemencé d’exemples pour aider à comprendre certaines notions utilisées. Dans un niveau d’ordre un peu différent, nous analysons une particularité du deuxième algorithme, c’est-à-dire la provenance des polynômes à plusieurs variables utilisés lors de la construction de la résolvante du polynôme dont nous voulons trouver le groupe de Galois.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

.

L’optimisation est un sujet très important dans tous les domaines. Cependant, parmi toutes les applications de l’optimisation, il est difficile de trouver des exemples de systèmes à optimiser qui ne comprennent pas un certain niveau d'incertitude sur les valeurs de quelques paramètres. Le thème central de cette thèse est donc le traitement des différents aspects de l’optimisation en présence d’incertitudes. Nous commençons par présenter un bref état de l’art des méthodes permettant de prendre en compte les incertitudes dans l’optimisation. Cette revue de la littérature a permis de constater une lacune concernant la caractérisation des propriétés probabilistes du point d’optimum de fonctions dépendant de paramètres aléatoires. Donc, la première contribution de cette thèse est le développement de deux méthodes pour approcher la fonction densité de probabilité (FDP) d’un tel point : la méthode basée sur la Simulation de Monte Carlo et la méthode de projection en dimension finie basée sur l’Approximation par polynômes de chaos. Les résultats numériques ont montré que celle-ci est adaptée à l’approximation de la FDP du point optimal du processus d'optimisation dans les situations étudiées. Il a été montré que la méthode numérique est capable d’approcher aussi des moments d'ordre élevé du point optimal, tels que l’aplatissement et l’asymétrie. Ensuite, nous passons au traitement de contraintes probabilistes en utilisant l’optimisation fiabiliste. Dans ce sujet, une nouvelle méthode basée sur des coefficients de sécurité est développée. Les exemples montrent que le principal avantage de cette méthode est son coût de calcul qui est très proche de celui de l’optimisation déterministe conventionnelle, ce qui permet son couplage avec un algorithme d’optimisation globale arbitraire. / The optimization is a very important tool in several domains. However, among its applications, it is hard to find examples of systems to be optimized that do not possess a certain uncertainty level on its parameters. The main goal of this thesis is the treatment of different aspects of the optimization under uncertainty. We present a brief review of the literature on this topic, which shows the lack of methods able to characterize the probabilistic properties of the optimum point of functions that depend on random parameters. Thus, the first main contribution of this thesis is the development of two methods to eliminate this lack: the first is based on Monte Carlo Simulation (MCS) (considered as the reference result) and the second is based on the polynomial chaos expansion (PCE). The validation of the PCE based method was pursued by comparing its results to those provided by the MCS method. The numerical analysis shows that the PCE method is able to approximate the probability density function of the optimal point in all the problems solved. It was also showed that it is able to approximate even high order statistical moments such as the kurtosis and the asymmetry. The second main contribution of this thesis is on the treatment of probabilistic constraints using the reliability based design optimization (RBDO). Here, a new RBDO method based on safety factors was developed. The numerical examples showed that the main advantage of such method is its computational cost, which is very close to the one of the standard deterministic optimization. This fact makes it possible to couple the new method with global optimization algorithms.

Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de noeuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique / In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic

Le théorème d'uniformisation locale est un résultat important en théorie des singularités. Connu en caractéristique nulle, il reste ouvert en caractéristique positive. Dans cette thèse, nous donnons une version simultanée de ce théorème en caractéristique nulle. On considère R un anneau local régulier muni d'une valuation centrée en son idéal maximal. Nous démontrons l'uniformisation locale par monomialisation simultanée des éléments de R. La preuve apportée ici est nouvelle et riche de trois choses : tout d'abord, nous monomialisons tous les éléments avec la même suite d'éclatements. De plus, cette suite est explicite et nous connaissons les coordonnées pas à pas. Pour finir, nous ne faisons aucune supposition sur le rang de la valuation. Afin de faire cela, nous utilisons une théorie intimement liée à la théorie des valuations : celle des éléments clefs, une généralisation des polynômes clefs, qui est détaillée dans le deuxième chapitre du manuscrit. On y donne une nouvelle définition des polynômes clefs et on étudie leur rapport précis avec les polynômes clefs de MacLane et Vaquié. Enfin, le dernier chapitre est dédié à un cadre plus général : celui des anneaux locaux d'équicaractéristique nulle quasi-excellents intègres. Dans ce cas, la théorie des éléments clefs, bien que nécessaire, n'est plus suffisante. Il nous faudra utiliser l'idéal premier implicite H d'un tel anneau R et montrer que l'on peut réduire l'étude à la régularisation du quotient du complété de R par H. / The local uniformization theorem is an important result in theory of singularities. Known in characteristic zero, it is an open problem in positive characteristic. In this thesis, we give a simultaneous version of this theorem in zero characteristic. We consider a regular local ring R with a valuation centered in its maximal ideal. We prove the local uniformization theorem by monomializing simultaneously the elements of R. The proof given is new and rich in three respects : first, we monomialize every element with the same sequence of blow-ups. Furthermore, this sequence is explicit and we know the coordinates at each step. In addition, the construction is independent of any hypothesis on the rank of the valuation. To this end, we use a theory intimately linked to that of valuations based on the notion of key elements, a generalization of key polynomials, which is explained in detail in the second chapter of this manuscript. We give a new definition of key polynomials and we study their precise relation with key polynomials of Mac Lane and Vaquié. The last chapter is devoted to the more general framework of local quasi-excellent domains of equicharacteristic zero. In this case, although still necessary, the theory of key elements is no longer sufficient. We need to use the implicit prime ideal H of such a ring R and show that the problem can be reduced to the desingularisation of the quotient of the completion of R by H.

Dans cette thèse nous étudions les algèbres des polynômes qui sont bornés sur un ensemble semi-algébrique non borné. Tout d'abord nous abordons le problème consistant à déterminer si un polynôme est borné sur un ensemble. Nous résolvons ce problème pour les polynômes à deux variables définis sur des ensembles semi-algébriques quelconques. Dans la section suivante nous donnons une méthode pour déterminer des générateurs de l'algèbre des polynômes bornés et ce pour une large classe de semi-algébriques du plan réel. Dans la section 3 nous établissons une relation entre les valeurs de bifurcation du complexifié d'un polynôme $f$ à deux variables et la stabilité de la famille d'algèbres des polynômes bornés sur les ensembles ${fle c}$. Dans la section 4 nous décrivons la structure de l'algèbre des polynômes bornés sur un certain type de sous-ensembles de $mathbb{R}^n$ avec $n$ arbitraire, que nous appelons tentacules pondérées. Nous donnons aussi une preuve géométrique du fait que l'algèbre d'un sous-ensemble non borné d'un ensemble algébrique propre n'est pas de type fini. Dans la section suivante nous établissons une correspondance entre les cônes convexes et les algèbres des ensembles obtenus par des inégalités sur des monômes appropriés. Enfin, nous démontrons une version du Positivstellensatz de Schmudgen pour les polynômes bornés sur un ensemble non compact. / The main topic of the thesis is a study of algebras of polynomials which are bounded on a given unbounded semialgebraic set. First we tackle the problem of deciding the boundedness of a polynomial on a set. We achieve it for polynomials in two variables for any semialgebraic set. We give also a method of finding generators of the algebra of bounded polynomials for a large class of semialgebraic subsets of the real plane. In Section 3 we have established a relation between bifurcation values of a complexification of polynomial $f$ in two variables and the family of algebras of bounded polynomials on the sets ${fle c}$. In section 4 we describe the algebras of bounded polynomials for subsets of $mathbb{R}^n$, where $n$ is arbitrary, which we call weighted tentacles. We also provide a geometric proof of the fact that for a unbounded subset of a proper algebraic set its algebra cannot be finitely generated. In the next section we establish a correspondence between convex cones and algebras of bounded polynomials on the sets described by monomial inequalities. At the end of this thesis we prove a version of Schmudgen's Positivstellensatz for bounded polynomials.