Sur plusieurs problèmes il est difficile d'avoir un seul algorithme qui résout optimalement (en temps d'exécution) toutes ses instances. Ce constat motive l'élaboration des approches permettant de combiner plusieurs algorithmes résolvant le même problème. Les approches permettant la combinaison d'algorithmes peuvent être mise en oeuvre au niveau système (en construisant des bibliothèques, des langages et composants adaptatifs etc.) ou au niveau purement algorithmique. Ce travail se focalise sur les approches génériques de combinaison d'algorithmes au niveau algorithmique avec en particulier l'approche du portfolio d'algorithmes. Un portfolio d'algorithmes définit une exécution concurrente de plusieurs algorithmes résolvant un même problème. Dans une telle exécution, les algorithmes sont entrelacées dans le temps et/ou l'espace. Sur une instance à résoudre, l'exécution est interrompue dès qu'un des algorithmes trouve une solution. Nous proposons dans cette thèse une classification des techniques de combinaison d'algorithmes. Dans celle ci nous précisons pour chaque technique le contexte le plus adapté pour son utilisation. Nous proposons ensuite deux techniques de construction des portfolio d'algorithmes. La première technique est basée sur une adaptation de la méthode des plus proches voisins en apprentissage automatique pour la combinaison des algorithmes. Cette technique est adaptative car elle essaie sur chaque instance de trouver un sous ensemble d'algorithmes adaptés pour sa résolution. Nous l'appliquons dans la combinaison des algorithmes itératifs pour la résolution des systèmes linéaires et nous montrons sur un jeu d'environ mille matrices creuses qu'elle permet de réduire le nombre d'itérations et le temps nécéssaire dans la résolution. En outre, sur certains jeux d'expérimentations, ces résultats montrent que la technique proposée peut dans la plupart des cas trouver l'algorithme le plus adapté à sa résolution. La seconde technique est basée sur le problème de partage de ressources que nous formulons. Etant donnés, un problème cible, un jeu de données le représentant, un ensemble d'algorithmes candidats le résolvant et le comportement en temps d'exécution du jeu de données sur les algorithmes candidats, le problème de partage de ressources a pour objectif de trouver la meilleure répartition statique des ressources aux algorithmes candidats de sorte à minimiser en moyenne le temps de résolution du jeu de données cibles. Ce problème vise à trouver une solution en moyenne plus robuste que chacun des algorithmes candidats pris séparémment. Nous montrons que ce problème est NP-complet et proposons deux familles d'algorithmes approchés et exacts pour le résoudre. Nous validons les solutions proposées en prenant des données issues d'une base de données pour SAT. Les résultats obtenus montrent que les solutions proposées permettent effectivement de bénéficier de la complémentarité des algorithmes résolvant un même problème pour la construction des algorithmes robustes.

LA FAIBLE DEFINITION DES MEMOIRES DE TRAMES IMPOSEE PAR DES CONTRAINTES TECHNOLOGIQUES POSE DES PROBLEMES DE DISCRETISATION DE L'IMAGE LORS DE SON AFFICHAGE. IL EN RESULTE LES DIFFERENTS DEFAUTS D'ALIASSAGE DUS A UN ECHANTILLONNAGE INSUFFISANT DE L'IMAGE SOUS SA FORME ANALOGIQUE. CES DEFAUTS SONT PERCEPTIBLES ESSENTIELLEMENT SOUS FORMES DE MARCHES D'ESCALIER SUR LES CONTOURS DE L'IMAGE, D'APPARITION ET DE DISPARITION DES PETITS OBJETS SUIVANT LEUR POSITION DANS LA SCENE ET DE PRESENCE DE MOIRE DANS LES SCENES PORTANT DES TEXTURES. POUR ATTEINDRE UN PLUS GRAND DEGRE DE REALISME EN SYNTHESE D'IMAGES, IL EST INDISPENSABLE DE RESOUDRE CES PROBLEMES DE DISCRETISATION. LA SOLUTION GENERALE EST UN PREFILTRAGE PASSE-BAS DE L'IMAGE AVANT SON AFFICHAGE. NOUS ABORDONS CES PROBLEMES SOUS UN ANGLE THEORIQUE ET PRATIQUE DANS CETTE THESE. NOUS ETUDIONS LES METHODES D'ANTIALIASSAGE EN SYNTHESE D'IMAGES DANS LES CAS LES PLUS COURANTS. NOUS PROPOSONS DES NOUVELLES METHODES EN PARTICULIER DES ALGORITHMES ORIGINAUX POUR RESOUDRE CES PROBLEMES DANS LES CAS DU TAMPON DE PROFONDEUR ET DES TEXTURES

Je me suis intéressé pendant ma thèse à la globalité du système de synthèse d'images. En effet, j'ai travaillé sur les différentes étapes du processus de la génération d'une image de synthèse: de la modélisation jusqu'au rendu. Mon objectif principal était de favoriser l'évolutivité et la flexibilité du système. Pour pouvoir atteindre cet objectif, j'ai utilisé la programmation orientée objet pour concevoir et implanter un modeleur de type arbre de construction en langage c++. J'ai proposé une méthodologie de choix de classes et une hiérarchie originale de classes. Pour rendre le système plus flexible, j'ai permis le mixage d'algorithmes d'élimination des parties cachées dans une même scène tout en assurant l'interaction en termes de réflexion, transparence et ombres portées entre tous les objets de la scène. Enfin, j'ai proposé un certain nombre d'outils et méthodes pour la gestion des niveaux de détails dans une scène.

Depuis quelques années, les déformations sont utilisées en synthèse d'images pour la modélisation des solides. La déformation libre est une méthode de transformation qui déforme des objets en déplaçant un maillage de points de contrôle définis dans un repère local et en utilisant une interpolation volumique. Deux extensions ont été développées. La première utilise l'interpolation de type b-spline, au lieu de l'interpolation de type bezier. La deuxième utilise un repère local cylindrique ou sphérique, au lieu d'un repère local cartésien. Pour visualiser des objets déformés un algorithme de facettisation adaptative est proposé. Pour déplacer des points de contrôle dans l'espace 3d avec un localiseur 2d, un curseur 3d est utilisé.

Les Algorithmes Évolutionnaires (AEs) sont des méthodes de recherche inspirées par la théorie darwinienne de l'évolution, travaillant sur une population de solutions potentielles, par itération de phases de sélections et de variations aléatoires. La sélection d'une représentation, la définition des paramètres ou l'attribution de leurs propres valeurs ont une influence cruciale sur les performances de l'algorithme. Un choix qui ne s'accorde pas à la fonction de fitness peut rendre le problème plus difficile à résoudre. Trouver une configuration appropriée pour un AE est donc depuis longtemps un grand défi. Bien que les AEs soient reconnus comme des méthodes compétitives sur des problèmes de grande taille, ils sont sujets à un certain nombre de critiques tel celui du réglage/contrôle des paramètres. Par réglage, nous entendons l'approche qui consiste à trouver des valeurs satisfaisantes pour les paramètres avant l'exécution de l'algorithme. Dans cette thèse, nous fournissons des arguments qu'un jeu de paramètres constants durant l'exécution semble être inadéquat. Notre contribution au vaste domaine de l'optimisation concerne le réglage automatique des paramètres selon le problème traité. Dans la première partie, nous exposons la problématique du réglage/contrôle des paramètres ainsi que les principales heuristiques existantes. Dans la deuxième, nous proposons deux méthodes pour le contrôle dynamique des paramètres associés à la représentation des solutions. Dans la troisième, nous proposons l'algorithme évolutionnaire à états (SEA), une variante parallèle des AEs ; cette nouvelle approche gère simultanément plusieurs AEs afin de contrôler dynamiquement les paramètres au cours du processus d'optimisation. Dans la dernière partie, nous présentons une instanciation du SEA qui intègre différents taux de mutation afin d'adapter le meilleur taux à la recherche. Cette nouvelle instance est testée sur le problème du sac à dos multidimensionnel. Des résultats comparables ont été obtenus, ce qui prouve que le SEA est capable de contrôler dynamiquement le compromis exploration/exploitation.

My thesis deals with register allocation. During this phase, the compiler has to assign variables of the source program, in an arbitrary big number, to actual registers of the processor, in a limited number k. Recent works, for instance the thesis of F. Bouchez and S. Hack, have shown that it is possible to split in two different decoupled step this phase: the spill - store the variables into memory to release registers - followed by the registers assignment. These works demonstrate the feasibility of this decoupling relying on a theoretic framework and some assumptions. In particular, it is sufficient to ensure after the spill step that the number of variables simultaneously live is below k.My thesis follows these works by showing how to apply this kind of approach when real-world constraints come in play: instructions encoding, ABI (application binary interface), register aliasing. Different approaches are proposed. They allow either to ignore these problems or to directly tackle them into the theoretic framework. The hypothesis of the models and the proposed solutions are evaluated and validated using a thorough experimental study with the compiler of STMicroelectronics. Finally, all these works have been done with the constraints of modern compilers in mind, the JIT (just-in-time) compilation, where the compilation time et the memory footprint of the compiler are key factors. We strive to offer solutions that cope with these criteria or improve the result until a given budget is reached. We, in particular, used the SSA (static single assignment) form to define algorithm like tree scan that generalizes linear scan based approaches proposed for JIT compilation.

De nombreux travaux de recherche actuels s'intéressent aux réseaux de capteurs sans fil (RCSF) et à leurs différentes problématiques. L'une d'entre elles est la gestion des données présentes au sein du RCSF. Généralement, les deux grands types de données manipulées sont soit celles collectées à l'aide d'un dispositif de mesure, soit celles gérées par le système d'exploitation. L'objectif de cette thèse est de proposer des solutions à cette problématique. Un microsystème de fichier a ainsi été conçu en prenant comme support un noyau temps réel au fonctionnement hybride à la fois multitâche et basé sur les événements. Ce noyau utilise un concept permettant d'offrir un niveau d'abstraction pour la gestion des processus ou des événements. Ce concept a été repris, au niveau du microsystème de fichiers, dans le cadre de l'accès aux données. L'autre caractéristique principale de ce microsystème de fichiers, par rapport aux systèmes existants, est de réunir, au sein d'un même système, des fonctionnalités de gestion de mémoire et d'interrogation de données. Ces deux éléments, que sont le microsystème de fichiers et le noyau temps réel, associés à un capteur sans fil multi-composant constituent une plateforme adaptative permettant la mise en place d'applications d'acquisition de données environnementales.

Tree automata, and their applications to verification from the common thread of this thesis In the first part, we definie a complete model-cheking framework.[...] The second part focus on an important aspect of the automata involved: constraints.[...] Finaly, we also study the very different variety of tree-walking automata which have tight connections with navigational languages on semi-structured documents.

Dans le cadre de cette thèse, nous considérons la complexité paramétrée de problèmes NP- complets. Plus précisément, nous nous intéressons à l'existence d'algorithmes de noyau polynomiaux pour des problèmes d'édition de graphes et de relations. Nous introduisons en particulier la notion de branches, qui permet d'obtenir des algorithmes polynomiaux pour des problèmes d'édition de graphes lorsque la classe de graphes cible respecte une décomposition d'adjacence. Cette technique nous permet ainsi d'élaborer les premiers algorithmes de noyaux polynomiaux pour les problèmes CLOSEST 3-LEAF POWER, COGRAPH EDITION et PROPER INTERVAL COMPLETION. Concernant les problèmes d'édition de relations, nous étendons la notion de Conflict Packing, qui a déjà été utilisée dans quelques problèmes paramétrés et permet d'élaborer des algorithmes de noyau linéaires pour différents problèmes. Nous présentons un noyau linéaire pour le problème FEEDBACK ARC SET IN TOURNAMENTS, et adaptons les techniques utilisées pour obtenir un noyau linéaire pour le problème DENSE ROOTED TRIPLET INCONSISTENCY. Dans les deux cas, nos résultats améliorent la meilleure borne connue, à savoir un noyau quadratique. Finalement, nous appliquons cette tech- nique sur les problèmes DENSE BETWEENNESS et DENSE CIRCULAR ORDERING, obtenant à nouveau des noyaux linéaires, qui constituent les premiers algorithmes de noyau polynomiaux connus pour ces problèmes.

Dans le problème de détection de communautés il est possible d'utiliser soit la dimension structurelle, soit la dimension compositionelle du réseau : dans le premier cas les communautés seraient composées par des groupes de noeuds fortement connectés mais peu similaires, et pour le deuxième cas, les groupes auraient des noeuds similaires mais faiblement connectés. Donc en ne choisissant qu'une des dimensions la quantité possible d'information à extraire est réduite. Cette thèse a pour objectif de proposer une nouvelle approche pour utiliser en même temps les dimensions structurelle et compositionelle lors de la détection de communautés de façon telle que les groupes aient des noeuds similaires et bien connectés. Pour la mise en oeuvre de cette approche il faut d'abord une nouvelle définition de communauté qui prend en compte les deux dimensions présentées auparavant et ensuite un modèle nouveau de détection qui utilise cette définition, en trouvant des groupes de noeuds similaires et bien connectés. Le modèle commence par l'introduction de la notion de point de vue qui permet de diviser la dimension compositionelle pour analyser le réseau depuis différentes perspectives. Ensuite le modèle, en utilisant l'information compositionelle, influence le processus de détection de communautés qui intègre les deux dimensions du réseau. La dernière étape est la visualisation du graphe de communautés qui positionne les noeuds selon leur similarité structurelle et compositionelle, ce qui permet d'identifier des noeuds importants pour les interactions entre communautés.