Made available in DSpace on 2016-08-29T15:39:01Z (GMT). No. of bitstreams: 1 tese_7557_Leonardo Rogério Binda da Silva.pdf: 4189335 bytes, checksum: 9b77cb2bc79d6f88555dd532f0f4d83a (MD5) Previous issue date: 2014-03-14 / O petróleo é atualmente o combustível mais utilizado no mundo. Recuperá-lo com a maior viabilidade econômica possível é uma busca incessante das companhias produtoras. Nesse cenário, a simulação numérica de reservatórios utilizando computadores paralelos de memória distribuída (clusters) desponta como uma importante ferramenta. Esses aplicativos manipulam malhas de pontos discretizados que representam o domínio do reservatório de petróleo. Uma etapa importante da simulação utilizando clusters é o particionamento dessa malha para que cada um dos nós processadores possa executar seus cálculos sobre uma porção da mesma. As malhas de domínio podem ser representadas por grafos. Particionar malhas, então, torna-se um problema de particionamento de grafos. Caso o número de vértices do grafo que representa a malha seja muito elevado, particionadores seriais podem apresentar problemas de desempenho. Particionadores de grafos utilizando clusters surgem como alternativas interessantes nessa situação, minimizando os tempos gastos nos particionamentos. Trata da implementação de um particionador paralelo de grafos para ser utilizado em clusters baseado nas Heurísticas de particionamento propostas e implementadas de maneira serial por Bonatto (2010). O particionador paralelo foi desenvolvido utilizando a linguagem de programação Java e a biblioteca de passagem de mensagens MPJ Express. Tipos abstratos de dados eficientes foram propostos e implementados para que o desempenho fosse otimizado. O particionador de grafos paralelo realizou o corte de diversos grafos, obtendo em sua grande maioria cortes menores do que os encontrados pelo particionador serial de Bonatto (2010) e por programas como o METIS e o CHACO. Melhorias ao particionador serial de Bonatto (2010) foram propostas. Análises de speedup e eficiência paralela foram realizadas para constatar os ganhos de tempos obtidos com a paralelização das heurísticas.

Dissertação (mestrado) - Universidade Federal de Santa Catarina. Centro Tecnologico / Made available in DSpace on 2016-01-08T15:39:56Z (GMT). No. of bitstreams: 1 82967.pdf: 5887865 bytes, checksum: 4125e0165ec77609d74b1306dc2f0ce5 (MD5) Previous issue date: 1987 / O presente trabalho tem por objetivo realizar uma análise comparativa entre dois algoritmos que determinam um caminho de mínimo custo, entre um vértice inicial e um vértice final especificados de um grafo com custos não-negativos. Inicialmente é feito um estudo desses algoritmos, bem como suas apresentações. Posteriormente é apresentada uma análise comparativa quanto ao desempenho computacional dos mesmos. Finalmente são relacionados os problemas estudados e um exemplo ilustra cada procedimento.

Orientador: Thiago de Melo / Banca: Alice Kimie Miwa Libardi / Banca: Andréa Cristina Prokopczyk Arita / Resumo: Neste trabalho verificamos as dificuldades apresentadas pelos alunos da E.E. Romeu de Moraes com relação às representações gráficas. Quando questionados sobre o porquê desta deficiência, foi difícil obter clareza sobre os fatos que os impedem a trabalhar com os gráficos. De maneira geral, nesta escola, os alunos argumentaram que viram poucas vezes o uso desta linguagem e que o uso de tabelas era mais frequente. Precisamos reverter esta situação, mostrando as vantagens que a comunicação via gráfico nos traz, pois dele podemos retirar informações importantes na solução de problemas. Ao longo desta dissertação mostraremos alguns conteúdos propostos para o 3° ano de Ensino Médio (estudo dos coeficientes de uma reta, análise das taxas de variação para a função afim e gráficos estatísticos buscando as medidas de tendência central) e retomaremos outros (par ordenado, plano cartesiano, razão, porcentagem, gráficos de setores, gráfico de barras, histograma e gráfico de linhas). Na maior parte destes assuntos, a representação gráfica ocorre e procuramos oferecê-la aos estudantes de diversas maneiras, seja construindo gráficos, seja observando-os e interpretando-os ou ainda, coletando dados para resolver os problemas propostos. Não pretendemos dar conta de todas as dificuldades apresentadas pelo corpo discente, mas apresentaremos algumas sugestões de atividades que podem facilitar o aprendizado dos mesmos / Abstract: In this work we analyze some difficulties when dealing with graphs which were presented by the students from E.E. Romeu de Moraes (São Paulo/SP). When we ask for the reason of this deficiency, it is difficult to get clear on the facts that prevent them working with graphics. In general, the students confirm that very rarely they make use of this feature and also say that dealing with tables is more common. We can change this situation showing the advantages which graphs communication brings to us, because it can derive important information for troubleshooting. Throughout this dissertation we show some proposed content for the 3rd year of high school (the study of coefficients of a straight line, analysis of growth rates for the statistical function and graphs seeking the central tendency) and other subjects (ordered pair, Cartesian plane, ratio, percentage, pie charts, bar graph, histogram and line graph). In most of these issues, the graphical representation occurs and we try to offer it to students in many ways, even drawing graphic, analyzing and interpreting it, or collecting data to solve the problems proposed. We do not intend to solve all the difficulties presented by the students, but we bring some suggestions for activities that can make learning easier to them / Mestre

Tese (doutorado) - Pontifícia Universidade Católica do Paraná, Curitiba, 2013 / Este estudo tem como foco a prática pedagógica da educação ambiental por meio da utilização de mapas conceituais nos cursos de formação docente. Em específico, procurou-se analisar se a Educação Ambiental pode ser trabalhada nos cursos de formação docente / The focus of the current study is the pedagogical practice on environmental education through the use of concept maps along undergraduate courses for teachers. The intention, more specifically, was to analyze whether or not Environmental Education can be

ARAÚJO, Júlio César Silva. Coloração e convexidade em grafos. 2012. 207 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-09-09T13:56:50Z No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T23:24:47Z (GMT) No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Made available in DSpace on 2016-09-27T23:24:47Z (GMT). No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) Previous issue date: 2012 / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de finition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de finition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems. / Nesta tese, estudamos vários problemas de teoria dos grafos relativos à coloração e convexidade em grafos. A maioria dos resultados contidos aqui são ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloração de grafos que é uma das áreas mais importantes de teoria dos grafos. Primeiro, consideramos três problemas de coloração chamados coloração gulosa, coloração ponderada e coloração ponderada imprópria. Em seguida, discutimos um problema de decisão, chamado boa rotulagem de arestas, cuja de finição foi motivada pelo problema de atribuição de frequências em redes óticas. A segunda parte desta tese é dedicada a um parâmetro de otimização em grafos chamado de número de fecho (geodético). A de finição deste parâmetro é motivada pela extensão das noções de conjuntos e fecho convexos no espaço Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuído.

Orientador: Celia Picinin de Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T21:07:02Z (GMT). No. of bitstreams: 1 Pedrotti_Vagner_M.pdf: 1466848 bytes, checksum: 52ed7d36d9f4f7cb6bee307b689f5f78 (MD5) Previous issue date: 2007 / Resumo: Um modulo de um grafo é um subconjunto de seus vertices que não é diferenciado, em relação à adjancencia peços demais vertices do mesmo grafo. Dado um mpodulo M de um grafo G, se todo módulo de G que intercepta M está contido nele ou o contém. M é denominado módulo forte¿Observação: O resumo, na íntegra poderá ser visualizado no texto completo da tese digital / Abstract: A module of a graph is a non distinguishable subset of nodes, regarding the nodes adjacency. Let M denote any module of a graph G. If every module of G wich overlaps M either contains M or is included in it, M is called a strong module...Note: The complete abstract is available with the full electronic digital thesis or dissertations / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

A busca por métodos de leitura biométrica tem crescido muito, alimentada pelas necessidades governamentais, militares e comerciais. Pesquisas indicam que o mercado de reconhecimento facial vai movimentar bilhões de dólares nos próximos anos. Dessa forma, encontrar métodos que atendem situações específicas impulsiona novos avanços nessa área. Cada aplicação de reconhecimento de faces precisa de uma solução particular. Há casos que o tempo de resposta é o fator mais importante; outros exigem que a face seja classificada mesmo que de forma parcial. Em todas essas situações, a acurácia e a robustez talvez sejam os atributos mais importantes. Entretanto, na maioria das vezes, tais características se comportam como grandezas inversas: aumentado o grau de confiança dos resultados o desempenho do método será afetado. Por isso, desenvolver uma metodologia que equilibra tais fatores é essencial para a construção de soluções aceitáveis. Este trabalho apresenta um novo algoritmo de reconhecimento facial, baseado em descritores locais e em redes complexas. O método é capaz de concentrar a informação, antes distribuída pelos diversos pontos dos descritores, em um único vetor de características, tornando a classificação mais rápida e eficiente. Além disso, o outro foco da metodologia é reduzir etapas de pré-processamento, evitando que processos sejam executados de forma desnecessária. Os experimentos foram realizados com bancos de faces bem conhecidos na literatura, revelando taxas de acurácia de até 98,5%. A técnica também apresentou bons resultados mesmo quando havia ruídos nas amostras, muitas vezes oriundos de objetos presentes na composição do cenário. Para uma análise complementar, algoritmos clássicos de reconhecimento facial foram submetidos ao mesmo conjunto de dados, gerando assim resultados comparativos entre as metodologias. / The search for biometric scanning methods has grown a lot due to government, military and commercial needs. Researches indicate the face recognition market will move billions of dollars in next years. Thus, finding methods to specific situations drives new advances in this area. Each application face recognition requires a particular solution. There are cases the response time is the most important factor; others require that face must be classified even if partially. In all these situations, accuracy and robustness may be the most important attributes. However, in most cases, these features behave as inverse greatness: increasing the confidence level of the results the method performance will be affected. Therefore, create the method which balances these factors is essential for construction of acceptable solutions. This paper presents a new face recognition algorithm based on local descriptors and complex networks. The method is able to concentrate the information before distributed by various point descriptors, in a unique feature vector. It makes the classification step faster and more efficient. Furthermore, another focus of the method is reduce pre-processing steps, avoiding unnecessary processes. The experiments were conducted with faces datasets well known in the literature, revealing accuracy rates of up to 98.5%. The technique also showed good results when there was noise in the samples, often derived from objects present in the composition of the scene. For additional analysis, classical facial recognition algorithms were subjected to the same data set, generating comparative results between both methodologies.

A busca por métodos de leitura biométrica tem crescido muito, alimentada pelas necessidades governamentais, militares e comerciais. Pesquisas indicam que o mercado de reconhecimento facial vai movimentar bilhões de dólares nos próximos anos. Dessa forma, encontrar métodos que atendem situações específicas impulsiona novos avanços nessa área. Cada aplicação de reconhecimento de faces precisa de uma solução particular. Há casos que o tempo de resposta é o fator mais importante; outros exigem que a face seja classificada mesmo que de forma parcial. Em todas essas situações, a acurácia e a robustez talvez sejam os atributos mais importantes. Entretanto, na maioria das vezes, tais características se comportam como grandezas inversas: aumentado o grau de confiança dos resultados o desempenho do método será afetado. Por isso, desenvolver uma metodologia que equilibra tais fatores é essencial para a construção de soluções aceitáveis. Este trabalho apresenta um novo algoritmo de reconhecimento facial, baseado em descritores locais e em redes complexas. O método é capaz de concentrar a informação, antes distribuída pelos diversos pontos dos descritores, em um único vetor de características, tornando a classificação mais rápida e eficiente. Além disso, o outro foco da metodologia é reduzir etapas de pré-processamento, evitando que processos sejam executados de forma desnecessária. Os experimentos foram realizados com bancos de faces bem conhecidos na literatura, revelando taxas de acurácia de até 98,5%. A técnica também apresentou bons resultados mesmo quando havia ruídos nas amostras, muitas vezes oriundos de objetos presentes na composição do cenário. Para uma análise complementar, algoritmos clássicos de reconhecimento facial foram submetidos ao mesmo conjunto de dados, gerando assim resultados comparativos entre as metodologias. / The search for biometric scanning methods has grown a lot due to government, military and commercial needs. Researches indicate the face recognition market will move billions of dollars in next years. Thus, finding methods to specific situations drives new advances in this area. Each application face recognition requires a particular solution. There are cases the response time is the most important factor; others require that face must be classified even if partially. In all these situations, accuracy and robustness may be the most important attributes. However, in most cases, these features behave as inverse greatness: increasing the confidence level of the results the method performance will be affected. Therefore, create the method which balances these factors is essential for construction of acceptable solutions. This paper presents a new face recognition algorithm based on local descriptors and complex networks. The method is able to concentrate the information before distributed by various point descriptors, in a unique feature vector. It makes the classification step faster and more efficient. Furthermore, another focus of the method is reduce pre-processing steps, avoiding unnecessary processes. The experiments were conducted with faces datasets well known in the literature, revealing accuracy rates of up to 98.5%. The technique also showed good results when there was noise in the samples, often derived from objects present in the composition of the scene. For additional analysis, classical facial recognition algorithms were subjected to the same data set, generating comparative results between both methodologies.

LIMA, Carlos Vinicius Gomes Costa. Sobre b-coloração de grafos com cintura pelo menos 6. 2013. 59 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza- Ceará, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T18:53:18Z No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-13T19:18:47Z (GMT) No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) / Made available in DSpace on 2016-06-13T19:18:47Z (GMT). No. of bitstreams: 1 2013_dis_cvgclima.pdf: 3781619 bytes, checksum: 164aea3629d83f1d6d8ba3efcf3ec056 (MD5) Previous issue date: 2013 / O problema de coloração está entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importância teorica e prática. Dado que o problema de colorir os vértices de um grafo G qualquer com a menor quantidade de cores é NP-difícil, várias heurísticas de coloração são estudadas a fim de obter uma coloração própria com um número de cores razoavelmente pequeno. Dado um grafo G, a heurística b de coloração se resume a diminuir a quantidade de cores utilizadas em uma coloração própria c, de modo que, se todos os vértices de uma classe de cor deixam de ver alguma cor em sua vizinhança, então podemos modificar a cor desses vértices para qualquer cor inexistente em sua vizinhança. Dessa forma, obtemos uma coloração c′ com uma cor a menos que c. Irving e Molove definiram a b-coloração de um grafo G como uma coloração onde toda classe de cor possui um vértice que é adjacente as demais classes de cor. Esses vértices são chamados b-vértices. Irving e Molove também definiram o número b-cromático como o maior inteiro k tal que G admite uma b-coloração por k cores. Eles mostraram que determinar o número b-cromático de um grafo qualquer é um problema NP-difícil, mas polinomial para árvores. Irving e Molove também definiram o m-grau de um grafo, que é o maior inteiro m(G) tal que existem m(G) vértices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau é um limite superior para número b-cromático e mostraram que o mesmo é igual a m(T) ou a m(T)−1, para toda árvore T, onde o número b-cromático é igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertação, verificamos a relação entre a cintura, que é o tamanho do menor ciclo, e o número b-cromático de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G é pelo menos g∗, então o número b-cromático é igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ é no máximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de Erdós-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ é 9. Caracterizamos os grafos cuja cintura é pelo menos 6 e não possuem um conjunto bom e mostramos como b-colori-los de forma ótima. Além disso, mostramos como bicolorir, também de forma ótima, os grafos cuja cintura é pelo menos 7 e não possuem conjunto bom. / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-Lov´asz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set.

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.