Introduction. Graphes de cordes. Généralités. Diagrammes orientés. Orientations géométriques. Pseudo-tournois de cordes orientées. PL-graphes. Graphes de cordes et matroïdes binaires. Bibliographie

.

Cette thèse s'inscrit dans le cadre des grappes dans le projet Grid'5000 (Projet Français pour les grilles). Grid'5000 est une plate-forme expérimentale qui offre la possibilité aux chercheurs de soumettre aux gestionnaires de ressource des programmes (travaux) et d'associer pour chaque requête un environnement. Une grappe est un ensemble de noeuds de calcul, connectés entre eux via un réseau dédié. Le processus de déploiement d'environnement sur les noeuds de calcul n'est pas sans conséquence. Un des problèmes que l'on rencontre est la défaillance des machines. Le démarrage excessif lors de de la phase déploiement peut causer un endomagement de celles-ci. Nous avons ainsi modélisé ce problème sous forme d'un problème d'ordonnancement bicritère. Le premier critère à minimiser comptabilise pour chaque machine (processeur) le nombre de déploiements effectués. Il permet ainsi permet de définir le nombre total de déploiements sur toutes les machines. Nous avons également considéré un second critère à minimiser, le makespan. Nous avons défini un algorithme Groups List Scheduling, basé sur une approche budget, avec un relâchement des contraintes d'optimalité. Cette approche nous a permis de définir une solution (alpha, beta)-budget-relaxée-approchée pour un problème d'optimisation bicritère. Dans le cadre du problème d'ordonnancement bicritère avec déploiement, l'algorithme GLS donne ainsi une solution (4,2)-budget-approchée-relaxée. Nous avons ensuite abordé ce problème d'ordonnancement bicritère avec déploiement en utilisant l'approche «courbe de Pareto». Nous avons défini un algorithme polynômial, qui permet de construire une courbe de Pareto (4+epsilon, 2)-approchée, à partir des solutions fournies par l'algorithme GLS. Une analyse expérimentale nous a permis d'évaluer les performances de l'algorithme GLS et de valider ainsi les rapports

On expose deux logiciels de traitement de chromatogrammes de gas oils qui permettent l'évaluation des richesses de composants particuliers: les n-paraffines. Le premier permet par des recalages par «moindres carrés» d'estimer ces richesses à partir de deux chromatogrammes: celui du gas oil, mais aussi celui de ce même gas oil, sans les n-paraffines. Le deuxième ne nécessite plus que le seul chromatogramme du gas oil: on remplace l'information manquante par la connaissance théorique acquise sur la forme des n-paraffines. On procède en deux étapes: 1) application de la théorie de l'inf-convolution spline, en vue de séparer au mieux, par un profil de n-paraffine normalisé celle-ci du reste du gas oil; 2) application des méthodes de minimisation à plusieurs variables pour choisir, parmi les formes possibles pour une n-paraffines la forme optimale

Une base de données est au service de plusieurs catégories d'utilisateurs ayant chacune sa vision personnelle et évolutive des différentes sortes d'objets d'un univers. L'application systématique du concept d'abstraction a permis de dégager la notion d'objet pouvant être vu selon différentes facettes, appartenir à plusieurs ensembles et/ou relations, tout en demeurant unique. Ces objets sont spécifiés à l'aide de p-types, concept défini dans le cadre des types abstraits algébriques. La définition d'un p-type est modulaire et évolutive; une vue du p-type est caractérisée par des fonctions attributs et des contraintes d'intégrité. Les contraintes étudiées sont les dépendances entre valeurs d'attributs d'une occurrence d'un p-type (DIA) et les dépendances inter-objets (DIO). L'analyse statique de ces contraintes permet de garantir leur cohérence et de minimiser les vérifications dynamiques

Étude du trace automatique des canaux d'interconnexion de circuits intégrés. Une première partie est consacrée au trace de canaux rectangulaires dont les points à interconnecter sont tous repartis sur deux faces parallèles : les canaux bifaces. Une modélisation du problème est proposée. La faisabilité du problème est étudié et un minorant de la largeur minimale du canal est calcule. Différentes circonstances dans lesquelles ce minorant ne peut être atteint sont identifiées. Une heuristique de trace est décrite et formalisée. Une deuxième partie est consacrée au problème de l'interconnexion d'un ensemble de blocs polygonaux repartis dans un plan et séparés par des canaux d'interconnexion : le problème multi-canal. Les différentes approches du problème sont analysées. Une stratégie originale pour la résolution du problème pose par les configurations en "matrice de blocs" est ensuite proposée. Une heuristique originale de trace est décrite, ainsi qu'un programme implémentant cette heuristique. Des résultats expérimentaux sont présentés.

Description de la factorisation sur Z[×] et de ses problèmes, et des différentes formes de remontées série ou parallèle, linéaire ou quadratique. On donne un algorithme nouveau basé sur la décomposition d'une fraction rationnelle

On adapte des méthodes numériques efficaces pour équations de Fredholm à la résolution d'équations singulières. On développe en particulier les variantes itératives de Brakhage et d' Atkinson de la méthode de Nyström. Les exemples numériques traités confirment la nette supériorité de la méthode itérative de Brakhage

Présentation d'un langage formel pour la spécification des processus communicants. On propose 3 interprétations possibles (modèles) de ce langage: la présentation d'une variété d'algèbres, un système de transition de termes, un arbre (fini ou infini). Introduction d'un calcul pour la construction de réseaux de processus

Réalisation pour l'édition de structures et spécification pou l'édition de la partie fonctionnelle. Le travail présenté se situe dans le domaine de l'aide à la conception des circuits analogiques et digitaux électroniques (projet CASCADE)