Orientadora : Profª. Drª. Elizabeth W. Karas / Co-orientadora : Profª. Drª. Mael Sachine / Orientador no exterior : Profª. Drª. Joaquim J. Júdice / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Matemática. Defesa: Curitiba, 25/02/2016 / Inclui referências : f. 133-144 / Resumo: Este trabalho engloba dois temas diferentes. Inicialmente, apresentamos um algoritmo para resolver problemas de otimizacao restrita que não faz uso das derivadas da funcao objetivo. O algoritmo mescla conceitos de restauração inexata com técnicas de filtro. Cada interação é decomposta em duas fases: uma fase de viabilidade e uma fase de otimalidade, as quais visam reduzir os valores da medida de inviabilidade e da funcao objetivo, respectivamente. A fase de otimalidade é computada por interações internas de região de confiança sem derivadas, sendo que seus modelos podem ser construídos por qualquer técnica, contanto que sejam aproximaçoes razoável para a função objetivo em torno do ponto corrente. Assumindo esta, e hipóteses clássicas, provamos que o algoritmo satisfaz certa condição de eficiência, a qual implica sua convergência global. Para a análise prática, são apresentados alguns resultados numéricos. O segundo tema refere-se a problemas de complementaridade linear. Nesta parte são discutidos alguns algoritmos de pivotamento em blocos principais, eficientes para solucionar este tipo de problema. Uma análise sobre algumas técnicas para garantia de convergência desses algoritmos _e realizada. Apresentamos alguns resultados numéricos para comparar a eficiencia e a robustez dos algoritmos discutidos. Além disso, são apresentadas duas aplicações para o método de pivotamento em blocos principais: decomposição em matrizes não negativas e métodos de gradiente projetados precondicionado. Para finalizar, nesta segunda aplicação, sugerimos uma matriz de precondicionamento. / Abstract: This work covers two diferent subjects. First we present an algorithm for solving constrained optimization problems that does not make explicit use of the objective function derivatives. The algorithm mixes an inexact restoration framework with filter techniques. Each iteration is decomposed in two phases: a feasibility phase that reduces an infeasibility measure; and an optimality phase that reduces the objective function value. The optimality step is computed by derivative-free trust-region internal iterations, where the models can be constructed by any technique, provided that they are reasonable approximations of the objective function around the current point. Assuming that this and classical hypotheses hold, we prove that the algorithm satisfes an eficiency condition, which provides its global convergence. Preliminar numerical results are presented. In the second subject, we discuss the linear complementarity problem. Some block principal pivoting algorithms, eficient for solving this kind of problem, are discussed. An analysis of some techniques to guarantee convergence results of these algorithms is made. We present some numerical results to compare the eficiency and the robustness of the algorithms. Moreover we discuss two applications of the block principal pivoting: nonnegative matrix factorization and preconditioned projected gradient methods. Furthermore, in this second application, we suggest a preconditioning matrix.

Resumo: E notável o crescente uso da Internet para a transmissão de vídeos, sejam eles estáticos, com conteúdo previamente armazenado, ou dinâmicos, com conteúdo gerado ao vivo, no momento de sua exibição. Enquanto em transmissães estáticas pode-se carregar completamente o conteúdo e assisti-lo sem saltos, em uma transmissão dinâmica essa característica é impraticável. As redes peer-to-peer (P2P) têm sido cada vez mais utilizadas para transmissões de mídias contínuas ao vivo. Um servidor fonte é responsável pela inserção inicial dos dados na rede. Cada usuário que está acompanhando a ransmissão, também chamado de peer, repassa os dados recebidos para outros usuários, ou seja, cada peer participante compartilha com os demais o conteúdo que possui. Essa estratégia diminui otencialmente a carga sobre o servidor fonte que realiza a transmissão. Como os usuários são esponsáveis pela difusão dos dados, um problema surge: a poluição de conteúdo. Um dado fica poluído quando, intencionalmente ou não, algum usuário repassa conteúdo incorreto para seus vizinhos, ou seja, um conteúdo diferente daquele gerado pelo fonte. O presente trabalho expõe uma nova solução para a detecção de alterações de conteúdo utilizando o diagnóstico baseado em comparações. Para realizar o diagnóstico, os participantes da rede P2P executam comparações sobre o conteúdo recebido de seus vizinhos. O resultado destas comparações permite a classificação dos peers em conjuntos com o objetivo de detectar se há poluição de conteúdo e quem são os peers poluídos. Essa estratégia foi implementada no Fireflies, um protocolo escalável para redes overlai tolerante a intrusões. Os resultados obtidos através de experimentos de simulação demonstraram que essa estratégia é viável para a detecção de alterações no conteúdo transmitido entre os usuários, além de apresentar baixa sobrecarga no tráfego da rede.

Made available in DSpace on 2014-06-11T19:22:34Z (GMT). No. of bitstreams: 0 Previous issue date: 2013-12-20Bitstream added on 2014-06-13T20:29:05Z : No. of bitstreams: 1 000750866.pdf: 4302130 bytes, checksum: efac3d1d795a3f0286001041f918cb45 (MD5) / Por se tratar de uma tarefa complexa, as instituições passaram a recorrer a diversas metaheurísticas no intuito de resolver um problema árduo e complexo que é a elaboração de grade horária. No Brasil, com o advento do desenvolvimento da microinformática a partir da década de 90, do século XX, esse problema foi tratado com o uso de ferramentas de programação linear e métodos matemáticos baseados em otimização clássica. Posteriormente, passou a ser executado pelas universidades públicas e privadas a partir de propostas computacionais, desenvolvidas para a resolução desse tipo de problema, usando técnicas fundamentadas no uso de metaheurísticas. O presente trabalho visa projetar e implementar computacionalmente um algoritmo tipo VNS (do inglês Variable Neighborhood Search) para resolver o problema de programação de horários em ambientes universitários; realizar uma análise teórica e experimental do desempenho do algoritmo VNS e discutir a aplicação desse algoritmo na otimização de outros problemas da família de problemas do tipo timetabling. Para isso foi desenvolvido um algoritmo de busca em vizinhança variável para resolver um tipo de problema da família timetabling em ambientes universitários. / Building of timetables is a hard work to accomplish due to its complexity, so that institutions started to make use of several Metaheuristics for solving timetabling problems. In Brazil, the development of Computer Science from the Nineties, within the late 20th century, allowed to handle this kind of problem with Linear Programming Tools and Mathematical Methods based upon Classical Optimization Techniques. Afterwards, the same task was carried out by private and public universities using computational proposals based upon Metaheuristics. The aim of this work is to project and implement VNS algorithm computationally to solve timetabling problems in university environments; to provide a theoretical and experimental analysis of the VNS algorithm performance and discuss its application in order to optimize any other type of timetabling family problems. Thus, an algorithm of variable neighborhood search was developed for solving problems of timetabling family in university environments.

No description available.

Resumo: Esta dissertação aborda uma proposta de metodologia de resolução de um problema de entregas que abrange a integração de dois problemas clássicos de Otimização Combinatória: o Problema de Carregamento de Container (PCC) e o Problema de Roteamento de Veículos (PRV). O problema específico analizado está na logística empregada no carregamento e entrega de eletrodomésticos (linha branca) vendidos à pessoa física. Para representar esta situação, assume-se um cenário fictício em que a empresa que vende os produtos possui um Centro de Distribuição de Produtos (CD) localizado na cidade de Curitiba e uma lista de doze possíveis produtos a serem vendidos. A partir desta lista foram gerados 160 pedidos diferentes para serem entregues em vinte endereços aleatórios localizados também na cidade de Curitiba. Para a resolução deste problema, apresenta-se uma metodologia baseada em formação de torres de caixas e um Algoritmo Bottom-Left para realizar o carregamento dos pedidos no compartimento de carga dos veículos e um Algoritmo Genético para realizar a otimização evolutiva da solução até que se encontre uma solução suficientemente próxima à solução ótima do problema, buscando diminuir, a cada geração, a distância total percorrida pelos veículos de entrega. Para demonstração e utilização desta metodologia, apresenta-se uma implementação dos algoritmos e técnicas de pesquisa operacional descritos acima para a resolução desenvolvida em linguagem de programação Microsoft Visual Basic. Utilizando-se esta implementação e o cenário construído para testes, obteve-se bons resultados em relação à distância total percorrida pelos veículos de entrega, com redução de 25% a 45% em relação às soluções iniciais aleatórias, sendo que em alguns casos, esta melhoria alcançou até 60%.

Resumo: A Computação Evolucionária (CE) introduz um novo paradigma para resolver problemas em Inteligência Artificial, representando candidatos à solução como indivíduos e evoluindo-os com base na Teoria da Seleção Natural de Darwin. Algoritmos Genéticos (AG) e Programação Genética (PG), duas importantes técnicas de CE, têm sido aplicadas com sucesso tanto em cenários teóricos quanto em situações práticas. Este trabalho discute o ajuste automático dos parâmetros que controlam o processo de busca neste tipo de algoritmo. Baseado em uma pesquisa recente, um método que controla o tamanho da população em AG é adaptado e implementado em PG. Uma série de experimentos clássicos foi realizada, antes e depois das modificações, mostrando que este método pode aumentar a robustez e a confiabilidade no algoritmo. Os dados permitem uma discussão sobre o método e a importância da adaptação de parâmetros em algoritmos de CE.

Orientador : Prof. Dr. Renato José da Silva Carmo / Coorientador : Prof. Dr. André Luís Vignatti / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 26/02/2016 / Inclui referências : f. 55-57 / Resumo: A teoria dos grafos é um ramo da matemática utilizada para modelar e representar um conjunto de elementos e suas relações, além de ser muito utilizada na resolução de problemas computacionais. Um grafo pode representar diversos sistemas naturais e digitais como ligações proteicas, redes sociais, conexões digitais, entre outras. Essas redes contêm diversas características, uma dessas é a distribuição de grau dos vértices. Muitos grafos do mundo real apresentam em sua estrutura uma distribuição de grau que segue uma lei de potência (Power Law), o que informalmente significa que existem poucos vértices de grau elevado, enquanto muitos vértices apresentam grau baixo. Dentro dos problemas clássicos algorítmicos, estamos interessados em problemas computacionalmente difíceis de serem resolvidos e que pertencem à classe NP-Difícil, especificamente o problema da cobertura por vértices mínima em grafos que apresentam uma distribuição de grau lei de potência. Assim, é apresentado neste trabalho um método inspirado em regras de redução ao núcleo do problema. Os resultados obtidos sugerem ser uma boa heurística de aproximação da solução _ótima, além de reduzir significativamente o tempo computacional na resolução do problema da cobertura por vértices. Palavras-chave: Grafos, Cobertura por Vértices, Regras de redução, Lei de Potência. / Abstract: Graph theory is a branch of mathematics used to model and represent a set of elements and their relationships, which is also often used to solve computational problems. A graph can represent various natural and digital systems, such as: protein binding, social networks, digital connections, among others. Those networks contain diverse characteristics, which one of these is the degree of the distribution of the vertices. Many graphs of the real world have in their structure a degree of distribution following a power-law, where informally means that there are few high degree vertices, while many other vertices have a low degree. Within the algorithmic classic problems, we are interested in computationally difficult problems to be solved and which belong to the NP-Hard class, specifically the problem of minimum vertex cover in graphs, that have a power-law degree distribution. Thus, this work presents a method based on reduction rules to the core of the problem. The achieved results indicate that it is a good approximation heuristic from the optimal solution, in addition to be a technique that a significantly reduces on the computational time to solve the problem of minimum vertex cover. Keywords: Graph, Vertex Cover, reduction rules, Power Law.

Resumo: Aplicações de Processamento de Imagens podem exigir poder de processamento tão alto que a computação tradicional não é capaz de fornecer. Uma alternativa eficiente é a computação de Propósito Geral em Placas Gráficas (GPGPU). CUDA ´e a API da NVidia que implementa o modelo de programação em placas gráficas. Muitas aplicaces que foram reimplementadas em CUDA estão alcançando ganhos significativos de desempenho. Este trabalho tem como objetivo aproveitar o processamento paralelo das placas gráficas através do modelo de computação CUDA para proporcionar melhor desempenho ao detector de bordas Canny na biblioteca de processamento de imagens ITK. Para isso, é apresentado um estudo sobre as arquiteturas CUDA e ITK, conceitos pertinentes e as abordagens utilizadas para implementar filtros ITK para executar em placas gráficas. Além do detector de bordas Canny, foram desenvolvidos o cálculo de gradiente Sobel e a Suavização Gaussiana, assim como uma classe de configuração CUDA para o ITK. O desempenho desses filtros foram avaliados mostrando ganhos em qualquer arquitetura de placa gráfica da NVidia. Além disso, técnicas eficientes de programação foram propostas e avaliadas nas arquiteturas de placas da NVidia G80, GT200 e Fermi. Palavras-chave: Computação em Placas Gráficas; GPGPU; CUDA; Processamento de Imagens; ITK; Canny; Suavização Gaussiana; Convolução; Sobel.

Orientador : Prof. Dr. Renato Carmo / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 28/09/2017 / Inclui referências : f. 107-113 / Resumo: O problema da Clique Máxima (CM) é um problema fundamental e há uma grande motivação pela busca de algoritmos tão eficientes quanto possível para resolvê-lo de forma exata. Como esperado para um problema NP-difícil, os melhores algoritmos com desempenho de pior caso conhecido tem custo de tempo exponencial. Por outro lado, resultados experimentais encontrados na literatura indicam que instâncias de tamanho considerável podem ser resolvidas usando algoritmos baseados na técnica de branch-and-bound. Com isso, observa-se uma distância entre os melhores resultados analíticos e os melhores resultados experimentais. Uma possível explicação para discrepância aparente entre teoria e prática foi encontrada pela análise de instâncias aleatórias. Diversos algoritmos de branch- and-bound para a solução exata do CM foram estudados, analisados e implementados. Com base nos resultados analíticos é proposta uma metodologia para comparação experimental de algoritmos, que tem como principal ponto positivo o fato de que algoritmos podem ser comparados independente de detalhes de implementação e execução. Vários algoritmos foram testados como prova de conceito. Também foram estudadas instâncias de pior caso para algoritmos de branch-and-bound que só utilizam coloração como limitante superior, resultando em um custo exponencial de tempo para estes algoritmos. Uma nova família de algoritmos foi desenvolvida, capaz de resolver tais instâncias em tempo polinomial. Recentemente, técnicas de resolvedores para problemas de satisfatibilidade têm sido aplicadas em algoritmos para CM. Tais técnicas dependem de uma redução entre os dois problemas, mas o significado em termos do grafo fica obscurecido nas descrições originais. Algumas técnicas foram estudadas e convertidas para uma descrição que não usa termos referentes aos problemas de satisfatibilidade. A implementação de vários algoritmos estudados foi disponibilizada em um repositório de acesso público. Palavras-chave: Solução exata. Branch-and-bound. Análise de algoritmos. Comparação experimental. / Abstract: e Maximum Clique problem (CM) is a fundamental problem and there is a great motivation for the development of efficient exact algorithms to solve it. As expected for a NP-hard problem, the best algorithms where worst case analyses have been conducted present exponential running times. On the other hand, experimental results available in the literature show that instances of considerable size can be solved by branch and bound algorithms. Therefore, there is an apparent gap between the best theoretical results and the best experimental results. One possible explanation for this discrepancy between theory and practice was found through the analyses of random instances. Several exact branch and bound algorithm for CM were studied, analyzed and implemented. Based on these analytical results, a new methodology for the comparison of algorithms is proposed, where algorithms can be tested and compared regardless of implementation and execution details. Several algorithms were tested as a proof of concept. Worst case instances for some branch and bound algorithms were studied, namely algorithms that adopt only coloring-based bounding techniques to reduce the search space. These algorithms present exponential time cost for the studied instances. A new family of algorithms was developed, which is able to solve the mentioned instances in polinomial time. Recently, techniques from satisfiability solvers have been used in algorithms for CM. Such techniques depend on a reduction between the problems, and the original descriptions in terms of propositional calculus obscures their graph theoretic meaning. Some of these techniques were studied and converted to a description that uses only graph theory terminology. The implementation of several algorithms was made available in a public access repository. Keywords: Exact solution. Branch-and-bound. Analysis of algorithms. Experimental comparison.

Orientadora : Profª. Drª. Maria Teresinha Arns Steiner / Co-orientador : Prof. Dr. Cassius Tadeu Scarpin / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduação em Engenharia de Produção. Defesa: Curitiba, 16/02/2016 / Inclui referências : f. 93-99 / Resumo: A educação e o cuidado na primeira infância vêm sendo tratados, cada vez mais, como assuntos prioritários em âmbito nacional. Isto vem ocorrendo, tanto por parte dos governos Federal, Estadual e Municipal, como pelas organizações da sociedade civil, por um número crescente de profissionais, que veem na Educação Infantil uma verdadeira "ponte" para a formação integral do cidadão. Assim, o objetivo do trabalho consiste em estudar a atual distribuição espacial dos centros públicos de Educação Infantil em Curitiba-PR, e otimizar a localização dessas unidades mediante a abordagem de quatro análises complementares, embora bastante independentes entre si. A primeira é a análise da Localização Atual das instalações, importante para efeitos práticos, pois os desequilíbrios podem ser mostrados em um mapa, juntamente com suas magnitudes. A segunda análise é a análise da Localização Proposta, que envolve a proposta de uma relocalização das unidades de toda a rede. A terceira análise é referente a uma estratégia de Expansão da capacidade das unidades existentes. Recorrendo ao modelo de transportes foi possível a avaliação numérica do número de vagas que deveriam ser abertas em cada unidade a fim de que a demanda fosse suprida. A quarta análise baseia-se numa estratégia de construção ou abertura de novas instalações, em que avalia-se dois modelos - o Problema das p-medianas (PPM) capacitado e o não-capacitado. Exceto para a terceira análise, o modelo básico empregado foi o das p-medianas, que pressupõe que o aluno prefere a escola mais próxima de sua residência. Os modelos foram resolvidos pelo solver CPLEX©. Para a representação dos resultados em mapas, utilizou-se o software ArcGis® 10.1, facilitando a interpretação dos mesmos. Em paralelo aos resultados obtidos pelo modelo exato, criou-se uma estratégia de solução do PPM não-capacitado baseada em Algoritmos Genéticos (AG). Os resultados de validação do AG indicaram que o método proposto neste trabalho apresenta soluções satisfatórias. O algoritmo proposto destaca-se pela qualidade de soluções para instâncias de maior porte (com 3282 vértices), por apresentar gaps consideravelmente inferiores às meta-heurísticas da literatura. Em suma, o estudo demonstrou que, de forma geral, existe a necessidade de planejamento imediato para expansão do ensino público infantil em Curitiba-PR, inclusive para o cumprimento efetivo das metas do Plano Nacional da Educação (PNE). Estima-se que a rede pública supra 30,6% em relação a demanda existente. Considerando as vagas absorvidas pela rede privada igual a 50% sobre a demanda, estima-se que ainda faltem 25.177 vagas a serem criadas. Dessa forma, tendo em vista uma evidente necessidade de grandes investimentos nesse campo, os resultados deste trabalho podem contribuir inclusive, para uma melhor estratégia de investimentos em Centros de Educação Infantil. / Abstract: The education and care in early childhood have been treated increasingly as priority issues at the national level. This has been occurring, both by the Federal, State and Municipal governments, as by civil society, a growing number of professionals see in kindergarten a real "bridge" to the integral formation of citizens. This study aims to study the current spatial distribution of public early childhood education facilities in Curitiba, PR, and optimize the location of these units through four complementary analysis approach, though quite independent of each other. The first is to analyze the Current Location of facilities, important for practical purposes, because the imbalances can be displayed on a map along with their magnitudes. The second analysis is the analysis of location proposal, involving a proposed relocation of the entire network drives. The third analysis refers to a strategy of expansion of capacity of existing units. The fourth analysis is based on a strategy of construction or opening of new facilities, in which we evaluate two models - the capacitated PPM and non-capacitated. Except for the third analysis, the basic model employed was the p-median, which assumes that the student prefers the school nearest their home. The models were created using the modeling language VB.NET© and they were solved by the solver CPLEX©. For the representation of the results, we used the ArcGis® 10.1 software, facilitating their interpretation. In parallel to the results obtained from the exact model, it was created a PPM solution strategy non-capacited based on Genetic Algorithm (GA). The GA validation results indicated that the method proposed in this study presents satisfactory solutions, and the goal of establishing a method of solution to the real problem of assessing the location of early childhood education centers has been reached. In short, the study showed that, in general, immediate planning is required to expand the children's public school in Curitiba-PR, including the effective implementation of the goals of the National Education Plan. Similarly, by looking up the obvious need for major investments in this field, the results of this work could contribute even to a better investment strategy in early childhood education centers.