Dans de multiples domaines, des structures qui semblent à première vue très simples sont très mal comprises. Un exemple qui nous vient vite à l'esprit, c'est la structure de l'ADN qui n'est qu'une suite d'un alphabet de quatre bases azotées, mais dont la combinaison cache encore de nombreux mystères. Dans ce mémoire nous nous sommes attardés à la rotation, la réflexion et à la permutation des lettres d'un mot. Si l'on ne prend que la rotation, l'ensemble de tous les mots que l'on peut fabriquer par rotation des lettres d'un mot donné est appelé collier. Cette notion mathématique bien connu revient, dans le concret, à écrire notre mot donné sur les perles d'un collier et à constater que le fait de tourner le collier autour de notre cou ne change pas l'objet lui-même. En ajoutant la réflexion à la rotation, on obtient les bracelets. Toutefois, lorsque l'on combine la permutation des lettres de l'alphabet aux bracelets ou aux colliers, on obtient des objets beaucoup moins connus et moins bien compris. Au cours de ce mémoire, nous nous sommes donc intéressés aux mots dont la permutation des lettres est combinée à d'autres actions. Deux principaux problèmes ont occupés nos recherches: le comptage de ces objets ainsi que l'énumération de ceux-ci. Ces deux avenues ont été fructueuses et nous ont donné de nouveaux résultats. Nous avons de plus trouvé divers domaines où ces objets semblent être un modèle pertinent et où nos résultats pourraient s'appliquer. / Simple structures seem to emerge from many different sciences. However, we still have a limited undertanding of those structures. A good exemple is DNA structure which is simply a series of nitrogenous bases taken from a four letter alphabet. Unfortunately, even if its structure is very simple, DNA still keeps many secrets to the scientific community. A better understanding of basic structures seems to be the basis to a better understanding of our environment. This is why we have focused on words under the action of rotation, reflexion and permutation of letters. Words under the action of rotation are called necklaces and are well studied. If the reflection is added to necklaces, bracelets are obtained. However, if we combine alphabet permutation with rotation and/or reflection, less understood objects are obtained. We focused on two major problems: counting objets and generating them. In both directions we have found interesting new results. We also found some fields in which our results could contribute.

L'objectif de ce travail est de développer deux modules pour créer une simulation Monte Carlo ayant comme objectif futur de calculer les doses de radiation d'un traitement en radiothérapie externe. Le premier module permet de lire, modéliser et réduire le nombre de voxels présent dans une série d'images médicales de type DICOM. La réduction doit se faire tout en gardant les informations essentielles pour une simulation Monte Carlo. Un algorithme a été développé pour appliquer une compression de type octree à la distribution des densités électroniques recueillies dans les images de tomodensitométrie. L'image résultante possède ainsi une certaine anisotropie au niveau de la résolution. Des résultats obtenus, la réduction du nombre total de voxels atteinte est de l'ordre de 75% de la taille initiale. Les simulations Monte Carlo démontrent qu'aucune information dosimétrique n'est perdue après la transformation. L'efficacité de la simulation se trouve améliorée tant au niveau de sa rapidité que de son utilisation de la mémoire. Le second module développé est un modèle d'accélérateur linéaire de type Primus (Siemens). Ce modèle permet d'obtenir des distributions de doses pour deux faisceaux de photons d'énergies différentes (6 et 23 megavolts [MV]). Dans les deux cas, les distributions de doses ont été comparées à des mesures expérimentales prises avec une chambre à ionisation. Les distributions de doses dans l'axe central du faisceau ont atteint un niveau de précision de 2%. Au niveau des distributions de doses hors axe, les déviations maximales sont de l'ordre de 5% et de 2mm dans les pénombres. Pour le faisceau de 23 MV, la géométrie présente une asymétrie qui devra être corrigée en modifiant le filtre égalisateur ou en utilisant une source de radiation asymétrique. Dans tous les cas, l'ouverture des collimateurs secondaires devra être optimisée afin d'éliminer les erreurs au niveau de la pénombre. Une fois ces modifications effectuées, les images DICOM compressées avec l'octree pourront être insérées à l'intérieur du modèle de l'accélérateur. Ce faisant, il suffirait d'ajuster la configuration des faisceaux et du patient pour évaluer un traitement en radiothérapie externe.

We present new approaches to define and analyze geometric graphs. <p><p>The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items of a dataset S contained in a region R(p,q) surrounding (p,q). We define region-counting disks and circles, and study the complexity of these objects. Algorithms to compute epsilon-approximations of region-counting distances and approximations of region-counting circles are presented.<p><p>We propose a definition of the locality for properties of geometric graphs. We measure the local density of graphs using the region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs.<p>We illustrate the locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around those vertices. We determine the local diameter of several well-studied graphs such as the Theta-graph, the Ordered Theta-graph and the Skip List Spanner. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties.<p><p>A family of proximity graphs, called Empty Region Graphs (ERG) is presented. The vertices of an ERG are points in the plane, and two points are connected if their neighborhood, defined by a region, does not contain any other point. The region defining the neighborhood of two points is a parameter of the graph. This family of graphs includes several known proximity graphs such as Nearest Neighbor Graphs, Beta-Skeletons or Theta-Graphs. We concentrate on ERGs that are invariant under translations, rotations and uniform scaling of the vertices. We give conditions on the region defining an ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and bounded degree. These conditions take the form of what we call tight regions: maximal or minimal regions that a region must contain or be contained in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and limitations of this general model for constructing a graph from a point set.<p><p>We introduce and analyze sigma-local graphs, based on a definition of locality by Erickson, to illustrate efficient construction algorithm on a subclass of ERGs. / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished

Ces dernières années, les réseaux sont devenus une source importante d’informations dans différents domaines aussi variés que les sciences sociales, la physique ou les mathématiques. De plus, la taille de ces réseaux n’a cessé de grandir de manière conséquente. Ce constat a vu émerger de nouveaux défis, comme le besoin de mesures précises et intuitives pour caractériser et analyser ces réseaux de grandes tailles en un temps raisonnable.<p>La première partie de cette thèse introduit une nouvelle mesure de similarité entre deux noeuds d’un réseau dirigé et pondéré :la covariance “sum-over-paths”. Celle-ci a une interprétation claire et précise :en dénombrant tous les chemins possibles deux noeuds sont considérés comme fortement corrélés s’ils apparaissent souvent sur un même chemin – de préférence court. Cette mesure dépend d’une distribution de probabilités, définie sur l’ensemble infini dénombrable des chemins dans le graphe, obtenue en minimisant l'espérance du coût total entre toutes les paires de noeuds du graphe sachant que l'entropie relative totale injectée dans le réseau est fixée à priori. Le paramètre d’entropie permet de biaiser la distribution de probabilité sur un large spectre :allant de marches aléatoires naturelles où tous les chemins sont équiprobables à des marches biaisées en faveur des plus courts chemins. Cette mesure est alors appliquée à des problèmes de classification semi-supervisée sur des réseaux de taille moyennes et comparée à l’état de l’art.<p>La seconde partie de la thèse introduit trois nouveaux algorithmes de classification de noeuds en sein d’un large réseau dont les noeuds sont partiellement étiquetés. Ces algorithmes ont un temps de calcul linéaire en le nombre de noeuds, de classes et d’itérations, et peuvent dés lors être appliqués sur de larges réseaux. Ceux-ci ont obtenus des résultats compétitifs en comparaison à l’état de l’art sur le large réseaux de citations de brevets américains et sur huit autres jeux de données. De plus, durant la thèse, nous avons collecté un nouveau jeu de données, déjà mentionné :le réseau de citations de brevets américains. Ce jeu de données est maintenant disponible pour la communauté pour la réalisation de tests comparatifs.<p>La partie finale de cette thèse concerne la combinaison d’un graphe de citations avec les informations présentes sur ses noeuds. De manière empirique, nous avons montré que des données basées sur des citations fournissent de meilleurs résultats de classification que des données basées sur des contenus textuels. Toujours de manière empirique, nous avons également montré que combiner les différentes sources d’informations (contenu et citations) doit être considéré lors d’une tâche de classification de textes. Par exemple, lorsqu’il s’agit de catégoriser des articles de revues, s’aider d’un graphe de citations extrait au préalable peut améliorer considérablement les performances. Par contre, dans un autre contexte, quand il s’agit de directement classer les noeuds du réseau de citations, s’aider des informations présentes sur les noeuds n’améliora pas nécessairement les performances.<p>La théorie, les algorithmes et les applications présentés dans cette thèse fournissent des perspectives intéressantes dans différents domaines.<p><p><p>In recent years, networks have become a major data source in various fields ranging from social sciences to mathematical and physical sciences. Moreover, the size of available networks has grow substantially as well. This has brought with it a number of new challenges, like the need for precise and intuitive measures to characterize and analyze large scale networks in a reasonable time. <p>The first part of this thesis introduces a novel measure between two nodes of a weighted directed graph: The sum-over-paths covariance. It has a clear and intuitive interpretation: two nodes are considered as highly correlated if they often co-occur on the same -- preferably short -- paths. This measure depends on a probability distribution over the (usually infinite) countable set of paths through the graph which is obtained by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. The entropy parameter allows to bias the probability distribution over a wide spectrum: going from natural random walks (where all paths are equiprobable) to walks biased towards shortest-paths. This measure is then applied to semi-supervised classification problems on medium-size networks and compared to state-of-the-art techniques.<p>The second part introduces three novel algorithms for within-network classification in large-scale networks, i.e. classification of nodes in partially labeled graphs. The algorithms have a linear computing time in the number of edges, classes and steps and hence can be applied to large scale networks. They obtained competitive results in comparison to state-of-the-art technics on the large scale U.S.~patents citation network and on eight other data sets. Furthermore, during the thesis, we collected a novel benchmark data set: the U.S.~patents citation network. This data set is now available to the community for benchmarks purposes. <p>The final part of the thesis concerns the combination of a citation graph with information on its nodes. We show that citation-based data provide better results for classification than content-based data. We also show empirically that combining both sources of information (content-based and citation-based) should be considered when facing a text categorization problem. For instance, while classifying journal papers, considering to extract an external citation graph may considerably boost the performance. However, in another context, when we have to directly classify the network citation nodes, then the help of features on nodes will not improve the results.<p>The theory, algorithms and applications presented in this thesis provide interesting perspectives in various fields.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

We present a set of approximation results for several covering problems in dense graphs. These results show that for several problems, classical algorithms with constant approximation ratios can be analyzed in a finer way, and provide better constant approximation ratios under some density constraints. In particular, we show that the maximal matching heuristic approximates VERTEX COVER (VC) and MINIMUM MAXIMAL MATCHING (MMM) with a constant ratio strictly smaller than 2 when the proportion of edges present in the graph (weak density) is at least 3/4, or when the normalized minimum degree (strong density) is at least 1/2. We also show that this result can be improved by a greedy algorithm which provides a constant ratio smaller than 2 when the weak density is at least 1/2. We also provide tight families of graphs for all these approximation ratios. We then looked at several algorithms from the literature for VC and SET COVER (SC). We present a unified and critical approach to the Karpinski/Zelikovsky, Imamura/Iwama and Bar-Yehuda/Kehat algorithms, identifying the general the general scheme underlying these algorithms.<p>Finally, we look at the CONNECTED VERTEX COVER (CVC) problem,for which we proposed new approximation results in dense graphs. We first analyze Carla Savage's algorithm, then a new variant of the Karpinski-Zelikovsky algorithm. Our results show that these algorithms provide the same approximation ratios for CVC as the maximal matching heuristic and the Karpinski-Zelikovsky algorithm did for VC. We provide tight examples for the ratios guaranteed by both algorithms. We also introduce a new invariant, the "price of connectivity of VC", defined as the ratio between the optimal solutions of CVC and VC, and showed a nearly tight upper bound on its value as a function of the weak density. Our last chapter discusses software aspects, and presents the use of the GRAPHEDRON software in the framework of approximation algorithms, as well as our contributions to the development of this system.<p><p>/<p><p>Nous présentons un ensemble de résultats d'approximation pour plusieurs problèmes de couverture dans les graphes denses. Ces résultats montrent que pour plusieurs problèmes, des algorithmes classiques à facteur d'approximation constant peuvent être analysés de manière plus fine, et garantissent de meilleurs facteurs d'aproximation constants sous certaines contraintes de densité. Nous montrons en particulier que l'heuristique du matching maximal approxime les problèmes VERTEX COVER (VC) et MINIMUM MAXIMAL MATCHING (MMM) avec un facteur constant inférieur à 2 quand la proportion d'arêtes présentes dans le graphe (densité faible) est supérieure à 3/4 ou quand le degré minimum normalisé (densité forte) est supérieur à 1/2. Nous montrons également que ce résultat peut être amélioré par un algorithme de type GREEDY, qui fournit un facteur constant inférieur à 2 pour des densités faibles supérieures à 1/2. Nous donnons également des familles de graphes extrémaux pour nos facteurs d'approximation. Nous nous somme ensuite intéressés à plusieurs algorithmes de la littérature pour les problèmes VC et SET COVER (SC). Nous avons présenté une approche unifiée et critique des algorithmes de Karpinski-Zelikovsky, Imamura-Iwama, et Bar-Yehuda-Kehat, identifiant un schéma général dans lequel s'intègrent ces algorithmes.<p>Nous nous sommes finalement intéressés au problème CONNECTED VERTEX COVER (CVC), pour lequel nous avons proposé de nouveaux résultats d'approximation dans les graphes denses, au travers de l'algorithme de Carla Savage d'une part, et d'une nouvelle variante de l'algorithme de Karpinski-Zelikovsky d'autre part. Ces résultats montrent que nous pouvons obtenir pour CVC les mêmes facteurs d'approximation que ceux obtenus pour VC à l'aide de l'heuristique du matching maximal et de l'algorithme de Karpinski-Zelikovsky. Nous montrons également des familles de graphes extrémaux pour les ratios garantis par ces deux algorithmes. Nous avons également étudié un nouvel invariant, le coût de connectivité de VC, défini comme le rapport entre les solutions optimales de CVC et de VC, et montré une borne supérieure sur sa valeur en fonction de la densité faible. Notre dernier chapitre discute d'aspects logiciels, et présente l'utilisation du logiciel GRAPHEDRON dans le cadre des algorithmes d'approximation, ainsi que nos contributions au développement du logiciel. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Un stable (ou ensemble indépendant) est un ensemble de sommets qui sont deux à deux non adjacents. De nombreux résultats classiques en optimisation combinatoire portent sur le nombre de stabilité (défini comme la plus grande taille d'un stable), et les stables se classent certainement parmi les structures les plus simples et fondamentales en théorie des graphes.<p><p>La thèse est divisée en deux parties, toutes deux liées à la notion de stables dans un graphe. Dans la première partie, nous étudions un problème de coloration de graphes, c'est à dire de partition en stables, où le but est de minimiser l'entropie de la partition. C'est une variante du problème classique de minimiser le nombre de couleurs utilisées. Nous considérons aussi une généralisation du problème aux couvertures d'ensembles. Ces deux problèmes sont appelés respectivement minimum entropy coloring et minimum entropy set cover, et sont motivés par diverses applications en théorie de l'information et en bioinformatique. Nous obtenons entre autres une caractérisation précise de la complexité de minimum entropy set cover :le problème peut être approximé à une constante lg e (environ 1.44) près, et il est NP-difficile de faire strictement mieux. Des résultats analogues sont prouvés concernant la complexité de minimum entropy coloring.<p><p>Dans la deuxième partie de la thèse, nous considérons les graphes dont le nombre de stabilité augmente dès qu'une arête est enlevée. Ces graphes sont dit être "alpha-critiques", et jouent un rôle important dans de nombreux domaines, comme la théorie extrémale des graphes ou la combinatoire polyédrique. Nous revisitons d'une part la théorie des graphes alpha-critiques, donnant à cette occasion de nouvelles démonstrations plus simples pour certains théorèmes centraux. D'autre part, nous étudions certaines facettes du polytope des ordres totaux qui peuvent être vues comme une généralisation de la notion de graphe alpha-critique. Nous étendons de nombreux résultats de la théorie des graphes alpha-critiques à cette famille de facettes.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2006-2007 / Une solution de plus en plus courante pour appuyer les forces militaires déployées en milieu urbain consiste à utiliser des plates-formes robotisées pour la réalisation des tâches présentant un niveau de risque important. Dans cette optique, les travaux de recherche présentés dans ce mémoire ont permis de développer un système exploitant un capteur volumétrique 3D pour effectuer la modélisation d'environnements urbains et l'exploration efficace de ceux-ci à l'aide d'une plate-forme mobile autonome. Un aspect important de ce projet est que, le modèle 3D de l'environnement étant préservé sous forme d'octree multirésolution tout au long du processus, les modules de cartographie, d'exploration et de navigation qui composent la plate-forme mobile peuvent y avoir accès en tout temps afin d'effectuer leurs tâches respectives. À partir des résultats obtenus pour des tests effectués en simulation et dans un environnement réel, il a été possible de valider que le système développé permet d'explorer un environnement de façon autonome tout en générant de façon simultanée un modèle 3D complet de l'espace parcouru.

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed.<p><p>We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time.<p><p>We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results.<p><p>After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances.<p><p>Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them.<p><p>Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case.<p><p>------------------------------------------------<p><p>Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits.<p><p>Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes.<p><p>Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3.<p><p>Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème.<p><p>Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas. <p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished