Página 1 dos resultados de 53 itens digitais encontrados em 0.013 segundos

‣ Problemas de fluxos em redes, com objectivos múltiplos

Eusébio, Augusto Manuel José
Fonte: Universidade de Coimbra Publicador: Universidade de Coimbra
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
28.151248%
O trabalho apresentado nesta Tese centra-se no domínio da optimização multi- -objectivo, mais concretamente dos problemas de fluxos em redes com dois ou mais objectivos, desenvolvendo-se um conjunto de algoritmos originais, para a determina ção de soluções eficientes e não-dominadas em problemas de fluxos em redes. Começámos por fazer uma revisão da bibliografia na área dos problemas de fluxos em redes, onde descrevemos os algoritmos exactos e os algoritmos aproximados, para problemas de fluxos em redes multi-objectivo com variáveis contínuas e com variáveis inteiras. Nesta revisão apercebemo-nos de que a maioria dos trabalhos existentes para este tipo de problemas se debruça apenas sobre o caso de problemas com dois objectivos. Além disso, percebemos também que existem nestes casos várias dificuldades. Partimos em busca de uma melhor compreensão deste tipo de problemas. Descobrimos também que um dos principais métodos utilizados na bibliografia, para calcular as soluções não-dominadas suportadas, afinal não calculava todas as soluções suportadas. Apresentámos exemplos que provam este facto. Propusemos um conjunto de novos algoritmos: um algoritmo do tipo primal-dual para o cálculo das soluções não-dominadas extremas no caso do problema de fluxos em redes bi-objectivo; um algoritmo baseado nos ciclos de custo zero...

‣ Filtros para a busca e extração de padrões aproximados em cadeias biológicas; Filter Algorithms for Approximate Patterns Matching and Extraction from Biological Strings

Soares Neto, Domingos
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 10/09/2008 Português
Relevância na Pesquisa
38.288884%
Esta dissertação de mestrado aborda formulações computacionais e algoritmos para a busca e extração de padrões em cadeias biológicas. Em particular, o presente texto concentra-se nos dois problemas a seguir, considerando-os sob as distâncias de Hamming e Levenshtein: a) como determinar os locais nos quais um dado padrão ocorre de modo aproximado em uma cadeia fornecida; b) como extrair padrões que ocorram de modo aproximado em um número significativo de cadeias de um conjunto fornecido. O primeiro problema, para o qual já existem diversos algoritmos polinomiais, tem recebido muita atenção desde a década de 60, e ganhou novos ares com o advento da biologia computacional, nos idos dos anos 80, e com a popularização da Internet e seus mecanismos de busca: ambos os fenômenos trouxeram novos obstáculos a serem superados, em razão do grande volume de dados e das bastante justas restrições de tempo inerentes a essas aplicações. O segundo problema, de surgimento um pouco mais recente, é intrinsicamente desafiador, em razão de sua complexidade computacional, do tamanho das entradas tratadas nas aplicações mais comuns e de sua dificuldade de aproximação. Também é de chamar a atenção o seu grande potencial de aplicação. Neste trabalho são apresentadas formulações adequadas dos problemas abordados...

‣ Algoritmos de aproximação para o problema de classificação metrica

Evandro Cesar Bracht
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 04/06/2004 Português
Relevância na Pesquisa
38.673464%
Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional; In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects...

‣ Um algoritmo exato para o problema de empacotamento bidimensional em faixas; A exact algorithm to two-dimensional level strip packing

Carlos Eduardo de Andrade
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 26/09/2006 Português
Relevância na Pesquisa
37.755547%
Problemas de corte e empacotamento aparecem freqüentemente na indústria e comércio, e sua solução de forma otimizada pode trazer grandes ganhos em diversos setores.Um problema muito comum, notadamente no setor têxtil e do papel, é o corte de um rolo ou faixa de um determinado material para obtenção de itens menores, onde temos por objetivo utilizar a menor extensão do rolo/faixa possível. Este problema, conhecido como Problema de Empacotamento Bidimensional em Faixas (PEBF), é tido como um problema de otimização combinatória de difícil resolução. Neste trabalho, apresentamos um algoritmo exato para o PEBF restrito a cortes de dois estágios (PEBF2). O algoritmo usa a técnica de branch-and-price, que utiliza, por sua vez, heurísticas baseadas em algoritmos aproximados para a obtenção de limitantes superiores. O algoritmo se mostrou eficaz na obtenção de soluções para instâncias de pequeno e médio porte; Cutting and packing problems are common problems that occur in many industry and business process. Their optimized resolution leads to great profits in several sectors. A common problem, that occur in textil and paper industries, is to cut a strip of some material to obtain several small items, using the minimum length of material. This problem...

‣ Problemas de roteamento de veiculos via metaheuristica tabu

Vitoria M.M. Pureza
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 20/08/1990 Português
Relevância na Pesquisa
28.277764%
O Problema de Roteamento de Veículos (PRV) consiste basicamente em definir rotas eficientes para uma frota de veículos que deve entregar quantidades de bens a um conjunto de clientes. Vários métodos têm sido propostos para tal tarefa, mas devido ao esforço computacional requerido, problemas de maior porte (50 clientes ou mais) são resolvidos por algoritmos aproximados. Dentre estes algoritmos aproximados, abordamos os métodos de melhoria de rotas. Estes métodos são caracterizados pela geração de uma solução inicial factível, seguida da aplicação de mecanismos de busca que alteram a solução inicial. Estes mecanismos promovem essencialmente a melhoria da função objetivo em direção a um mínimo local. Neste ponto, dada a falta de movimentos de melhoria, o algoritmo pára. Apesar do desempenho excelente deste métod6S, observa-se uma limitação fundamental. Sendo o PRV um problema combinatório e, portanto, não convexo, o ótimo local obtido pode não ser o ótimo global. Conseqüentemente, a qualidade da solução final depende drasticamente da solução de partida. Várias técnicas foram elaboradas com vistas à superação da otimalidade local. A maioria delas recomeça o processo de busca a partir de soluções iniciais diferentes ou atrasa a obtenção do ponto ótimo. Outra maneira de lidar com tais limitações é através da aplicação da estratégia de Busca Tabu. Ao invés de evitar ótimos locais...

‣ Algoritmos para problemas de empacotamento; Algorithms for packing problems

Eduardo Candido Xavier
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 05/12/2006 Português
Relevância na Pesquisa
48.209873%
Neste trabalho estudamos diversos problemas de empacotamento considerados NP-difíceis. Assumindo a hipótese de que P ? NP, sabemos que não existem algoritmos eficientes (complexidade de tempo polinomial) exatos para resolver tais problemas. Uma das abordagens consideradas para tratar tais problemas é a de algoritmos de aproximação, que são algoritmos eficientes e que geram soluções com garantia de qualidade. Neste trabalho apresentamos alguns algoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes e geram soluções de muito boa qualidade; In this work we study several packing problems that are NP-hard. If we consider that P ? NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algorithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Another way to deal with NP-hard problems is to develop heuristics. We also consider column generation based heuristics for packing problems. In this case...

‣ 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 Português
Relevância na Pesquisa
48.28888%
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...

‣ Algoritmos para problemas de escalonamento em grades; Algorithms for scheduling problems in grid

Robson Roberto Souza Peixoto
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 15/04/2011 Português
Relevância na Pesquisa
48.838984%
Nesta dissertação estudamos algoritmos para resolver problemas de escalonamento de tarefas em grades computacionais. Dado um conjunto de tarefas submetidas a uma grade computacional, deve-se definir em quais recursos essas tarefas serão executadas. Algoritmos de escalonamento são empregados com o objetivo de minimizar o tempo necessário para executar todas as tarefas (makespan) que foram submetidas. Nosso foco é estudar os atuais algoritmos de escalonamento usados em grades computacionais e comparar estes algoritmos. Nesta dissertação apresentamos algoritmos onlines, aproximados e heurísticas para o problema. Como resultados novos, provamos fatores de aproximação para o algoritmo RR quando utilizado para resolver os problemas R; sit|Tj|Cmax, R; sit|Tj|TPCC, R; sit|Tj = L| Cmax e R; sit|Tj = L|TPCC é justo. Por fim, definimos uma interface que adiciona replicação de tarefas a qualquer algoritmo de escalonamento, onde nós mostramos a aproximação desta interface, e apresentamos uma comparação via simulação dos algoritmos sem e com replicação. Nossas simulações mostram que, com a utilização de replicação, houve a redução no makespan de até 80% para o algoritmo Min-min. Nas nossas análises também fazemos uso da métrica RTPCC que calcula exatamente a quantidade de instruções que foram usadas para executar todas as tarefas.; In this dissertation...

‣ Uma ferramenta de auditoria para algoritmos de rearranjo de genomas; An audit tool for genome rearrangement algorithms

Gustavo Rodrigues Galvão
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 20/12/2012 Português
Relevância na Pesquisa
49.11253%
Ao longo da evolução, mutações globais podem alterar a ordem dos genes de um genoma. Tais mutações são chamadas de eventos de rearranjo. Em Rearranjo de Genomas, estimamos a distância evolutiva entre dois genomas calculando-se a distância de rearranjo entre eles, que é o tamanho da menor sequência de eventos de rearranjo que transforma um genoma no outro. Representando genomas como permutações, nas quais os genes aparecem como elemento, à distância de rearranjo pode ser obtido resolvendo-se o problema combinatório de ordenar uma permutação utilizando o menor número de eventos de rearranjo. Este problema, que é referido como Problema da Ordenação por Rearranjo, varia de acordo com os tipos de eventos de rearranjo considerados. Nesta dissertação, focamos nosso estudo em dois tipos de eventos: reversões e transposições. Variações do Problema da Ordenação por Rearranjo que consideram esses eventos têm se mostrado difíceis de ser resolvida otimamente, por isso a maior parte dos algoritmos propostos - os quais denominamos genericamente por algoritmos de rearranjo de genomas - são aproximados e é esperado que os próximos avanços ocorram nesse sentido. Em razão disso, desenvolvemos uma ferramenta que avalia as respostas desses algoritmos. Para ilustrar sua aplicação...

‣ Algoritmos para problemas de empacotamento e roteamento; Algorithms for packing and routing problems

Jefferson Luiz Moisés da Silveira
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 02/10/2013 Português
Relevância na Pesquisa
58.77641%
Neste trabalho estamos interessados em problemas de empacotamento e roteamento. Assumindo a hipótese de que P ≠ NP, sabemos que não existem algoritmos eficientes para resolver tais problemas. Além de algoritmos exatos, duas das abordagens para resolver tais problemas são Algoritmos Aproximados e Heurísticas. Nesta tese mostramos algoritmos baseados nestas três abordagens para ambos os problemas, de empacotamento e roteamento. Os dois primeiros problemas atacados foram generalizações de problemas clássicos de empacotamento: O problema da mochila bidimensional e o problema de empacotamento em faixas. Estes foram generalizados adicionando restrições na forma de carregamento e descarregamento dos itens no recipiente (restrições estas, que aparecem no contexto de problemas de roteamento). O terceiro problema é uma combinação de problemas de empacotamento e roteamento. Neste caso, atacamos uma generalização do clássico Pickup and Delivery Problem. Propomos os primeiros resultados de aproximação para algumas versões dos problemas de empacotamento supracitados. Além disto, apresentamos algumas abordagens práticas para o terceiro problema. As heurísticas foram avaliadas através de experimentos computacionais comparando os seus resultados com algoritmos exatos.; In this work we are interested in packing and routing problems. Assuming P ≠ NP...

‣ O problema da árvore geradora com muitas folhas; The maximum leaf spanning tree problem

Márcio Félix Reis
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 08/05/2014 Português
Relevância na Pesquisa
48.592295%
Neste trabalho estudamos o problema da árvore geradora com muitas folhas (PAGMF). Este problema pode ser usado como abstração para diversos problemas práticos e sabe-se que é NP-difícil. Estudamos, implementamos e executamos testes para algoritmos aproximados e exatos para o PAGMF e para um caso particular que considera apenas grafos cúbicos. O principal objetivo do trabalho foi verificar o comportamento prático dos algoritmos estudados. Para as instâncias testadas, em geral, o algoritmo guloso apresentou melhores resultados para o PAGMF e o algoritmo 2-aproximado teve os melhores resultados para os grafos cúbicos.; In this work we study the maximum leaf spanning tree problem (MLSTP). This problem can be used as an abstraction for many practical problems and is known to be NP-hard. We studied, implemented and executed tests for approximate and exact algorithms for the MLSTP and for a particular case that considers only cubic graphs. The main objective of this study was to investigate the practical behavior of the algorithms studied. For the tested instances, in general, the greedy algorithm showed better results for the MLSTP and the 2-approximate algorithm had the best results for cubic graphs.

‣ Algoritmos aproximados para cobertura de objetos geométricos por discos; Approximation algorithms for coverage of geometric objects by disks

Anderson Toshiyuki Sasaki
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 24/02/2014 Português
Relevância na Pesquisa
58.947007%
No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ≠ NP,, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC - Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano...

‣ Approximation algorithms for facility location problems and other supply chain problems; Algoritmos de aproximação para problemas de alocação de instalações e outros problemas de cadeia de fornecimento

Lehilton Lelis Chaves Pedrosa
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Publicado em 04/07/2014 Português
Relevância na Pesquisa
37.755547%
O resumo poderá ser visualizado no texto completo da tese digital.; The abstract is available with the full electronic document.

‣ Escalonamento de tarefas com localidade de dados em grids; Task scheduling with data locality in grids

Marcelo Galvão Póvoa
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado Formato: application/pdf
Publicado em 04/02/2015 Português
Relevância na Pesquisa
48.592295%
Sistemas computacionais conhecidos como Data Grids fornecem uma infraestrutura computacional distribuída para processamento e armazenamento de dados, com várias aplicações envolvendo computação em larga escala. Devido ao uso de um grande volume de dados, é necessário não apenas um escalonamento eficiente de tarefas, mas também uma distribuição inteligente de réplicas dos dados para se atingir o melhor desempenho. Esses dois problemas já foram extensivamente estudados de forma independente na literatura, mas estamos concentrados em um formulação integrada em um problema estático, de forma a otimizar uma única função objetivo. Primeiramente, mostramos que este problema não pode admitir um algoritmo aproximado. Porém, considerando uma versão restrita do problema, apresentamos um algoritmo aproximado original com fator de aproximação constante. Também fazemos um estudo de algoritmos aproximados para problemas relacionados disponíveis na literatura. Sob um aspecto mais prático, introduzimos duas heurísticas originais para o problema. A primeira é baseada no agrupamento de máquinas próximas em clusters, enquanto a segunda procura identificar grupos de dados frequentemente acessados em conjunto. Comparamos esses algoritmos com duas abordagens adaptadas da literatura...

‣ Implementação e análise do problema caixeiro viajante usando uma nova abordagem através dos algoritmos genético e simulated annealing

Ramos, José Márcio Benite
Fonte: Florianópolis, SC Publicador: Florianópolis, SC
Tipo: Dissertação de Mestrado Formato: ii, 218 f.| il., tabs., grafs.
Português
Relevância na Pesquisa
37.950256%
Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação.; Atualmente observa-se uma forte tendência em se utilizar métodos aproximados na resolução de problemas de otimização combinatorial. Esses métodos, que muitas vezes vêm em substituição a métodos exatos, nem sempre garantem uma solução ótima para um problema, porém, normalmente são capazes de oferecer solução aproximada de boa qualidade, em um tempo de processamento aceitável. Neste trabalho é apresentada e investigada uma nova proposta de um método de aproximação baseado na combinação dos algoritmos Genético (AG) e Simulated Annealing (SA). Na observação do seu comportamento foi utilizado o notório problema de otimização combinatorial, de complexidade NP-completo, conhecido como o Problema do Caixeiro Viajante (PCV).

‣ Roteamento de multi-fluxos em redes de filas genéricas

Morabito,Reinaldo; de Souza,Maurício C.
Fonte: Sociedade Brasileira de Pesquisa Operacional Publicador: Sociedade Brasileira de Pesquisa Operacional
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/12/2010 Português
Relevância na Pesquisa
28.179585%
Problemas de multi-fluxo de commodities com custos não lineares e convexos surgem freqüentemente na alocação de tráfego em redes de comunicação, em função das medidas de desempenho serem baseadas principalmente em atrasos médios de transmissão devido à congestão. A rede física forma uma rede de filas aberta onde as commodities devem ser simultaneamente roteirizadas desde suas origens até seus destinos. Métodos exatos de avaliação de desempenho estão disponíveis quando os processos de chegada e serviço na rede são considerados como processos de Poisson. Nestes casos, a rede pode ser decomposta e cada arco da rede pode ser analisado separadamente como um sistema de fila M/M/1. Porém, em muitos outros casos estas hipóteses de processos de Poisson não são verificadas nas situações práticas. Métodos aproximados de decomposição têm sido desenvolvidos para avaliação do desempenho de redes de filas com distribuições de probabilidade genéricas, dado que, para estas redes, em geral não existem métodos exatos ou eles são muito difíceis de serem computados. Neste trabalho propomos um algoritmo que combina métodos de roteamento de fluxos e métodos aproximados de decomposição para tratar problemas de multi-fluxo de commodities em redes de filas abertas genéricas.

‣ Aproximação espectral e construção de wavelets com aplicações em eletrogastrografia

José de Sobral Cintra, Renato; Magalhães de Oliveira, Helio (Orientador)
Fonte: Universidade Federal de Pernambuco Publicador: Universidade Federal de Pernambuco
Tipo: Outros
Português
Relevância na Pesquisa
38.277764%
Análise de Sinais é uma das partes mais importantes da área de Processamento de Sinais. Esta tese encontra-se dividida em três partes, cada uma abordando um tópico de análise de sinais. Foram endereçadas as seguintes subáreas: (i) métodos aproximados para avaliação espectral; (ii) construção de wavelets e (iii) análise de sinais biomédicos. O problema da estimação espectral sujeita à minimização da complexidade computacional foi abordado por meios de métodos de aproximação. Dois métodos foram utilizados para propor algoritmos eficientes para a transformada discreta de Hartley. O primeiro método introduzido consiste da transformada de Hartley arredondada, um procedimento que utiliza a função de arredondamento para gerar uma matriz de transformação com complexidade multiplicativa nula. A segunda abordagem contempla a proposição da transformada aritmética de Hartley. É demonstrado o papel da interpolação como elemento decisivo na teoria das transformadas aritméticas. Esquemas de interpolação para as transformadas de Hartley, Fourier cosseno e Fourier seno são introduzidos. O foco foi então dirigido para a construção de novas wavelets. Dois procedimentos foram examinados: (i) definição de novas wavelets a partir de equações diferenciais e (ii) construção de wavelets ótimas associadas a uma dada classe de sinais. Da primeira abordagem...

‣ Propagaci??n aproximada de intervalos de probabilidad en grafos de dependencias

Cano Utrera, Andr??s
Fonte: Universidad de Granada Publicador: Universidad de Granada
Tipo: Tese de Doutorado
Português
Relevância na Pesquisa
28.151248%
Las redes bayesianas han sido usadas muy frecuentemente para la construcci??n de sistemas expertos bayesianos. Estos sistemas expertos trabajan con valores de probabilidad precisos. Para un experto resulta muy dif??cil el dar una gran cantidad de probabilidades precisas a la hora de construir el sistema experto. Debido a ello en esta tesis se propone el uso de intervalos de probabilidad para representar la incertidumbre. Existen algoritmos exactos de propagaci??n de intervalos de probabilidad sobre redes que transforman los intervalos en conjuntos convexos de probabilidad para poder obtener resultados finales correctos. Estos algoritmos son bastante complejos, y en la pr??ctica s??lo son capaces de resolver problemas muy simples. Por tanto, en esta tesis se han constru??do algoritmos aproximados de propagaci??n en grafos de dependencias, en los que las distribuciones vienen dadas por intervalos de probabilidad. Los algoritmos constru??dos han utilizado t??cnicas de optimizaci??n combinatoria tales como el enfriamiento simulado y los algoritmos gen??ticos. Tambi??n hemos utilizado los ??rboles de probabilidad para representar y operar con los distintos potenciales haciendo la propagaci??n a??n m??s eficiente y permitiendo adaptarnos a la capacidad de memoria de nuestro ordenador. Los ??rboles de probabilidad han permitido adaptarnos a la capacidad de memoria de nuestro ordenador a la hora de realizar los c??lculos.

‣ Diseño e implementación de algoritmos aproximados de clustering balanceado en PSO

Lai, Chun-Hau
Fonte: Universidad de Chile Publicador: Universidad de Chile
Tipo: Tesis
Português
Relevância na Pesquisa
58.838984%
Magíster en Ciencias, Mención Computación; Este trabajo de tesis está dedicado al diseño e implementación de algoritmos aproximados que permiten explorar las mejores soluciones para el problema de Clustering Balanceado, el cual consiste en dividir un conjunto de n puntos en k clusters tal que cada cluster tenga como m ́ınimo ⌊ n ⌋ puntos, k y éstos deben estar lo más cercano posible al centroide de cada cluster. Estudiamos los algoritmos existentes para este problema y nuestro análisis muestra que éstos podrían fallar en entregar un resultado óptimo por la ausencia de la evaluación de los resultados en cada iteración del algoritmo. Entonces, recurrimos al concepto de Particles Swarms, que fue introducido inicialmente para simular el comportamiento social humano y que permite explorar todas las posibles soluciones de manera que se aproximen a la óptima rápidamente. Proponemos cuatro algoritmos basado en Particle Swarm Optimization (PSO): PSO-Hu ́ngaro, PSO-Gale-Shapley, PSO-Aborci ́on-Punto-Cercano y PSO-Convex-Hull, que aprovechan la característica de la generación aleatoria de los centroides por el algoritmo PSO, para asignar los puntos a estos centroides, logrando una solución más aproximada a la óptima. Evaluamos estos cuatro algoritmos con conjuntos de datos distribuidos en forma uniforme y no uniforme. Se encontró que para los conjuntos de datos distribuidos no uniformemente...

‣ ALGORITMO PARA EL APRENDIZAJE DE REGLAS DE CLASIFICACION BASADO EN LA TEORÍA DE LOS CONJUNTOS APROXIMADOS EXTENDIDA

Filiberto,Yaima; Bello,Rafael; Caballero,Yailé; Frías,Mabel
Fonte: DYNA Publicador: DYNA
Tipo: Artigo de Revista Científica Formato: text/html
Publicado em 01/10/2011 Português
Relevância na Pesquisa
38.179585%
Los conjuntos aproximados han demostrado ser efectivos para desarrollar técnicas de aprendizaje automático, entre ellos métodos para el descubrimiento de reglas de clasificación. En este trabajo se presenta un algoritmo para generar reglas de clasificación basado en relaciones de similaridad, lo que permite que sea aplicable en casos donde los rasgos tienen dominio discreto o continuo. Los resultados experimentales muestran un desempeño satisfactorio en comparación con otros algoritmos conocidos como C4.5 y MODLEM