[pt] As redes de sensores sem fio se constituem numa área que outorga grandes oportunidades para a oferta de uma série de aplicações inovadoras e com baixo custo. Os dispositivos destas redes são bastantes pequenos e sua fonte de alimentação são baterias. O tempo de vida destas é limitado, limitando assim o tempo da vida dos sensores e da rede como um todo. Por esta razão nos últimos anos o tema de eficiência energética tem atraído grande interesse de pesquisadores. O aumento do custo da energia e do consumo global da energia pelo setor de ICT (Information and Communications Technologies) têm crescido vertiginosamente devido ao aumento continuo do número de clientes e da demanda por aplicações de maior complexidade. Por tudo isso têm sido desenvolvidos distintos métodos e técnicas para economizar energia nas RSSF. Neste trabalho se implementam dois algoritmos que levam em conta critérios para economizar os custos de energia da rede e através de experimentos de simulação se avalia os mesmos. Nos resultados pode se observar as vantagens de trabalhar com sistemas que visam a eficiência energética. / [en] The WSNs (Wireless Sensor Networks) belong to an area that gives rise to great opportunities to spread innovative and low cost applications. These kinds of networks are composed of tiny devices with limited energy. The main source of power supply for WSNs are batteries, which are limited in cycle life, thus limiting the sensors lifetime and the network as a whole. Due to that fact, the energy efficiency network is becoming the main concern to be addressed by researchers. Rising energy prices and global energy consumption by the ICT (Information and Communications Technologies) sector have grown dramatically due to the continuous increase in customer number and the demand for more complex applications. For the reasons outlined above, different energy-saving techniques for WSNs have been developed. Two energy-saving algorithms for WSNs were implemented in this thesis, and they were tested by experimental evaluation using simulation. The results obtained from the simulations showed the advantages of working with systems aiming at energy efficiency.

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-31T18:16:44Z No. of bitstreams: 1 ELVIS RODRIGUES DA SILVA - DISSERTAÇÃO PPGCC 2007..pdf: 3374100 bytes, checksum: 70beb2c61d7b1eb969fe1e64941edd84 (MD5) / Made available in DSpace on 2018-07-31T18:16:44Z (GMT). No. of bitstreams: 1 ELVIS RODRIGUES DA SILVA - DISSERTAÇÃO PPGCC 2007..pdf: 3374100 bytes, checksum: 70beb2c61d7b1eb969fe1e64941edd84 (MD5) Previous issue date: 2007-04 / Os sistemas de roteamento vêm se tornando ferramentas bastante úteis recentemente. Eles pretendem ajudar os usuários a encontrar o caminho mais adequado entre dois lugares de acordo com a distância da viagem, o tempo do percurso, e outros critérios. Esta dissertação apresenta uma arquitetura orientada a serviços e propõe um novo algoritmo de busca de rotas chamado Coolest Path. Este algoritmo habilita personalização multi-critério de acordo com a distância da viagem, o tempo, pontos turísticos e a simplicidade do caminho. Além disso, a dissertação propõe restrições a serem acrescentadas aos caminhos calculados: A-autonomy, onde o usuário define uma constante A e o algoritmo provê um caminho com N paradas, uma a cada distância A; e T-autonomy, onde o usuário define uma constante T e o algoritmo provê um caminho com N paradas, uma a cada T unidades de tempo. Essas paradas são realizadas em pontos de interesse (ex. pontos turísticos). Os algoritmos são fornecidos na forma de serviços Web, ou seja, são acessíveis de qualquer dispositivo conectado à Internet: um browser desktop, um celular ou um quiosque turístico localizado em um aeroporto. O serviço de roteamento é uma extensão ao framework iGIS. / Routing systems have become very powerful tools recently. They help users in finding the most suitable path between two places using travel distance, time and others criteria. This dissertation presents a routing system based on service-oriented architecture, which includes the proposal of an innovative algorithm known as coolest path. This algorithm enables multi-criteria personalization by using travel distance, time, points of interest and path simplicity. Moreover, constrained paths are also supported including the implementation of a-autonomy in road networks and the proposal of a new algorithm: t-autonomy, which returns the best path with N stops, such that the travel time between any two consecutive points in the path is not greater than t. These algorithms are implemented as an iGIS extension by using Web services technology.

Este trabalho investigou diferenças entre grupos etários distintos nas associações semânticas de palavras em três estudos. O primeiro buscou apresentar e discutir pesquisas que avaliaram a organização e processamento léxico-semânticos entre grupos de crianças, adultos e idosos. O segundo comparou as associações semânticas de palavras entre 247 crianças de 3ª série, 108 adultos jovens universitários e 57 idosos. O terceiro analisou comparativamente os grafos computacionais das associações semânticas de palavras entre 57 crianças de 3ª série, 57 adultos jovens universitários e os 57 idosos supracitados. Nos estudos empíricos observou-se que a força de associação entre alvo e associada mais frequente foi maior para as crianças do que para adultos e idosos. Os tamanhos de conjunto significativo e total dos alvos foram, em média, menores para os idosos e o índice de diversidade de respostas foi maior no grupo dos adultos. A modelagem de grafos indicou que crianças possuem redes de associação de palavras com maiores distâncias entre os nós e menor número de nós, ligações e agrupamentos. Adultos e idosos apresentaram redes com estruturas semelhantes. Assim, entende-se que essas associações sofrem reestruturações e ajustes da infância para a idade adulta e que na velhice ocorrem apenas mudanças quantitativas. Limitações e implicações dos estudos para a área são discutidas. / This research investigated differences in three age groups on semantic word associations in three studies. The first one aimed to present and discuss research that investigated the organization and processing of semantic elements in children, adults, and elderly. . The second one compared semantic word associations among 247 third grade children, 108 young college students adults, and 57 elderly. The third study compared semantic associations through graph analysis of 57 third grade children, 57 college students adults, and the 57 elderly cited above. The empirical studies demonstrated that the strength of the first associate to each target was higher for children compared to adults and elderly. The target’s total and meaning set sizes were lower for elderly and the response’s diversity index was higher for adults. Graph analysis suggested that children have semantic word association’s networks with greater inter-node distances and less number of nodes, connections, and clusters. Adults and elderly showed networks with similar structures. It was hypothesized that these associations pass by restructuring and tuning processes from childhood to adulthood and that after the 60 years old only quantitative changes occur. Limitations and contributions to the field are discussed.

O estudo investiga a dinâmica da transformação intra-urbana sob o enfoque teórico da auto-organização, explorando a possibilidade de existência de padrões espaço-temporais no fenômeno de alocação de tipologias funcionais (estoques construídos e atividades) ao longo de um século, no bairro Santana de Porto Alegre- RS-Brasil. A transformação das tipologias funcionais e a auto-regulação do fenômeno locacional são estudadas sob o enfoque da aleatoriedade envolvida nas localizações espaciais das variáveis tipológicas dentro de uma rede espacial de estrutura viária consolidada, permitindo, desta forma, identificar regras microespaciais que estabeleçam conversões entre as tipologias funcionais ao longo do tempo. Parte-se da hipótese básica de que o fenômeno de alocação das unidades de forma construída e atividades abastecem-se da informação contida no cenário urbano presente para o estabelecimento locacional futuro, ou seja, a alocação de uma tipologia funcional em um lote depende do estado tipológico alocado neste lote no período imediatamente anterior. O estudo investiga a dinâmica da transformação intra-urbana sob o enfoque teórico da auto-organização, explorando a possibilidade de existência de padrões espaço-temporais no fenômeno de alocação de tipologias funcionais (estoques construídos e atividades) ao longo de um século, no bairro Santana de Porto Alegre- RS-Brasil. A transformação das tipologias funcionais e a auto-regulação do fenômeno locacional são estudadas sob o enfoque da aleatoriedade envolvida nas localizações espaciais das variáveis tipológicas dentro de uma rede espacial de estrutura viária consolidada, permitindo, desta forma, identificar regras microespaciais que estabeleçam conversões entre as tipologias funcionais ao longo do tempo. Parte-se da hipótese básica de que o fenômeno de alocação das unidades de forma construída e atividades abastecem-se da informação contida no cenário urbano presente para o estabelecimento locacional futuro, ou seja, a alocação de uma tipologia funcional em um lote depende do estado tipológico alocado neste lote no período imediatamente anterior. A espacialização das regras de transição no ArcView Gis 3.3 representa a ultima etapa do modelo e permite a validação do método proposto, através da comparação dos locais com maior probabilidade de mudança apresentados pelo modelo com os locais onde de fato ocorreram as conversões entre os tipos de unidades de forma construída e atividades. Nesta etapa também são possíveis diferentes explorações como a predição de estados futuros, descrição de diferentes tipos de comportamentos entre os diferentes tipos de estoques e atividades, e inferência de zonas mais ou menos instáveis às transformações. A investigação demonstra que o estado tipológico atual condensa toda a história sistêmica definindo a qualidade de markovicidade ao fenômeno locacional, possibilitando a inferência de possíveis estados futuros e patamares de estabilidade sistêmica através dos padrões comportamentais estabelecidos dentro da rede espaço-temporal. O estudo amplia o conhecimento a respeito do fenômeno locacional e colabora para o desenvolvimento de modelos aplicados ao planejamento urbano, dirigidos para a gestão do uso do solo e da qualidade ambiental urbana. / The study investigates the dynamics of intra-urban transformation using the theoretical perspective of self-organization and exploring the possibility of space-time patterns in the phenomenon of built form change in the span of a century in Porto Alegre, Brazil. The succession of built form and the self-regulation of the locational phenomenon are both studied by the perspective of the randomness of the spatial positioning of typological variables in a spatial network with consolidated road infrastructure. This allows for the identification of micro-spatial rules which establish conversions among the built form units throughout time. The basic hypothesis is that the phenomenon of built form allocation feeds from the information contained in the urban scenario for future locational establishment. Therefore, the allocation of a built form unit in one lot depends on the typological state of the lot in the period immediately before. The investigation of these space-time patterns is undertaken using the investigative method based on the structural representation of the physical base of the lot network (through the Graph Theory), exploring the behaviour of the built form types in time (through the Markov Chains) and inferring about the self-regulation of the systems (using Kolmogorov Entropy and Shannon Information measures). From this description, one can obtain the transaction matrices of each corresponding time period between two decades, reaching a total of nine matrices and three medium matrices, representing the behaviour of the system’s locational phenomenon in three separate phases. The limitations regarding the spatial response of the markovian model are overcome through the spatialization of the transition rules in the irregular cellular network through the program ArcView Gis 3.3. The rules are obtained through conditional transition matrices built from the temporal dependence of the state of the lot in time t+1 with its state in time t and with the state of its neighbors in time t. The spatialization of the transition rules in ArcView Gis 3.3 represents the final stage of the model and allows the validation of the method proposed through the comparison of the locations with higher probability of change presented by the model with the locations where there were in fact conversions between types of built units and activities. In this stage, different explorations are also made possible through the prediction of future states, description of different types of behaviors among the different types of stocks and activities and the inference of zones that are more or less unstable regarding transformations. The study increases the comprehension of the locational phenomenon and collaborates for the development of models applied to urban planning directed towards the management of soil use and urban environmental quality. The investigation demonstrates that the current typological state condenses all the systemic history, granting the locational phenomenon the quality of markovicity, thus allowing the inference of possible future states and systemic stability platforms through the behavioural patterns established in the space-time network.

Submitted by Marcos Grilo Rosa (grilo@uefs.br) on 2017-01-05T19:11:59Z No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Rejected by Maria Auxiliadora da Silva Lopes (silopes@ufba.br), reason: Prezado Marcos, Favor registrar os nomes completos dos participantes da banca; inserir o "abstract" e as "key words". Saudações, Maria Auxiliadora Lopes UFBA/Faced/Biblioteca on 2017-01-09T14:10:18Z (GMT) / Submitted by Marcos Grilo Rosa (grilo@uefs.br) on 2017-01-09T17:16:07Z No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Approved for entry into archive by Maria Auxiliadora da Silva Lopes (silopes@ufba.br) on 2017-01-19T14:35:53Z (GMT) No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / Made available in DSpace on 2017-01-19T14:35:53Z (GMT). No. of bitstreams: 1 tesevsfinalMarcosGrilo.pdf: 11311408 bytes, checksum: 3ce07aff3fe0fb9dc534e80e667eeb5b (MD5) / No campo da inteligência artificial, redes semânticas são utilizadas para a representação de conhecimento e processamento de linguagem natural. Redes semânticas são sistemas de representação do conhecimento baseados em grafos cujos vértices são palavras e as arestas, os relacionamentos entre as palavras estabelecidos por alguma regra. Lidar com redes semânticas é uma atividade bastante complicada, principalmente, quando se manipula redes com milhares de palavras. Conjecturamos a possibilidade de se representar uma dada rede semântica baseada em títulos de artigos de periódicos científicos (RST) por meio de uma RST uniforme, de modo que esta possua a mesma estrutura topológica e reflita o vocabulário da RST original. O problema da nossa tese consiste em saber qual o menor tamanho de uma RST uniforme que pode ser obtida de uma dada RST. Esta pesquisa visa determinar o ponto crítico no qual ocorre uma mudança topológica de uma RST de modo que a rede obtida reflita o vocabulário da RST original. Realizamos um experimento que consistiu em submeter RST a estratégias de remoção de vértices. Os resultados apontam a existência de uma fração fp de vértices removidos aleatoriamente e uniformemente que mantém a estrutura topológica e reflita o vocabulário da RST original. Desta forma, RST podem ser representadas por RST uniformes mínimas. A representação do conhecimento é determinante em processos e cientes de busca de informações e difusão de conhecimento. Ademais, RST uniformes mínimas poderão auxiliar pesquisadores na busca mais e ciente de temas relacionados ao seu objeto de investigação. / Abstract In the field of artificial intelligence, semantic networks are used for knowledge representation and natural language processing. Semantic networks are graph-based knowledge representation systems whose vertices are words and edges, relationships between words set by a rule. Dealing with semantic networks is a very complicated activity, mainly, when it handles networks with thousands of words. We conjecture the possibility of representing a given semantic network based on titles of scientific papers (RST) by a uniform RST, so that this has the same topological structure and reflect the vocabulary of the original RST. The problem of our thesis is to know what a uniform smaller RST can be obtained from a given RST. This study aims to determine the critical point at which there is a topological change of a RST so that the network obtained reflect the vocabulary of the original RST. We conducted an experiment that it consists to submit RST removing vertices strategies. The results indicate the existence of a fraction fp vertices removed randomly and evenly preserving the topological structure and reflect the vocabulary of the original RST. Thus, RST may be represented by minimum uniform RST. The representation of knowledge is determinant in efficient processes search of information and diffusion of knowledge. In addition, minimum uniform RST can assist researchers in the most efficient search issues related to its investigation.

SILVA, Aline Alves da. Decomposição e largura em árvore de grafos planares livres de ciclos pares induzidos. 2007. 80 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2007. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T17:52:45Z No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T12:18:29Z (GMT) No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) / Made available in DSpace on 2016-07-13T12:18:29Z (GMT). No. of bitstreams: 1 2007_dis_aasilva.pdf: 635256 bytes, checksum: 0ac10f7ac58ad14294969b2e4a830ce0 (MD5) Previous issue date: 2007 / The definitions of tree decomposition and treewidth were introduced by Robertson and Seymour in their series of papers on graph minors, published during the nineties. It is known that many NP-hard problems can be polynomially solved if a tree decomposition of bounded treewidth is given. So, it is of interest to bound the treewidth of certain classes of graphs. In this context, the planar graphs seem to be specially challenging because, in despite of having many known bounded metrics (for example, chromatic number), they have unbounded treewidth. So, an alternative approach is to restrict ourselves to a subclass of planar graphs. In this work, we investigate the class of even-hole-free planar graphs. We show that if G is an even-hole-free planar graph, then it does not contain a subdivision of the 10£10 grid. So, if the grid minors of G are obtained from subdivisions, then G has treewidth at most 49. Furthermore, two polynomial, non-exact algorithms to compute a tree decomposition of a even-hole-free planar graph are given, both based on known characterizations of even-hole-free graphs. In the ¯rst one, a tree decomposition is built from basic graphs by concatenating the tree decomposition of small pieces via the clique, k-stars (k = 1; 2; 3) and 2-join cutsets. In the second one, a tree decomposition is built by including one by one the vertices of G, following their bi-simplicial order. / Os conceitos de Decomposição em Árvore e Largura em Árvore foram introduzidos por Robertson e Seymour em sua série de artigos sobre menores de grafos, publicados ao longo da década de 90. Sabe-se que muitos problemas NP - difíceis podem ser resolvidos polinomialmente para um grafo G, dada uma decomposição em Árvore de G de largura limitada. Logo, limitar a largura em árvore de uma classe de grafos torna-se um objeto de estudo de grande interesse. Neste contexto, a classe dos grafos planares se mostra bastante intrigante, uma vez que, apesar de possuir outras métricas limitadas em valores baixos (por exemplo, número cromático), não possui largura em árvore limitada. Desta forma, uma alternativa é restringir a classe estudada para uma subclasse dos grafos planares. Neste trabalho, nós investigamos a classe dos grafos planares livres de buracos pares. Nós mostramos que se G é um grafo planar livre de buracos pares, então ele não contém uma subdivisão de uma grade 10 £ 10. Portanto, se os menores grades de G são obtidos de subdivisões G tem largura em árvore no máximo 49. Além disso, dois algoritmos não exatos polinomiais para computar uma decomposição em árvore de um grafo planar livre de buracos pares são apresentados, ambos baseados em caracterizações conhecidas de tal classe de grafos. No primeiro algoritmo, uma decomposição em árvore é construída a partir de grafos básicos pela concatenação de decomposições em árvores de pedaços pequenos via os cortes clique, k-estrelas (k = 1; 2; 3) e 2-join. No segundo, uma decomposição em árvore é construída pela inclusão dos vértices de G um a um, seguindo sua ordem bi-simplicial.

MARTINS, Nicolas de Almeida. Problemas de coloração de grafos com poucos P4´s. 2013. 53 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T14:47:13Z No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T12:11:19Z (GMT) No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) / Made available in DSpace on 2016-07-20T12:11:19Z (GMT). No. of bitstreams: 1 2013_dis_namartins.pdf: 515331 bytes, checksum: 2fe3c128ef3ee2889aa0c4a91d5fd916 (MD5) Previous issue date: 2013 / The coloring problems are among the most studied in the graph theory due to its great theoretical and practical importance. The L(2;1)-labeling problem, for instance, can be applied to the frequency assignment of transmission towers in order to decrease interference in transmissions. However most of the graph coloring problems are difficult to solve (NP-hard). In this thesis, we study the L(2;1)-coloring, the harmonious coloring and M-partition of graphs. Considering that the coloring problems addressed in this thesis are all NP-hard, we decided to study the restrictions of these problems to (q;q4)-graphs, with q fixed. The solutions use the Primeval decomposition of these graphs. We also emphasize that this class contains the cographs and P4-sparse graphs. The algorithms found in this way are called Fixed parameter tractable (FPT), because they run on polynomial time if we consider a certain parameter as a fixed value. Besides obtaining algorithms for several coloring problems restricted to (q;q4)-graphs, with q fixed, we also evaluated Conjecture of Griggs-Yeh graphs with respect to P4-Sparse and P4-Laden graphs. / Os problemas de coloração estão entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teórica e prática. O problema da L(2,1)-coloração, por exemplo, pode ser aplicado na atribuição de frequências de rádio a torres de transmissão visando a diminuição de interferências nas transmissões. No entanto a maior parte das colorações de Grafos é de difícil resolução(NP-Difíceis). Nesta dissertação, estudamos os problemas de L(2,1)-coloração, coloração harmônica e M-partição. Tendo em vista que os problemas de coloração abordados nesta dissertação são todos NP-difíceis, decidimos estudar as restrições destes problemas a (q,q-4)-grafos , com q fixo. As soluções utilizam a decomposição primeval destes grafos. Ressaltamos ainda que esta classe contém os cografos e os grafos P4-esparsos. Os algoritmos encontrados desta maneira são chamados de Fixed Parameter Tractable(FPT), pois são polinomiais quando consideramos um determinado parâmetro como um valor fixo. Além da obtenção de algoritmos para diversos problemas de coloração restritos aos (q,q-4)-grafos, com q fixo, também avaliamos a Conjectura de Griggs-Yeh com relação aos grafos P_4-Esparsos e P_4-Laden.

XAVIER, Alinson Santos. Geração de Facetas para Politopos de Conjuntos Independentes. 2011. 141 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2011. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:04:42Z No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-05-23T19:10:07Z (GMT) No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) / Made available in DSpace on 2016-05-23T19:10:07Z (GMT). No. of bitstreams: 1 2011_dis_asxavier.pdf: 1098827 bytes, checksum: b69a55ab904901d692a7afbf26cfbb04 (MD5) Previous issue date: 2011 / A stable set of a graph is a set of pairwise non-adjacent vertices. The maximum stable set problem is to find a stable set of maximum cardinality in a given graph. The maximum induced k-partite subgraph problem is to find k stable sets such that their union has maximum cardinality. Besides having applications in various fields, including computer vision, molecular biology and VLSI circuit design, these problems also model other important combinatorial problems, such as set packing and vertex coloring. In the present work, we study the facial structure of the polytopes associated with both problems. First, we describe a new facet generating procedure for the stable set polytope, which unifies and subsumes several previous procedures. Besides generating many well-known facet inducing inequalities, this procedure can also generate new facet-inducing inequalities which have not been previously described. Then, we study the maximum induced k-partite polytope formulated by asymmetric representatives. We describe its simplest facets, show that some of its facets arise from vertex induced subgraphs, and identify two classes of subgraphs which generate facets of the polytope. To reach these main results, we study the affine equivalence between polyhedra, and also develop a new facet generating procedure for general polyhedra which subsumes the many versions of the lifting of variables. / Um conjunto independente de um grafo é um subconjunto de vértices que não contém nenhum par de vértices vizinhos. O problema do maior conjunto independente consiste em encontrar um conjunto independente de cardinalidade máxima. O problema do maior subgrafo induzido k-partido consiste em encontrar k conjuntos independentes cuja união tenha cardinalidade máxima. Além de possuírem aplicação em diversas áreas, como visão computacional, biologia molecular e projeto de circuitos integrados, estes problemas também modelam outros problemas de otimização combinatória, como empacotamento de conjuntos e coloração de vértices. Neste trabalho, estudamos os politopos associados aos dois problemas. Primeiro, descrevemos um novo procedimento de geração de facetas para o politopo de conjuntos independentes, que unifica e generaliza diversos procedimentos anteriores. Além de gerar várias classes de desigualdades indutoras de facetas já conhecidas, este procedimento também gera novas desigualdades que ainda não foram descritas na literatura. Em seguida, estudamos o politopo do subgrafo induzido k-partido associado à formulação por representantes de cor. Identificamos suas facetas mais simples, mostramos que facetas podem ser geradas a partir de subgrafos induzidos, e descrevemos duas classes de subgrafos que geram facetas deste politopo. Para obter os principais resultados desta dissertação, fazemos um estudo da relação de afim-isomorfismo entre poliedros, e desenvolvemos um novo procedimento de conversão de faces em facetas que generaliza as diversas versões do procedimento de levantamento de variáveis.

Em muitas representações de objetos ou sistemas físicos se faz necessário a utilização de técnicas de redução de dimensionalidade que possibilitam a análise dos dados em baixas dimensões, capturando os parâmetros essenciais associados ao problema. No contexto de aprendizagem de máquina esta redução se destina primordialmente à clusterização, reconhecimento e reconstrução de sinais. Esta tese faz uma análise meticulosa destes tópicos e suas conexões que se encontram em verdadeira ebulição na literatura, sendo o mapeamento de difusão o foco principal deste trabalho. Tal método é construído a partir de um grafo onde os vértices são os sinais (dados do problema) e o peso das arestas é estabelecido a partir do núcleo gaussiano da equação do calor. Além disso, um processo de Markov é estabelecido o que permite a visualização do problema em diferentes escalas conforme variação de um determinado parâmetro t: Um outro parâmetro de escala, Є, para o núcleo gaussiano é avaliado com cuidado relacionando-o com a dinâmica de Markov de forma a poder aprender a variedade que eventualmente seja o suporte do dados. Nesta tese é proposto o reconhecimento de imagens digitais envolvendo transformações de rotação e variação de iluminação. Também o problema da reconstrução de sinais é atacado com a proposta de pré-imagem utilizando-se da otimização de uma função custo com um parâmetro regularizador, γ, que leva em conta também o conjunto de dados iniciais. / In many representations of objects or physical systems it is necessary to use techniques of dimensionality reduction that enable the analysis of data at low dimensions, capturing the essential parameters associated with the problem. Within the context of machine learning this reduction is primarily intended for clustering , recognition and reconstruction of signals. This thesis makes a thorough analysis of these topics and their connections which are true boiling in the literature, the difusion mapping being the main focus of this work . This method is constructed from a graph where the vertices are the signs ( problem data ) and the weight of edges is established based on the Gaussian kernel of the heat equation. Furthermore , a Markov process is established which allows the visualization of the problem at diferent scales according to the variation of a given parameter t . Another scale parameter, Є , for the Gaussian core is carefully evaluated by relating it to the dynamic Markov so you can learn the variety that eventually support the data. This thesis proposed the recognition of digital images involving transformations of rotation and variation of illumination. Also the problem of reconstruction of signals is attacked with the proposed pre - image using the optimization of a cost function with a smoothing parameter, γ, Which also takes into account the initial dataset.

Orientador: Prof. Dr. Rafael de Mattos Grisi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional, 2015. / Este trabalho apresenta uma introdução ao estudo da Teoria dos Grafos, com um dicionário visual e um histórico detalhado das origens deste ramo da matemática. Será dada uma ênfase especial ao estudo de grafos planares e na imersão de grafos em outras superfícies. Por fim, é apresentado um plano de aula para o professor interessado em introduzir o ensino de grafos a alunos do ensino fundamental e médio. / This paper presents an introduction to the study of Graph Theory, with a visual dictionary and a detailed history of the origins of this branch of mathematics. It will be given a special emphasis on the study of planar graphs and also in immersion graphs in other surfaces. Finally, we present a lesson plan for teacher interested in introducing the teaching of graphs to students of primary and secondary education.