É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.

Étude des méthodes de placements : évaluation des critères d'optimisation, et fonction du cout de placement. Présentation des heuristiques de placement suivant une classification synthétique afin de mettre en évidence leurs avantages, leurs inconvénients et leurs domaines d'application. Principes d'adaptation des méthodes de placement au traitement des réseaux structurés. Implantation des connexions dans les structures à canaux d'interconnexion. Détail des stratégies basées sur une décomposition du traitement en deux phases successives. Étude en particulier des méthodes de tracé global sur les réseaux prédiffusés. Présentation d'un système d'implantation automatise sur les réseaux de cellules prédiffusés structurés en matrice de macro-site.