This thesis studies the relationship between the first generation biofuels and selected commodities and assets in the USA, Europe, and Brazil. It is the first attempt to combine the taxonomy and wavelet analyses in a single research application. Our unique dataset comprises 32 weekly price series covering the 2003--2015 time period. First, we employ a method of minimum spanning trees and hierarchical trees to model a biofuel-related price network. We demonstrate a development phase shift between Brazilian and the US/EU biofuel industries. We reveal a strong and stable connection between Brazilian ethanol and its main production factor, local sugarcane. We further find that US ethanol is closely linked to corn. In the contrary, European biodiesel exhibits only moderate ties to its production factors. Subsequent wavelet analysis scrutinizes the identified price connections both in time and frequency domains. Both Brazilian and US ethanols are found to be positively related to their respective feedstock commodities. In particular, feedstock proves to lead the price of the biofuel and not vice versa. Moreover, the dynamics remains qualitatively unchanged when controlled for the influence of crude oil.

Für einen Algorithmus zum Lösen eines Graphenproblems wird üblicherweise angenommen, dieser sei mit wahlfreiem Zugriff (random access) auf den Eingabegraphen G ausgestattet, als auch mit einem Arbeitsspeicher, der G vollständig aufzunehmen vermag. Diese Annahmen erweisen sich als fragwürdig, wenn Graphen betrachtet werden, deren Größe jene konventioneller Arbeitsspeicher übersteigt. Solche Graphen können nur auf externen Speichern wie Festplatten oder Magnetbändern vorrätig gehalten werden, auf denen wahlfreier Zugriff sehr zeitaufwändig ist. Um riesige Graphen zu bearbeiten, die auf externen Speichern liegen, hat Muthukrishnan 2003 das Modell eines Semi-Streaming Algorithmus vorgeschlagen. Dieses Modell beschränkt die Größe des Arbeitsspeichers und verbietet den wahlfreien Zugriff auf den Eingabegraphen G. Im Gegenteil wird angenommen, die Eingabe sei ein Datenstrom bestehend aus Kanten von G in beliebiger Reihenfolge. In der vorliegenden Dissertation entwickeln wir Algorithmen im Semi-Streaming Modell für verschiedene Graphenprobleme. Für das Testen des Zusammenhangs und der Bipartität eines Graphen, als auch für die Berechnung eines minimal spannenden Baumes stellen wir Algorithmen vor, die asymptotisch optimale Laufzeiten erreichen. Es ist bekannt, dass kein Semi-Streaming Algorithmus existieren kann, der ein größtes gewichtetes Matching in einem Graphen findet. Für dieses Problem geben wir den besten bekannten Approximationsalgorithmus an. Schließlich zeigen wir, dass sowohl ein minimaler als auch ein maximaler Schnitt in einem Graphen nicht von einem Semi-Streaming Algorithmus berechnet werden kann. Für beide Probleme stellen wir randomisierte Approximationsalgorithmen im Semi-Streaming Modell vor. / An algorithm solving a graph problem is usually expected to have fast random access to the input graph G and a working memory that is able to store G completely. These powerful assumptions are put in question by massive graphs that exceed common working memories and that can only be stored on disks or even tapes. Here, random access is very time-consuming. To tackle massive graphs stored on external memories, Muthukrishnan proposed the semi-streaming model in 2003. It permits a working memory of restricted size and forbids random access to the input graph. In contrast, the input is assumed to be a stream of edges in arbitrary order. In this thesis we develop algorithms in the semi-streaming model approaching different graph problems. For the problems of testing graph connectivity and bipartiteness and for the computation of a minimum spanning tree, we show how to obtain running times that are asymptotically optimal. For the problem of finding a maximum weighted matching, which is known to be intractable in the semi-streaming model, we present the best known approximation algorithm. Finally, we show the minimum and the maximum cut problem in a graph both to be intractable in the semi-streaming model and give semi-streaming algorithms that approximate respective solutions in a randomized fashion.

[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

Neste trabalho foi analisada a influência de um evento sobre o mercado de ações brasileiro a partir das redes, e suas árvores geradoras mínimas, obtidas de medidas de dependência baseadas nas correlações de Pearson, de Spearman e de Kendall. O evento considerado foi a notícia da noite de 17 de maio de 2017 em que o dono da empresa brasileira JBS, Joesley Batista, gravou o então Presidente da República Michel Temer autorizando a compra do silêncio de um Deputado Federal. O dia seguinte a notícia, 18 de maio de 2017, foi definido como o dia do evento. Foram coletados dados de alta frequência de 58 ações do Ibovespa no período de 11 a 25 de maio de 2017. As alterações nas redes das ações do mercado foram analisadas comparando-se o período anterior e posterior ao evento em duas escalas de tempo: (1) Redes diárias: cinco pregões antes do evento, o dia do evento e, cinco pregões depois do evento, com cotações a cada 15 minutos; (2) Agrupadas em antes e depois: agrupando os dados dos 5 dias antes e dos 5 dias depois do evento. O estudo das redes diárias indicou mudança de tendência nas suas propriedades no decorrer do período que contém o evento, com cotações a cada 15 minutos. Isto sugeriu que análise do efeito médio contido nos dados agrupados antes de depois do evento poderiam tornar mais evidente as mudanças na estrutura de rede das ações. As redes antes e depois do evento apresentaram mudanças significativas nas suas métricas que ficaram mais evidenciadas nas árvores geradoras mínimas. As redes geradas pelas correlações de Kendall e Spearman apresentaram um número maior de agrupamentos antes e depois do evento e, após o evento, as árvores geradoras mínimas apresentaram uma redução do número de agrupamentos de ações para todos os tipos de correlação. As distribuições de grau ponderado após o evento indicam uma probabilidade maior de vértices com graus distante da média. As métricas das árvores geradoras mínimas por correlação de Spearman sofreram a maior variação, seguidas pelas de Kendall e Pearson, e também, indicaram que as redes após o evento ficaram mais robustas, ou seja, mais rígidas. A maior robustez das redes após o evento indica maior conectividade do mercado, tornando-o, como um todo, mais suscetível ao impacto de novos acontecimentos. / In this work the influence of an event on the Brazilian stock market was analyzed from networks and its minimum spanning trees obtained from measures of dependence based on the Pearson, Spearman, and Kendall\'s correlations. The event considered was the news in the evening of May 17, 2017 in which the owner of the Brazilian company JBS, Joesley Batista, recorded the Brazilian President Michel Temer authorizing the purchase of the silence of a congress member. The day just after the news, May 18, 2017, was defined as the event day. High-frequency data from 58 Ibovespa shares were collected from 11 to 25 May 2017. Changes in the stocks networks were analyzed comparing the period before and after the event in two time scales: (1) Daily networks: five trade sections before the event, the day of the event and, five trade sections after the event, with price every 15 minutes; (2) Grouped before and after do evento: grouping data from 5 days before and 5 days after event. The study of the daily networks indicated a change of trend in their properties during the period that contains the event, with quotations every 15 minutes. The study of daily networks indicated a change of trend in their properties during the period containing the event. This suggested that analysis of the mean effect of grouped data before and after the event could highlight the changes in the network structure. The networks before and after the event showed significant changes in their metrics, which became more evident from the minimum spanning trees. After the event, the minimum spanning trees for grouped data got a smaller number of clusters in the networks for all kind of correlations. The networks generated by Kendall and Spearman correlations presented a larger number of clusters before and after the event. The weighted degree distributions after the event suggest a power law decay tail for all the correlations considered and indicates a higher probability of vertices with weighted degrees far away from the mean weighted degree. The minimum spanning tree metrics generated by Spearman correlation suffered the greatest variation, followed by those of Kendall and Pearson; and their values indicates that after the event the networks became more robust, that is, more rigid. The increase in the networks robustness after the event indicates a higher market connectivity, making it as a whole, more susceptible to the impact of new events.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:00:35Z No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:58:27Z (GMT) No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-06T15:58:27Z (GMT). No. of bitstreams: 2 Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-08-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Many relevant problems to NP-Hard class are present in the real world. Among them we can mention the problems of network design (PNDs) that involve electricity distribution, vehicle traffic, and others. There are not algorithms which provide a exact solution for these types of problems with an acceptable computation time. Over the years, research has been developed used evolutionary algorithms (EAs) to provide an efficient solution with a acceptable computation time for these problems. In addition, appropriate data structures may further improve the performance of EAs to PNDs. The node-depth-degree (NDDE) representation have show significant results for PNDs. The application of EAs in hardware can improve the performance of the algorithm. In this sense, this work presents the implementation of a EA in Nios II processor of a FPGA board to solving the PND minimum spanning tree with degree constraint. The results demonstrate that the implementation of EAs in hardware brings significant results with better performance, due to the power of parallelism present in the FPGA. / Diversos problemas pertinentes a classe NP-Difícil estão presentes no mundo real. Dentre eles pode-se citar os problemas de projeto de redes (PPRs) que envolvem distribuição de energia elétrica, tráfego de veículos, entre outros. Não existem algoritmos que forneçam uma solução exata para esses tipos de problemas com um tempo de computação aceitável. Ao longo dos anos pesquisas estão sendo desenvolvidas utilizado algoritmos evolutivos (EAs) para fornecer uma solução eficiente com tempo de computção aceitável para tais problemas. Além disso, estruturas de dados adequadas podem melhorar ainda mais o desempenho dos EAs para PPRs. A representação nó-profundidade-grau (NDDE) apresenta resultados significativos para PPRs. A aplicação de EAs em hardware pode melhorar o desempenho do algoritmo. Nesse sentido, este trabalho apresenta a implementação de um EA no processador Nios II de uma placa FPGA para solução do PPR da árvore geradora mínima com restrição de grau. Os resultados demonstram que a implementação de EAs em hardware traz resultados significativos com melhor desempenho, devido ao poder de paralelismo presente no FPGA.

De nos jours la protection des données numériques est un problème très important. Que ce soit pour des applications de confidentialité, de communication, de traçabilité ou d'identification par exemple, il est nécessaire de développer des techniques adaptées. Dans le cadre de cette thèse en collaboration avec la société STRATEGIES S.A., la méthode choisie pour la protection de maillages 3D est l'insertion de données cachées, également appelée tatouage numérique. Pour des données 3D, un des problèmes les plus importants est la phase de synchronisation qui intervient dans les algorithmes d'insertion et d'extraction des données. Cette phase permet de repérer, de sélectionner et d'ordonner les « zones » qui sont privilégiées pour la dissimulation d'information. Nous avons choisi d'orienter le manuscrit sur cette phase. Ainsi, nous proposons une classification des méthodes de tatouages en fonction de leur méthode de synchronisation. Puis en se basant sur des techniques de synchronisation par des structures de données, telle que les arbres couvrants de poids minimum, nous proposons une analyse théorique de cette structure. Dans un premier temps nous expliquons les raisons de la sensibilité des arbres à la mobilité des points. Puis connaissant ses faiblesses, nous proposons une autre technique de synchronisation toujours basée sur les arbres couvrants de poids minimum. / Data security is one of the main issue in computer science. We need to develop solutions for confidentiality, communication, fingerprinting or identification applications for exemple. In this thesis made with STRATEGIES S.A., the chosen method to protect 3D meshes is watermarking.Watermarking is divided in two steps, the embedding and the extraction. In both of them a synchronization phase is needed. It is one of the most important step for 3D mesh because it permits to look for areas available to embed information, and order them. All the thesis is devoted to the synchronization step. First of all, we propose a classification of watermarking techniques based on the type of synchronization method instead of evaluation criterions such as robustness or capacity.Then, from methods based on Euclidean minimum spanning tree, we propose a theoritical analysis of the mobility of the vertices in that kind of structure. First, we explain the reasons of the sensibility of the structure. Secondly, we propose another scheme based on the Euclidean minimum spanning tree knowing its fragility.

Pattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches: 1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time. In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree. A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive. Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure.

This thesis addresses statistical estimation and testing of signals over a graph when measurements are noisy and high-dimensional. Graph structured patterns appear in applications as diverse as sensor networks, virology in human networks, congestion in internet routers, and advertising in social networks. We will develop asymptotic guarantees of the performance of statistical estimators and tests, by stating conditions for consistency by properties of the graph (e.g. graph spectra). The goal of this thesis is to demonstrate theoretically that by exploiting the graph structure one can achieve statistical consistency in extremely noisy conditions. We begin with the study of a projection estimator called Laplacian eigenmaps, and find that eigenvalue concentration plays a central role in the ability to estimate graph structured patterns. We continue with the study of the edge lasso, a least squares procedure with total variation penalty, and determine combinatorial conditions under which changepoints (edges across which the underlying signal changes) on the graph are recovered. We will shift focus to testing for anomalous activations in the graph, using the scan statistic relaxations, the spectral scan statistic and the graph ellipsoid scan statistic. We will also show how one can form a decomposition of the graph from a spanning tree which will lead to a test for activity in the graph. This will lead to the construction of a spanning tree wavelet basis, which can be used to localize activations on the graph.

Proximity problems and point set embeddability problems are fundamental and well-studied in computational geometry and graph drawing. Examples of such problems that are of particular interest to us in this dissertation include: finding the closest pair among a set P of points, finding the k-nearest neighbors to each point p in P, answering reverse k-nearest neighbor queries, computing the Yao graph, the Semi-Yao graph and the Euclidean minimum spanning tree of P, and mapping the vertices of a planar graph to a set P of points without inducing edge crossings. In this dissertation, we consider so-called kinetic version of these problems, that is, the points are allowed to move continuously along known trajectories, which are subject to change. We design a set of data structures and a mechanism to efficiently update the data structures. These updates occur at critical, discrete times. Also, a query may arrive at any time. We want to answer queries quickly without solving problems from scratch, so we maintain solutions continuously. We present new techniques for giving kinetic solutions with better performance for some these problems, and we provide the first kinetic results for others. In particular, we provide: • A simple kinetic data structure (KDS) to maintain all the nearest neighbors and the closest pair. Our deterministic kinetic approach for maintenance of all the nearest neighbors improves the previous randomized kinetic algorithm. • An exact KDS for maintenance of the Euclidean minimum spanning tree, which improves the previous KDS. • The first KDS's for maintenance of the Yao graph and the Semi-Yao graph. • The first KDS to consider maintaining plane graphs on moving points. • The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1. • The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points. / Graduate

One of the most important factors on the success of evolutionary algorithms (EAs) about trees is the representation of them. The representation should exhibit efficiency, locality and heritability to enable effective evolutionary computing. Neville proposed three different methods for encoding labeled trees. The first one is similar with Pr&uuml / fer&#039 / s encoding. In 2001, it is reported that, the use of Pr&uuml / fer numbers is a poor representation of spanning trees for evolutionary search, since it has low locality for random trees. In the thesis Neville&#039 / s other two encodings, namely Neville branch numbers and Neville leaf numbers, are studied. For their performance in EA their properties and algorithms for encoding and decoding them are also examined. Optimal algorithms with time and space complexities of O(n) , where n is the number of nodes, for encoding and decoding Neville branch numbers are given. The localities of Neville&#039 / s encodings are investigated. It is shown that, although the localities of Neville branch and leaf numbers are perfect for star type trees, they are low for random trees. Neville branch and Neville leaf numbers are compared with other codings in EAs and SA for four problems: &#039 / onemax tree problem&#039 / , &#039 / degree-constrained minimum spanning tree problem&#039 / , &#039 / all spanning trees problem&#039 / and &#039 / all degree constrained spanning trees problem&#039 / . It is shown that, neither Neville nor Pr&uuml / fer encodings are suitable for EAs. These encodings are suitable for only tree enumeration and degree computation. Algorithms which are timewise and spacewise optimal for &#039 / all spanning trees problem&#039 / (ASTP) for complete graphs, are given by using Neville branch encoding. Computed time and space complexities for solving ASTP of complete graphs are O(nn-2) and O(n) if trees are only enumerated and O(nn-1) and O(n) if all spanning trees are printed , respectively, where n is the number of nodes. Similarly, &#039 / all degree constrained spanning trees problem&#039 / of a complete graph is solvable in O(nn-1) time and O(n) space.