Página 1 dos resultados de 55073 itens digitais encontrados em 0.039 segundos
Combinação afim de algoritmos adaptativos.; Affine combination of adaptive algorithms.
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 13/04/2009
PT
Relevância na Pesquisa
36.4%
#Adaptive eletrical filters#Algorithms (combination)#Algoritmos (combinação)#Análise de algoritmos#Analysis of algorithms#Filtros elétricos adaptativos
A combinação de algoritmos tem despertado interesse para melhorar o desempenho de filtros adaptativos. Esse método consiste em combinar linearmente as saídas de dois filtros operando em paralelo com passos de adaptação diferentes para se obter um filtro com conver- gência rápida e um erro quadrático médio em excesso (EMSE - excess mean squared error) reduzido. Nesse contexto, foi proposta a combinação afim de dois algoritmos LMS (least-mean square), cujo parâmetro de mistura não fica restrito ao intervalo [0, 1] e por isso é considerada como uma generalização da combinação convexa. Neste trabalho, a combinação afim de dois algoritmos LMS é estendida para os algoritmos supervisionados NLMS (normalized LMS) e RLS (recursive least squares) e também para equalização autodidata, usando o CMA (constant modulus algorithm). Foi feita uma análise em regime da combinação afim desses algoritmos de forma unificada, considerando entrada branca ou colorida e ambientes estacionários ou não- estacionários. Através dessa análise, verificou-se que a combinação afim de dois algoritmos da mesma família pode apresentar uma redução de EMSE de até 3 dB em relação ao EMSE de seus filtros componentes e conseqüentemente ao EMSE da combinação convexa. Para garantir que a estimativa combinada seja pelo menos tão boa quanto a do melhor filtro componente...
Link permanente para citações:
Desenvolvimento de modelos e algoritmos sequenciais e paralelos para o planejamento da expansão de sistemas de transmissão de energia elétrica; Development of mathematical models, sequential and parallel algorithms for transmission expansion planning
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 16/03/2012
PT
Relevância na Pesquisa
36.4%
#Algoritmos multiobjetivos#Evolutionary algorithms#Metaheurísticas#Metaheuristics#Multiple generation dispatch scenarios#Múltiplos cenários de geração#Optimization#Otimização#Parallel programming#Planejamento de sistemas de transmissão#Programação paralela
O principal objetivo deste estudo é propor uma nova metodologia para lidar com o problema de Planejamento da Expansão de Redes de Transmissão de Energia Elétrica com Múltiplos Cenários de Geração (PERTEEG). Com a metodologia proposta neste trabalho almeja-se construir planos de expansão de redes de transmissão de energia elétrica que sejam capazes de, no menor custo de investimento possível, satisfazer às novas exigências dos sistemas elétricos modernos, tais como construção de redes de transmissão livres de congestionamento e robustas à incerteza em relação aos cenários de geração futuros. Através de estudos realizados na literatura do problema, verificou-se que novos modelos e metodologias de abordagem do PERTEEG se fazem necessários. Ao se modelar o PERTEEG visando construir redes de transmissão que contornem as incertezas em relação aos cenários de geração futuros e concomitantemente minimizar o custo de investimento para a expansão do sistema, o planejador se depara com um problema de otimização multiobjetivo. Existem na literatura da pesquisa operacional diversos algoritmos que visam lidar com problemas multiobjetivos. Nesta tese, foram aplicados dois desses algoritmos: Nondominated Sorting Genetic Algorithms-II (NSGA-II) e SPEA2: Strength Pareto Evolutionary Algorithm (SPEA2). Em primeira análise...
Link permanente para citações:
Algoritmos evolutivos para modelos de mistura de gaussianas em problemas com e sem restrições; Evolutionary algorithms for gausian mixture models with and without constraints
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 09/12/2014
PT
Relevância na Pesquisa
36.41%
#Agrupamento de dados#Algoritmos evolutivos#Aprendizado de máquina#Evolutionary algorithms#Machine learning#Semi-supervised clustering
Nesta tese, são estudados algoritmos para agrupamento de dados, com particular ênfase em Agrupamento de Dados com Restrições, no qual, além dos objetos a serem agrupados, são fornecidos pelo usuário algumas informações sobre o agrupamento desejado. Como fundamentação para o agrupamento, são considerados os modelos de mistura finitos, em especial, com componentes gaussianos, usualmente chamados de modelos de mistura de gaussianas. Dentre os principais problemas que os algoritmos desenvolvidos nesta tese de doutorado buscam tratar destacam-se: (i) estimar parâmetros de modelo de mistura de gaussianas; (ii) como incorporar, de forma eficiente, restrições no processo de aprendizado de forma que tanto os dados quanto as restrições possam ser adicionadas de forma online; (iii) estimar, via restrições derivadas de conceitos pré-determinados sobre os objetos (usualmente chamados de classes), o número de grupos destes conceitos. Como ferramenta para auxiliar no desenvolvimento de soluções para tais problemas, foram utilizados algoritmos evolutivos que operam com mais de uma solução simultaneamente, além de utilizarem informações de soluções anteriores para guiar o processo de busca. Especificamente, foi desenvolvido um algoritmo evolutivo baseado na divisão e união de componentes para a estimação dos parâmetros de um modelo de mistura de gaussianas. Este algoritmo foi comparado com o algoritmo do mesmo gênero considerado estado-da-arte na literatura...
Link permanente para citações:
Análise formal da complexidade de algoritmos genéticos; Formal analysis of genetic algorithms complexity
Fonte: Universidade Federal do Rio Grande do Sul
Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Dissertação
Formato: application/pdf
POR
Relevância na Pesquisa
36.43%
O objetivo do trabalho é estudar a viabilidade de tratar problemas de otimização, considerados intratáveis, através de Algoritmos Genéticos, desenvolvendo critérios para a avaliação qualitativa de um Algoritmo Genético. Dentro deste tema, abordam-se estudos sobre complexidade, classes de problemas, análise e desenvolvimento de algoritmos e Algoritmos Genéticos, este ultimo sendo objeto central do estudo. Como produto do estudo deste tema, é proposto um método de desenvolvimento de Algoritmos Genéticos, utilizando todo o estudo formal de tipos de problemas, desenvolvimento de algoritmos aproximativos e análise da complexidade. O fato de um problema ser teoricamente resolvível por um computador não é suficiente para o problema ser na prática resolvível. Um problema é denominado tratável se no pior caso possui um algoritmo razoavelmente eficiente. E um algoritmo é dito razoavelmente eficiente quando existe um polinômio p tal que para qualquer entrada de tamanho n o algoritmo termina com no máximo p(n) passos [SZW 84]. Já que um polinômio pode ser de ordem bem alta, então um algoritmo de complexidade polinomial pode ser muito ineficiente. Genéticos é que se pode encontrar soluções aproximadas de problemas de grande complexidade computacional mediante um processo de evolução simulada[LAG 96]. Como produto do estudo deste tema...
Link permanente para citações:
Algoritmos para problemas de classificação e particionamento em grafos; Algorithms for classification and partitioning in graphs
Fonte: Biblioteca Digital da Unicamp
Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado
Formato: application/pdf
Publicado em 13/12/2007
PT
Relevância na Pesquisa
36.42%
#Otimização combinatoria#Algoritmos - Programação#Programação inteira#Combinatorial optimization#Algorithms#Integer Programming
O trabalho desenvolvido neste doutorado consistiu em conceber algoritmos para uma série de problemas NP-dificeis sob a abordagem de aproximabilidade, complementado com resultados heurísticos e também de programação inteira. O estudo foi focado em problemas de classificação e particionamento em grafos, como classificação métrica, corte balanceado e clusterização. Houve um equilíbrio entre teoria e aplicabilidade, ao obterse algoritmos com bons fatores de aproximação e algoritmos que obtiveram soluções de qualidade em tempo competitivo. O estudo concentrou-se em três problemas: o Problema da Classificação Métrica Uniforme, o Problema do Corte Balanceado e o Problema da Localização de Recursos na versão contínua. Inicialmente trabalhamos no Problema da Classificação Métrica Uniforme, para o qual propusemos um algoritmo O (logn)-aproximado. Na validação experimental, este algoritmo obteve soluções de boa qualidade em um espaço de tempo menor que os algoritmos tradicionais. Para o Problema do Corte Balanceado, propusemos heurísticas e um algoritmo exato. Experimentalmente, utilizamos um resolvedor de programação semidefinida para resolver a relaxação do problema e melhoramos substancialmente o tempo de resolução da relaxação ao construir um resolvedor próprio utilizando o método de inserção de cortes sobre um sistema de programação linear. Finalmente...
Link permanente para citações:
Algoritmos para problemas de escalonamento em grades; Algorithms for scheduling problems in grid
Fonte: Biblioteca Digital da Unicamp
Publicador: Biblioteca Digital da Unicamp
Tipo: Dissertação de Mestrado
Formato: application/pdf
Publicado em 15/04/2011
PT
Relevância na Pesquisa
36.4%
#Computação em grade (Sistema de computador)#Escalonamento de produção#Algoritmos aproximados#Algoritmos online#Computational grids (Computer systems)#Scheduling#Approximation algorithms#Online algorithms
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...
Link permanente para citações:
Practical comparison of approximation algorithms for scheduling problems
Fonte: Sociedade Brasileira de Pesquisa Operacional
Publicador: Sociedade Brasileira de Pesquisa Operacional
Tipo: Artigo de Revista Científica
Formato: text/html
Publicado em 01/08/2004
EN
Relevância na Pesquisa
36.4%
In this paper we consider an experimental study of approximation algorithms for scheduling problems in parallel machines minimizing the average weighted completion time. We implemented approximation algorithms for the following problems: P|r j|sigmaCj, P||sigmaw jCj, P|r j|sigmaw jCj, R||sigmaw jCj and R|r j|sigmaw jCj. We generated more than 1000 tests over more than 200 different instances and present some practical aspects of the implemented algorithms. We also made an experimental comparison on two lower bounds based on the formulations used by the algorithms. The first one is a semidefinite formulation for the problem R||sigmaw jCj and the other one is a linear formulation for the problem R|r j|sigmaw jCj. For all tests, the algorithms obtained very good results. We notice that algorithms using more refined techniques, when compared to algorithms with simple strategies, do not necessary lead to better results. We also present two heuristics, based on approximation algorithms, that generate solutions with better quality in almost all instances considered.
Link permanente para citações:
6.852J / 18.437J Distributed Algorithms, Fall 2001; Distributed Algorithms
Fonte: MIT - Massachusetts Institute of Technology
Publicador: MIT - Massachusetts Institute of Technology
EN-US
Relevância na Pesquisa
36.42%
#distributed algorithms#algorithm#concurrent algorithms#distributed networks#process synchronization#computational resources#distributed consensus#distributed graph algorithms#distributed termination#deadlock detection#concurrency control
Design and analysis of concurrent algorithms, emphasizing those suitable for use in distributed networks. Process synchronization, allocation of computational resources, distributed consensus, distributed graph algorithms, election of a leader in a network, distributed termination, deadlock detection, concurrency control, communication, and clock synchronization. Special consideration given to issues of efficiency and fault tolerance. Formal models and proof methods for distributed computation. Alternate years. From the course home page: Course Description 6.852J / 18.437J intends to: (1) provide a rigorous introduction to the most important research results in the area of distributed algorithms, and (2) prepare interested students to carry out independent research in distributed algorithms. Topics covered include: design and analysis of concurrent algorithms, emphasizing those suitable for use in distributed networks, process synchronization, allocation of computational resources, distributed consensus, distributed graph algorithms, election of a leader in a network, distributed termination, deadlock detection, concurrency control, communication, and clock synchronization. Special consideration is given to issues of efficiency and fault tolerance. Formal models and proof methods for distributed computation are also discussed.
Link permanente para citações:
6.046J / 18.410J Introduction to Algorithms, Fall 2001; Introduction to Algorithms
Fonte: MIT - Massachusetts Institute of Technology
Publicador: MIT - Massachusetts Institute of Technology
EN-US
Relevância na Pesquisa
36.4%
#algorithms#efficient algorithms#sorting#search trees#heaps#hashing#divide-and-conquer#dynamic programming#amortized analysis#graph algorithms#shortest paths
Techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; amortized analysis; graph algorithms; shortest paths; network flow; computational geometry; number-theoretic algorithms; polynomial and matrix calculations; caching; and parallel computing. Enrollment may be limited.
Link permanente para citações:
6.854J / 18.415J Advanced Algorithms, Fall 1999; Advanced Algorithms
Fonte: MIT - Massachusetts Institute of Technology
Publicador: MIT - Massachusetts Institute of Technology
EN-US
Relevância na Pesquisa
36.41%
#fundamental algorithms#implementation#data structures#network flows#linear programming#computational geometry#approximation algorithms#algorithmic design#algorithmic analysis#string algorithms#maximum flows
A first-year graduate course in algorithms. Emphasizes fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Data structures. Network flows. Linear programming. Computational geometry. Approximation algorithms. Alternate years.
Link permanente para citações:
Fixed-Parameter Algorithms for the Consensus Analysis of Genomic Data; Festparameter-Algorithmen fuer die Konsens-Analyse Genomischer Daten; Fixed-Parameter Algorithms for the Consensus Analysis of Genomic Data
Fonte: Universität Tübingen
Publicador: Universität Tübingen
Tipo: Dissertation; info:eu-repo/semantics/doctoralThesis
EN
Relevância na Pesquisa
36.42%
#Algorithmentheorie , Berechnungskomplexität , Bioinformatik#004#Festparameteralgorithmen , Algorithmische Biologie , Konsensanalyse, NP-harte Probleme , Exakte Loesungen#fixed-parameter algorithms , computational biology , consensus analysis , NP-hard problems , exact solutions
Fixed-parameter algorithms offer a constructive and powerful approach
to efficiently obtain solutions for NP-hard problems combining two
important goals: Fixed-parameter algorithms compute optimal solutions
within provable time bounds despite the (almost inevitable)
computational intractability of NP-hard problems. The essential idea
is to identify one or more aspects of the input to a problem as the
parameters, and to confine the combinatorial explosion of
computational difficulty to a function of the parameters such that the
costs are polynomial in the non-parameterized part of the input. This
makes especially sense for parameters which have small values in
applications. Fixed-parameter algorithms have become an established
algorithmic tool in a variety of application areas, among them
computational biology where small values for problem parameters are
often observed. A number of design techniques for fixed-parameter
algorithms have been proposed and bounded search trees are one of
them. In computational biology, however, examples of bounded search
tree algorithms have been, so far, rare.
This thesis investigates the use of bounded search tree algorithms for
consensus problems in the analysis of DNA and RNA data. More
precisely...
Link permanente para citações:
Algoritmos paralelos para alocação e gerência de processadores em máquinas multiprocessadoras hipercúbicas; Parallel algorithms for processor allocation in hypercubes
Fonte: Universidade Federal do Rio Grande do Sul
Publicador: Universidade Federal do Rio Grande do Sul
Tipo: Dissertação
Formato: application/pdf
POR
Relevância na Pesquisa
36.43%
#Computer architecture#Arquitetura de computadores#Processamento paralelo#Parallel processing#Algoritmos paralelos#Processor allocation#Parallel algorithms#Hipercubo#Alocacao : Processadores#Hypercubes
Nos últimos anos, máquinas maciçamente paralelas, compostas de centenas de processadores, vem sendo estudadas como uma alternativa para a construção de supercomputadores. Neste novo conceito de processamento de dados, grandes velocidades são alcançadas através da cooperação entre os diversos elementos processadores na resolução de um problema. Grande parte das máquinas maciçamente paralelas encontradas no mercado utilizam-se da topologia hipercúbica para a interconexão de seus múltiplos processadores, ou podem ser configuradas como tal. Uma alternativa interessante para o compartilhamento da capacidade de processamento destas máquinas é sua utilização como computador agregado a uma rede, servindo a diversos usuários [DUT 91]. Desta forma, a máquina hipercúbica se comporta como um banco de processadores, que permite que cada usuário aloque parte de seus processadores para seu uso pessoal. Isto resulta em um aumento no desempenho da rede ao nível de supercomputadores com um custo relativamente baixo e viabiliza a construção de máquinas hipercúbicas com altas dimensões, evitando que estas sejam sub-utilizadas. Neste tipo de contexto, cabe ao sistema operacional atender as requisições dos usuários do hipercubo compartilhado de forma eficiente...
Link permanente para citações:
Efficient Algorithms and Data Structures for Massive Data Sets
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 19/05/2010
Relevância na Pesquisa
36.41%
For many algorithmic problems, traditional algorithms that optimise on the
number of instructions executed prove expensive on I/Os. Novel and very
different design techniques, when applied to these problems, can produce
algorithms that are I/O efficient. This thesis adds to the growing chorus of
such results. The computational models we use are the external memory model and
the W-Stream model.
On the external memory model, we obtain the following results. (1) An I/O
efficient algorithm for computing minimum spanning trees of graphs that
improves on the performance of the best known algorithm. (2) The first external
memory version of soft heap, an approximate meldable priority queue. (3) Hard
heap, the first meldable external memory priority queue that matches the
amortised I/O performance of the known external memory priority queues, while
allowing a meld operation at the same amortised cost. (4) I/O efficient exact,
approximate and randomised algorithms for the minimum cut problem, which has
not been explored before on the external memory model. (5) Some lower and upper
bounds on I/Os for interval graphs.
On the W-Stream model, we obtain the following results. (1) Algorithms for
various tree problems and list ranking that match the performance of the best
known algorithms and are easier to implement than them. (2) Pass efficient
algorithms for sorting...
Link permanente para citações:
Vsep-New Heuristic and Exact Algorithms for Graph Automorphism Group Computation
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.4%
#Computer Science - Data Structures and Algorithms#Computer Science - Discrete Mathematics#Mathematics - Combinatorics#ma.CO
One exact and two heuristic algorithms for determining the generators, orbits
and order of the graph automorphism group are presented. A basic tool of these
algorithms is the well-known individualization and refinement procedure. A
search tree is used in the algorithms - each node of the tree is a partition.
All nonequivalent discreet partitions derivative of the selected vertices are
stored in a coded form. A new strategy is used in the exact algorithm: if
during its execution some of the searched or intermediate variables obtain a
wrong value then the algorithm continues from a new start point losing some of
the results determined so far. The algorithms has been tested on one of the
known benchmark graphs and shows lower running times for some graph families.
The heuristic versions of the algorithms are based on determining some number
of discreet partitions derivative of each vertex in the selected cell of the
initial partition and comparing them for an automorphism - their search trees
are reduced. The heuristic algorithms are almost exact and are many times
faster than the exact one. The experimental tests exhibit that the worst-cases
running time of the exact algorithm is exponential but it is polynomial for the
heuristic algorithms. Several cell selectors are used. Some of them are new. We
also use a chooser of cell selector for choosing the optimal cell selector for
the manipulated graph. The proposed heuristic algorithms use two main heuristic
procedures that generate two different forests of search trees.; Comment: 40 pages; 1. Changed algorithm COMP (fig.11)- cases CS2/CS4 are
solved in new way;2. Corrected are some bad symbols!
Link permanente para citações:
Converting online algorithms to local computation algorithms
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 07/05/2012
Relevância na Pesquisa
36.4%
We propose a general method for converting online algorithms to local
computation algorithms by selecting a random permutation of the input, and
simulating running the online algorithm. We bound the number of steps of the
algorithm using a query tree, which models the dependencies between queries. We
improve previous analyses of query trees on graphs of bounded degree, and
extend the analysis to the cases where the degrees are distributed binomially,
and to a special case of bipartite graphs.
Using this method, we give a local computation algorithm for maximal matching
in graphs of bounded degree, which runs in time and space O(log^3 n).
We also show how to convert a large family of load balancing algorithms
(related to balls and bins problems) to local computation algorithms. This
gives several local load balancing algorithms which achieve the same
approximation ratios as the online algorithms, but run in O(log n) time and
space.
Finally, we modify existing local computation algorithms for hypergraph
2-coloring and k-CNF and use our improved analysis to obtain better time and
space bounds, of O(log^4 n), removing the dependency on the maximal degree of
the graph from the exponent.; Comment: ICALP 2012, to appear
Link permanente para citações:
Graph Iterators: Decoupling Graph Structures from Algorithms
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/03/2010
Relevância na Pesquisa
36.4%
I will present a way to implement graph algorithms which is different from
traditional methods. This work was motivated by the belief that some ideas from
software engineering should be applied to graph algorithms. Re-usability of
software is an important and difficult problem in general, and this is
particularly true for graph algorithms. The scientific literature demonstrates
plenty of applications of graph algorithms as subroutines for other algorithms.
Moreover, many practical problems from various domains may be modeled as graph
problems and hence solved by means of graph algorithms. Chapter 2 introduces
some data structures that will be used in 5 basic graph algorithms in chapter
3. Chapter 4 discusses an implementation of a maximum cardinality matching
algorithm for general graphs. Chapter 5 explains some techniques in C++, which
are useful to implement the data structures and algorithms in an efficient way.
Finally chapter 6 contains some concluding remarks.
Link permanente para citações:
Linear-Time Pointer-Machine Algorithms for Path-Evaluation Problems on Trees and Graphs
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.4%
We present algorithms that run in linear time on pointer machines for a
collection of problems, each of which either directly or indirectly requires
the evaluation of a function defined on paths in a tree. These problems
previously had linear-time algorithms but only for random-access machines
(RAMs); the best pointer-machine algorithms were super-linear by an
inverse-Ackermann-function factor. Our algorithms are also simpler, in some
cases substantially, than the previous linear-time RAM algorithms. Our
improvements come primarily from three new ideas: a refined analysis of path
compression that gives a linear bound if the compressions favor certain nodes,
a pointer-based radix sort as a replacement for table-based methods, and a more
careful partitioning of a tree into easily managed parts. Our algorithms
compute nearest common ancestors off-line, verify and construct minimum
spanning trees, do interval analysis on a flowgraph, find the dominators of a
flowgraph, and build the component tree of a weighted tree.; Comment: 41 pages; 10 figures; 1 table; 65 references. This work is partially
covered by the extended abstracts, ``Linear-Time Pointer-Machine Algorithms
for Least Common Ancestors, MST Verification, and Dominators,'' Proc. 30th
ACM Symp. on Theory of Computing...
Link permanente para citações:
Compositional competitiveness for distributed algorithms
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/06/2003
Relevância na Pesquisa
36.4%
#Computer Science - Data Structures and Algorithms#Computer Science - Distributed, Parallel, and Cluster Computing#F.1.2#F.2.m
We define a measure of competitive performance for distributed algorithms
based on throughput, the number of tasks that an algorithm can carry out in a
fixed amount of work. This new measure complements the latency measure of Ajtai
et al., which measures how quickly an algorithm can finish tasks that start at
specified times. The novel feature of the throughput measure, which
distinguishes it from the latency measure, is that it is compositional: it
supports a notion of algorithms that are competitive relative to a class of
subroutines, with the property that an algorithm that is k-competitive relative
to a class of subroutines, combined with an l-competitive member of that class,
gives a combined algorithm that is kl-competitive.
In particular, we prove the throughput-competitiveness of a class of
algorithms for collect operations, in which each of a group of n processes
obtains all values stored in an array of n registers. Collects are a
fundamental building block of a wide variety of shared-memory distributed
algorithms, and we show that several such algorithms are competitive relative
to collects. Inserting a competitive collect in these algorithms gives the
first examples of competitive distributed algorithms obtained by composition
using a general construction.; Comment: 33 pages...
Link permanente para citações:
Exact Algorithms via Monotone Local Search
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/12/2015
Relevância na Pesquisa
36.41%
#Computer Science - Data Structures and Algorithms#Computer Science - Discrete Mathematics#Mathematics - Combinatorics
We give a new general approach for designing exact exponential-time
algorithms for subset problems. In a subset problem the input implicitly
describes a family of sets over a universe of size n and the task is to
determine whether the family contains at least one set. Our approach is based
on "monotone local search", where the goal is to extend a partial solution to a
solution by adding as few elements as possible. More formally, in the extension
problem we are also given as input a subset X of the universe and an integer k.
The task is to determine whether one can add at most k elements to X to obtain
a set in the (implicitly defined) family. Our main result is that an O*(c^k)
time algorithm for the extension problem immediately yields a randomized
algorithm for finding a solution of any size with running time O*((2-1/c)^n).
In many cases, the extension problem can be reduced to simply finding a
solution of size at most k. Furthermore, efficient algorithms for finding small
solutions have been extensively studied in the field of parameterized
algorithms. Directly applying these algorithms, our theorem yields in one
stroke significant improvements over the best known exponential-time algorithms
for several well-studied problems, including d-Hitting Set...
Link permanente para citações:
Comparação de algoritmos computacionais de cálculo de dose em radioterapia aplicada aos tumores de pulmão; Comparison of dose calculation algorithms in radiotherapy applied to lung tumors
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 16/09/2015
PT
Relevância na Pesquisa
36.43%
#Algorithms#Algoritmos#Computer simulation#Dosagem de radiação#Lung neoplasms#Neoplasias pulmonares#Planejamento de radioterapia assistida por computador#Radiation dosage#Radiocirurgia#Radiosurgery#Radioterapia conformal
INTRODUÇÃO: Na Radioterapia, a acurácia da distribuição de dose em cálculos com correção de heterogeneidade está diretamente relacionada à escolha do algoritmo de cálculo. Existe uma variedade de algoritmos de cálculo disponíveis no mercado, variando em tempo de processamento e acurácia. Este estudo teve como objetivos quantificar a acurácia de dez diferentes algoritmos de cálculo em objetos simuladores de pulmão e analisar o impacto da escolha do algoritmo na distribuição de dose em radioterapia aplicada a tumores de pulmão. METODOLOGIA: Foram utilizados placas simuladoras de água (água sólida RW3) e pulmão (cortiça) para determinar a Porcentagem de Dose em Profundidade (PDP) e perfil transversal dentro da heterogeneidade (cortiça). As medidas foram realizadas em um Clinac Varian 6EX, com feixes de fótons de 6 MV e dois tamanhos de campo (5 x 5 cm2 e 10 x 10 cm2), irradiando-se filmes radiocrômicos Gafchromic EBT3 e câmara de ionização Scanditronix Wellhofer CC13. Planejamentos de 25 pacientes - 11 com técnica tridimendional (3D) e 14 com técnica de Radioterapia Estereotática Corpórea (SBRT) - foram realizados, inicialmente sem correção de heterogeneidade e, mantendo-se as UM, os cálculos com os diferentes algoritmos/métodos de correção foram comparados com o planejamento inicial. Foram avaliados as doses no volume alvo e nos órgãos em risco. RESULTADOS: As medidas realizadas em objetos simuladores revelaram que os algoritmos baseados no princípio da convolução (Eclipse® Pencil Beam Convolution com métodos de correção Batho...
Link permanente para citações: