Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert. Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel. Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend. Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.

Το ερευνητικό αντικείμενο της συγκεκριμένης διατριβής αναφέρεται στην επεξεργασία έγχρωμης εικόνας με χρήση της θεωρίας γράφων, την ανάκτηση εικόνας καθώς και την οργάνωση / διαχείριση βάσεων δεδομένων με μεθόδους γραφημάτων και αναγνώρισης προτύπων, με εφαρμογή σε πολυμέσα. Τα συγκεκριμένα προβλήματα προσεγγίστηκαν διατηρώντας τη γενικότητά τους και επιλύθηκαν με βάση τα ακόλουθα σημεία: 1. Ανάπτυξη τεχνικών για την επιλογή χαρακτηριστικών από τις εικόνες βάσει χαρακτηριστικών χαμηλού επιπέδου (χρώματος και υφής), για χρήση τους σε εφαρμογές ομοιότητας και ανάκτησης εικόνας. 2. Υπολογισμός μετρικών και αποστάσεων στο χώρο των χαρακτηριστικών. 3. Μελέτη της πολυσχιδούς δομής των εικόνων μιας βάσης στο χώρο των χαρακτηριστικών. 4. Ελάττωση της διάστασης του χώρου και παραγωγή αναπαραστάσεων δύο διαστάσεων. 5. Εφαρμογή των μεθόδων αυτών σε υποκειμενικές αποστάσεις εικόνων. Η θεωρία γράφων και οι μέθοδοι αναγνώρισης προτύπων χρησιμοποιήθηκαν προκειμένου να παρουσιαστούν βέλτιστες λύσεις αφενός στο πρόβλημα της ανάκτησης εικόνων από βάσεις δεδομένων και αφετέρου στην οργάνωση και διαχείριση τέτοιων βάσεων εικόνων. Η διατριβή φέρνει πιο κοντά την επεξεργασία εικόνας με μεθόδους προερχόμενες από τη θεωρία γραφημάτων, τη στατιστική και την αναγνώριση προτύπων. Σε όλη τη διάρκεια της διατριβής, ιδιαίτερη έμφαση δόθηκε στο ζήτημα της εύρεσης του κατάλληλου συνδυασμού μεταξύ της αποτελεσματικότητας των συστημάτων και της αποδοτικότητας στα πλαίσια της εφαρμογής των προτεινόμενων αλγοριθμικών διαδικασιών. Τα αναλυτικά πειραματικά αποτελέσματα που πραγματοποιήθηκαν, αποδεικνύουν την βελτιωμένη απόδοση των προτεινόμενων μεθοδολογιών. / The subject of this doctoral thesis is related to color image processing using graph theoretic methods, image retrieval and image database management and organization in the reduced feature space, using pattern recognition analysis, with multimedia applications. The author attempted to approach the thesis subject by retaining its genericness and addressing the following points: 1. Development of techniques for extraction of image visual attributes based on low level features (color and texture information), to be used for image similarity and retrieval practices. 2. Calculation of metrics and distances in the feature space. 3. Study of the image manifolds created in the selected feature space. 4. Application of dimensionality reduction techniques and production of biplots. 5. Application of the proposed methodologies using perceptual image distances. Graph theory and pattern recognition methodologies were incorporated in order to provide novel solution to color image retrieval of image databases, as well as to image database management and organization. The current thesis brings closer image processing with graph theoretic methodologies, statistical analysis and pattern recognition. Throughout the thesis, consideration has been taken for finding the best trade off between effectiveness and efficiency when applying the proposed algorithmic procedures. The extended experimental results carried out in all stages of the projected studies reveal the enhanced performance of the proposed methodologies.

L’objectif principal de cette thèse est d’étudier le problème du contrôle de suivi distribué pour les systèmes de formation de multi-robots à contrainte non holonomique. Ce contrôle vise à entrainer une équipe de robots mobile de type monocycle pour former une configuration de formation désirée avec son centroïde se déplaçant avec une autre trajectoire de référence dynamique et pouvant être spécifié par le leader virtuel ou humain. Le problème du contrôle de suivi a été résolu au cours de cette thèse en développant divers contrôleurs distribués pratiques avec la considération d’un taux de convergence plus rapide, une précision de contrôle plus élevée, une robustesse plus forte, une estimation du temps de convergence explicite et indépendante et moins de coût de communication et de consommation d’énergie. Dans la première partie de la thèse nous étudions d’abord au niveau du chapitre 2 la stabilité à temps fini pour les systèmes de formation de multi-robots. Une nouvelle classe de contrôleur à temps fini est proposée dans le chapitre 3, également appelé contrôleur à temps fixe. Nous étudions les systèmes dynamiques de suivi de formation de multi-robots non holonomiques dans le chapitre 4. Dans la deuxième partie, nous étudions d'abord le mécanisme de communication et de contrôle déclenché par l'événement sur les systèmes de suivi de la formation de multi-robots non-holonomes au chapitre 5. De plus, afin de développer un schéma d'implémentation numérique, nous proposons une autre classe de contrôleurs périodiques déclenchés par un événement basé sur un observateur à temps fixe dans le chapitre 6. / The main aim of this thesis is to study the distributed tracking control problem for the multi-robot formation systems with nonholonomic constraint, of which the control objective it to drive a team of unicycle-type mobile robots to form one desired formation configuration with its centroid moving along with another dynamic reference trajectory, which can be specified by the virtual leader or human. We consider several problems in this point, ranging from finite-time stability andfixed-time stability, event-triggered communication and control mechanism, kinematics and dynamics, continuous-time systems and hybrid systems. The tracking control problem has been solved in this thesis via developing diverse practical distributed controller with the consideration of faster convergence rate, higher control accuracy, stronger robustness, explicit and independent convergence time estimate, less communication cost and energy consumption.In the first part of the thesis, we first study the finite-time stability for the multi-robot formation systems in Chapter 2. To improve the pior results, a novel class of finite-time controller is further proposed in Chapter 3, which is also called fixed-time controller. The dynamics of nonholonomic multi-robot formation systems is considered in Chapter 4. In the second part, we first investigate the event-triggered communication and control mechanism on the nonholonomic multi-robot formation tracking systems in Chapter 5. Moreover, in order to develop a digital implement scheme, we propose another class of periodic event-triggered controller based on fixed-time observer in Chapter 6.

Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'Axenovich. / This dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich.

Pour faire face aux mutations du paysage énergétique, les réseaux de distribution d'électricité sont soumis à des exigences de fonctionnement avec des indices de fiabilité à garantir. Dans les années à venir, de grands investissements sont prévus pour la construction des réseaux électriques flexibles, cohérents et efficaces, basés sur de nouvelles architectures et des solutions techniques innovantes, adaptatifs à l'essor des énergies renouvelables. En prenant en compte ces besoins industriels sur le développement des réseaux de distribution du futur, nous proposons, dans cette thèse, une approche reposant sur la théorie des graphes et l'optimisation combinatoire pour la conception de nouvelles architectures pour les réseaux de distribution. Notre démarche consiste à étudier le problème général de recherche d'une architecture optimale qui respecte l'ensemble de contraintes topologiques (redondance) et électrotechniques (courant maximal, plan de tension) selon des critères d'optimisation bien précis : minimisation du coût d'exploitation (OPEX) et minimisation de l'investissement (CAPEX). Ainsi donc, les deux familles des problèmes combinatoires (et leurs relaxations) ont été explorées pour proposer des résolutions efficaces (exactes ou approchées) du problème de planification des réseaux de distribution en utilisant une formulation adaptée. Nous nous sommes intéressés particulièrement aux graphes 2-connexes et au problème de flot arborescent avec pertes quadratiques minimales. Les résultats comparatifs de tests sur les instances de réseaux (fictifs et réels) pour les méthodes proposées ont été présentés. / To cope with the changes in the energy landscape, electrical distribution networks are submitted to operational requirements in order to guarantee reliability indices. In the coming years, big investments are planned for the construction of flexible, consistent and effective electrical networks, based on the new architectures, innovative technical solutions and in response to the development of renewable energy. Taking into account the industrial needs of the development of future distribution networks, we propose in this thesis an approach based on the graph theory and combinatorial optimization for the design of new architectures for distribution networks. Our approach is to study the general problem of finding an optimal architecture which respects a set of topological (redundancy) and electrical (maximum current, voltage plan) constraints according to precise optimization criteria: minimization of operating cost (OPEX) and minimization of investment (CAPEX). Thus, the two families of combinatorial problems (and their relaxations) were explored to propose effective resolutions (exact or approximate) of the distribution network planning problem using an adapted formulation. We are particularly interested in 2-connected graphs and the arborescent flow problem with minimum quadratic losses. The comparative results of tests on the network instances (fictional and real) for the proposed methods were presented.

This thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. The d-dimensional hypercube is the graph with vertex set {0,1}^d where two vertices are adjacent if they differ in exactly one coordinate. In Chapter 2 we obtain an upper bound on the 'saturation number' of Q_m in Q_d. Specifically, we show that for m &ge; 2 fixed and d large there exists a subgraph G of Q_d of bounded average degree such that G does not contain a copy of Q_m but, for every G' such that G &subne; G' &sube; Q_d, the graph G' contains a copy of Q_m. This result answers a question of Johnson and Pinto and is best possible up to a factor of O(m). In Chapter 3, we show that there exists &epsilon; &gt; 0 such that for all k and for n sufficiently large there is a collection of at most 2^{(1-&epsilon;)k} subsets of [n] which does not contain a chain of length k+1 under inclusion and is maximal subject to this property. This disproves a conjecture of Gerbner, Keszegh, Lemons, Palmer, P&aacute;lv&ouml;lgyi and Patk&oacute;s. We also prove that there exists a constant c &isin; (0,1) such that the smallest such collection is of cardinality 2^{(1+o(1))^ck} for all k. In Chapter 4, we obtain an exact expression for the 'weak saturation number' of Q_m in Q_d. That is, we determine the minimum number of edges in a spanning subgraph G of Q_d such that the edges of E(Q_d)\E(G) can be added to G, one edge at a time, such that each new edge completes a copy of Q_m. This answers another question of Johnson and Pinto. We also obtain a more general result for the weak saturation of 'axis aligned' copies of a multidimensional grid in a larger grid. In the r-neighbour bootstrap process, one begins with a set A₀ of 'infected' vertices in a graph G and, at each step, a 'healthy' vertex becomes infected if it has at least r infected neighbours. If every vertex of G is eventually infected, then we say that A₀ percolates. In Chapter 5, we apply ideas from weak saturation to prove that, for fixed r &ge; 2, every percolating set in Q_d has cardinality at least (1+o(1))(d choose r-1)/r. This confirms a conjecture of Balogh and Bollob&aacute;s and is asymptotically best possible. In addition, we determine the minimum cardinality exactly in the case r=3 (the minimum cardinality in the case r=2 was already known). In Chapter 6, we provide a framework for proving lower bounds on the number of comparable pairs in a subset S of a partially ordered set (poset) of prescribed size. We apply this framework to obtain an explicit bound of this type for the poset &Vscr;(q,n) consisting of all subspaces of &Fopf;_qⁿordered by inclusion which is best possible when S is not too large. In Chapter 7, we apply the result from Chapter 6 along with the recently developed 'container method,' to obtain an upper bound on the number of antichains in &Vscr;(q,n) and a bound on the size of the largest antichain in a p-random subset of &Vscr;(q,n) which holds with high probability for p in a certain range. In Chapter 8, we construct a 'finitely forcible graphon' W for which there exists a sequence (&epsilon;_i)^&infin;_i=1 tending to zero such that, for all i &ge; 1, every weak &epsilon;_i-regular partition of W has at least exp(&epsilon;_i^-2/2^{5log&lowast;&epsilon;_i^-2}) parts. This result shows that the structure of a finitely forcible graphon can be much more complex than was anticipated in a paper of Lov&aacute;sz and Szegedy. For positive integers p,q with p/q &VerticalSeparator;&ge; 2, a circular (p,q)-colouring of a graph G is a mapping V(G) &rarr; &Zopf;_p such that any two adjacent vertices are mapped to elements of &Zopf;_p at distance at least q from one another. The reconfiguration problem for circular colourings asks, given two (p,q)-colourings f and g of G, is it possible to transform f into g by recolouring one vertex at a time so that every intermediate mapping is a p,q-colouring? In Chapter 9, we show that this question can be answered in polynomial time for 2 &le; p/q &LT; 4 and is PSPACE-complete for p/q &ge; 4.

Cette thèse a pour objectif d’apporter un ensemble d’outils logiciels s’inscrivant dans une méthodologie globale de conception de systèmes mécatroniques. Elle arrive en complément de travaux déjà menés au sein du laboratoire sur le pré-dimensionnement d’actionneurs aéronautiques de nouvelle génération : les actionneurs électromécaniques (EMA). Cette technologie apporte de nouvelles problématiques qui forcent les ingénieurs à modifier leur processus de développement et ce dès la phase de spécification où des profils de mission devront être générés/transformés/analysés de manière à simplifier la conception et assurer leur validation. Une toolbox Simulink a donc été créée dans cette thèse pour répondre à ce besoin de transformation de l’information entre avionneur et systémier. Comme tout système embarqué, le concepteur fait face à des compromis entre performances, durée de vie et intégration, qui peuvent se résumer à un problème d’optimisation décrit par un ensemble d’équations et de contraintes. Un effort particulier de description a été mené sur le conditionnement de ces équations sous la forme d’un séquencement de calculs explicites adaptés aux algorithmes d’optimisation. La méthode et son implémentation logicielle, toutes deux basées sur la théorie des graphes, interagissent avec le concepteur de manière à l’informer des erreurs de singularité ou de bouclages algébriques apparaissant dans son problème et à lui fournir des pistes de résolution. Pour finir, des études de pré-dimensionnement d’actionneurs de train d’atterrissage et de surfaces de vol primaires (aileron et spoiler), réalisées dans le cadre de cette thèse, dresseront les possibilités offertes par cette approche innovante : conception intégrée avec une cinématique complexe, conception collaborative pluri-partenaires découplée, utilisation de surfaces de réponse pour accélérer l’optimisation / The aim of this thesis is to bring a package of software tools included in a whole methodology dealing with mechatronic systems design. It comes as an add-on to the work already carried out at the laboratory in the field of the new generation of aircraft actuation systems: electromechanical actuators (EMA). This technology triggers new problematics leading the engineers to modify their development process as early as the specification phase, when mission profiles have to be generated/transformed/analyzed in order to simplify the design and ensure the validation step. Thus a Simulink toolbox has been created to meet the need for an information translator working as an intermediate between airframer and system-supplier. As for all the embedded systems, the designer has to face some performance-lifetime-integration trade-off, which can be considered as an optimization problem described by a set of equations and constraints. Particular attention is paid here to the conditioning of those explicit equations in order to obtain a standardized calculation sequence adapted to many optimization algorithms. The method and implemented software, both based on the graph theory, interact with the designer to inform him on the possible singularity and algebraic loop issues, providing some leads for their resolution. Finally, some preliminary sizing studies of landing gear and primary flight control surfaces (aileron and spoiler) actuation systems are presented to highlight the possibilities brought out by this innovative approach: integrated design with complex kinematics, collaborative multi-partners design, use of response surfaces to speed up the optimization

Neste trabalho, foram utilizadas técnicas e conceitos tipicamente encontrados em estudos de Redes Complexas, uma sub-área da Física Estatística, para caracterizar a Internet e sua evolução em uma década, de 1998 a 2007. Foi considerada como unidade básica de análise, a estrutura Sistema Autônomo. Nesta caracterização, foram utilizadas várias ferramentas computacionais desenvolvidas em linguagem C/C++, que permitiram classificar, simular e modelar propriedades dinâmicas. Dentre estas propriedades podemos destacar o coeficiente de conectividade, fundamental para os estudos topológicos, e o parâmetro menor caminho médio, ambos baseados nas propriedades da matriz adjacência. Os dados experimentais foram inicialmente obtidos nos roteadores de borda da RedeRio de Computadores - FAPERJ e posteriormente, os dados relativos ao intervalo de estudo, foram retirados da base de dados disponibilizada pela Universidade de Oregon. Foi proposto um modelo de crescimento de uma rede complexa baseado nas premissas de crescimento contínuo e conexão preferencial não linear com suporte aos mecanismos de rearranjo e novas conexões entre nós já existentes. Este modelo se mostrou bastante adequado no estudo das propriedades consideradas. Foi desenvolvido um método para cálculo do menor caminho médio que apresentou performance superior àqueles normalmente utilizados pela comunidade acadêmica. O comportamento da topologia sob o ponto de vista da distribuição de probabilidades de conexão e do ranque de conectividade, apresentaram comportamento linear constante no período estudado com coeficientes médios iguais a -2,0 e -0,93, respectivamente. O parâmetro menor caminho médio global da Internet permaneceu praticamente inalterado e igual a 4, 2 ao longo da década estudada. / Connection networks are observed in many areas of human knowledge. The characterization and topological studies of these networks may be performed through distribution of connectivity degrees, rank properties, shortest path length between nodes, adjacency matrix etc, typical concepts from Complex networks, a filed of study of Statistical Physics domain. In this thesis we characterize the Internet connections evolution from 1998 to 2007. The Internet may be seen under several levels of reach and complexity considering different basic units. A wide vision is to consider the Internet basic element as an Autonomous System - AS, which is defined as a cluster of LANs or routers submitted to the same policy of usage, connectivity and technically administrated by the same network management group. The complex network considered in this work is composed by Autonomous Systems (vertices) and the established tra connection (edges) between them obtained from the BGP routing table. Many interesting property of this networks is analyzed, e.g. degree distribution (the rank and outdegree exponents) from 1998 to 2007 and the shortest path length (L), obtained by a proposed computational method (Friburgo algorithm) among each pair of ASs represented in the adjacency matrix. Finally, we present the behavior of the power law function and the shortest path length of the Internet for each year. Simulations of the connections network were carried out by a proposed model developed from continuous growth premises, possibilities of new and rearranging connections. This model was based on the concept of potential preferable connection showing a stable exponential factor that reproduces the true shortest path parameter over the decade.

Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-11T17:36:54Z No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:21Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T13:03:27Z (GMT) No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) / Made available in DSpace on 2016-10-21T13:03:34Z (GMT). No. of bitstreams: 1 DissVAK.pdf: 4608619 bytes, checksum: 3022034b9035e4e8caf1195902d24581 (MD5) Previous issue date: 2016-08-12 / Não recebi financiamento / Cluster analysis is the organization of a collection of patterns into clusters based on similarity which is determined by using properties of data. Clustering techniques can be useful in a variety of knowledge domains such as biotechnology, computer vision, document retrieval and many others. An interesting area of biology involves the concept of microRNAs (miRNAs) that are approximately 22 nucleotide-long non-coding RNA molecules that play important roles in gene regulation. Clustering miRNA sequences can help to understand and explore sequences belonging to the same cluster that has similar biological functions. This research work investigates and explores seven unsupervised clustering algorithms based on graphs that can be divided into three categories: algorithm based on region of influence, algorithm based on minimum spanning tree and spectral algorithm. To assess the contribution of the proposed algorithms, data from miRNA families stored in the online miRBase database were used in the conducted experiments. The results of these experiments were presented, analysed and evaluated using clustering validation indexes as well as visual analysis. / A análise de agrupamento é uma organização de coleção de padrões em grupos, baseando-se na similaridade das propriedades pertencentes aos dados. A técnica de agrupamento pode ser utilizado em muitas áreas de conhecimento como biotecnologia, visão computacional, recuperação de documentos, entre outras. Uma área interessante da biologia envolve o conceito de microRNAs (miRNAs), que são moléculas não-codificadas de RNA com aproximadamente 22 nucleotídeos e que desempenham um papel importante na regulação dos genes. O agrupamento de sequências de miRNA podem ajudar em sua exploração e entendimento, pois as sequências que pertencem ao mesmo grupo possuem uma função biológica similar. Esse trabalho explora e investiga sete algoritmos de agrupamentos não-supervisionados baseados em grafos que podem ser divididos em três categorias: algoritmos baseados em região de influência, algoritmos baseados em árvore spanning minimal e algoritmo espectral. Para avaliar a contribuição dos algoritmos propostos, os experimentos conduzidos utilizaram os dados das famílias de miRNAs disponíveis no banco de dados denominado miRBase. Os resultados dos experimentos foram apresentados, analisados e avaliados usando índices de validação de agrupamento e análise visual.

Os sistemas de transporte público (STP) são entidades complexas formados por vários subsistemas (administração, gerenciamento de frota, manutenção de veículos, segurança, bilhetagem, engenharia de tráfego, urbanismo, recursos humanos, entre outros). Os STP oferecem diversas rotas de veículos coletivos para atender os usuários do serviço mas o planejamento das rotas é uma das áreas que exigem atenção e são de difícil avaliação de desempenho. Estas rotas formam malhas que podem ser abstraídas como grafos, em vários tipos de representações, como por exemplo as paradas associadas aos nós e uma rota (ou linha) de veículos associada a uma sequência de conexões ou arestas que interligam estes pontos. Da representação do STP como grafos, é possível extrair informações importantes a partir de métricas como dimensões, centralidades, pesos, entre outras, e classificar o STP em algum modelo já estudado. A partir do modelo estabelecido, melhorias no sistema podem ser propostas e uma posterior re-análise dos resultados das novas medidas no modelo pode justificar ou não uma possível implementação destas propostas no sistema real. Neste trabalho um sistema de transporte público foi analisado como rede complexa, especificamente o STP de Curitiba, no estado do Paraná, Brasil. Demonstrou-se que este sistema, em representação espaço-L, possui características de rede complexa do tipo scale free. Tal sistema possuía onze categorias de rotas de ônibus, sendo que as principais categorias foram analisadas como rede complexa para avaliar sua influência nas métricas do sistema como um todo. Adicionalmente, combinando as métricas de redes complexas com o método k-means de agrupamento nesse STP, foram identificadas regiões geográficas da cidade que possuem as maiores e menores características de conectividade para os habitantes de Curitiba, sinalizando possíveis degradações de atendimento do sistema de transporte. O estudo revelou que, em Curitiba, a região central é a melhor servida, enquanto que algumas regiões periféricas no sudeste e nordeste da cidade são pouco favorecidas de transporte público. / Public transportation systems (PTS) are complex entities composed by many different subsystems (administration, vehicles management and maintenance, security, taxing, trafic engineering, urbanism, human resources and others). PTS offers various routes using public sharing vehicules to serve users, and the route planning is one of the issues that demand attention and has hard performance assessment. This routes form meshes in many types of representation, e. g., vehicle stops as nodes and a route as a sequence of links that connect their nodes. From PTS representation as graphs, it is possible to extract valuable informations from metrics as dimensions, centralities, weight and others, and to classify this PTS within some model already studied. Towards established models, system enhancements can be proposed and posterior re- analysis of such improved systems can justify or not their implementation in the real system. At this work a public transport system was analysed as Complex Network, specifically Curitiba’s PTS, (Paraná, Brazil). Here it was demonstrated that this system, represented in l-space, has network characteristics of scale-free networks. This system has eleven bus routes categories, in which main categories were analysed as complex networks to assess their influence on whole system metrics. Additionally, combining both complex network metrics and k-means method on this PTS, geographic areas of the city showing best and worst connectivity characteristics for the inhabitants of Curitiba were identified, which allows detecting potential transportation system weakness. This study revealed that Curitiba’s central region is best served, and some periphericals areas at southeast and northeast have low public transportation service.