Página 1 dos resultados de 193 itens digitais encontrados em 0.050 segundos

O problema da subsequência comum máxima sem repetições; The repetition-free longest common subsequence problem

Tjandraatmadja, Christian
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 26/07/2010 PT
Relevância na Pesquisa
76.05%
Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo.; We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique...

Processos de decisão Markovianos fatorados com probabilidades imprecisas; Factored Markov decision processes with Imprecise Transition Probabilities

Delgado, Karina Valdivia
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 19/01/2010 PT
Relevância na Pesquisa
75.99%
Em geral, quando modelamos problemas de planejamento probabilístico do mundo real, usando o arcabouço de Processos de Decisão Markovianos (MDPs), é difícil obter uma estimativa exata das probabilidades de transição. A incerteza surge naturalmente na especificação de um domínio, por exemplo, durante a aquisição das probabilidades de transição a partir de um especialista ou de dados observados através de técnicas de amostragem, ou ainda de distribuições de transição não estacionárias decorrentes do conhecimento insuficiente do domínio. Com o objetivo de se determinar uma política robusta, dada a incerteza nas transições de estado, Processos de Decisão Markovianos com Probabilidades Imprecisas (MDP-IPs) têm sido usados para modelar esses cenários. Infelizmente, apesar de existirem diversos algoritmos de solução para MDP-IPs, muitas vezes eles exigem chamadas externas de rotinas de otimização que podem ser extremamente custosas. Para resolver esta deficiência, nesta tese, introduzimos o MDP-IP fatorado e propomos métodos eficientes de programação matemática e programação dinâmica que permitem explorar a estrutura de um domínio de aplicação. O método baseado em programação matemática propõe soluções aproximadas eficientes para MDP-IPs fatorados...

Aproximação de métricas finitas por métricas arbóreas e aplicações; Approximation of finite metrics by tree metrics and applications

Lima, Murilo Santos de
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 15/12/2011 PT
Relevância na Pesquisa
76.11%
Muitos problemas de otimização em grafos, em especial problemas métricos, são mais fáceis de resolver em árvores. Portanto, uma estratégia para obter um bom algoritmo para certos problemas é obter uma árvore que aproxime o grafo, e utilizar uma solução do problema nessa árvore como uma solução aproximada para o problema no grafo original. Neste trabalho é estudada a técnica de Fakcharoenphol, Rao e Talwar, que mostraram como aproximar uma métrica finita arbitrária com n pontos por uma métrica numa árvore com distorção esperada O(lg n) -- o ótimo assintótico. Essa estratégia resulta em algoritmos de aproximação com boas razões de aproximação, e em algoritmos com bom fator de competitividade para diversos problemas de otimização online e distribuídos. É apresentada especificamente a aplicação da técnica ao problema do emparelhamento mínimo bipartido online, que ilustra como a aproximação de métricas auxilia na resolução de um problema e os cuidados que devem ser tomados nessa aplicação.; Many optimization problems on graphs, especially metric problems, are easier to solve on trees. Therefore, a strategy for obtaining a good algorithm for certain problems is to obtain a tree that approximates the graph...

Algoritmos para o problema da cobertura por sensores; Algorithms for the sensor cover problem

Barbosa, Rafael da Ponte
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 12/12/2011 PT
Relevância na Pesquisa
76.05%
Neste trabalho estudamos aspectos algorítmicos do Problema da Cobertura por Sensores. Em linhas gerais, este problema a entrada consiste em uma região a ser monitorada por um conjunto de sensores previamente posicionados, cada qual dotado de bateria com duração limitada, e o objetivo é atribuir a cada sensor um tempo de início, de modo que toda a região seja coberta o maior tempo possível. Focamos nosso estudo no caso unidimensional do problema, chamado Problema da Cobertura de Faixa Restrita, no qual a região a ser monitorada é um intervalo (da reta real). Estudamos diversas variantes, de acordo com os subintervalos que os sensores cobrem (se de tamanhos fixos ou variados), e de acordo com a duração das baterias (se uniformes ou não). Estudamos também o caso preemptivo: quando os sensores podem ser ligados mais de uma vez. Para este último caso, projetamos um algoritmo polinomial bem simples. O Problema da Cobertura de Faixa Restrita é NP-difícil no caso não-preemptivo em que os sensores têm bateria de duração variável. Para este caso, em 2009 Gibson e Varadarajan apresentaram um algoritmo polinomial que provaram ser uma 5-aproximação. Provamos que este algoritmo tem fator de aproximação 4, e mostramos que este fator é justo. Apresentamos também formulações lineares inteiras para este caso...

k-árvores de custo mínimo; Minimum cost k-trees

Oshiro, Marcio Takashi Iura
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 11/06/2010 PT
Relevância na Pesquisa
96.17%
Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação.; This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

Uma abordagem orientada a sistemas para otimização de escalonamento de processos em grades computacionais; A system-centric approach for process scheduling optimization in computational grids

Gabriel, Paulo Henrique Ribeiro
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 26/04/2013 PT
Relevância na Pesquisa
96.27%
Um dos maiores desafios envolvidos no projeto de grades computacionais é o escalonamento de processos, o qual consiste no mapeamento de processos sobre os computadores disponíveis, a fim de reduzir o tempo de execução de aplicações ou maximizar a utilização de recursos. A literatura na área de Sistemas Distribuídos trata, geralmente, esses dois objetivos separadamente, dando origem às abordagens de escalonamento orientado a aplicações e orientado a recursos, respectivamente. Mais recentemente, uma nova abordagem, denominada escalonamento orientado a sistemas, tem recebido destaque, buscando otimizar ambos objetivos simultaneamente. Seguindo essas abordagens, algoritmos heurísticos e de aproximação têm sido propostos. Os heurísticos buscam por soluções de maneira eficiente sem, contudo, apresentar garantias quanto à qualidade das soluções obtidas. Em contrapartida, os algoritmos de aproximação provêm tais garantias, contudo são mais difíceis de serem projetados, o que justifica o fato de haver apenas versões simplificadas desses algoritmos para cenários de escalonamento de processos. A falta de algoritmos de aproximação adequados para abordar o problema de escalonamento de processos e a necessidade de soluções que atendam o escalonamento orientado a sistemas motivaram esta tese de doutorado que apresenta a proposta do Min Heap-based Scheduling Algorithm (MHSA)...

Problemas de alocação e precificação de itens; Allocation and pricing problems

Schouery, Rafael Crivellari Saliba
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 14/02/2014 PT
Relevância na Pesquisa
75.99%
Nessa tese consideramos problemas de alocação e precificação de itens, onde temos um conjunto de itens e um conjunto de compradores interessados em tais itens. Nosso objetivo é escolher uma alocação de itens a compradores juntamente com uma precificação para tais itens para maximizar o lucro obtido, considerando o valor máximo que um comprador está disposto a pagar por um determinado item. Em particular, focamos em três problemas: o Problema da Compra Máxima, o Problema da Precificação Livre de Inveja e o Leilão de Anúncios de Segundo Preço. O Problema da Compra Máxima e o Problema da Precificação Livre de Inveja modelam o problema que empresas que vendem produtos ou serviços enfrentam na realidade, onde é necessário escolher corretamente os preços dos produtos ou serviços disponíveis para os clientes para obter um lucro interessante. Já o Leilão de Anúncios de Segundo Preço modela o problema enfrentado por empresas donas de ferramentas de busca que desejam vender espaço para anunciantes nos resultados das buscas dos usuários. Ambas as questões, tanto a precificação de produtos e serviços quanto a alocação de anunciantes em resultados de buscas, são de grande relevância econômica e, portanto...

Algoritmos para o problema da árvore de Steiner com coleta de prêmios; Algorithms for prize-collecting Steiner tree problem

Matsubara, Camila Mari
Fonte: Biblioteca Digitais de Teses e Dissertações da USP Publicador: Biblioteca Digitais de Teses e Dissertações da USP
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 14/12/2012 PT
Relevância na Pesquisa
86.15%
Neste projeto estudamos algoritmos de aproximação para o problema da árvore de Steiner com coleta de prêmios. Trata-se de uma generalização do problema da árvore de Steiner, onde é dado um grafo com custos positivos nas arestas e penalidades positivas nos vértices. O objetivo é encontrar uma subárvore do grafo que minimize a soma dos custos das arestas mais a soma das penalidades dos vértices que não pertencem à subárvore. Em 2009, os autores Archer, Bateni, Hajiaghayi e Karloff obtiveram pela primeira vez um algoritmo com fator de aproximação estritamente menor do que 2. Além de analisarmos este algoritmo, estudamos também a implementação de algoritmos 2-aproximação para o problema da árvore de Steiner e da árvore de Steiner com coleta de prêmios.; In this project we analyze approximation algorithms for the prize-collecting Steiner tree problem. This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices. The goal is to find a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don't belong to the subtree. In 2009, the authors Archer, Bateni, Hajiaghayi e Karloff described...

Partição retangular minima de um retangulo em programação linear inteira

Claudio Nogueira de Menezes
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 20/06/1997 PT
Relevância na Pesquisa
75.86%
Dado um retângulo R e um conjunto finito não vazio P de pontos no interior de R, estudamos o problema de particionar R em retângulos menores tal que nenhum ponto em P está no interior de qualquer retângulo da partição. O objetivo é minimizar a soma dos comprimentos dos segmentos de reta definindo a partição. Este problema é NP-difícil e uma generalização deste tem aplicação em projeto de circuitos VLSI. Neste trabalho implementamos os principais algoritmos de aproximação que têm sido propostos para este problema e propomos dois diferentes modelos de programação linear inteira. No primeiro modelo, onde variáveis são associadas a segmentos de reta, fazemos uma investigação do poliedro associado ao problema. Inequações lineares definindo facets são apresentadas e resultados computacionais para um algoritmo Branch-and-Cut baseado nestas inequações são reportados. O segundo modelo é baseado em uma redução do problema em questão para o problema set partitioning. Um algoritmo Branch-and-Price para este modelo foi implementando e os resultados são comparados com aqueles obtidos pelo algoritmo Branch-and-Cut. Os experimentos computacionais realizados mostraram a viabilidade da resolução exata deste problema através de técnicas de programação linear inteira...

Algoritmos de aproximação para problemas de empacotamento em faixa com restrições de descarregamento; Approximation algorithms for the strip packing problem with unloading constraints

Jefferson Luiz Moisés da Silveira
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 25/03/2011 PT
Relevância na Pesquisa
76.23%
Neste trabalho estudamos problemas de empacotamento com restrições de descarregamento considerados NP-difíceis. Estes problemas possuem aplicações nas áreas de logística e roteamento. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes (complexidade de tempo polinomial) e que geram soluções com garantia de qualidade. Estudamos técnicas para o desenvolvimento de algoritmos aproximados e também alguns algoritmos para problemas de empacotamento online que podem ser utilizados na resolução do problema estudado. Propomos também algumas heurísticas para o problema e, além disto, provamos que duas destas heurísticas possuem garantias de aproximação com fatores constantes. Realizamos testes computacionais com estes algoritmos propostos. Dentre estes, a heurística GRASP foi a que obteve melhores resultados para as instâncias de teste consideradas.; In this work we study some NP-hard packing problems with unloading constraints. These problems have applications in logistics and routing problems. Assuming P ? NP, there are no efficient algorithms to solve these problems. On way to deal with these problems is using approximation algorithms...

Aproximação de funções irregularmente amostradas com bases hierárquicas adaptativas de elementos tensoriais compactos; Sampled irregularly functions approximation with tensorial elements compacts adaptive hierarchical bases

Gilcélia Regiane de Souza
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 11/10/2013 PT
Relevância na Pesquisa
75.99%
Nesta tese, desenvolvemos algoritmos eficientes para a aproximação de funções que tem importantes detalhes de pequena escala confinados em pequenas região do domínio. Assumimos que a função objetivo é amostrada em um número finito de pontos dados, com densidade uniforme ou densidade não uniforme. Neste trabalho optamos por utilizar uma base multinível (ou multiresolução), em que os centros dos elementos em cada nível são um subconjunto de uma grade regular de centros, independentemente dos pontos de amostragem. As bases em questão têm estrutura multiescala semelhante à usada na análise wavelet em d dimensões. No entanto, os seus elementos são funções explícitas definidas pelo produto de d funções univariadas de suporte limitado (tais como pseudo-gaussianas modelada por polinômios truncados ou spline). Descrevemos um algoritmo incremental de aproximação, que procede do nível mais grosseiro para o mais detalhado, sendo que em cada nível são usados apenas os elementos da base localizados nas regiões onde a aproximação é ainda insuficientemente precisa. Em cada nível, usamos um processo iterativo com o método de mínimos quadrados que é projetado para ignorar dados discrepantes e detalhes que só podem ser aproximados em escalas menores.; I this thesis we develop efficient algorithms for the approximation of functions that have important small-scale details confined to small portions of their domain. We assume that the target function is sampled at a finite number of data points...

Representação combinatória e algébrica das permutações na análise do problema de rearranjo de genomas por reversões

Lima, Thaynara Arielly de
Fonte: Universidade de Brasília Publicador: Universidade de Brasília
Tipo: Dissertação
POR
Relevância na Pesquisa
75.99%
Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Matemática, 2010.; Na genômica comparativa soluções algoríıtmicas eficientes para o problema da dist ância de rearranjo de genomas são uma ferramenta importante para o desenvolvimento de software que permite estabelecer relacionamento evolutivo entre organismos, por exemplo para a constr~ção de árvores filogenéticas de organismos. Existem diversas operações sobre palavras que modelam mutações ocorridas nos genes dos seres vivos (e.g. reversões, transposições, troca de blocos, etc.). Restritos à operação de reversão o problema de rearranjo de genomas ´é NP-difícil. Sendo assim, é plausível considerar algoritmos de aproximação. O algoritmo conhecido que melhor aproxima a solução do problema de rearranjo via reversões tem raio de 1.375. No seu artigo seminal, Bafna e Pevzner apresentam soluções O(n2) de raios de aproximação 1.5 para permutações com sinal e 7 4 para permutações sem sinal. Neste trabalho propõ-se um uso cuidadoso e discriminado entre as representações combinatória (palavras e grafos de pontos de quebra) e algébrica (ciclos de permuta ções) das permutações, que contribuirão para analisar com precisão e de maneira adequada diversas características do problema da distância de reversão e das soluções apresentadas por Bafna e Pevzner. _________________________________________________________________________________ ABSTRACT; Efficient algorithmic solutions to the problem of genome rearrangements in comparative genomics are an important tool for the development of software allowing one to estabilish the evolution link between organisms...

Algoritmos de recuperação de fase para sistemas ópticos com modulação DP-QPSK

Ferreira, Hugo Borges
Fonte: Universidade de Brasília Publicador: Universidade de Brasília
Tipo: Dissertação
POR
Relevância na Pesquisa
75.97%
Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnologia, 2011.; O crescimento na demanda por tráfego Ethernet tem motivado o desenvolvimento de novos sistemas de transporte de dados a altas taxas e longas distâncias. Um novo esquema de transmissão óptica aparece como solução, permitindo taxas de transmissão superiores a 100 Gb/s por canal óptico. Esse esquema utiliza a modulação QPSK e a multiplexação de sinais em polarizações ortogonais (dual polarization QPSK - DP-QPSK), então, um receptor coerente se faz necessário. Nesses sistemas aliam-se processamento digital de sinais aos detectores coerentes para a compensaçãao de distorções ocorridas na transmissão e recepção. A recuperação de fase é um tópico relevante no projeto de receptores coerentes e várias técnicas podem ser aplicadas. Analisaram-se três técnicas de recuperação de fase, as clássicas Viterbi & Viterbi (V&V) e algoritmo direcionado a decisão (DD), e uma técnica computacionalmente eficiente, chamada aqui de hardware-efficient. Aliado à recuperação de fase, um algoritmo de recuperação de portadora, responsável por estimar diferen¸cas entre a frequência dos lasers transmissor e receptor, também foi estudado. Nas simulações...

Um framework para processamento paralelo de algoritmos de aumento de resolução de vídeos

Freitas, Pedro Garcia
Fonte: Universidade de Brasília Publicador: Universidade de Brasília
Tipo: Dissertação
POR
Relevância na Pesquisa
76.02%
Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2013.; O aumento dimensional de sinais visuais consiste na alteração do tamanho de uma imagem ou de um vídeo para dimensões espaciais maiores, utilizando técnicas de processa- mento digital de sinais. Geralmente, esse aumento é feito com a utilização de técnicas de interpolação. Contudo, essas técnicas de interpolação produzem distorções nas imagens au- mentadas. Tais distorções ocorrem porque a imagem aumentada possui apenas as amostras da imagem original, de dimensões menores, que são insu cientes para reconstrução exata do sinal, o que gera efeitos de aliasing. Assim sendo, as técnicas de interpolação apenas estimam os coe cientes não-amostrados do sinal, o que muitas vezes produz resultados insatisfatórios para muitas aplicações, necessitando de outras técnicas para reconstituir os coe cientes não-amostrados com maior precisão. Para melhorar a aproximação de uma imagem estimada com relação à imagem origi- nal, existem técnicas que reconstroem os coe cientes não-amostrados. Essas técnicas são chamadas de super-resolução. Elas consistem em aumentar a resolução utilizando...

Desenvolvimento de algoritmos de otimização para métodos sem malha

Rocha, João Nuno Delgado de Aguilar Botelho
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Dissertação de Mestrado
POR
Relevância na Pesquisa
75.93%
Recentemente surgiu um novo tipo de métodos computacionais referenciados como métodos sem malha. Estes métodos têm sido amplamente usados no estudo e na resolução de problemas de engenharia, mais usualmente em problemas que contam com grandes deslocamentos, como a simulação de processos de conformação plástica e em problemas com elevadas taxas de deformação, com impacto e fratura estrutural. Devido ao caráter não interpolatório das funções de aproximação dos métodos sem malha, a definição das condições de fronteira é um dos maiores problemas destes métodos. Por outro lado, o facto de os nós poderem ser distribuídos aleatoriamente pelo domínio físico do problema em análise, sem ser necessário o recurso implícito a conetividades, torna os métodos sem malha bastante apelativos para problemas de contacto e impacto com fratura e desagregação de material. Este trabalho foca-se no desenvolvimento dos métodos sem malha, assim como na descrição e análise comparativa dos métodos sem malha mais relevantes nos dias de hoje e nos algoritmos e técnicas computacionais capazes de tornar estes métodos mais eficientes. São ainda propostos alguns algoritmos que resultam num substancial aumento de performance do método EFG (Element Free Galerkin) assim como uma implementação do método NEM (Natural Element Method) com base no algoritmo de Fortune e em funções de forma não Sibsonianas. Por fim conclui-se que o aumento de performance dos métodos sem malha pode ser conseguido recorrendo a técnicas e metodologias usadas com frequência nas ciências computacionais...

Aplicações e algoritmos de segurança rodoviária com o uso de sistemas de GPS e de comunicações WAVE

Cardoso, Fábio
Fonte: Instituto Politécnico de Lisboa Publicador: Instituto Politécnico de Lisboa
Tipo: Dissertação de Mestrado
Publicado em /11/2013 POR
Relevância na Pesquisa
76%
Os acidentes rodoviários são um problema de grande importância para toda a humanidade. O objetivo desta tese é desenvolver um sistema, através de comunicação WAVE, vehicle-tovehicle, capaz de alertar os automobilistas de risco de colisões. O sistema desenvolvido utiliza os dados recebidos por um sistema de GPS para o processamento dos algoritmos de segurança, estudados no estado da arte e desenvolvidos nesta tese. Para um cenário de aproximação súbita foram estudados os algoritmos da Mazda, Honda, PATH, NHTSA e IEEE, para um cenário de cruzamento/entroncamento os algoritmos da IET, Ford, Safety zones e Taiwan. Para o cenário de curva foi desenvolvido o algoritmo de Cobra. Percebe-se a possibilidade de evitar um acidente com a obtenção de aviso dum cenário de risco de colisão, no interior duma localidade, cerca de 15 m antes do cruzamento, distância suficiente para as devidas precauções, em auto-estrada, circulando a 120 km/h, 60 m antes do veículo que circula a 40 km/h à frente, numa curva com 33 m de raio, recebe-se um aviso de excesso de velocidade aproximando-se excedendo os 31 km/h. Resultados plausíveis através da prática no terreno.; Road accidents are problems of great importance to all humanity. The objective of this thesis is to develop a system...

Algoritmos para o problema do caixeiro viajante multiobjectivo

Paquete, Luís
Fonte: Universidade do Algarve. Faculdade de Economia Publicador: Universidade do Algarve. Faculdade de Economia
Tipo: Parte de Livro
Publicado em 26/08/2005 POR
Relevância na Pesquisa
76.11%
O Problema do Caixeiro Viajante Multiobjectivo é um problema de optimização combinatório bastante simples de ser formalizado mas que surge em muitas aplicações de transporte e logística. Contudo, a resolução deste problema é um grande desafio em temos computacionais, não só porque herda a dificuldade inerente à versão com um só objectivo mas também devido ao número excessivo de soluções óptimas. Deste modo, alternativas aos algoritmos exactos são necessárias para aplicações reais onde é exigido um tempo rápido de resposta. Este artigo revê algumas destas alternativas que retornam uma aproximação às soluções óptimas em tempo considerado razoável, em particular,algoritmos de aproximação e métodos de pesquisa local estocástica.

Estratégias de partições mistas para o problema da patrulha

Josué da Silva Filho, Luiz; Rose Benning Salgado, Liliane (Orientador)
Fonte: Universidade Federal de Pernambuco Publicador: Universidade Federal de Pernambuco
Tipo: Outros
PT_BR
Relevância na Pesquisa
86.05%
Patrulhar é o ato de andar ou viajar por uma área, em intervalos regulares, para protegê-la ou supervisioná-la. Informalmente, uma boa estratégia de patrulhamento é aquela que minimiza o tempo gasto entre duas visitas à mesma localização. Além de sua aplicação prática, o Problema da Patrulha Multiagentes (PMA) é um problema didático, pois compreende desde problemas computacionais simples, como a determinação do menor caminho entre dois pontos em um território até problemas mais complexos inerentes ao estudo de Sistemas Multiagentes (SMA). Para o estudo de SMAs, o PMA mostra-se rico, pois envolve várias características relevantes de um SMA como coordenação, comunicação, organização, negociação, conceitos de sociedades de agentes, entre outros. Em 2002, um trabalho pioneiro, realizado pelo grupo de Inteligência Artificial do Centro de Informática da Universidade Federal de Pernambuco, propôs as primeiras arquiteturas para o PMA e as avaliou empiricamente. Trabalhos posteriores propuseram soluções mais sofisticadas, como a utilização de negociação e aprendizagem, elaborando e avaliando uma maior quantidade de arquiteturas. Apesar dos trabalhos empíricos realizados, uma abordagem teórica do PMA se fazia necessária para a evolução na pesquisa do problema. Em cooperação com a Universidade Paris 6 na França...

Um método social-evolucionário para geração de rankings que apoiem a recomendação de eventos; A social-evolutionary method for generating rankings that support the event recommendation

Pascoal, Luiz Mário Lustosa
Fonte: Universidade Federal de Goiás; Brasil; UFG; Programa de Pós-graduação em Ciência da Computação (INF); Instituto de Informática - INF (RG) Publicador: Universidade Federal de Goiás; Brasil; UFG; Programa de Pós-graduação em Ciência da Computação (INF); Instituto de Informática - INF (RG)
Tipo: Dissertação Formato: application/octet-stream; application/pdf
POR
Relevância na Pesquisa
75.97%
With the development of web 2.0, social networks have achieved great space on the internet, with that many users provide information and interests about themselves. There are expert systems that make use of the user’s interests to recommend different products, these systems are known as Recommender Systems. One of the main techniques of a Recommender Systems is the Collaborative Filtering (User-based) which recommends products to users based on what other similar people liked in the past. Therefore, this work presents model approximation of functions that generates rankings, that through a Genetic Algorithm, is able to learn an approximation function composed by different social variables, customized for each Facebook user. The learned function must be able to reproduce a ranking of people (friends) originally created with user’s information, that apply some influence in the user’s decision. As a case study, this work discusses the context of events through information regarding the frequency of participation of some users at several distinct events. Two different approaches on learning and applying the approximation function have been developed. The first approach provides a general model that learns a function in advance and then applies it in a set of test data and the second approach presents an specialist model that learns a specific function for each test scenario. Two proposals for evaluating the ordering created by the learned function...

Algoritmos de aproximação estocástica com valor do passo adaptativo

Cruz, João Pedro Antunes Ferreira da
Fonte: Universidade de Aveiro Publicador: Universidade de Aveiro
Tipo: Tese de Doutorado
POR
Relevância na Pesquisa
86.24%
Consideram-se os algoritmos iterativos de aproximação estocástica (AE) do zero de uma função dada quando o valor da função é perturbado aleatoriamente. A teoria da AE está bem desenvolvida para o caso em que o valor do passo do algoritmo é determinístico, dependendo apenas do número da iteração do algoritmo; em particular, foram elaborados algoritmos assimptoticamente optimais. No entanto, em muitos problemas práticos abordados de forma heurística (em particular redes neuronais), verifica-se que são mais efectivos, num periodo transitório, os algoritmos cujo valor do passo é aleatório, sendo determinado através dos parâmetros correntes do algoritmo. A tese concentra-se nos algoritmos onde o valor do passo aumenta caso os incrementos de aproximações consecutivas mantenham o sentido (indicando que o algoritmo está na "zona determinística"), e diminui no caso contrário (estando o algoritmo na "zona estocástica"). No algoritmo de Kesten, o passo mantém-se caso hajam dois incrementos com o mesmo sinal, e em caso oposto, o passo é decrementado. Na tese, o algoritmo é generalizado podendo o passo aumentar caso duas iterações ocorram no mesmo sentido. É demonstrada a convergência para o zero com probabilidade 1 para o caso de funções unidimensionais e multidimensionais com um único zero. É também demonstrada a normalidade assimptótica das estimativas. Podem encontrar-se na literatura...