Cette thèse présente l'étude et l'implantation de deux méthodes pour le placement automatique de circuits intégrés. Un circuit intégré peut être considéré comme un ensemble de blocs et une liste d'interconnexions entre ces blocs. Le probleme du placement consiste a disposer les blocs sur la surface hôte en respectant diverses contraintes et en optimisant des critères comme la surface occupée et la longueur totale de connexions. Les méthodes présentées ici sont toutes les deux guidées par l'optimisation de la connectique. La première fait appel a une technique d'analyse de données, l'analyse d'un tableau de proximités. Dans un premier temps, des proximités sont definies entre les blocs de façon a refléter un agencement ideal en fonction de la connectique. L'utilisation de l'atp permet alors d'obtenir une disposition planaire des blocs respectant au mieux les proximités qui ont été définies. L'analyse effectuée fait le point sur les diverses façons de définir les proximités entre les blocs, ainsi que sur les traitements ultérieurs destines a l'obtention d'un placement réalisable. Les qualités et les limitations de cette approche sont ensuite discutées. La seconde methode est connue sous le nom de placement par bipartitionnements successifs. L'ensemble des blocs du circuit et la surface hôte sont ainsi bipartitionnes récursivement jusqu'à ce que l'emplacement de chaque bloc soit déterminé. A partir des algorithmes existants, des heuristiques ont été mises au point afin de permettre la prise en compte de contraintes supplémentaires comme le traitement des plots d'entrées-sorties ou des blocs pré-fixes. L'expérimentation a permis de valider ces heuristiques et de comparer les résultats du placement a ceux fournis par la première methode

.

Nous proposons dans ce travail de nouvelles méthodes de décomposition basées sur l'algorithme du point proximal et ses extensions en optimisation convexe sous contraintes. On y démontre en particulier la sensibilité numérique de ces méthodes au choix d'un certain paramètre utilise pour accélérer la convergence. Ces méthodes sont appliquées a plusieurs modèles, notamment aux problèmes de transports dans les réseaux et aux problèmes de localisation. Les performances ont été validées a la fois du point de vue séquentiel et du point de vue massivement parallèle après une mise en œuvre sur la connection machine cm-2

Lustre est un langage de programmation spécialement conçu pour la réalisation des systèmes réactifs. Le besoin de garantir que ces systèmes ont un comportement conforme a celui attendu nécessite de définir et de mettre en œuvre des méthodes de vérification formelle des programmes lustre, qui sont relatées dans cette thèse. La vérification d'un système consiste a contrôler que tous ses comportements sont corrects vis-a-vis de ses spécifications. Les comportements d'un programme lustre peuvent classiquement être représentés par une machine d'états finis, dont la génération permet de vérifier ses spécifications. La methode standard mettant en œuvre ce principe est limitée par le probleme d'explosion de la machine générée, qui n'est pas minimale. Un nouvel algorithme évitant ce probleme est présenté. Son implémentation nécessite l'emploi d'une technique de représentation et de manipulation symbolique de la machine (bdds), dont le cout d'utilisation est largement abaisse grâce a de nombreuses optimisations. Basées sur cette technique, deux autres implémentations originales de la methode standard et de la nouvelle methode proposée ci-dessus sont décrites. Les aspects de diagnostic correspondant au cas ou les programmes sont incorrects vis-a-vis de leurs spécifications sont aussi abordes

Le probleme aborde dans ce mémoire est celui de la planification des mouvements d'un mobile a soumis a des contraintes cinématiques et dynamiques et se déplaçant dans un espace de travail dynamique w. Ce mémoire défend la thèse selon laquelle le probleme considère, connu pour être complexe, peut entre résolu de façon efficace lorsqu'il existe une structuration de w naturelle pour a, i.e. Lorsqu'il est possible de structurer w en un ensemble de zones libres a l'intérieur desquelles a peut se déplacer. Dans ce cas, le probleme peut être aborde suivant deux directions complémentaires: 1) la planification de chemin qui prend en compte les contraintes cinématiques de a et les obstacles fixes de w, et; 2) la planification de trajectoire qui prend en compte les contraintes dynamiques de a et les obstacles mobiles de w. Ce mémoire traite le cas d'une voiture dans le réseau routier. Les zones libres sont alors définies par les voies de circulation. A est soumis a une contrainte cinématique non-holonome qui l'oblige a se déplacer dans une direction perpendiculaire a l'axe de ses roues. De plus, le rayon de braquage, l'accélération et la vitesse de a sont limites. Nous commençons par présenter deux techniques de resolution propres a chacune des deux planifications mentionnées ci-dessus et bien adaptées au contexte dans lequel nous nous plaçons. Puis, nous montrons comment intégrer ces deux techniques au sein d'un système de planification de mouvement qui permet de résoudre efficacement le probleme considéré

Cette thèse présente des méthodes et outils de conception de systèmes integres sur tranche entière (wafer scale intégration). L'application traitée (dans le cadre d'un projet européen esprit) est une architecture constituée d'un réseau 2d de 6720 processeurs (pe) monobits, destinée au traitement d'image de bas niveau. Pour tolérer les défauts de fin fabrication, une approche hiérarchisée a été implantée. Au niveau sous-système, une technique de redondance figee a consiste a implanter une colonne de pes de réserve, destines a remplacer les pes défaillants. Au niveau tranche entière, une technique de construction d'une cible maximale n'utilisant que des sous-systèmes s'appuient sur l'implantation d'un réseau de commutateurs permettant d'éviter les sous-systèmes défaillants. Une architecture originale des réseaux de commutateurs contrôle a partir des plots externes et des algorithmes efficaces de définition et construction du réseau opérationnel constituent les points forts de cette thèse

Dans le cadre de la conception et de la réalisation d'un outil informatique pour la création musicale, on s'intéresse au geste instrumental pour contrôler en temps réel des processus de synthèse sonore par simulation de mécanisme instrumentaux et pour étudier sa relation a la composition musicale. Pour décrire et classifier le geste instrumental, assimile a une séquence d'événements gestuels, capte et mémorise sous la forme de signaux échantillonnes, nous posons le probleme de la segmentation. En considérant le jeu instrumental sur clavier nous proposons des éléments de syntaxe gestuelle et en déduisons des critères pour la segmentation automatique. Nous nous intéressons ensuite à la représentation graphique des événements gestuels segmentes et a leur composition et transformation. Nous définissons plusieurs niveaux de représentation et pour chacun d'eux, des procédures de traitement manuels ou pris en charge, tout ou en partie, par des modèles de composition. L'éditeur de geste, intégré dans le système de synthèse sonore cordis-anima, synthétise l'ensemble de ces possibilites

L'objectif de cette thèse est la conception d'une implantation parallèle efficace de Prolog. Sur une machine sans mémoire commune. Le modèle de calcul exploite le parallélisme ou selon l'approche multisequentielle classique. La partie principale de cette thèse est l'étude de méthodes de partage de contexte entre plusieurs machines abstraites Prolog. Un prototype est présent et des résultats préliminaires décrits. Ce prototype délivre un accroissement de performance effectif par parallélisation par rapport a des systèmes séquentiels

Cette thèse est consacrée a l'étude des algorithmes en optimisation non convexe, a l'implémentation des codes a l'usage industriel et aux simulations numériques dans les problèmes de grande tailles. L'étude des problèmes quadratiques (convexes ou non convexes) sous contraintes linéaires et quadratiques ainsi que celle des méthodes de région de confiance pour minimisation d'une fonction de classe c#2, font l'objet de deux premiers chapitres. Les chapitres 3 et 4 sont réservés a l'optimisation non convexe (classification, dualité, stabilité et les algorithmes de sous gradients de resolution). Enfin, les simulations numériques dans les problèmes concrets de grande taille sont présentées et commentées dans le dernier chapitre

Dans la fabrication des produits pétroliers en raffinerie, les lois linéaires de mélange permettent de représenter les ensembles de mélanges faisables par des zonotopes. La faisabilité d'un mélange est un probleme important qui est résolu par des méthodes d'optimisation convexe. Le but du travail présente est de montrer que, dans le cas de la dimension trois, la géométrie algorithmique apporte d'autres solutions a ce probleme. La spécificité des zonoedres et l'utilisation d'une structure de données de type arête-ailée permettent la mise en œuvre d'algorithmes de géométrie optimaux pour les représenter, puis des algorithmes de manipulation et visualisation rapides et robustes destines a être utilises de manière concrète. Le logiciel développe a partir de ces outils apporte une aide efficace dans la décision de la fabrication des gazoles. Dans le cadre plus vaste de la séparation, l'état de séparation d'un système physico-chimique est représente par un zonoide. Les Zonodres fournissent une approche géométrique pour l'étude de tels objets