Orientador: Fabrício Aparecido Breve / Banca: Moacir Antonelli Ponti / Banca: Daniel Carlos Guimarães Pedronette / Resumo: As pesquisas realizadas para o Sequenciamento de Genomas, Proteômica, Sistemas Biológicos, Diagnósticos Médicos, entre outros, geram uma grande quantidade de dados, fazendo necessário o apoio de soluções computacionais para a análise e interpretação desses dados. A utilização de técnicas de Aprendizado de Máquina, para a extração de conhecimentos úteis dessas grandes quantidades de dados, tem sido amplamente discutida entre pesquisadores da Biologia e da Computação. O processo para se rotular todos os dados gerados pelas pesquisas biológicas, assim como em outras áreas, é difícil, caro e/ou demorado. Assim, buscar maneiras de se atingir uma grande acurácia com poucos dados rotulados torna-se uma tarefa importante e desafiadora. Nesse sentido, o Aprendizado SemiSupervisionado mostra-se como uma opção importante uma vez que utiliza dados rotulados e não rotulados para o treinamento, sendo uma categoria intermediária entre o Aprendizado Supervisionado e o Não Supervisionado. Diversas abordagens para algoritmos de Aprendizado Semi-Supervisionado são encontradas na literatura. Dentre elas, destacam-se os métodos baseados em grafos, que representam os dados de entrada como nós de um grafo cuja estrutura é utilizada para propagar informações de rótulos dos nós rotulados para os demais nós. Destaca-se ainda que a abordagem baseada em grafos possui uma grande fundamentação matemática e computacional. Nesse contexto, este trabalho apresenta uma análise comparativa de alguns algoritmos semi-supervisionados, baseados em grafos, quando aplicados a dados biológicos relacionados aos campos de estudos da Proteômica e Transcriptômica. Adicionalmente, o trabalho propõe um novo dataset com dados reais oriundos de pesquisas biológicas com o transcriptoma de formigas da espécie Mycocepurus goeldii. Alguns experimentos realizados com os algoritmos semi-supervisionados são apresentados, levando em consideração sua... / Abstract: Research conducted for the sequencing of genomes, Proteomics, Systems Biology, Medical Diagnostics, among others, generate a lot of data, making it necessary the support of computing solutions for the analysis and interpretation of such data. The possibility of using machine learning techniques to extract useful knowledge of these large amounts of data has been widely discussed among researchers of Biology and Computer Science. The process of labeling all data generated by biological research, as well as in other areas, is difficult, costly and / or time consuming. Thus, searching ways to achieve a high accuracy with few labeled data is an important and challenging task. Accordingly, the Semi-Supervised Learning shows up as an important option since it uses both labeled and unlabeled data for training, being an intermediate category between the Supervised and Unsupervised Learning. Several approaches to semi-supervised learning algorithms are found in the literature. Among them, the highlights are the graph-based methods, which represent the input data as nodes in a graph, which structure is used to propagate label information from labeled nodes to the other nodes. It is also noteworthy that the graph-based approach has a great mathematical and computational validity. In this context, this paper presents a comparative analysis of some semi-supervised algorithms based on graphs, when applied to biological data analysis related to the field of proteomics and transcriptomics studies. In addition, the paper proposes a new dataset with actual data from biological research with the transcriptome of the Mycocepurus goeldii species of ants. Some experiments performed with semi-supervised algorithms are presented, considering its efficacy when compared with a few supervised methods / Mestre

O problema de geração de estruturas de coalizão (CSG) envolve o particionamento do conjunto de agentes em todos os subconjuntos(ou, coalizões) possíveis. O que torna esse problema desafiador é o número de coalizões possíveis crescer exponencialmente a medida que novos agentes são inseridos, o número de coalizões é (2n − 1) onde n é o número de agentes. Entretanto, em muitas aplicações do mundo real, existem limitações inerentes nas coalizões possíveis: por exemplo, determinados agentes podem ser proibidos de estar na mesma coalizão, ou a estrutura de coalizão pode ser obrigada a conter coalizões do mesmo tamanho. Quando consideramos CSG restrito por grafos, onde a viabilidade de uma coalizão é restrita por um grafo de sinergia dos agentes, a complexidade computacional pode ser a mesma ou menor, dependendo do que se considera uma coalizão válida. Os grafos de sinergia são representações dos agentes como sendo os vértices e as suas relações são as arestas. Este trabalho é um estudo sobre a utilização de restrições envolvendo grafos como uma heurística sobre as coalizões para o problema enumeração de coalizão, de forma a considerar uma coalizão factível ou não de acordo com a densidade do subgrafo induzido pelos agentes. Os trabalhos atuais, que utilizam os grafos de restrição como heurística para reduzir a complexidade computacional, consideram uma coalizão válida somente se o subgrafo formado pelos agentes da coalizão é conexo. Verificou-se experimentalmente para grafos com a propriedade power law, comum em uma variedade de grafos reais, que restringir uma coalizão válida como sendo um subgrafo conexo pode não ser uma redução significativa. Entretanto a utilização de um subgrafo com restrições mais fortes, em particular uma clique garante uma redução exponencial do número de coalizões consideradas. Não existem teoremas que possam calcular qual a quantidade de subgrafos conexos ou mesmo o número de cliques em um grafo do tipo power law. No presente trabalho foi possível calcular experimentalmente para grafos power law com ate 17 vértices, sendo que também são apresentados resultados analíticos para grafos estrela (Kn−1,1 ). Os grafos estrela são uma aproximação aceitável, pois formam um hub, estrutura característica de grafos power law. Como trabalhos futuros podem ser citados: o mapeamento de domínios para os quais a restrição de clique seria adequada, além do desenvolvimento de um algoritmo que incorpore a restrição diretamente na contagem de coalizões validas. / The coalition structures generating problem (CSG) involves partitioning the set of agents in all possible subsets (or coalitions). What makes this problem challenging is the number of possible coalitions that grows exponentially as new agents are inserted. The number of coalitions is (2n − 1) where n is the number of agents. However, in many real-world applications, there are inherent limitations on possible coalitions: for example, some individuals may be prohibited from being in the same coalition or coalition structure may be required to contain coalitions of the same size. When we consider CSG restricted by graphs where the viability of a coalition is restricted by a synergy graph, the computational complexity can be maintained or eventually be smaller depending on what is considered a valid coalition. Synergy graphs are representations of the agents as being the vertices and their relationships are the edges. This work is a study on the use of restrictions involving graphs as a heuristic about coalitions for the problem coalition enumeration in order to consider a feasible coalition or not according to the density of the subgraph induced by the agents. Current works using the restriction graphs as heuristics to reduce the computational complexity, consider a coalition valid only if the subgraph formed by the agents of the coalition is connected. In this work it as experimentally verify for power law graphs, present in a variety of real graphs, that restricting availability coalition as a connected subgraph may in not prohibited a significant gain. However, they using a subgraphs with strong restrictions, in particular a clique, guarantees an exponential reduction in the number of considered coalition. There no are theorems calculate subgraphs or even the number of cliques on a type power law graph. In the present work it was possible to calculate values experimental for graphs of up to 17 vértices, being also presented analytics results for star graphs (Kn−1,1 ). Star graphs are an acceptable approximation, was they account for hubs, a characteristic structure of power law graphs. As future works can be cited the study of domains where the clique restriction is adequate as well as the development of an algorithm that incorporates the restriction for coalition counting.

Made available in DSpace on 2013-08-07T18:53:25Z (GMT). No. of bitstreams: 1 000389987-Texto+Completo-0.pdf: 1360851 bytes, checksum: d8bf43ca52fd146b24970288170182a3 (MD5) Previous issue date: 2007 / In the recent years, the society observes with enthusiasm the rapid proliferation of a vast diversity of embedded systems targeted to safe-critical applications like health-care systems, telecommunication, automotive and aerospace. As a consequence, besides the need for low-cost components, mainly memory, it is also mandatory the use of more robustness hardware and software parts that integrate these systems. Among the possible types of faults, those that change the control-flow of the processors that carry out embedded applications are focused on this work. Very often, these types of faults induce in catastrophic system failure. By catastrophic failure, we mean those faults that in addition to drive the system to an unexpected behavior, it is also needed to reinitialize the system to recover from the faulty state. Thus, the use of techniques capable of detecting these types of faults prevents them from spreading through the system and ultimately, generating incorrect outputs. Unfortunately, the use of fault detection techniques increase memory overhead and degrades system performance. These collateral effects may be critical, preventing real-time embedded systems from attaining their goals. As possible solutions to the mentioned problems, three hypotheses were investigated, and one of them was implemented. Therefore, this work proposes an approach based on software profiling that analyses the control-flow graph of applications, to optimize the number of checkpoints to be inserted along with the application code. In order to validate the proposed approach, we performed fault injection of three types of faults: jump, nop and bit-flips. This fault injection process was accelerated by means of hardware prototyping of the system. In this case, we used a FPGA (Field-Programmable Gate Array) mounted on a Xilinx commercial board. Detailed analysis of the obtained results indicates that the proposed approach reduces the number of checkpoints to be inserted along with the application code, thus, minimizing memory overhead and system performance degradation, while maintaining approximately unchanged the fault detection coverage, when compared to another existing approaches in the literature. / Nos últimos anos, observa-se com grande euforia o crescimento do mercado de sistemas embarcados nas áreas econômico-sociais de grande importância, tais como a saúde, telecomunicações, automotiva e aeroespacial, entre outras. Como conseqüência, exige-se maior robustez tanto do hardware quanto do software integrante destes sistemas, além de componentes de baixo custo, principalmente memória. Dentre os tipos possíveis de falhas, as falhas que alteram o fluxo de controle de processadores que executam aplicações embarcadas, por implicarem em quase sempre em falhas catastróficas do sistema, são focadas nesta dissertação. Por falhas catastróficas, entende-se como sendo aquelas falhas que além de induzir o sistema a produzir um comportamento diferente daquele esperado para a sua função, implicam na maioria das vezes também na reinicialização do sistema como forma de recuperação da falha. Assim, a utilização de técnicas capazes de detectar estes tipos de falhas evita que as mesmas se propaguem pelo sistema e acabem gerando saídas incorretas, pois tais falhas podem ser catastróficas para a segurança dos usuários e para a imagem e reputação das empresas. Porém, a utilização de técnicas de detecção de falhas gera um aumento na taxa de ocupação de memória do sistema, bem como provoca aumento da degradação de desempenho, o que pode ser considerado um fator crítico tratando-se de aplicações embarcadas de tempo-real. Como alternativa para minimizar estes fatores, três hipóteses foram investigadas, sendo uma delas implementada. Assim, nesta dissertação propõe-se uma abordagem baseada em software profiling que analisa o grafo de fluxo de controle da aplicação, visando à otimização do número de assinaturas (checkpoints) a serem inseridas no código-fonte. Para validar a abordagem proposta, foi realizada por simulação a injeção de três tipos de falhas: jump, nop e bit-flip, sobre diferentes programas aplicativos. Este processo de injeção de falhas foi acelerado via prototipagem do sistema em hardware, através do uso de um FPGA (Field-Programmable Gate Array) em uma placa comercial da Xilinx. A análise dos resultados obtidos indica que a técnica proposta reduz o número de assinaturas inseridas no código da aplicação, e portanto, minimizando o overhead de memória e a degradação do desempenho do sistema, ao passo que mantém aproximadamente inalterado nível de cobertura de falhas quando comparada a outras técnicas atualmente existentes na literatura.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Dissertação(mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2013. / Submitted by Alaíde Gonçalves dos Santos (alaide@unb.br) on 2013-10-08T12:16:21Z No. of bitstreams: 1 2013_RobertoVilaGabriel.pdf: 3245364 bytes, checksum: b4dd6dc2376cbbe449b55b6bcfd55654 (MD5) / Approved for entry into archive by Guimaraes Jacqueline(jacqueline.guimaraes@bce.unb.br) on 2013-10-16T14:03:06Z (GMT) No. of bitstreams: 1 2013_RobertoVilaGabriel.pdf: 3245364 bytes, checksum: b4dd6dc2376cbbe449b55b6bcfd55654 (MD5) / Made available in DSpace on 2013-10-16T14:03:06Z (GMT). No. of bitstreams: 1 2013_RobertoVilaGabriel.pdf: 3245364 bytes, checksum: b4dd6dc2376cbbe449b55b6bcfd55654 (MD5) / Este trabalho está baseado no artigo: The self-dual point of the two-dimensional random-cluster model is critical for q ≥ 1, escrito pelos matemáticos Vincent Beffara e Hugo Duminil-Copin publicado no periódico Probability Theory and Related Fields em 2012. Neste trabalho os autores provam uma conjectura bastante antiga sobre o valor do ponto crítico do Modelo de Aglomerados Aleatórios na rede Z2. Eles mostraram que o ponto auto-dual, psd(q) = √q /(1 + √q ); para q ≥ 1 é crítico na rede quadrada. Como uma aplicação deste resultado, eles mostraram também que as funções de conectividade, na fase subcrítica, decaem exponencialmente com respeito à distância entre dois pontos. _______________________________________________________________________________________ ABSTRACT / This work is based on the paper: The self-dual point of the two-dimensional randomcluster model is critical for, q ≥ 1, by Vincent Beffara and Hugo Duminil-Copin, Probability Theory and Related Fields 2012. In this work the authors proved an old conjecture about the critical point of the Random-Cluster Model in the square lattice. They shown that the self dual point, psd(q) = √q /(1 + √q ); for q ≥ 1 is critical on the square lattice. As an application they shown that the connectivity functions, in the subcritical phase, decays exponentially fast with the distance of the points.

Relações min-max são objetos centrais em otimização combinatória. Elas basicamente afirmam que, numa dada estrutura, o valor ótimo de um certo problema de minimização é igual ao valor ótimo de um outro problema de maximização. Relações desse tipo fornecem boas caracterizações e descrições poliédricas para diversos problemas importantes, além de geralmente virem acompanhadas de algoritmos eficientes para os problemas em questão. Muitas vezes, tais algoritmos eficientes são obtidos naturalmente das provas construtivas dessas relações; mesmo quando isso não ocorre, essas relações revelam o suficiente sobre a estrutura combinatória dos problemas, levando ao desenvolvimento de algoritmos eficientes. O foco principal desta dissertação é o estudo dessas relações em grafos. Nossa ênfase é sobre grafos orientados. Apresentamos o poderoso arcabouço poliédrico de Edmonds e Giles envolvendo fluxos submodulares, bem como o algoritmo de Frank para um caso especial desse arcabouço: o teorema de Lucchesi-Younger. Derivamos também diversas relações min-max sobre o empacotamento de conectores, desde o teorema de ramificações disjuntas de Edmonds até o teorema de junções disjuntas de Feofiloff-Younger e Schrijver. Apresentamos também uma resenha completa sobre as conjecturas de Woodall e sua versão capacitada, conhecida como conjectura de Edmonds-Giles. Derivamos ainda algumas relações min-max clássicas sobre emparelhamentos, T-junções e S-caminhos. Para tanto, usamos um teorema de Frank, Tardos e Sebö e um arcabouço bastante geral devido a Chudnovsky, Geelen, Gerards, Goddyn, Lohman e Seymour. Ao longo do texto, ilustramos vários aspectos recorrentes, como o uso de ferramentas da combinatória poliédrica, a técnica do descruzamento, o uso de funções submodulares, matróides e propriedades de troca, bem como alguns resultados envolvendo subestruturas proibidas. / Min-max relations are central objects in combinatorial optimization. They basically state that, in a given structure, the optimum value of a certain minimization problem equals the optimum value of a different, maximization problem. Relations of this kind provide good characterizations and polyhedral descriptions to several important problems and, moreover, they often come with efficient algorithms for the corresponding problems. Usually, such efficient algorithms are obtained naturally from the constructive proofs involved; even when that is not the case, these relations reveal enough of the combinatorial structure of the problem, leading to the development of efficient algorithms. The main focus of this dissertation is the study of these relations in graphs. Our emphasis is on directed graphs. We present Edmonds and Giles\' powerful polyhedral framework concerning submodular flows, as well as Frank\'s algorithm for a special case of this framework: the Lucchesi-Younger Theorem. We also derive several min-max relations about packing connectors, starting with Edmonds\' Disjoint Branchings Theorem and ending with Feofiloff-Younger and Schrijver\'s Disjoint Dijoins Theorem. We further derive some classical min-max relations on matchings, T-joins and S-paths. To this end, we use a theorem due to Frank, Tardos, and Sebö and a general framework due to Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour. Throughout the text, we illustrate several recurrent themes, such as the use of tools from polyhedral combinatorics, the uncrossing technique, the use of submodular functions, matroids and exchange properties, as well as some results involving forbidden substructures.

Neste trabalho, apresentamos um algoritmo que determina o número de autovalores de uma matriz simétrica qualquer que representa uma árvore, num dado intervalo real. Várias aplicações são obtidas em relação à distribuição dos autovalores da matriz laplaciana perturbada, uma matriz de representação de grafos que inclui, como casos particulares, a matriz de adjacências, a matriz laplaciana combinatória, a matriz laplaciana sem sinal e a matriz laplaciana normalizada, amplamente estudadas em Teoria Espectral de Grafos. Além disso, desenvolvemos também um algoritmo de localização de autovalores da matriz de adjacências de um grafo unicíclico. Este procedimento permite obter propriedades espectrais de grafos unicíclicos denominados centopeias unicíclicas. / In this work, we present an algorithm that computes the number of eigenvalues of any symmetric matrix that represents a tree, in a given real interval. Several applications are obtained about the distribution of the eigenvalues of the perturbed Laplacian matrix, which is a matrix representation of graphs that includes, as special cases, the adjacency matrix, the combinatorial Laplacian matrix, the signless Laplacian matrix and the normalized Laplacian matrix, widely studied in Spectral Graph Theory. In addition, we also develop an algorithm that locates the eigenvalues of the adjacency matrix of a unicyclic graph. This procedure allows us to obtain spectral properties of unicyclic caterpillars.

Orientador: Varese Salvador Timóteo / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia / Made available in DSpace on 2018-08-17T09:47:55Z (GMT). No. of bitstreams: 1 Pereira_VanessaHelena_M.pdf: 2435236 bytes, checksum: c61f3c9e770fd549a5b0fac102f12ffc (MD5) Previous issue date: 2010 / Resumo: A necessidade da operação intermitente de redes complexas leva ao estudo das falhas nas redes de topologia livre de escala (Scale-Free) de Barabási-Albert. Neste trabalho introduzem-se as teorias fundamentais ao estudo das redes complexas, além da revisão de vários trabalhos científicos relacionados às falhas e aos mecanismos de contenção destas. Utilizando o software Attacker-Defender, são construídas várias redes complexas Scale-Free de diferentes tamanhos, representadas por grafos. Estas redes são utilizadas para simular dois tipos de falhas mais frequentes: falhas aleatórias e falhas direcionadas aos hubs (nós com maior número de arestas incidentes) em duas etapas. Na primeira etapa, em dez tamanhos de redes são testadas quatro situações distintas. Na segunda etapa, em sete tamanhos de redes, são testadas dez diferentes vulnerabilidades. A partir da análise dos resultados da primeira etapa, observa-se qual dos quatro cenários analisados é o mais vantajoso para contenção de falhas nas redes. A análise da segunda etapa permite definir a descrição matemática do comportamento dos nós sobreviventes e atingidos no pós-falha, em cada uma das redes, para cada tipo de falha, através de métodos e funções específicas encontradas. / Abstract: The need for the intermittent operation of complex networks leads to the study of failures in these networks topology called Scale-Free, Barabási-Albert. In this work we introduce the fundamental theories to the study of complex networks, in addition to reviewing various scientific studies related to the failures and the mechanisms against cascade failures. Using the Attacker-Defender software, Scale-Free complex networks of different sizes are built, represented as graphs. These networks are used to simulate the two most common types of failures: random failures and attacks to hubs (nodes with the largest number of incident edges) in two steps. In the first step in ten sizes of networks are tested in distinct four cases. In the second step, in seven sizes of networks are tested ten different vulnerabilities. From the analysis of the results of the first step, it is observed which cases are best for the networks. The analysis of the second step provides the mathematical description of the behavior of the survivors and the affected nodes, after the failure in each network for each type of failure, through methods and specific functions was found. / Mestrado / Tecnologia e Inovação / Mestre em Tecnologia

Orientador: Margarida Pinheiro Mello / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T06:57:47Z (GMT). No. of bitstreams: 1 Gower_RobertMansel_M.pdf: 908087 bytes, checksum: f8067f63c68dadafecf74e1387966331 (MD5) Previous issue date: 2011 / Resumo: Dentro do contexto de programação não linear, vários algoritmos resumem-se à aplicação do método de Netwon aos sistemas constituídos pelas condições de primeira ordem de Lagrange. Nesta classe de métodos é necessário calcular a matriz hessiana. Nosso foco é o cálculo exato, dentro da precisão da máquina, de matrizes hessianas usando diferenciação automática. Para esse fim, exploramos o cálculo da matriz hessiana sob dois pontos de vista. O primeiro é um modelo de grafo que foca nas simetrias que ocorrem no processo do cálculo da hessiana. Este ângulo propicia a intuição de como deve ser calculada a hessiana e leva ao desenvolvimento de um novo método de modo reverso para o cálculo de matrizes hessianas denominado edge pushing. O segundo ponto de vista é uma representação puramente algébrica que reduz o cálculo da hessiana à avaliação de uma expressão. Esta expressão pode ser usada para demonstrar algoritmos já existentes e projetar novos. Para ilustrar, deduzimos dois novos algoritmos, edge pushing e um novo algoritmo de modo direto, e uma série de outros métodos conhecidos [1], [20, p.157] e [9]. Apresentamos estudos teóricos e empíricos sobre o algoritmo edge pushing. Analisamos sua complexidade temporal e de uso de memória. Implementamos o algoritmo como um driver do pacote ADOL-C [19] e efetuamos testes computacionais, comparando sua performance com à de dois outros drivers em dezesseis problemas da coleção CUTE [5]. Os resultados indicam que o novo algoritmo é muito promissor. Pequenas modificações em edge pushing produzem um novo algoritmo, edge pushing sp, para o cálculo da esparsidade de matrizes hessianas, um passo necessário de uma classe de métodos que calculam a matriz hessiana usando colorações de grafos, [14, 19, 30]. Estudos de complexidade e testes numéricos são realizados comparando o novo método contra um outro recentemente desenvolvido [30] e os testes favorecem o novo algoritmo edge pushing sp. No capítulo final, motivado pela disponibilidade crescente de computadores com multiprocesadores, investigamos o processamento em paralelo do cálculo de matrizes hessianas. Examinamos o cálculo em paralelo de matrizes hessianas de funções parcialmente separáveis. Apresentamos uma abordagem desenvolvida para o cômputo em paralelo que pode ser usando em conjunto com qualquer método de cálculo de hessiana e outra estratégia específica para métodos de modo reverso. Testes são executados em um computador com memória compartilhada usando a interface de programação de aplicativo OpenMP / Abstract: In the context of nonlinear programming, many algorithms boil down to the application of Newton's method to the system constituted by the first order Lagrangian conditions. The calculation of Hessian matrices is necessary in this class of solvers. Our focus is on the exact calculation, within machine precision, of Hessian matrices through automatic differentiation. To this end, we detail the calculations of the Hessian matrix under two points of view. The first is an intuitive graph model that focuses on what symmetries occur throughout the Hessian calculation. This provides insight on how one should calculate the Hessian matrix, and we use this enlightened perspective to deduce a new reverse Hessian algorithm called edge pushing. The second viewpoint is a purely algebraic representation of the Hessian calculation via a closed formula. This formula can be used to demonstrate existing algorithms and design new ones. In order to illustrate, we deduce two new algorithms, edge pushing and a new forward algorithm, and a series of other known Hessian methods [1], [20, p.157] and [9]. We present theoretical and empirical studies of the edge pushing algorithm, establishing memory and temporal bounds, and comparing the performance of its computer implementation against that of two algorithms available as drivers of the software ADOL-C [14, 19, 30] on sixteen functions from the CUTE collection [5]. Test results indicate that the new algorithm is very promising. As a by-product of the edge pushing algorithm, we obtain an efficient algorithm, edge pushing sp, for automatically obtaining the sparsity pattern of Hessian matrices, a necessary step in a class of methods used for computing Hessian matrices via graph coloring, [14, 19, 30]. Complexity bounds are developed and numerical tests are carried out comparing the new sparsity detection algorithm against a recently developed method [30] and the results favor the new edge pushing sp algorithm. In the final chapter, motivated by the increasing commercial availability of multiprocessors, we investigate the implementation of parallel versions of the edge pushing algorithm. We address the concurrent calculation of Hessian matrices of partially separable functions. This includes a general approach to be used in conjunction with any Hessian software, and a strategy specific to reverse Hessian methods. Tests are carried out on a shared memory computer using the OpenMP paradigm / Mestrado / Analise Numerica / Mestre em Matemática Aplicada

Orientadores: Marcelo Firer, Luiz Antonio Barrera San Martin / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T23:33:46Z (GMT). No. of bitstreams: 1 Talpo_HumbertoLuiz_D.pdf: 1408389 bytes, checksum: b11f884cbf1e05f81138a8e91a5980dc (MD5) Previous issue date: 2006 / Resumo: Seja G uma árvore homogênea e Aut(G) seu grupo de automorfismos. Um automorfismo f Î Aut(G) é par se d(f(x),x) º0 mod 2 para todo vértice x Î G, onde d(.,.) é a função distância definida pelo comprimento do menor caminho ligando os vértices. O conjunto Aut+(G) de todos os automorfismos pares é um subgrupo de índice 2 em Aut(G). Definimos uma geodésica g Ì G como um subgrafo isomorfo a Z (onde Z é visto como um grafo que possui arestas unindo inteiros consecutivos). Uma reflexão em uma geodésica g é um automorfismo involutivo f (f² =1) tal que f(x) = x se, e somente se, x Î G. Denotamos por R o conjunto de todas as reflexões em geodésicas. Neste trabalho (Capítulo 2) provamos que, dada uma árvore homogênea de grau par G, o número de cobertura de Aut+(G) pelas reflexões em geodésicas é 11, no seguinte sentido: dado f Î Aut+(G) existem f1, f2,... fk com k £ 11, tais que f(x) = fk °fk-1°...°f1(x) para todo vértice x em G. Além disso, considerando árvores homogêneas, sabemos que o grupo de automorfismos é completo e o subgrupo de automorfismos pares é simples. Flexibilizamos a condição de homogeneidade e conseguimos demonstrar (Capítulo 3) para o caso de árvores semi-homogêneas, que o grupo de automorfismos é simples e completo / Abstract: Let G be a homogeneous tree and Aut(G) its group of automorphism. An automorphism Î Aut(G) is said to be even if d(f(x),x) º0 mod 2 for every vertex x Î G of , where d(.,.) is the canonical distance function defined by the minimum length of paths connecting the vertices. The set Aut+(G) of all even automorphism is a subgroup of index 2 in Aut(G). We define a geodesic g Ì G as a subtree isomorphic to the standard tree of the integers Z, that is, a homogeneous subtree of degree 2. A reflection in a geodesic g is an involutive automorphism f (f² =1) such that f(x) = x if x Î G. We denote by R the set of all reflections in geodesics. In this work (Chapter 2) we prove that, for every even degree tree G, the covering number of Aut+(G) by reflections in geodesics is 11, in the sense that give f Î Aut+(G) there are f1, f2,... fk with k £ 11, such that f(x) = fk °fk-1°...°f1(x) for every vertex x in G.Moreover, if we consider homogeneous trees we know that automorphisms group is complete and the even automorphisms subgroup is simple. We vary the homogeneous condition and we prove that (Chapter 3) for the semi-homogeneous trees, the automorphisms group is simple and complete / Doutorado / Doutor em Matemática