L'approximation des convexes lisses par des polytopes pour la distance de Hausdorff a connu de nombreux résultats théoriques grâce à l'apport de la géométrie riemannienne. Nous rappelons ces résultats portant principalement sur le comportement asymptotique et montrons leur utilité pour certains cas pratiques. Puis nous établissons notre résultat principal, à savoir que ce problème d'approximation d'un convexe est, en un sens bien précis, équivalent à celui de l'approximation d'une norme par une autre. Nous établissons ensuite les propriétés d'un produit d'approximations de normes, ce qui nous permet de construire par récurrence sur la dimension des polytopes approchant certains convexes lisses, ainsi que des approximations optimales des normes Lp. Enfin nous montrons à travers différentes applications à la géométrie algorithmique en quoi une approximation de norme permet de transformer un algorithme de résolution exacte en un algorithme de résolution approchée mais moins coûteux.

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.

La modélisation géométrique d'un problème de gestion de la fabrication des mélanges (faisabilité simultanée de deux mélanges) fait apparaître des polytopes nouveaux résultant de la somme de triangles particuliers qui dans ce contexte sont appelés convexes de 2-mélanges. De façon plus générale, la somme de triangles peut être considérée comme la généralisation des zonotopes (somme de segments). De ce point de vue, l'étude menée ici fait apparaître que la propriété de zone associée à un segment du zonotope se généralise à trois demi-zones associées à chaque triangle; et que la complexité combinatoire (nombre de faces du polytope), par rapport au nombre de sommandes, est du même ordre de grandeur que celle des zonotopes. On traite également le problème de la construction de tels polytopes, des algorithmes optimaux en temps sont proposés. Concernant le problème particulier des mélanges, le premier cas non trivial est celui de mélanges à trois composantes qui nous place en dimension 6. L'appartenance d'un point au convexe de 2-mélanges détermine la faisabilité simultanée des mélanges. Les facettes de ce polytope sont décrites, en détail, dans le cas de la dimension 6, dans le but d'obtenir des conditions de faisabilité des deux mélanges. Le problème de la décomposition de polytopes en somme de Minkowski de polytopes plus simples est exposé, ainsi que les principaux résultats existant.

Dans cette thèse, nous proposons une méthode de résolution des problèmes de la géométrie algorithmique posés pour des objets courbes (par opposition aux objets "linéaires" : ensembles de points, segments, polygones ...). Les objets que nous étudions sont des courbes de Bézier composites, choisies, d'une part, pour le réalisme qu'elles assurent dans la modélisation géométrique, et d'autre part, pour la facilité du traitement algorithmique que leurs propriétés offrent. Notre approche met l'accent sur les aspects topologiques des problèmes abordés, en évitant les incohérences que la résolution en arithmétique flottante d'équations algébriques de degré élevé (générées par le traitement direct des courbes) peut le plus souvent introduire. Cet objectif est atteint par l'utilisation d'approximations polygonales convergentes, qui dans le cas des courbes de Bézier sont naturellement fournies par les polygones de controle par l'intermédiaire de la subdivision de de Casteljau. Deux des problèmes fondamentaux de la géométrie algorithmique sont traités ici, l'enveloppe convexe et les arrangements, les deux en dimension 2. Dans le cas des arrangements, la notion de topologie (combinatoire) est bien connue ; dans celui de l'enveloppe convexe, nous la définissons rigoureusement. Pour les deux problèmes, nous montrons qu'il est possible d'obtenir toute l'information topologique définissant (de manière, il est vrai, implicite, mais correcte et complète) la solution exacte en travaillant exclusivement sur les approximations polygonales des objets donnés. Les résultats théoriques obtenus sont concrétisés par des algorithmes dont la convergence et la correction sont démontrées et pour lesquels des études de cout sont réalisées. Des exemples illustrent le fonctionnement de ces algorithmes, validant la méthode proposée.

La résolution efficace de certaines questions de géométrie algorithmique, par exemple les calculs de visibilité ou l'approximation de forme, soulève de nouvelles questions de géométrie des droites, domaine classique dont l'origine remonte à la seconde moitié du 19e siècle. Ce mémoire s'inscrit dans ce cadre, et étudie les nombres de Helly de certains ensembles de droites, un indice reliée à certains théorèmes de la base apparaissant en optimimisation combinatoire. Formellement, le nombre de Helly d'une famille d'ensembles d'intersection vide est le cardinal de sa plus petite sous-famille d'intersection vide et minimale pour l'inclusion relativement à cette propriété. En 1957, Ludwig Danzer a formulé la conjecture que pour tout $d \ge 2$ il existe une constante $h_d$ telle que pour toute famille $\{B_1, \ldots, B_n\}$ de boules deux à deux disjointes et de même rayon, le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $h_d$; ici, $T(B_i)$ désigne l'ensemble des droites coupant $B_i$. Danzer a, de plus, spéculé que la constante $h_d$ (minimale) croît strictement avec $d$. Nous prouvons que de telles constantes existent, et que $h_d$ est au moins $2d-1$ et au plus $4d-1$ pour tout $d \ge 2$. Cela prouve la première conjecture et étaye la seconde. Nous introduisons, pour étudier les conjectures de Danzer, un analogue local du nombre de Helly que nous appellons nombre d'épinglement et qui se rattache à la notion d'immobilisation étudiée en robotique. Nous montrons que le nombre d'épinglement est borné pour toute famille (suffisament générique) de polyèdres ou d'ovaloides de $R^3$, deux cas où les nombres de Helly peuvent être arbitrairement grands. Un théorème de Tverberg énonce que si $\{B_1, \ldots, B_n\}$ est une famille de convexes du plan disjoints et congruents par translation alors le nombre de Helly de $\{T(B_1), \ldots, T(B_n)\}$ est au plus $5$. Quoique relativement différentes, notre preuve et celle de Tverberg exploitent toutes deux le fait que toute intersection d'au moins deux $T(B_i)$ a un nombre borné de composantes connexes, chacune contractile. Par des considérations sur l'homologie de projections de complexes et d'ensembles simpliciaux, nous unifions ces deux preuves et montrons que cette condition topologique suffit à établir une borne explicite sur le nombre de Helly.

Les travaux présentés dans cette thèse concernent l'ordonnancement<br />pour les plates-formes hétérogènes à grande échelle. Nous nous<br />intéressons principalement aux opérations de communications<br />collectives comme la diffusion de données, la distribution de données<br />ou la réduction. Nous étudions ces problèmes dans le cadre de leur<br />régime permanent, en optimisant le débit d'une série d'opérations de<br />communications, en vue d'obtenir un ordonnancement asymptotiquement<br />optimal du point de vue du temps d'exécution total. Après avoir<br />présenté un cadre général d'étude qui nous permet de connaître la<br />complexité du problème pour chaque primitive, nous développons, pour<br />le modèle de communication un-port bidirectionnel, une méthode de<br />résolution pratique fondée sur la résolution d'un programme linéaire<br />en rationnels. Cette étude du régime permanent est illustrée par des<br />expérimentations sur Grid5000 et se prolonge vers l'ordonnancement<br />d'applications multiples sur des grilles de calcul.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations (i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance (augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources.

La rétine numérique programmable est un imageur qui combine fonctions d'acquisition et de traitement de l'image au sein de chaque pixel. L'objectif de notre travail consiste à utiliser ce circuit dans un système de détection et d'analyse du mouvement en se conformant à ses capacités de calcul et de mémorisation limitées. Nous présentons d'abord trois méthodes de détection du mouvement adaptées à nos contraintes : un calcul de fond par une moyenne récursive classique ; un estimateur statistique, le filtre Σ-

Motivé par la découverte automatique de la structure hiérarchique de séquences d'ADN, nous nous intéressons au probléme classique de la recherche de la plus petite grammaire algébrique générant exactement une séquence donnée. Ce probléme NP-dur a été largement étudié pour des applications comme la compression de données, la découverte de structure et la théorie algorithmique de l'information. Nous proposons de décomposer ce probléme en deux problémes d'optimisation complémentaires. Le premier consiste á choisir les chaînes de la séquence qui seront les constituants de la grammaire finale alors que le second, que nous appelons ''analyse grammaticale minimale'', consiste á trouver une grammaire de taille minimale permettant l'analyse syntaxique de ces constituants. Nous donnons une solution polynomiale au probléme d' ''analyse grammaticale minimale'' et montrons que cette décomposition permet de définir un espace de recherche complet pour le probléme de la plus petite grammaire algébrique. Nous nous intéressons aux algorithmes praticables permettant de retourner une approximation du probléme en un temps suffisamment raisonnable pour être appliqués á de grandes séquences telles que les séquences génomiques. Nous analysons l'impact de l'utilisation de classes différentes de maximalité de répétitions pour le choix des constituants et le compromis entre l'efficacité et la taille de la grammaire finale. Nous présentons des avancées algorithmiques pour une meilleure efficacité des algorithmes hors-ligne existants, dont notamment la mise á jour incrémentale de tableaux de suffixes en cours de recodage. Enfin, la nouvelle décomposition du probléme nous permet de proposer de nouveaux algorithmes génériques permettant de trouver des grammaires 10\% plus petites que l'état de l'art. Enfin, nous nous intéressons á l'impact de ces idées sur les applications. En ce qui concerne la découverte de structures, nous étudions le nombre de grammaires minimales et montrons que ce nombre peut être exponentiel dans le pire cas. Nos expérimentations sur des jeux de séquences permettent cependant de montrer une certaine stabilité de structure au sein des grammaires minimales obtenues á partir d'un ensemble de constituants. En ce qui concerne la compression des données, nous contribuons dans chacune des trois étapes de la compression á base de grammaires. Nous définissons alors un nouvel algorithme qui optimise la taille de la chaine de bits finale au lieu de la taille de la grammaire. En l'appliquant sur les séquences d'ADN, nos expérimentations montrent que cet algorithme surpasse tout autre compresseur spécifique d'ADN á base de grammaire. Nous améliorons ce résultat en utilisant des répétitions inexactes et arrivons á améliorer les taux de compression de 25\% par rapport aux meilleurs compresseurs d'ADN á base de grammaire. Outre l'obtention de taux de compression plus performants, cette approche permet également envisager des généralisations intéressantes de ces grammaires.

Nous abordons dans cette thèse le problème du calcul de la topologie de courbes algébriques planes. Nous présentons un algorithme qui, grâce à l'application d'outils algébriques comme les bases de Gröbner et les représentations rationnelles univariées, ne nécessite pas de traitement particulier de cas dégénérés. Nous avons implanté cet algorithme et démontré son efficacité par un ensemble de comparaisons avec les logiciels similaires. Nous présentons également une analyse de complexité sensible a la sortie de cet algorithme. Nous discutons ensuite des outils nécessaires pour l'implantation d'algorithmes de géométrie non-linéaire dans CGAL, la bibliothèque de référence de la communauté de géométrie algorithmique. Nous présentons un noyau univarié pour CGAL, un ensemble de fonctions nécessaires pour le traitement d'objets courbes définis par des polynômes univariés. Nous avons validé notre approche en la comparant avec les implantations similaires.