Cette présente un point de vue algorithmique parllèle et séquentiel sur le traitement des graphes. Le chapitre~1 est consacré au modèle \lscPRAM qui est le modèle de parallèlisme le plus simple qui soit : plusieurs processeurs ont accès à une mémoire partagée. Même avec la simplification apportée par le modèle, certains problèmes restent difficiles à résoudre. La section~1.1 introduit une représentation adaptée aux traitement algorithmique des ordres de dimension fixée $d$ et permet de calculer une représentation classique de l'ordre, ce calcul est lié aux traitement de requêtes géométriques dans un espace de dimension $d$. La section~1.2 est consacrée à la reconnaissance en parallèle des ordres \lscN-free et la section~1.3 traite de la reconnaissance des graphes de comparabilité. D'une manière générale, l'étude de classes particulières de graphes permet de résoudre des problèmes qui sont difficiles dans le cas général en utilisant une structure algorithmique sous-jacente à la classe considérée. Le problème de la reconnaissance consiste à trouver cette structure. Le chapitre~2 est au consacré au modèle \lscCGM qui est un modèle de machine parallèle dite << à gros grain >> qui priviligie l'étude du placement distribué des données d'un problème, \cad{} sur les différentes mémoires des ordinateurs qui vont travailler ensemble sur le problème. Ce chapitre reprend les problèmes abordés dans le modèle \lscPRAM et en fournit des solutions dans le modèle \lscCGM. Un algorithme de \anglais{list-ranking} est de plus présenté dans la section d'un graphe dans ce modèle. Le chapitre~3 est consacré à un << modèle de calcul >> très particulier issu d'un problème de téléphonie \lscGSM. Ce chapitre regroupe d'une part les différentes idées algorithmiques qui s'appliquent à un tel problème soumis à de multiples contraintes et d'autre part des simulations permettant d'évaluer la pertinence des différentes idées. Ce problème est de nature continue mais on peut néanmoins y apporter des solutions issues de l'algorithmique discrète telles que les techniques liées aux des composantes connexes d'un graphe. Par soucis de continuité, un algorithme de composante connexes est donné dans chacun des trois modèles abordés. Enfin, le chapitre~4 est consacré à une nouvelle technique algorithmique : l'affinage de partition. La section~4.1 tente de cerner cette technique et montre les ressemblances entre différents algorithmes existants. Cette technique nous permettra de généraliser certains de ces algorithmes à la résolution d'autres problèmes proches. L'affinage de partition nous permettra ensuite dans la section~4.2 de donner des algorithmes simples pour résoudre la reconnaissance des graphes d'intervalles et l'orientation transitive, deux problèmes dont les solution algorithmiques efficaces étaient jusque là très difficiles à implanter et reposaient sur des structures de données complexes.

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.

No abstract

Cette thèse traite de la construction de quelques représentations par les frontières, ou BREP (pour "Boundary REPresentation"), et des difficultés rencontrées. Aussi cette introduction rappelle-t-elle très brièvement ce que sont les BREP; on se reportera à [PERO 87] pour un exposé plus détaillé et pour d'autres références. La synthèse d'images et la CAO utilisent diverses modélisations des solides pour les visualiser et calculer leurs propriétés géométriques et mécaniques : masse, aire de l'enveloppe, centre de gravité, axes principaux d'inertie, etc. Plusieurs modèles informatiques des solides ont été proposés :

L'ARN (acide ribonucléique) est une molécule ubiquitaire qui joue plusieurs rôles fondamentaux au sein de la cellule: synthèse des protéines avec les ARN messagers, activité catalytique ou implicationdans la régulation, les ARN non-codants. Les nouvelles technologies de séquençage à haut-débit permettent de produire des milliards de séquences à moindre coût, posant de manière cruciale la question de l'analyse de ces données. L'objectif de cette thèse est de définir de nouvelles méthodes computationnelles pour aider à l'analyse de ces séquences dans le cas des ARN non-codants. Dans cette perspective, la "structure secondaire" d'un ARN, formée par l'ensemble des appariements entrebases, délivre des informations utiles pour étudier la fonction de l'ARN. Notre travail se concentre plus particulièrement sur l'ensemble des structures potentielles que peut adopter une séquence d'ARN donnée, ensemble que nous appelons "multi-structure". Nous apportons deux contributions: un algorithme pour générer systématiquement toutes les structures localement optimales composantune multi-structure, et un algorithme basé sur la recherche d'unemulti-structure pour identifier un ARN non-codant dans une séquence génomique. Ces résultats ont été mis en oeuvre dans deux logiciels, Alterna et Regliss, appliqués avec succès à des ensembles de test.

Le travail, exposé dans ce rapport, se divise en deux parties. La première partie a fait l'objet d'un rapport de recherche publié en Avril 1984 [Tall]. La deuxième partie résulte d'un travail qui s'est déroulé de juin 1984 i juin 1985. Pour produire des images de hautes qualités, on est obligé de manipuler des grandes quantités de données. D'où l' intérêt d'étudier des algorithmes et des structures de données efficaces pour résoudre ~es problèmes géométriques. On pourra ainsi obtenir des méthodes efficaces pour la manipulation de données graphiques. On peut citer i ce propos, les travaux pionners de SHAMOS dans le domaine de la complexité géométrique [Sham]. La deuxième partie contient la description d 'un logiciel interactif *de manipulation de graphes et d'ordres. A notre connaissnce, la plus ancienne réalisation de ce type de logiciel est le "Graph theory interactive system" de WOLFBERG [Wolf]. Suivant les travaux de GUIDO sur CABRI (CAhier de BRouillon Informatisé), nous desirons offrir un poste de travail sur les graphes pour des chercheurs en théorie des graphes. CABRI est une bonne approche du problème, mais reste d'un emploi malaisé. Nous avons donc étudiés de nouveau le problème en nous attachant à décrire une meilleure interface utilisateur. Nous nous sommes inspirés des travaux sur les logiciels interactif existant, comme ceux développés chez XEROX, au PALO-ALTO RESEARCH CENTER (Smit] chez NIEVERGELT [Sere].

Les travaux décrits dans cette thèse portent sur le problème de vérification des systèmes avec espaces d'états infinis, et, en particulier, avec des structures de données chaînées. Plusieurs approches ont émergé, sans donner des solutions convenables et robustes, qui pourrait faire face aux situations rencontrées dans la pratique. Nos travaux proposent une approche nouvelle, qui combine les avantages de deux approches très prometteuses: la représentation symbolique a base d'automates d'arbre, et la logique de séparation. On présente également plusieurs améliorations concernant l'implementation de différentes opérations sur les automates d'arbre, requises pour le succès pratique de notre méthode. En particulier, on propose un algorithme optimise pour le calcul des simulations sur les systèmes de transitions étiquettes, qui se traduit dans un algorithme efficace pour le calcul des simulations sur les automates d'arbre. En outre, on présente un nouvel algorithme pour le problème d'inclusion sur les automates d'arbre. Un nombre important d'expérimentes montre que cet algorithme est plus efficace que certaines des méthodes existantes.

Les réseaux GAI sont une représentation graphique compacte et expressive des préférences d'un décideur en Décision Multiattribut, c'est-à-dire dans des situations où les alternatives sur lesquelles portent les choix du décideur sont décrites à l'aide d'un ensemble d'attributs (de caractéristiques). L'exploitation de leur structure graphique permet de définir des procédures efficaces d'élicitation de préférences (détermination des préférences à l'aide de questionnaires) ainsi que des algorithmes assez performants de prise de décision (calcul de l'alternative préférée du décideur ou des k meilleures alternatives). Le but de cette thèse est double. Tout d'abord elle vise à étendre les algorithmes de prise de décision dans des cas où les réseaux GAI sont denses, c'est-à-dire dans des situations où leur structure ne permet pas aux algorithmes de l'état de l'art de s'exécuter en un temps raisonnable. Pour cela, une nouvelle méthode de triangulation approchée a été développée, qui produit des réseaux GAI approchés sur lesquels des mécanismes d'inférence adaptés permettent d'obtenir les alternatives optimales des réseaux GAI d'origine. Ensuite, elle propose de nouvelles méthodes d'inférence en Décision multicritère. Plus précisément, elle propose des approches pour déterminer des frontières de Pareto (exactes ou approchées avec garantie de performance) ou des frontières de Lorenz. Elle prop ose également des algorithmes pour déterminer des solutions optimales dans les cas où les critères peuvent être agrégés via des opérateurs tels que OWA (Ordered Weighted Average), l'intégrale de Choquet ou bien encore la norme de Tchebyche ff.

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