On décrit et on étudie une matrice Q inversible telle que Q F = JQ ou J est la forme normale de Jordan d'une matrice carrée A, et F sa forme de Frobenius. On propose un algorithme efficace pour le calcul de l'inverse de Q et deux algorithmes donnant la forme de Frobenius d'une matrice n x n quelconque. Dans le cas ou les éléments de A sont des nombres rationnels, on montre que la complexité de l'un des algorithmes est polynomiale. On considère aussi le cas des matrices A coefficients dans le corps des nombres algébriques sur Q

.

Les algorithmes d'evaluation parallele des expressions et des circuits arithmetiques peuvent etre vus comme des extracteurs du parallelisme intrinseque contenu dans les programmes sequentiels, parallelisme qui depasse celui qui peut etre lu sur le graphe de precedence et qui tient a la semantique des operateurs utilises. La connaissance des proprietes algebriques, comme l'associativite ou la distributivite, permet une reorganisation des calculs qui n'affecte pas les resultats. Plus la structure algebrique utilisee sera riche en proprietes, plus il sera possible d'en tirer parti pour ameliorer les algorithmes d'evaluation. Generalisant les algorithmes concus pour les semi-anneaux, nous proposons un algorithme qui ameliore les majorations precedemment connues pour la contraction de circuits arithmetiques dans un treillis. Des simulations de cet algorithme ont permis de mettre en evidence ses qualites de << predicteur automatique de complexite >>. Reorganiser explicitement les calculs a l'aide de ces algorithmes, c'est-a-dire realiser un compilateur complet, permet de comparer la realite des algorithmes paralleles sur machines a memoire distribuee et la puissance des algorithmes theoriques. Un prototype a ete realise, base sur une simplification/extension du langage C. Enfin, l'interet de ces techniques dans le domaine de la parallelisation des nids de boucles, pour guider la recherche de reductions cachees dans ces nids, semble prometteuse, parce qu'elle est peu couteuse a mettre en oeuvre et fournit des informations de qualite. En cela, les recherches en algorithmique parallele theorique rejoignent les preoccupations de la parallelisation effective.

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.

L'acceptation et l'utilisation des services Web en industrie se développent de par leursupport au développement d'application distribuées comme compositions d'entitéslogicielles plus simples appelées services. En complément à la vérification, le testpermet de vérifier la correction d'une implémentation binaire (code source nondisponible) par rapport à une spécification. Dans cette thèse, nous proposons uneapproche boîte-noire du test de conformité de compositions de services centralisées(orchestrations). Par rapport à l'état de l'art, nous développons une approchesymbolique de façon à éviter des problèmes d'explosion d'espace d'état dus à la largeutilisation de données XML dans les services Web. Cette approche est basée sur desmodèles symboliques (STS), l'exécution symbolique de ces modèles et l'utilisationd'un solveur SMT. De plus, nous proposons une approche de bout en bout, quiva de la spécification à l'aide d'un langage normalisé d'orchestration (ABPEL) etde la possible description d'objectifs de tests à la concrétisation et l'exécution enligne de cas de tests symboliques. Un point important est notre transformation demodèle entre ABPEL et les STS qui prend en compte les spécifications sémantiquesd'ABPEL. L'automatisation de notre approche est supportée par un ensemble d'outilsque nous avons développés.

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.

Stochastic differential inclusions can be considered as a generalisation of stochastic differential equations. In particular a multivalued mapping describes the set of equations, in which a solution has to be found. This paper presents an existence result for a special parabolic stochastic inclusion. The proof is based on the method of upper and lower solutions. In the deterministic case this method was effectively introduced by S. Carl.