Une série de Tchebychev est un développement dans la base des polynômes de Tchebychev. Ces séries sont importantes en théorie de l'approximation. Contrairement aux séries de Taylor, l'algorithmique en calcul formel autour d'elles n'est pas très développée. Cette thèse propose de nouveaux algorithmes pour ces séries. Une première partie présente des algorithmes rapides pour convertir une série de Tchebychev tronquée en une série de Taylor tronquée et réciproquement, et pour multiplier ou diviser deux séries de Tchebychev tronquées. Le reste de la thèse porte sur les séries de Tchebychev solutions d'une équation différentielle linéaire à coefficients polynomiaux. Dans cette classe, les coefficients des séries sont solutions d'une récurrence linéaire. Cette thèse montre comment calculer cette récurrence efficacement, puis comment l'utiliser pour obtenir un calcul approché efficace des coefficients malgré des instabilités numériques. Ces algorithmes mènent au calcul efficace d'une approximation sur un segment par un polynôme de degré fixé d'une fonction solution d'une équation différentielle linéaire. Enfin, le calcul des récurrences pour les coefficients de séries est généralisé au cas des séries de Fourier généralisées. L'ensemble est illustré d'exemples à partir de programmes développés durant cette thèse.

In 2003 Cohn and Umans introduced a new group-theoretic framework for doing fast matrix multiplications, with several conjectures that would imply the matrix multiplication exponent $\omega$ is 2. Their methods have been used to match one of the fastest known algorithms by Coppersmith and Winograd, which runs in $O(n^{2.376})$ time and implies that $\omega \leq 2.376$. This thesis discusses the framework that Cohn and Umans came up with and presents some new results in constructing combinatorial objects called uniquely solvable puzzles that were introduced in a 2005 follow-up paper, and which play a crucial role in one of the $\omega = 2$ conjectures.

The focus of this dissertation is the advancement of theory and computation related to exact precision mathematical programming. Optimization software based on floating-point arithmetic can return suboptimal or incorrect resulting because of round-off errors or the use of numerical tolerances. Exact or correct results are necessary for some applications. Implementing software entirely in rational arithmetic can be prohibitively slow. A viable alternative is the use of hybrid methods that use fast numerical computation to obtain approximate results that are then verified or corrected with safe or exact computation. We study fast methods for sparse exact rational linear algebra, which arises as a bottleneck when solving linear programming problems exactly. Output sensitive methods for exact linear algebra are studied. Finally, a new method for computing valid linear programming bounds is introduced and proven effective as a subroutine for solving mixed-integer linear programming problems exactly. Extensive computational results are presented for each topic.

This thesis presents a unified framework for the analysis of instantaneous kinematics and statics of spatial manipulators. The proposed formulation covers the entire range of kinematic behavior, with kinematic singularity and isotropy appearing as special cases. An analogous treatment of statics is also presented. It is established that the formulations presented are capable of generating exact solutions in closed form for several interesting problems in manipulator analysis. Several such results have been obtained via extensive usage of symbolic computation tools developed for this purpose. The proposed approach is applicable to manipulators of different architectures. However, the focus is on the parallel and hybrid manipulators, as their analysis presents more challenges than their serial counterparts. The theory of screws has been adopted as the basis of the formulation. Instantaneous kinematics and statics are studied in terms of the principal bases of the space of twists, se(3), and the space of wrenches, se* (3), respectively. A dual number parameterisation of the motion space is adopted to make the formulation compact and dimensionally consistent. The properties of the dual combination obviate the need for an explicit scaling between the linear and angular velocities or the forces and moments. Hence the results obtained from the formulation are purely geometrical. The analysis of the twists is performed via the dual velocity Jacobian matrix. The principal basis of se(3) is obtained from the eigenproblem of a symmetrical dual matrix associated with the Jacobian. The notion of a dual eigenproblem is introduced in this context. Solutions are provided for the general case, as well as a few special cases. The computations involve the solution of at most a cubic equation for any arbitrary degree-of-freedom of rigid-body motion, and closed form results are therefore ensured. The results of the eigen-analysis lead to a decoupling of the rotational and the pure translational components of a rigid-body motion. This is termed as the partitioning of degrees-of-freedom. They also motivate an interesting classification of the manipulators based on the instantaneous partition of its degrees-of-freedom. This notion is further extended to analyse the effects of a singularity on the motion characteristics of a manipulator. Due to the duality of se(3) and se*(3), the formulation of statics is completely analogous, and involves, in essence, only the substitution of the dual wrench-transformation matrix for the dual Jacobian. A similar partitioning of the wrench system is introduced based on the eigen-decomposition in the context of statics. It is shown that the principal screws associated with either a system of twists or wrenches can be obtained from a generalised eigenproblem of two symmetric real matrices arising out of the symmetric dual matrix mentioned above. The general 2-and 3-screw systems are analysed in closed form via the generalised characteristic polynomial. Several special screw systems are described in terms of algebraic equations in terms of the coefficients of this polynomial. Principal bases for 4-and 5-systems are obtained in a novel fashion without deriving their reciprocal systems explicitly. Using the same approach based on the analysis of the characteristic polynomial, compact algebraic conditions for singularity and isotropy are derived as the special cases of a single formulation. The above formulations establish the existence of exact closed-form results. However, to implement them symbolically for a real application problem, capabilities in existing computer algebra systems do not suffice in general. Therefore simplification and computational algorithms are developed for dealing with large expressions with algebraic and trigonometric terms typically appearing in kinematics and statics. Three canonical forms of such expressions and the corresponding simplification schemes are presented. The theoretical developments are illustrated with examples of serial, parallel and hybrid manipulators throughout the thesis. However, the most important applications of these are in the kinematic and static analysis of a semi-regular Stewart platform manipulator (in which the top and bottom platforms are semi-regular hexagons). Using the degeneracy of the wrench transformation matrix as the singularity criterion, the singularity manifold of the manipulator is obtained via extensive application of the symbolic simplification algorithms. The constant-orientation singularity manifold is derived in a compact closed form, and a complete geometric characterisation and explicit parameterisation of the same are presented. The constant-position singularity manifold is also obtained in closed form. On the other hand, families of configurations of the manipulator for combined kinematic or static isotropy for a given architecture are derived in closed form. Also, architectural designs are obtained for the manipulator such that it exhibits combined kinematic or static isotropy at a given configuration.

Cette thèse est en majeure partie dédiée au calcul rapide de remontée p-adique par des algorithmes détendus. Dans une première partie, nous présentons le cadre général des algorithmes détendus et de leur application au calcul de p-adiques récursifs. Pour appliquer ce cadre à la remontée p-adique de divers systèmes d'équations, il reste à transformer ces équations implicites en équations récursives. Ainsi, la seconde partie traite des systèmes d'équations linéaires, éventuellement différentiels. La remontée de résolutions de systèmes polynomiaux se trouve en troisième partie. Dans tous les cas, les nouveaux algorithmes détendus sont comparés, en théorie comme en pratique, aux algorithmes existants. En quatrième partie, nous étudions l'algèbre de décomposition universelle d'un polynôme. Nous développons un algorithme rapide pour calculer une représentation adéquate de cette algèbre et l'utilisons pour manipuler efficacement les éléments de l'algèbre. Finalement, nous montrons en annexe que la recherche d'invariants fondamentaux d'algèbres d'invariants sous un groupe fini peut se faire directement modulo p, facilitant ainsi leur calcul.

Le sujet de ma thèse consiste à analyser la sécurité d'un système de stockage pair à pair. Durant la première phase j'ai commencé par me familiariser avec le système existant (que du code), par la suite j'ai analysé la résistance du système en la présence d'attaques internes (que j'ai implémenté) en utilisant la simulation (travaux publiés dans HPCS'11). Le simulateur utilisé est un simulateur propriétaire qui reprend le code initial du système et modulable. Les résultats de cette analyse (perte de données) m'ont conduit à mettre en place un mécanisme de détection pour détecter ces attaques avant qu'elles ne causent la perte des données. Ce mécanisme de détection consiste à mettre en place un système de notation à deux niveaux : niveau 1:notation des échanges entre pair, niveau 2: notation des notes accordées à chaque pair (confiance en ces notes). Le principe de ce système est basé sur l'historique des échanges et la diffusion des notes entre les pairs. Dans un premier temps un système de notation à un niveau à été modélisé, implémenté et son efficacité analysée en utilisant deux méthodes (simulation pour les résultats quantitatifs et le model-checking pour les résultats qualitatifs. Pour la partie modélisation et vérification j'ai utilisé le formalisme ABCD [1], et les compilateurs SNAKES[2] et NICO[3,4]. Les résultats ont montrés la limite de ce système de notation à un seul niveau. (Travaux publiés dans TMS'12). A noter que jusque là seulement quelques attaques ont été détectées. En parallèle de tout ça un travail de modélisation dans un contexte de génie logiciel à été fait. Modélisation de l'application (Java) en utilisant le formalisme ABCD.

Le calcul de l'infimum global $f^*$ d'un polynôme à $n$ variables sous contraintes est une question centrale qui apparaît dans de nombreux domaines des sciences de l'ingénieur. Pour certaines applications, il est important d'obtenir des résultats fiables. De nombreuses techniques ont été développées dans le cas où les contraintes sont données par des inéquations polynomiales. Dans cette thèse, on se concentre sur le problème d'optimisation d'un polynôme à $n$ variables sous des contraintes définies par des équations polynomiales à $n$ variables. Notre but est d'obtenir des outils, algorithmes et implémentations efficaces et fiables pour résoudre ces problèmes d'optimisation. Notre stratégie est de ramener le problème d'optimisation sous des contraintes qui définissent des ensembles algébriques de dimension quelconque à un problème équivalent, sous des nouvelles contraintes dont on maîtrise la dimension. La variété algébrique définie par ces nouvelles contraintes est l'union du lieu critique du polynôme objectif et d'un ensemble algébrique de dimension au plus 1. Pour cela, on utilise des objets géométriques définis comme lieux critiques de projections linéaires. Grâce au bon contrôle de la dimension, on prouve l'existence de certificats pour des bornes inférieures sur $f^*$ sur nos nouvelles variétés. Ces certificats sont donnés par des sommes de carrés et on ne suppose pas que $f^*$ est atteint. De même, on utilise les propriétés de nos objets géométriques pour concevoir un algorithme exact pour le calcul de $f^*$. S'il existe, l'algorithme renvoie aussi un minimiseur. Pour un problème avec $s$ contraintes et des polynômes de degrés au plus $D$, la complexité est essentiellement cubique en $(sD)^n$ et linéaire en la complexité d'évaluation des entrées. L'implantation, disponible sous forme de bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre des problèmes inatteignables par les autres algorithmes exacts.

O principal objetivo do presente trabalho é expor o procedimento de quantização de teorias de Yang-Mills, através do método de Faddeev-Popov, no formalismo de 1a Ordem, e investigar num primeiro momento sua equivalência (clássica e quântica) ao formalismo usual (2a Ordem) e algumas de suas aplicações, principalmente no cálculo de correções quânticas. Para isso, ideias gerais a respeito do processo de quantização via formalismo de Faddeev-Popov foram expostas, e posteriormente utilizadas no processo de quantização de teorias de Yang-Mills no formalismo de 1a Ordem. Apresenta-se também as ideias gerais relativas ao método de regularização dimensional utilizado no cálculo de correções quânticas à nível de 1-loop para a teoria de Yang-Mills no formalismo de 1a ordem, utilizando-se, para isso, computação simbólica. Foi demonstrado que via formalismo de 1a Ordem, a estrutura ultravioleta encontrada no propagador do bóson de gauge é consistente com a renormalizabilidade da teoria. Embora tenhamos diferenças quanto a estrutura das interações neste novo formalismo, a estrutura das divergências ultravioletas continua a mesma do formalismo usual. / The main objective of the present work is to expose the quantization procedure of Yang- Mills theories in first order formalism, by Faddeev Popov\'s method. We want to investigate the classical and quantum equivalence between first and second order formalism, and look and analyze the differences in practical calculations of quantum corrections. Therefore, the general ideas about quantizantion by Faddeev-Popov\'s method was exposed, and used later in first order theory. It is also presented in this work, the main ideas concerning to dimensional regularization used in quantum corrections calculations at one-loop order for Yang-Mills theories, using for that, symbolic computation. It has been shown that upon using the first order formalism, the ultraviolet structre found in gauge boson propagator is also consistent to the theory\'s renormalizability. Although we have differences concerning to interactions structures in this new formalism, the ultraviolet structures from usual formalism is also found in it.

Les motivations initiales de ce travail proviennent de l'étalonnage de caméras en vision artificielle. Nous nous sommes surtout intéressés aux manières d'exploiter des mesures dans les images (détection d'objets) et des considérations géométriques formelles. Nous avons élargi nos recherches à la problématique suivante :"l'interaction entre symbolique et numérique ". Ce travail se divise en trois parties. La première partie traite de la résolution d'équations polynomiales avec des coefficients approchés. Nous étudions des méthodes matricielles qui transforment la résolution en la recherche des valeurs et des vecteurs propres d'une matrice. Ces transformations et et les calculs de valeurs et vecteurs propres sont continues par rapport aux coefficients et permettent donc de résoudre des équations à coefficients approchés. La deuxième partie présente un cadre algébrique permettant d'exprimer simplement des contraintes géométriques. Ce formalisme nous a permis de modéliser de manière fine l'étalonnage d'une ou plusieurs caméras avec l'aide d'un plan. L'étalonnage ne peut être effectué pratiquement qu'avec des résolutions numériques de systèmes linéaires. La troisième partie est consacrée à l'étude et surtout à l'utilisation des outils de démonstration automatique en géométrie pour la construction de modèles 3D articulés. Par des optimisations numériques, nous déterminons les paramètres des modèles articulés qui permettent aux images de ces modèles de coïncider avec les données extraites des photographies

Cette thèse porte sur l'étude de certains aspects des codes correcteurs d'erreurs et leurs applications à la sécurité de l'information. Plus spécifiquement, on s'est intéressé aux problèmes de décodage complet et de décodage en liste. Une nouvelle notion de codes a été introduite en liant une famille de codes et un algorithme de décodage, mettant ainsi en évidence les codes pour lesquels le décodage complet est réalisable en un temps polynomial. On présente ensuite une reformulation de l'algorithme de Koetter et Vardy pour le décodage en liste pour les codes alternant et analysons sa complexité. Cette méthode a permit de présenter une réduction de la taille de la clé du cryptosystème de McEliece, allant jusqu'à 21\% pour la variante dyadique. On s'est également intéressé à la stéganographie basée sur les codes. On propose différentes bornes caractérisant les stégosystèmes utilisant des codes linéaires, de façon à assurer la solvabilité du problème d'insertion avec des positions verrouillées. Une de ces bornes permet d'affirmer que plus le rang MDS du code utilisé est bas, plus ce code permettra de concevoir un stégosystème efficace. On montre également que les codes non-linéaires systématiques sont également de bons candidats. Enfin, on reformule le problème d'insertion bornée avec des positions verrouillées rendant ainsi l'insertion toujours possible, et on démontre que les codes de Hamming binaires permettent de satisfaire à toutes les contraintes exhibées.