The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the shortest distances and paths between vertices with any given single failure in constant time without reconstructing the oracle. Using their paper as a guideline, we have implemented their algorithm in C++ and recorded each step in this thesis. Each step has its own pseudo-code and its own analysis to prove that the entire oracle construction stays within the stated running time and total space bounds, from the authors. The effciency of the algorithm is compared against that of the brute-force methods total running time and total space needed. Using multiple test cases with an increasing number of vertices and edges, we have experimentally validated that their algorithm holds true to their statements of space, running time, and query time.

Title: On the Dijkstra's algorithm in the Pedestrian Flow Problem Author: Tereza Petrášová Department: Department of Numerical Mathematics Supervisor: doc. RNDr. Jiří Felcman, CSc., Department of Numerical Mathe- matics Abstract: The pedestrian flow problem is described by a coupled system of the first order hyperbolic partial differential equations with the source term and by the functional minimization problem for the desired direction of motion. The functional minimization is based on the modified Dijkstra's algorithm used to find the minimal path to the exit. The original modification of the Dijkstra's algorithm is proposed to increase its efficiency in the pedestrian flow problem. This approach is compared with the algorithm of Bornemann and Rasch for determination of the desired direction of motion based on the solution of the so- called Eikonal equation. Both approaches are numerically tested in the framework of two splitting algorithms for solution of the coupled problem. The former splitting algorithm is based on the finite volume method yielding for the given time instant the piecewise constant approximation of the solution. The latter one uses the implicit discretization by a space-time discontinuous Galerkin method based on the discontinuous piecewise polynomial approximation. The numerical examples...

Made available in DSpace on 2014-06-11T19:24:42Z (GMT). No. of bitstreams: 0 Previous issue date: 2009-12-16Bitstream added on 2014-06-13T19:52:21Z : No. of bitstreams: 1 silva_isr_me_botfca.pdf: 1100428 bytes, checksum: 826dc0fb9625c7e450be2699f43ec0bd (MD5) / A atual preocupação com o meio ambiente tem feito com que empresas produtoras de cana-de-açúcar invistam na mudança do sistema de colheita. Essa mudança consiste na redução da queima do canavial na pré-colheita e na utilização do corte mecanizado com cana crua. Porém, a colheita com corte mecanizado torna disponível a biomassa residual e sem as queimadas e com o maior acúmulo do palhiço sobre o solo, criamse condições favoráveis para o aparecimento de parasitas e atraso da brota da cana, comprometendo a próxima safra. Vários autores mostram a viabilidade do uso do palhiço na produção de energia. Pois, além do potencial energético desta biomassa, têm-se como vantagens as questões ambientais, a manutenção de empregos e a substituição dos recursos energéticos de fontes naturais. Mas, as grandes dificuldades ainda encontradas para aproveitamento desse resíduo para geração de energia são o grande número de maquinário envolvido no sistema de coleta deste resíduo e o alto custo que este processo demanda, principalmente o custo com transporte. O presente trabalho tem como objetivo propor aplicações de técnicas matemáticas de otimização para auxiliar o planejamento do recolhimento do palhiço da cana-de-açúcar para aproveitamento na geração de energia, estudando a melhor forma de carregamento dos fardos de palhiço, facilitando o transporte, diminuindo custos e desgastes de maquinários. Para isto, é sugerido o uso de técnicas de agricultura de precisão para mapear o palhiço enfardado, desta forma pode-se definir uma rota para recolher os fardos no campo e transportá-los para o centro de processamento. Para determinação da rota, propõe-se o uso do algoritmo de menor caminho da teoria de grafos, utilizando uma variação do algoritmo de Dijkstra. / The current concern with the environment has made sugar cane growers invest in changing their harvesting system. This change consists of the reduced burning of cane fields before harvesting and the use of mechanized cutting for raw canes. However, mechanized harvesting makes residual biomass available and, without the burning, the major accumulation of crop residue on the ground, creating favorable conditions for the emergence of parasites and delay of new shoots, affecting the next crop. Several authors show the feasibility of using crop residue for energy production. Besides the energy potential of the biomass, there are advantages for the environmental issues, preservation of jobs and the replacement of energy resources from natural sources. But the great difficulties still found in using this residue for power generation are the large number of machinery involved in the collection system of the waste and the high costs of this process, mainly transport costs. This paper aims to propose applications of mathematical optimization techniques to help plan the collection of sugar cane crop residue to be used for power generation, by studying the best way of loading bales of crop residue, making it easy to transport them, therefore reducing costs and wear on machinery. For this, we suggested the use of techniques of Precision Agriculture to map the baled crop residue, which allows you to define a route to pick up the bales in the field and transport them to the processing center. To determine the route, it is proposed to use the shortest path algorithm from graph theory, using a variation of Dijkstra's algorithm.

Orientador: Helenice de Oliveira Florentino Silva / Banca: Adriana Cristina Cherri Nicola / Banca: Odivaldo José Seraphim / Resumo: A atual preocupação com o meio ambiente tem feito com que empresas produtoras de cana-de-açúcar invistam na mudança do sistema de colheita. Essa mudança consiste na redução da queima do canavial na pré-colheita e na utilização do corte mecanizado com cana crua. Porém, a colheita com corte mecanizado torna disponível a biomassa residual e sem as queimadas e com o maior acúmulo do palhiço sobre o solo, criamse condições favoráveis para o aparecimento de parasitas e atraso da brota da cana, comprometendo a próxima safra. Vários autores mostram a viabilidade do uso do palhiço na produção de energia. Pois, além do potencial energético desta biomassa, têm-se como vantagens as questões ambientais, a manutenção de empregos e a substituição dos recursos energéticos de fontes naturais. Mas, as grandes dificuldades ainda encontradas para aproveitamento desse resíduo para geração de energia são o grande número de maquinário envolvido no sistema de coleta deste resíduo e o alto custo que este processo demanda, principalmente o custo com transporte. O presente trabalho tem como objetivo propor aplicações de técnicas matemáticas de otimização para auxiliar o planejamento do recolhimento do palhiço da cana-de-açúcar para aproveitamento na geração de energia, estudando a melhor forma de carregamento dos fardos de palhiço, facilitando o transporte, diminuindo custos e desgastes de maquinários. Para isto, é sugerido o uso de técnicas de agricultura de precisão para mapear o palhiço enfardado, desta forma pode-se definir uma rota para recolher os fardos no campo e transportá-los para o centro de processamento. Para determinação da rota, propõe-se o uso do algoritmo de menor caminho da teoria de grafos, utilizando uma variação do algoritmo de Dijkstra. / Abstract: The current concern with the environment has made sugar cane growers invest in changing their harvesting system. This change consists of the reduced burning of cane fields before harvesting and the use of mechanized cutting for raw canes. However, mechanized harvesting makes residual biomass available and, without the burning, the major accumulation of crop residue on the ground, creating favorable conditions for the emergence of parasites and delay of new shoots, affecting the next crop. Several authors show the feasibility of using crop residue for energy production. Besides the energy potential of the biomass, there are advantages for the environmental issues, preservation of jobs and the replacement of energy resources from natural sources. But the great difficulties still found in using this residue for power generation are the large number of machinery involved in the collection system of the waste and the high costs of this process, mainly transport costs. This paper aims to propose applications of mathematical optimization techniques to help plan the collection of sugar cane crop residue to be used for power generation, by studying the best way of loading bales of crop residue, making it easy to transport them, therefore reducing costs and wear on machinery. For this, we suggested the use of techniques of Precision Agriculture to map the baled crop residue, which allows you to define a route to pick up the bales in the field and transport them to the processing center. To determine the route, it is proposed to use the shortest path algorithm from graph theory, using a variation of Dijkstra's algorithm. / Mestre

This thesis deals with the distributed and stochastic algorithms including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Furthermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in Matlab.

Submitted by William Justo Figueiro (williamjf) on 2015-07-18T13:23:58Z No. of bitstreams: 1 51c.pdf: 3316384 bytes, checksum: 9eb62dc3d062f0ca82674a6d3feb7fdc (MD5) / Made available in DSpace on 2015-07-18T13:23:58Z (GMT). No. of bitstreams: 1 51c.pdf: 3316384 bytes, checksum: 9eb62dc3d062f0ca82674a6d3feb7fdc (MD5) Previous issue date: 2011-03-29 / Nenhuma / O crescimento do tráfego nas redes de telecomunicações por serviços de banda larga, telefonia fixa e móvel tem demandado esforços no planejamento e estudo da recomposição da rede, em especial redes de transporte, tornando elevado o nível de complexidade na elaboração de projetos que envolvem redes. A complexidade de interligação aumenta de acordo com as restrições impostas pela capacidade de investimentos e custos operacionais na obtenção da solução ótima para a melhor topologia de rede. Para resolver problemas de planejamento e recomposição da rede de telecomunicações é necessária a utilização de recurso computacional, pois problemas que envolvem redes desta natureza possuem a característica do conjunto de problemas de otimização combinatória, considerados difíceis. Com o objetivo de planejar e realizar estudos na recomposição da rede de telecomunicações, neste trabalho é apresentada a estratégia que visa o uso de recursos heurísticos como algoritmo genético e Dijkstra, bem como o conceito de rede fictícia na modelagem e solução computacional na obtenção da solução ótima referente à topologia de rede, possibilitando a análise prévia do tráfego na topologia proposta caso houver a incidência de falhas. / The growth of traffic on telecommunications networks for broadband services, fixed and mobile telephony has demanded efforts in planning and study the restoration of the network, especially transport networks, making the high level of complexity in developing projects that involve networks. The interconnection complexity increases with the restrictions imposed by the capacity of investment and operating costs in obtaining the optimal solution for the best network topology. To resolve issues of planning and rebuilding of the telecommunication networks is necessary to use computational resources, since problems involving networks of this nature have the feature set of combinatorial optimization problems, considered difficult. With the objective to plan and carry out studies on the recomposition of the telecommunications network, in this work the strategy for use as heuristic genetic algorithm and Dijkstra, as well as the concept of fictitious network modeling and computational solution to obtain the solution great on the network topology, enabling preliminary analysis of traffic on the proposed topology where there incidence of failures.

This thesis deals with the distributed and stochastic algorithms including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Furthermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in Matlab.

This thesis deals with the distributed and stochastic algorithms, including testing their convergence in networks. The theoretical part briefly describes above mentioned algorithms, including their division, problems, advantages and disadvantages. Futhermore, two distributed algorithms and two stochastic algorithms are chosen. The practical part is done by comparing the speed of convergence on various network topologies in MATLAB.

This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.

The work deals with the measurement and management in power. Provides an introduction to the problems of remote meter reading, management, and describes the current situation in the field of modern technologies Smart metering and Smart grids. It also analyzed the issue of collection of networks and data collection from a large number of meters over a wide area. For the purpose of data transmission are described GPRS, PLC, DSL, ... Further, there are given options to streamline communication. This area is used hierarchical aggregation. Using k-means algorithm is a program designed to calculate the number of concentrators and their location in the group of meters. The finished program is written in Java. It has a graphical interface and shows how the calculation is conducted. To verify the results of the optimization program is given simulation model in OPNET Modeler tool. Audited results are described in the conclusion and can deduce that using the optimization program is to streamline communications.