Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/2240
Título: Probabilistic models for a class of computing costs distributions
Autor: Carvalho, Alda Cristina Jesus Valentim Nunes de
Orientador: Crato, Nuno
Gomes, Carla
Palavras-chave: Heavy tails
Random algorithms
Search trees
Stable distributions
Constraint Satisfaction Problems
Computing costs
Caudas pesadas
Algoritmos aleatórios
Árvores de procura
Distribuições estáveis
Problemas de satisfiabilidade de restrições
Custos de computação
Data de Defesa: Jun-2010
Editora: Instituto Superior de Economia e Gestão
Citação: Carvalho, Alda Cristina Jesus Valentim Nunes de. 2010. "Probabilistic models for a class of computing costs distributions". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão
Resumo: Constraint Satisfaction Problems are the subject of intense research in Artificial Intelligence and Operations Research, They often exhibit high complexity, requir¬ing a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Randomized search methods have greatly extended our ability to solve hard computational problems. As literature often shows, in some cases, runtime distributions display heavy-tailed behavior. The results in literature are mainly empirical. In this work, we propose a mathematical approach based on probabilistic models. The Constraint Satisfaction Problem studied is the Latin square. We show how the different regimes observed can be captured by a mixture of stable distributions. We also provide search tree models for any degree of heavy-tailedness. Finally, we show how to generate heavy tails in Latin squares. A scale free urn model is presented to set a lower bound for the tail. All our research results have significant economic implications as Constraint Satis¬faction Problems are ubiquitous in scheduling and other typical Operations Research problems. Our results provide modeling tools for the tail behavior of computational costs and give a new insight into the nature of their computational complexity.
Problemas de satisfiabilidade com restrições têm sido alvo de muita investigação em Inteligência Artificial e Investigação Operacional. Estes problemas apresentam geralmente uma grande complexidade, sendo necessário usar uma combinação de heurísticas e métodos de procura para os resolver em tempo útil. A introdução de métodos de procura aleatórios permitiu resolver muitos desses problemas computa¬cionais complexos. Muitos dos trabalhos sobre a distribuição dos tempos de computação mostram que esta exibe caudas pesadas. Estes resultados são sobretudo empíricos. Neste tra¬balho, propomos uma abordagem mais matemática, baseada em modelos proba¬bilísticos. O problema estudado é o quadrado latino. Mostra-se como os diferentes regimes observados podem ser reproduzidos através de uma mistura de distribuições estáveis. Também se mostra como reproduzir qualquer tipo de decaimento da cauda da distribuição através de árvores de procura. Finalmente, mostra-se como gerar as caudas pesadas no quadrado latino, apresenta-se uma urna com auto-semelhança para estabelecer um limite inferior para a cauda da distribuição. Os resultados deste trabalho têm implicações económicas, uma vez que os problemas de satisfiabilidade com restrições aparecem em problemas de calendarização e outros problemas de Investigação Operacional. Os resultados apresentados neste trabalho fornecem modelos para a cauda da distribuição dos custos de computação e dão novas pistas para o estudo da sua natureza complexa.
Descrição: Doctorate in Applied Mathematics for Business and Economics
URI: http://hdl.handle.net/10400.5/2240
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
tese.pdf4,08 MBAdobe PDFVer/Abrir    Acesso Restrito. Solicitar cópia ao autor!


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.