L'ensemble des solutions d'une équation différentielle algébrique, ordinaire ou aux dérivées partielles se scinde entre la solution générale et les solutions singulières. Ces notions peuvent être définies de manière rigoureuse dans le cadre de l'algèbre différentielle, une théorie fondée par J.F.Ritt. Des travaux récents dans ce domaine ont permis de mettre au point des algorithmes effectifs pour déterminer la trivialité d'un système différentiel en effectuant une première décomposition. On peut ainsi déterminer si une équation différentielle admet des solutions singulières et quelles sont elles. Les décompositions obtenues ne sont néanmoins pas minimales. Nous proposons un algorithme, qui évite les factorisations, pour éliminer les composantes redondantes. En termes analytiques, il s'agit de distinguer les solutions singulières essentielles, qui sont enveloppes de la solution générale, des solutions singulières particulières, qui sont limites de solutions essentielles. la solution générale, des solutions singulières particulières, qui sont limites de solutions essentielles. Au c\oe ur de cette détermination se tient le Théorème des petites puissances, la réalisation effective étant soutenue par l'algorithme Rosenfeld-Gröbner. Nous présentons de plus un algorithme et quelques critères qui permettent de calculer les bases différentielles des composantes essentielles. De telles bases permettent une analyse des points singuliers ainsi que des heuristiques d'intégration.

Dans cette thèse, nous développons une théorie de<br />déformation pour les singularités lagrangiennes. Pour une singularité<br />lagrangienne, un complexe de modules à différentielle non-linéaire,<br />dont la première cohomologie est isomorphe à l'espace de déformations<br /> infinitésimales de la singularité, est défini. La cohomologie en degré deux contient des informations sur les obstructions. Ce<br />complexe est relié à la théorie des modules différentiels. Nous<br />démontrons que, sous une condition géométrique, sa cohomologie est<br />constituée de faisceaux constructibles. Nous décrivons une méthode<br />utilisant du calcul formel pour déterminer cette cohomologie pour<br />des surfaces quasi-homogènes.

La première partie de cette thèse présente le cadre des équations différen- tielles à retard. Ces équations apparaissent notamment dans des modélisations de phénomènes physiques (calcul de marées) et physiologiques. La recherche de forme normale d'équation différentielle à retard est rendue difficile du fait de la dimension infinie de l'espace des conditions initiales. On présente une méthode de calcul due à T. Faria qui permet de réduire cette difficulté en utilisant des variétés centrales de dimension finie, sur lesquelles on peut faire un calcul de forme normale « classique ». On étend ensuite ce résultat à l'aide d'une méthode de G. Gaeta permettant la renormalisation de formes normales usuelles, pour des équations différentielles ordinaires. En utilisant ces deux méthodes, on démontre un théorème donnant l'existence d'une forme renormalisée d'équation différentielle à retard. Dans une deuxième partie, on présente et on étudie le formalisme moulien développé par Jean Ecalle. On utilise ce formalisme pour la recherche de formes normales de champs de vecteurs, et on l'applique à des champs hamiltoniens en coordonnées cartésiennes, puis en coordonnées action-angle. On obtient ainsi une nouvelle démonstration de la version formelle du théorème de Kolmogorov et du théorème de Birkhoff. On présente également une feuille de calcul avec Maple mettant en œuvre certains de ces calculs, et témoignant ainsi de la remarquable aptitude du formalisme moulien à être utilisé dans les logiciels de calcul formel.

Nous présentons un système de retour arrière distribué basé sur le Calcul des Systèmes Communicants de Robin Milner. L'algèbre de pro- cessus réversible ainsi définie (RCCS) nous permet de poser les fondements théoriques du retour arrière dans un calcul concurrent. En particulier, étant donné un processus et un passé, nous montrons que RCCS permet de re- venir en arrière dans tout passé causalement équivalent. Nous exprimons aussi l'équivalence comportementale associée aux processus réversibles en utilisant une notion de bisimulation mettant en relation les traces causales des processus. Il en résulte une méthode de programmation déclarative de systèmes transactionnels qui peuvent être efficacement vérifiés à l'aide d'un algorithme basé sur des structures d'événements. Par l'intermédiaire d'une construction catégorique, nous montrons que cette méthode peut être géné- ralisée à une large classe de calculs concurrents.

On présente trois algorithmes dans cette thèse: Le premier algorithme résout de systèmes polynomiaux homogènes et paramétrés zéro-dimensionnels avec un temps simplement exponentiel en le nombre n des inconnus, cet algorithme décompose l'espace des paramètres en un nombre fini d'ensembles constructibles et calcule le nombre fini de solutions par de représentations rationnelles paramétriques uniformes sur chaque ensemble constructible. Le deuxième algorithme factorise absolument de polynômes multivariés paramétrés avec un temps simplement exponentiel en n et en la borne supérieure d de degrés de polynômes à factoriser. Le troisième algorithme décompose les variétés algébriques définies par de systèmes algébriques paramétrés de dimensions positives en composantes absolument irréductibles d'une manière uniforme sur les valeurs des paramètres. La complexité de cet algorithme est doublement exponentielle en n. D'autre part, la borne inférieure du problème de résolution de systèmes algébriques paramétrés est doublement exponentielle en n.

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.

Les outils présentés dans ce mémoire ont pour but d'améliorer, par l'apport de méthodes et de techniques de calcul formel, les performances et les capacités de calcul des logiciels qui modélisent et le comportement dynamique de systèmes de corps mécaniques reliés entre eux. On s'intéresse à la possibilité d'écrire de manière automatique un ensemble d'équations différentielles régissant la dynamique de tels systèmes à partir de leurs descriptions physiques. Dans le premier chapitre, on décrit soigneusement les objets mécaniques et mathématiques qui interviennent dans l'étude dynamique des systèmes multicorps, et on met en évidence un problème fondamental : la nature de l'ensemble des configurations admissibles des mécanismes à structures bouclées. Le deuxième chapitre est une étude détaillée, sur un exemple, des différentes méthodes de génération des équations du mouvement de systèmes multicorps, dans l'optique de leur implémentation dans un logiciel de calcul symbolique. Il montre l'intérêt des techniques formelles et permet de spécifier les outils qui doivent être créés pour mener à bien cette implémentation. Dans le troisième chapitre, on présente les outils formels qui ont été développés pour aider à construire un générateur automatique des équations de la dynamique de systèmes polyarticulés. On se consacre, dans le quatrième chapitre, à apporter des éléments de solutions au problème de la détermination de la dimension des variétés de configurations de mécanismes à structures bouclées. Plusieurs méthodes faisant appel à des techniques algébriques, probabilistes et géométriques sont exposées, ainsi que leurs implémentations, et leurs expérimentations.

L'objet de cette thèse est une description effective des espaces de modules des courbes hyper- elliptiques de genre 3 en caractéristiques positives. En caractéristique nulle ou impaire, on obtient une paramétrisation de ces espaces de modules par l'intermédiaire des algèbres d'invariants pour l'action du groupe spécial linéaire sur les espaces de formes binaires de degré 8, qui sont de type fini. Suite aux travaux de Lercier et Ritzenthaler, les cas des corps de caractéristiques 3, 5 et 7 restaient ouverts. Pour ces derniers, les méthodes classiques de la caractéristique nulle sont inno- pérantes pour l'obtention de générateurs pour les algèbres d'invariants en jeu. Nous nous sommes donc contenté d'exhiber des invariants séparants en caractéristiques 3 et 7. En outre, nos résultats concernant la caractéristique 5 suggèrent l'inadéquation de cette approche pour ce cas. À partir de ces résultats, nous avons pu expliciter la stratification des espaces de modules des courbes hyperelliptiques de genre 3 en caractéristiques 3 et 7 selon les groupes d'automorphismes et implémenté divers algorithmes, dont celui de Mestre, pour la reconstruction d'une courbe à partir de son module, ie la valeur de ses invariants. Pour cette phase de reconstruction, nous nous sommes notamment attaché aux questions arithmétiques, comme l'existence d'une obstruction à être un corps de définition pour le corps de module et, dans le cas contraire, à l'obtention d'un modèle de la courbe sur ce corps minimal. Enfin pour la caractéristique 2, notre approche est différente, dans la mesure où les courbes sont étudiées via leur modèle d'Artin-Schreier. Nous exhibons pour celles-ci des invariants bigradués qui dépendent de la structure arithmétique des points de ramifications des courbes. / The aim of this thesis is to provide an explicite description of the moduli spaces of genus 3 hyperelliptic curves in positive characteristic. Over a field of characteristic zero or odd, a parame- terization of these moduli spaces is given via the algebra of invariants of binary forms of degree 8 under the action of the special linear group. After the work of Lercier and Ritzenthaler, the case of fields of characteristic 3, 5 and 7 are still open. However, in these remaining case, the classical methods in characteristic zero do not work in order to provide generators for these algebra of invariants. Hence we provide only separating invariants in characteristic 3 and 7. Furthermore our results in characteristic 5 show this approach is not suitable. From these results, we describe the stratification of the moduli spaces of genus 3 hyperelliptic curves in characteristic 3 and 7 according to the automorphism groups of the curves and imple- ment algorithms to reconstruct a curve from its invariants. For this reconstruction stage, we paid attention to arithmetic issues, like the obstruction to be a field of definition for the field of moduli. Finally, in the characteristic 2 case, we use a different approach, given that the curves are defined by their Artin-Schreier models. The arithmetic structure of the ramification points of these curves stratify the moduli space in 5 cases and we define in each case invariants that characterize the isomorphism class of hyperelliptic curves.

Dans cette thèse nous appliquons des techniques provenant du calcul formel et de la théorie des langages afin d'améliorer les opérations élémentaires dans certaines tours de corps finis. Nous appliquons notre construction au problème du calcul d'isogénies entre courbes elliptiques et obtenons une variante plus rapide (à la fois en théorie et en pratique) de l'algorithme de Couveignes. Le document est divisé en quatre parties. Dans la partie I nous faisons des rappels d'algèbre et de théorie de la complexité. La partie II traite du principe de transposition : nous généralisons des idées de Bostan, Schost et Lecerf et nous montrons qu'il est possible de transposer automatiquement des programmes sans pertes en complexité-temps et avec une petite perte en complexité-espace. La partie III combine les résultats sur le principe de transposition avec des techniques classiques en théorie de l'élimination ; nous appliquons ces idées pour obtenir des algorithmes asymptotiquement optimaux pour l'arithmétique des tours d'Artin-Schreier de corps finis. Nous décrivons aussi une implantation de ces algorithmes. Enfin, dans la partie IV nous utilisons les résultats précédents afin d'accélérer l'algorithme de Couveignes et de comparer le résultat avec les autres algorithmes pour le calcul d'isogénies qui font l'état de l'art. Nous présentons aussi une nouvelle généralisation de l'algorithme de Couveignes qui calcule des isogénies de degré inconnu.