Cette thèse traite du problème fondamental que constitue la planification de trajectoires de robots manipulateurs. Une première partie précise le contexte robotique de notre travail et présente le système général de programmation automatique développe au Lifia. Nous analysons ensuite l'importance de la représentation des connaissances nécessaires aux raisonnements géométriques particuliers a la planification de déplacements. Les méthodes de modélisation et les concepts de représentation que nous avons mis en oeuvre sont ensuite présentes. Une deuxième partie traite de la planification de trajectoires pour une structure articulée. Une methode de planification globale par construction de l'espace des configurations est présentée, ainsi qu'une methode de replanification locale par application de champs de potentiels et, enfin, une methode hybride réalisant la synthèse de ces approches complémentaires, pour lesquelles sont décrits algorithmes, résultats d'expérimentation et futurs développements

Différentes analyses de la méthode de Givens en parallèle sur une architecture à mémoire partagée sont examinées. Présentation de résultats de complexité et d'algorithmes asymptotiquement optimaux. Dans une deuxième partie, consacrée aux architectures à mémoire distribuée, les couts de communication sont pris en compte. Une analyse macroscopique montre l'influence de l'architecture sur la complexité des décompositions de Givens et de Householder s'exécutant sur différents réseaux de processeurs fonctionnant par échange de messages

Présentation d'une méthodologie de simulation du fonctionnement logique du coprocesseur arithmétique FELIN. Étude des méthodes de Durand-Kerner et d'Ehrlich pour la recherche simultanée de toutes les racines d'un polynôme à coefficients complexes. Elles sont ensuite comparées à cinq variantes algorithmiques. Une étude comparative est proposée. L'étude expérimentale de ces différentes méthodes est menée sur une architecture vectorielle

Divers algorithmes d'études locale d'ensembles invariants compacts de systèmes dynamiques sont présentés dans ce travail. Nous commençons par développer des méthodes de calcul numérique de la densité locale autour d'un point d'un ensemble de Julia de fraction rationnelle. Ce problème est important dans le domaine de l'étude des modèles hiérarchiques de la physique statistique. De plus, cette densité serait un des paramètres principaux de la caractérisation d'invariants compacts de systèmes dynamiques (attracteur étrange...). L'application de ces méthodes demande des algorithmes d'accès rapide à des régions (rectangle, cercle) du compact numériquement approche par un ensemble forme d'un grand nombre de points. Nous avons mis au point un algorithme, réellement implémentable et expérimentalement efficace, qui résout ce problème. Nous montrons que, sous certaines conditions, ce procédé permet l'estimation de quelques dimensions fractales de l'ensemble considère. Un logiciel, nomme Elsep et écrit en langage Pascal, qui regroupe et exploite tous ces algorithmes ponctue cette étude. Des résultats numériques et graphiques illustrent chacune des parties traitées

L'objet de cette thèse est l'étude des aspects algorithmiques de l'effet petit monde dans les grands réseaux d'interaction.Les observations expérimentales ont montré que les grands réseaux d'interactions (sociales, informatiques, biologiques), présentaient des propriétés macroscopiques communes. Une d'elles est l'effet petit monde qui consiste en l'existence de chemins très courts entre toutes les paires de noeuds qui peuvent être découverts en n'utilisant qu'une vue locale du réseau. Nous nous intéressons à cette caractéristique algorithmique de l'effet petit monde, à son application au routage informatique décentralisé, et à son émergence dans les réseaux réels.Nous proposons un nouvel algorithme de routage décentralisé sur le modèle aléatoire de petit monde de Kleinberg, qui calcule des chemins de longueur O(log n.(loglog n)^2), asymptotiquement plus courts que ceux des algorithmes existants (en O((log n)^2)). Cet algorithme pourrait également s'appliquer aux réseaux pair-à-pair. Nous précisons cette étude en comparant les charges induites pas les différents algorithmes proposés sur ce modèle.En tentant d'exhiber les caractéristiques minimales d'un graphe qui permettent de l'augmenter en un petit monde par l'ajout de raccourcis aléatoires, nous proposons un nouveau modèle de petit monde qui généralise celui de Kleinberg. Il s'agit d'ajouter une distribution de liens dépendant de la taille des boules de la métrique des distance sous-jacente. Ce modèle peut par ailleurs être étendu simplement pour produire toute distribution des degrés, dont en particulier la fameuse loi de puissance. Enfin, nous proposons le premier schéma distribué qui permette de transformer un réseau de diamètre quelconque en petit monde en ajoutant un seul nouveau lien par noeud, il s'agit d'un premier pas vers la compréhension de l'émergence naturelle du phénomène dans les réseaux réels.

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné n'est pas nécessairement considéré comme disqualifié, et il convient d'actualiser avec soin l'état de l'art de la cryptanalyse. Les travaux de ce mémoire s'inscrivent dans cette optique. Nous décrivons en particulier comment nous avons atteint un record de calculs de logarithmes discrets: \GFn(607).<br /><br />Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépasse<br />le simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité.<br /><br />On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur \GF p.<br /><br />Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène.

Il existe de nombreux démonstrateurs automatiques qui effectuent des raisonnements modulo une théorie équationnelle, c'est-à-dire enconsidérant non pas des termes, mais des classes d'équivalence de termes. En général, les travaux accomplis dans ce domaine ont pour but de concevoir des techniques pour faire de la déduction modulo une théorie particulière. Dans [Avenhaus & Plaisted, 2001], Jürgen Avenhaus et David Plaisted ont cherché à déterminer des techniques qui pourraient être employées dans le traitement non plus d'une théorie particulière, mais de toute une classe de théories équationnelles: les théories permutatives. Les auteurs ont introduit les notions de terme stratifié et d'ensemble stratifié, et décrit les procédures qui devraient être implémentées dans un démonstrateur automatique basé sur ces termes stratifiés. Les propriétés de régularité de ces théories font qu'il est possible d'employer des techniques efficaces de théorie algorithmique des groupes pour les traiter. Les auteurs espéraient que l'efficacité de ces techniques contrebalancerait le nombre élevé de clauses qui pourraient être générées dans un démonstrateur automatique basé sur ces termes stratifiés. Cependant, les algorithmes proposés pour faire de la déduction avec des termes stratifiés sont basés sur une énumération explicite des éléments des groupes, et sont donc exponentiels. Dans ce mémoire, nous développons les travaux d'Avenhaus et Plaisted, et modifions leur formalisme pour pouvoir faire l'usage le plus intensif possible des techniques de théorie algorithmique des groupes.

L'objet de cette thèse est double. Tout d'abord elle vise à répondre à certaines questions relatives aux notions de spectres euclidien et inhomogène (pour la norme) d'un corps de nombres, et notamment à celles qui concernent son minimum euclidien (pour la norme). Nous établissons en particulier que pour tout corps de nombres K, le minimum euclidien de K, noté M(K), est égal à son minimum inhomogène M(\overline{K}), et que si le rang du groupe des unités de K est strictement supérieur à 1, les spectres euclidiens et inhomogènes de K sont égaux et rationnels lorsque K n'est pas CM. Les résultats que nous établissons sous l'hypothèse r > 1 ont pour conséquence la décidabilité de l'euclidianité pour la norme. <br />Nous montrons également comment calculer explicitement M(K). Nous décrivons un algorithme pour le cas où K est totalement réel, qui a permis de construire des tables jusqu'au degré 8 ; nous indiquons comment le transposer à des corps de nombres quelconques. En outre, cet algorithme a permis de trouver de nombreux exemples de corps de nombres principaux, non euclidiens pour la norme et euclidiens en deux étapes.

L'évolution technique des "objets communicants" tels que les ordinateurs portables, les assistants personnels, etc..., confirme l'intérêt porté aux technologies "sans fil". Le développement rapide des protocoles de communication sans fil (Bluetooth, WIFI, ...) a permis la généralisation de nouveaux "réseaux locaux ad-hoc" principalement caractérisés par leur topologie dynamique et l'hétérogénéité de leurs composants. Aussi, les infrastructures logicielles reposant sur de tels environnements doivent pouvoir s'adapter et gérer cette dynamicité (connexions/déconnexions fréquentes ainsi que la forte variabilité des communications. Dans ce contexte, l'objectif général est de concevoir des algorithmes permettant de maintenir la cohérence d'un groupe d'entités hétérogènes partageant des services sur des architectures fortement instables. La problématique concerne donc la prise de décision en environnement distribué en considérant les particularités du réseau sous-jacent. Dans cette thèse, nous proposons une méthodologie d'approche concernant la caractérisation des performances envisageables dans un environnement totalement distribué s'appuyant sur un protocole de communication sans fil. Cette approche consiste également en l'identification des différentes perturbations susceptibles d'interférer dans le bon déroulement des applications. Par ailleurs, un algorithme de consensus adapté aux spécificités de l'environnement et basé sur un principe d'interaction avec un mécanisme de détection de défaillances a été développé et implanté. Afin de valider cette approche algorithmique, diverses expérimentations et évaluations qualitatives et quantitatives ont été réalisées.