Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes. / When wood is transported from forest sites to mills, several unforeseen events may occur, events which perturb planned trips (e.g., because of weather conditions, forest fires, or the occurrence of new loads). When such events take place while the trip is under way, the truck involved must be rerouted to an alternative itinerary. Without relevant information on such alternative itineraries, the truck driver may choose a needlessly long one or, even worse, an itinerary that may itself be "closed" by an unforeseen event (the same event as for the original itinerary or another one). It is thus critical to provide drivers with real-time information, in particular, suggestions of alternative itineraries, when the planned one cannot be performed. Recourse strategies to deal with unforeseen events depend on the characteristics of the studied supply chain, such as the presence of auto-loaders and the management policy of forestry transportation companies. We present three papers dealing with three differ- ent application contexts, as well as models and solution methods adapted to each context. In the first paper, we assume a context where truck drivers are provided a priori with the whole weekly plan. In this context, every effort must be made to minimize the changes in the initial plan. Although the fleet of trucks is homogeneous, there is a priority ranking of the truck drivers. The priority drivers are ensured the highest work- loads. Minimizing the changes in their plans is also a priority. Since the consequences of unforeseen events on transportation are cancellations and/or delaying of some trips, the proposed approach deals first with single cancellations and single delayed trips and builds on these simple events to deal with more complex ones. In this approach, we try to reschedule the impacted trips within the same week in such a way that a loader is free at the truck arrival time both at the forest site and at the mill. In this way, none of the other trips will be impacted or changed. This approach provides the dispatchers with alternative plans in a few seconds. Better solutions could be found if the dispatcher is allowed to make more changes to the original plan. In the second paper, we assume a context where only one trip at a time is communicated to the drivers. The dispatcher waits until the truck finishes its trip before revealing the next trip. This context is more flexible and provides more recourse possibilities. Also, the weekly problem can be divided into daily problems since the demand is daily and the mills are open only for limited periods in the day. We use a mathematical programming model based on a time-space network representation to react to disruptions. Although the latter can have different impacts on the initial transportation plan, one key characteristic of the proposed model is that it remains valid for dealing with all the unforeseen events, regardless of their nature. Indeed, the impacts of such events are reflected in the time-space network and in the input parameters rather than in the model itself. The model is solved for the current day each time an unforeseen event is revealed. In the last paper, the fleet of trucks is heterogeneous, including trucks with onboard loaders. The route configuration of the latter is different than the regular truck routes, since they do not have to be synchronized with the loaders. We use a mathematical model where the columns can be easily and naturally interpreted as truck routes. We solve this model using column generation. As a first step, we relax the integrality of the decision variables and consider only a subset of feasible routes. The feasible routes with a potential to improve the solution are added iteratively to the model. A time-space network is used both to represent the impacts of unforeseen events and to generate these routes. The solution obtained is generally fractional and a heuristic branch-and-price algorithm is used to find integer solutions. Several disruption scenarios were developed to test the proposed approach on case studies from the Canadian forest industry and numerical results are presented for the three contexts.

Le développement des techniques de traitement des requêtes de classement est un axe de recherche très actif dans le domaine de la recherche d'information. Plusieurs applications nécessitent le traitement des requêtes de classement multicritères, telles que les méta-moteurs de recherche sur le web, la recherche dans les réseaux sociaux, la recherche dans les bases de documents multimédia, etc. Contrairement aux requêtes booléennes traditionnelles, dans lesquelles le filtrage est basé sur des prédicats qui retournent vrai ou faux, les requêtes de classement utilisent des prédicats de similarité retournant un score de pertinence. Ces requêtes spécifient une fonction d'agrégation qui combine les scores individuels produits par les prédicats de similarité permettant de calculer un score global pour chaque objet. Les k objets avec les meilleurs scores globaux sont retournés dans le résultat final. Dans cette thèse, nous étudions dans un premier temps les techniques et algorithmes proposés dans la littérature conçus pour le traitement des requêtes top-k multicritères dans des contextes spécifiques de type et de coût d'accès aux scores, et nous proposons un cadre générique capable d'exprimer tous ces algorithmes. Ensuite, nous proposons une nouvelle stratégie en largeur «breadth-first», qui maintient l'ensemble courant des k meilleurs objets comme un tout, à la différence des stratégies en profondeur habituelles qui se focalisent sur le meilleur candidat. Nous présentons un nouvel algorithme «Breadth-Refine» (BR), basé sur cette stratégie et adaptable à n'importe quelle configuration de type et de coût d'accès aux scores. Nous montrons expérimentalement la supériorité de l'algorithme BR sur les algorithmes existants. Dans un deuxième temps, nous proposons une adaptation des algorithmes top-k à la recherche approximative, dont l'objectif est de trouver un compromis entre le temps de recherche et la qualité du résultat retourné. Nous explorons l'approximation par arrêt prématuré de l'exécution et proposons une première étude expérimentale du potentiel d'approximation des algorithmes top-k. Dans la dernière partie de la thèse, nous nous intéressons à l'application des techniques top-k multicritères à la recherche par le contenu dans les grandes bases de données multimédia. Dans ce contexte, un objet multimédia (une image par exemple) est représenté par un ou plusieurs descripteurs, en général sous forme de vecteurs numériques qui peuvent être vus comme des points dans un espace multidimensionnel. Nous explorons la recherche des k plus proches voisins (k-ppv) dans ces espaces et proposons une nouvelle technique de recherche k-ppv approximative «Multi-criteria Search Algorithm » (MSA) basée sur les principes des algorithmes top-k. Nous comparons MSA à des méthodes de l'état de l'art dans le contexte des grandes bases multimédia où les données ainsi que les structures d'index sont stockées sur disque, et montrons qu'il produit rapidement un très bon résultat approximatif. / Efficient processing of ranking queries is an important issue in today information retrieval applications such as meta-search engines on the web, information retrieval in social networks, similarity search in multimedia databases, etc. We address the problem of top-k multi-criteria query processing, where queries are composed of a set of ranking predicates, each one expressing a measure of similarity between data objects on some specific criteria. Unlike traditional Boolean predicates returning true or false, similarity predicates return a relevance score in a given interval. The query also specifies an aggregation function that combines the scores produced by the similarity predicates. Query results are ranked following the global score and only the best k ones are returned.In this thesis, we first study the state of the art techniques and algorithms designed for top-k multi-criteria query processing in specific conditions for the type of access to the scores and cost settings, and propose a generic framework able to express any top-k algorithm. Then we propose a new breadth-first strategy that maintains the current best k objects as a whole instead of focusing only on the best one such as in all the state of the art techniques. We present Breadth-Refine (BR), a new top-k algorithm based on this strategy and able to adapt to any combination of source access types and to any cost settings. Experiments clearly indicate that BR successfully adapts to various settings, with better results than state of the art algorithms.Secondly, we propose an adaptation of top-k algorithms to approximate search aiming to a compromise between execution time and result quality. We explore approximation by early stopping of the execution and propose a first experimental study of the approximation potential of top-k algorithms. Finally, we focus on the application of multi-criteria top-k techniques to Large Scale Content-Based Image Retrieval. In this context an image is represented by one or several descriptors, usually numeric vectors that can be seen as points in a multidimensional space. We explore the k-Nearest Neighbors search on such space and propose “Multi-criteria Search Algorithm” (MSA) a new technique for approximate k-NN based on multi-criteria top-k techniques. We compare MSA with state of the art methods in the context of large multimedia databases, where the database and the index structure are stored on disk, and show that MSA quickly produces very good approximate results.

Cette thèse aborde le problème de la recherche d'images à grande échelle. Pour aborder la recherche d'images à grande échelle, il est nécessaire de coder des images avec des représentations compactes qui peuvent être efficacement utilisées pour comparer des images de manière significative. L'obtention d'une telle représentation compacte peut se faire soit en comprimant des représentations efficaces de grande dimension, soit en apprenant des représentations compactes de bout en bout. Le travail de cette thèse explore et avance dans ces deux directions. Dans notre première contribution, nous étendons les approches de quantification vectorielle structurée telles que la quantification de produit en proposant une représentation somme pondérée de codewords. Nous testons et vérifions les avantages de notre approche pour la recherche approximative du plus proche voisin sur les caractéristiques d'image locales et globales, ce qui est un moyen important d'aborder la recherche d'images à grande échelle. L'apprentissage de la représentation compacte pour la recherche d'images a récemment attiré beaucoup d'attention avec diverses approches basées sur le hachage profond proposées. Dans de telles approches, les réseaux de neurones convolutifs profonds apprennent à coder des images en codes binaires compacts. Dans cette thèse, nous proposons une approche d'apprentissage supervisé profond pour la représentation binaire structurée qui rappelle une approche de quantification vectorielle structurée telle que PQ. Notre approche bénéficie de la recherche asymétrique par rapport aux approches de hachage profond et apporte une nette amélioration de la précision de la recherche au même débit binaire. L'index inversé est une autre partie importante du système de recherche à grande échelle en dehors de la représentation compacte. À cette fin, nous étendons nos idées pour l'apprentissage de la représentation compacte supervisée pour la construction d'index inversés. Dans ce travail, nous abordons l'indexation inversée avec un apprentissage approfondi supervisé et essayons d'unifier l'apprentissage de l'indice inversé et de la représentation compacte. Nous évaluons minutieusement toutes les méthodes proposées sur divers ensembles de données accessibles au public. Nos méthodes surpassent ou sont compétitives avec l'état de l'art. / This thesis addresses the problem of large-scale image search. To tackle image search at large scale, it is required to encode images with compact representations which can be efficiently employed to compare images meaningfully. Obtaining such compact representation can be done either by compressing effective high dimensional representations or by learning compact representations in an end-to-end manner. The work in this thesis explores and advances in both of these directions. In our first contribution, we extend structured vector quantization approaches such as Product Quantization by proposing a weighted codeword sum representation. We test and verify the benefits of our approach for approximate nearest neighbor search on local and global image features which is an important way to approach large scale image search. Learning compact representation for image search recently got a lot of attention with various deep hashing based approaches being proposed. In such approaches, deep convolutional neural networks are learned to encode images into compact binary codes. In this thesis we propose a deep supervised learning approach for structured binary representation which is a reminiscent of structured vector quantization approaches such as PQ. Our approach benefits from asymmetric search over deep hashing approaches and gives a clear improvement for search accuracy at the same bit-rate. Inverted index is another important part of large scale search system apart from the compact representation. To this end, we extend our ideas for supervised compact representation learning for building inverted indexes. In this work we approach inverted indexing with supervised deep learning and make an attempt to unify the learning of inverted index and compact representation. We thoroughly evaluate all the proposed methods on various publicly available datasets. Our methods either outperform, or are competitive with the state-of-the-art.

Dans le cadre du projet GUIMUTEIC, qui vise à équiper les visiteurs de musées d'un outils d'aide à la visite équipé d'une caméra, cette thèse adresse le problème d'accès à l'information en mobilité.On s'intéresse à comment rendre l'information à propos des œuvres accessible et automatique aux visiteurs de lieux touristiques.Elle s'inscrit dans le cadre du projet GUIMUTEIC, qui vise à équiper les visiteurs de musées d'un outil d'aide à l'accès à l'information en mobilité.Être capable de déterminer si le visiteur désire avoir accès à l'information signifie identifier le contexte autour de lui, afin de fournir une réponse adaptée, et réagir à ses actions.Ceci soulève les problématiques d'identification de points d'intérêts, pour déterminer le contexte, et d'identification de gestes de utilisateurs, pour répondre à ses demandes.Dans le cadre du notre projet, le visiteur est donc équipé d'une caméra embarquée.L'objectif est de fournir un solution à l'aide à la visite, en developpant des méthodes de vision pour l'identification d'objet, et de detection de gestes dans les vidéos à la première personne.Nous proposons dans cette thèse une étude de la faisabilité et de l'intérêt de l'aide à la visite, ainsi que de la pertinence des gestes dans le cadre de l'interaction avec un système embarqué.Nous proposons une nouvelle approche pour l'identification d'objets grâce à des réseaux de neurones profonds siamois pour l'apprentissage de similarité entre les images, avec apprentissage des régions d'intérêt dans l'image.Nous explorons également l'utilisation de réseaux à taille réduite pour le détection de gestes en mobilité.Nous présentons pour cela une architecture utilisant un nouveau type de bloc de convolutions, pour réduire le nombre de paramètres du réseau et permettre son utilisation sur processeur mobile.Pour évaluer nos propositions, nous nous appuyons sur plusieurs corpus de recherche d'image et de gestes, crée spécialement pour correspondre aux contraintes du projet. / This thesis is part of the GUIMUTEIC project, which aim is to equip museum tourist with an audio-guide enhanced by a camera.This thesis adress the problem of information access in mobile environment, by automaticaly providing information about museum artefacts.To be able to give this information, we need to know when the visitor desire guidance, and what he is looking at, to give the correct response.This raises issues of identification of points of interest, to determine the context, and identification of user gestures, to meet his demands.As part of our project, the visitor is equipped with an embedded camera.The goal is to provide a solution to help with the visit, developing vision methods for object identification, and gesture detection in first-person videos.We propose in this thesis a study of the feasibility and the interest of the assistance to the visit, as well as the relevance of the gestures in the context of the interaction with an embedded system.We propose a new approach for objects identification thanks to siamese neural networks to learn images similarity and define regions of interest.We are also exploring the use of small networks for gesture recognition in mobility.We present for this an architecture using new types of convolution blocks, to reduce the number of parameters of the network and allow its use on mobile processor.To evaluate our proposals, we rely on several corpus of image search and gestures, specificaly designed to match the constraints of the project.

Dans le champ de la recherche en génomique, comme dans d'autres domaines très informatisés, les bases de données et les biobanques sont organisées en infrastructures. Ce nouveau modèle organisationnel doit permettre de soutenir l'effort technique et collaboratif requis pour traiter des Big Data, c'est-à-dire des jeux de données trop volumineux et complexes pour être traités en utilisant les méthodes classiques. L'établissement de ces nouveaux environnements constitue un véritable défi technique et philosophique. Il requiert, pour être opérationnel, des cadres réglementaires adaptés, ouverts à la fois à l'internationalisation et à des perspectives de long terme, mais certains de ces changements ne sont pas compatibles avec les procédures éthiques courantes, notamment la procédure de consentement éclairé. L'éthique de la recherche en génomique doit donc être repensée. Faut-il puiser dans la technique les nouvelles solutions de gouvernance de la recherche ? Ou bien est-il plus juste de répondre à ces évolutions en analysant les situations de tension morale suscitées par de nouveaux développements et en décidant de les traiter en fonction de ce à quoi nous tenons collectivement ? L'enjeu de ce travail, qui relève d'une approche pragmatiste, consiste à cultiver une attitude réflexive à propos des changements en cours dans la recherche en génomique. Cette tâche suppose d'expliciter le rôle des biobanques et des bases de données dans la production, la validation et la publication de la recherche génomique. Il est également nécessaire de rendre compte des tensions auxquelles le développement de ces dispositifs donne lieu lorsqu'ils sont incompatibles avec les procédures actuelles. On peut alors examiner si les dispositifs tels qu'ils sont conçus sont désirables dans les contextes où ils sont développés, soulignant ainsi la dimension politique de l'éthique de la recherche. Cette thèse repose sur l'analyse de situations concrètes issues de projets de recherche dans lesquels nous avons été impliquée. Nous utilisons aussi plusieurs disciplines étudiant la science telle qu'elle se fait (philosophie, anthropologie, sociologie et histoire). Au cours de cet examen, l'idée régulatrice de personne-membre est proposée, pour favoriser la prise en compte des appartenances sociales et politiques du sujet de l'éthique de la recherche en génomique. / In genomic research, as in other highly computerised scientific fields, databases and biobanks are today (re-)organised into infrastructures. This new organisational model should support the technical and collaborative effort needed to deal with Big Data, that is, data sets that are too large and too complex to be treated with conventional methods. Establishing these new environments is an actual technical challenge that requires, in order to be operational, appropriate regulatory frameworks that are both open to internationalisation and long-term prospects. But some of these changes are not consistent with current ethics procedures, including the informed consent process. The ethics of genomics research must therefore be reconsidered by asking whether it is in technology that we must draw new solutions for the governance of research or whether we must respond to these evolutions by proposing a political treatment to clarify what we value collectively. This work, which is based on a pragmatist approach, intends to cultivate a reflexive attitude on the changes being made in genomic research by describing situations of moral tension. This requires elucidating the role of biobanks and databases in the production, validation and publication of genomic research; accounting for the conflicts of values to which the development of these devices can give rise when they are incompatible with the current procedures and thus to examine whether the devices as conceived are desirable in the contexts where they are developed. This thesis is based on the analysis of concrete situations, resulting from research projects in which we have been involved or from studies of science in practices (philosophy, anthropology, sociology and history). During this examination, the regulatory idea of a person-member is proposed, in order to favor the consideration of the social and political affiliations of the subject of ethics to research in genomics.

Les problèmes d'optimisation en variables 0-1 mixtes permettent de modéliser de nombreux problèmes réels difficiles à résoudre. Cette thèse s'intéresse à la mise en oeuvre de méthodes de résolution hybrides pour obtenir des solutions de bonne qualité en des temps raisonnables pour ces problèmes. L'ensemble des algorithmes présentés dans cette thèse est testé sur le problème du sac-à-dos multidimensionnel. Il consiste à maximiser une fonction linéaire en respectant un ensemble de contraintes linéaires. Après une présentation de quelques concepts fondamentaux utilisés en recherche opérationnelle pour résoudre les problèmes d'optimisation, nous présentons dans le premier chapitre différents problèmes de la famille du sac-à-dos. Nous abordons dans le second chapitre un ensemble de méthodes efficaces existantes pour résoudre le problème du sac-à-dos multidimensionnel. Nous proposons dans le chapitre 3 une première méthode hybride qui combine la programmation dynamique et la recherche tabou au sein d'un processus dit d'intensification globale. Des concepts de réduction sont également intégrés dans la programmation dynamique de manière à essayer de réduire la taille du problème. La seconde approche décrite dans le chapitre 4 combine la recherche dispersée avec des éléments de la recherche tabou et des chemins reliants pour affiner la recherche. Une étude expérimentale est menée pour mesurer l'impact de différents composants de l'algorithme. Nous terminons dans le chapitre 5 par une méthode utilisant conjointement la relaxation en continu et la relaxation en nombres entiers mixtes pour résoudre efficacement les problèmes en variables 0-1. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes. La dernière approche permet d'améliorer quelques meilleures valeurs connues sur des instances existantes du problème du sac-à-dos multidimensionnel.

L'étude réalisée montre un décalage important entre la preuve en mathématiques et la preuve telle qu'elle vit en classe, surtout au collège : actuellement la transposition didactique dénature son sens, réduisant son apprentissage à celui de savoir faire des exercices d'écriture formelle. Il s'avère nécessaire de changer les pratiques, pour que la preuve soit enseignée de manière plus satisfaisante sur les plans épistémologique et didactique. Nous montrons qu'il est pertinent, et possible, d'amorcer ce changement par un travail sur les conceptions des enseignants. Pour cela nous proposons une ingénierie de formation fondée sur trois problèmes : tout d'abord est montré le rapport existant des élèves à la preuve ; ensuite, les enseignants, mis en situation de recherche de problèmes, produisent des preuves. Les résultats obtenus à partir des problèmes choisis permettent à la fois de préciser le rapport des enseignants à la preuve et d'amorcer avec eux une réflexion sur leurs pratiques.

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.

Comme la complexité des circuits VLSI croit, la tache de vérification des masques devient de plus en plus longue. L'utilisation des descriptions hiérarchiques permet le développement de méthodes d'analyse hiérarchique plus efficaces. Cette thèse explore une méthode de recherche géométrique par hiérarchie de Quadtrees et l'utilisation hiérarchique de l'algorithme d'équivalence union-find pour la recherche et la mise à jour des équivalences électriques. Des algorithmes hiérarchiques et géométriques utilisables pour l'édition, la vérification géométrique et topologique (connectique) de conceptions VLSI sont présentés. L'intérêt de telles méthodes dans la vérification et le compactage de ces conceptions est aussi aborde. Des quadtrees adaptatifs particuliers (mixed-quadtrees) ont été conçus et testés pour optimiser les outils conventionnels d'extraction et de vérification de la description géométrique des masques de conceptions non structurées et pour permettre une édition rapide de conceptions structurées. Ce document présente les arguments qui ont contribue à la conception d'un tel sous-systeme de recherche géométrique et topologique, le sous-système lui-même et certains algorithmes hiérarchiques. Les méthodes hiérarchiques, géométriques et topologiques ainsi explorées, sont applicables à un grand nombre de taches, comme l'extraction des conceptions, leur vérification, leur édition et leur compactage et sur des descriptions symboliques ou réelles. Ces méthodes permettent l'utilisation interactive d'un certain nombre d'algorithmes d'extraction, de vérification et d'adaptation des conceptions éditées à un ensemble de règles technologiques. Un extracteur et vérificateur géométrique et topologique de conceptions structurées est actuellement réalisé dans le but d'évaluer hiérarchiquement l'efficacité de tels algorithmes. Un aperçu des problèmes qui peuvent être résolus plus rapidement ou dans un mode interactif est également présenté