Thèse (M.Inf.) -- Université du Québec à Chicoutimi, programme en extension de l'Université du Québec à Montréal, 2005. / Bibliogr.: f. 125-130. Document électronique également accessible en format PDF. CaQCU

Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées " alignements ", sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision.

Dans cette thèse, nous étudions les aspects structurels et algorithmiques de différents problèmes de théorie des graphes. Rappelons qu’un graphe est un ensemble de sommets éventuellement reliés par des arêtes. Deux sommets sont adjacents s’ils sont reliés par une arête.<p>Tout d’abord, nous considérons les deux problèmes suivants :le problème de vertex cover et celui de dominating set, deux cas particuliers du problème de hitting set. Un vertex cover est un ensemble de sommets qui rencontrent toutes les arêtes alors qu’un dominating set est un ensemble X de sommets tel que chaque sommet n’appartenant pas à X est adjacent à un sommet de X. La version connexe de ces problèmes demande que les sommets choisis forment un sous-graphe connexe. Pour les deux problèmes précédents, nous examinons le prix de la connexité, défini comme étant le rapport entre la taille minimum d’un ensemble répondant à la version connexe du problème et celle d’un ensemble du problème originel. Nous prouvons la difficulté du calcul du prix de la connexité d’un graphe. Cependant, lorsqu’on exige que le prix de la connexité d’un graphe ainsi que de tous ses sous-graphes induits soit borné par une constante fixée, la situation change complètement. En effet, pour les problèmes de vertex cover et de dominating set, nous avons pu caractériser ces classes de graphes pour de petites constantes.<p>Ensuite, nous caractérisons en termes de dominating sets connexes les graphes Pk- free, graphes n’ayant pas de sous-graphes induits isomorphes à un chemin sur k sommets. Beaucoup de problèmes sur les graphes sont étudiés lorsqu’ils sont restreints à cette classe de graphes. De plus, nous appliquons cette caractérisation à la 2-coloration dans les hypergraphes. Pour certains hypergraphes, nous prouvons que ce problème peut être résolu en temps polynomial.<p>Finalement, nous travaillons sur le problème de Pk-hitting set. Un Pk-hitting set est un ensemble de sommets qui rencontrent tous les chemins sur k sommets. Nous développons un algorithme d’approximation avec un facteur de performance de 3. Notre algorithme, basé sur la méthode primal-dual, fournit un Pk-hitting set dont la taille est au plus 3 fois la taille minimum d’un Pk-hitting set. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Cette thèse étudie des systèmes locaux de gestion de transfert de pétrole ayant une architecture de réseau de canalisation. Pour leur représentativité, deux systèmes localisés au Venezuela et appartenant à l'entreprise PDVSA (Pétroles du Venezuela) ont été retenus pour illustrer les méthodes proposées et les valider : le Terminal Maritime de Pétrole de Guaraguao et le Centre de Stockage de Punta de Palmas. Dans ces réseaux des connexions, appelées « alignements », sont établies en ouvrant/fermant des vannes à travers d'un système SCADA (Supervisory Control and Data Acquisition). Le choix d'un alignement doit tenir compte de critères d'optimisation. La minimisation des interférences avec d'autres alignements, liée à la notion de capacité opérative, a été identifiée comme le critère de choix le plus important. Les contributions de cette thèse reposent sur une modélisation sous forme de graphes, et sur des algorithmes appartenant au domaine de la recherche opérationnelle. Elles contribuent à fournir aux opérateurs de supervision des outils d'analyse permettant d'optimiser le choix des alignements. Des indicateurs permettant de quantifier l'impact des opérations d'alignement ou des défaillances, sur la capacité opérative du système, sont proposés. La minimisation de l'impact sur la capacité opérative, va correspondre à la minimisation des interférences avec des alignements potentiels. Un algorithme de calcul de ces indicateurs, est présenté, ainsi que des algorithmes de recherche de chemin, de détermination d'éléments critiques, et de recherche d'alignements utilisant des pompes. Ces algorithmes sont basés sur des algorithmes classiques s'adressant au problème du plus court chemin, du flot maximum et du nombre maximum de chemins disjoints. Cependant, ils utilisent des méthodes innovantes, comme l'ajout de contraintes considérant l'existence de sous-types d'alignements, le calcul dynamique des coûts des chemins à partir de son impact sur la capacité opérative, et la recherche de chemins via un point intermédiaire obligatoire. Les contributions sont potentiellement applicables dans des domaines autres que le transport de pétrole. Les algorithmes ont été mis en œuvre en utilisant le langage Python et ont été testés en utilisant les données réelles des réseaux étudiés. L'objectif à moyen terme de ces travaux est le développement d'un logiciel d'assistance à la prise de décision. / This thesis studies local crude oil transportation systems with a pipe network architecture. Two representative systems, belonging to PDVSA (Venezuelan oil company), have been studied: the Guaraguao Crude Oil Seaport and the Punta de Palmas Tanks Yard. In this systems, connections, called "alignments", are established by opening/closing valves using a SCADA(Supervisory Control and Data Acquisition) system. Alignment choice is made based on optimization criteria. Interferences minimization with other alignments, related to the notion of operative capacity, has been identified as the most important criterion. The contributions of this thesis are based on graph modelling and algorithms from operational research. The main goal is to provide analysis tools allowing alignment choice optimization. Indexes permitting the quantification of alignments or failures impact on the operative capacity of the system are proposed. Minimizing the impact on the operative capacity will correspond to minimizing interferences with potential alignments. An algorithm computing these indexes is presented, as well as complementary developments such as a path search algorithm, an algorithm for critical elements determination, and algorithm for alignments using pumps. These algorithms are based on classical algorithms for the shortest path problem, the maximum flow problem and the maximum disjoint paths problem. However, they use innovative methods such as adding constraints when considering alignment sub-types, the dynamic computation of path costs based on their impact on operative capacity, and path search considering an obligatory intermediate node. These contributions can potentially be applied in areas other than oil transportation. The algorithms had been implemented in Python and had been tested using real data from the studied systems. The middle term goal of these works is the development of assistance software for decision making.

Dans cette thèse, nous nous intéressons à la recherche d’images similaires avec des descripteurs structurés par découpages d’images sur les graphes.Nous proposons une nouvelle approche appelée “bag-of-bags of words” (BBoW) pour la recherche d’images par le contenu (CBIR). Il s’agit d’une extension du modèle classique dit sac-de-mots (bag of words - BoW). Dans notre approche, une image est représentée par un graphe placé sur une grille régulière de pixels d’image. Les poids sur les arêtes dépendent de caractéristiques locales de couleur et texture. Le graphe est découpé en un nombre fixe de régions qui constituent une partition irrégulière de l’image. Enfin, chaque partition est représentée par sa propre signature suivant le même schéma que le BoW. Une image est donc décrite par un ensemble de signatures qui sont ensuite combinées pour la recherche d’images similaires dans une base de données. Contrairement aux méthodes existantes telles que Spatial Pyramid Matching (SPM), le modèle BBoW proposé ne repose pas sur l’hypothèse que des parties similaires d’une scène apparaissent toujours au même endroit dans des images d’une même catégorie. L’extension de cette méthode ` a une approche multi-échelle, appelée Irregular Pyramid Matching (IPM), est ´ également décrite. Les résultats montrent la qualité de notre approche lorsque les partitions obtenues sont stables au sein d’une même catégorie d’images. Une analyse statistique est menée pour définir concrètement la notion de partition stable.Nous donnons nos résultats sur des bases de données pour la reconnaissance d’objets, d’indexation et de recherche d’images par le contenu afin de montrer le caractère général de nos contributions / Image representation is a fundamental question for several computer vision tasks. The contributions discussed in this thesis extend the basic bag-of-words representations for the tasks of object recognition and image retrieval.In the present thesis, we are interested in image description by structural graph descriptors. We propose a model, named bag-of-bags of words (BBoW), to address the problems of object recognition (for object search by similarity), and especially Content-Based Image Retrieval (CBIR) from image databases. The proposed BBoW model, is an approach based on irregular pyramid partitions over the image. An image is first represented as a connected graph of local features on a regular grid of pixels. Irregular partitions (subgraphs) of the image are further built by using graph partitioning methods. Each subgraph in the partition is then represented by its own signature. The BBoW model with the aid of graphs, extends the classical bag-of-words (BoW) model by embedding color homogeneity and limited spatial information through irregular partitions of an image. Compared to existing methods for image retrieval, such as Spatial Pyramid Matching (SPM), the BBoW model does not assume that similar parts of a scene always appear at the same location in images of the same category. The extension of the proposed model to pyramid gives rise to a method we named irregular pyramid matching (IPM).The experiments demonstrate the strength of our approach for image retrieval when the partitions are stable across an image category. The statistical analysisof subgraphs is fulfilled in the thesis. To validate our contributions, we report results on three related computer vision datasets for object recognition, (localized)content-based image retrieval and image indexing. The experimental results in a database of 13,044 general-purposed images demonstrate the efficiency and effectiveness of the proposed BBoW framework.