Made available in DSpace on 2014-06-12T15:53:30Z (GMT). No. of bitstreams: 2
arquivo1920_1.pdf: 3817805 bytes, checksum: 7b50528318a4bbf365ddf3fc6ad1ca73 (MD5)
license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5)
Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Os algoritmos de busca meta-heurística vêm sendo pesquisados em inúmeros domínios, inclusive
na resolução de restrições. Devido à sua capacidade de atuação em problemas que a
solução é desconhecida, são utilizados em diversas situações. Os algoritmos evolutivos são uma
família dos algoritmos de busca, que simulam o comportamento da natureza. Os problemas de
satisfação de restrição (CSP) são compostos por um conjunto de conjunções de variáveis, caracterizando
uma restrição. Valores são associados às variáveis, os quais devem satisfazer a
restrição, caso contrário, são considerados inválidos. Problemas de resolução de restrição estão
associados a diversos contextos, desde problemas de alocação de recursos a design de circuitos
integrados. Algoritmos de busca meta-heurística vêm sendo utilizados para a solução de CSP,
resolvendo o problema da limitação dos provadores de teoremas, que necessitam modelar uma
teoria para serem capazes de encontrar uma solução. Neste trabalho, investigamos o uso do
algoritmo de busca meta heurística em um tipo de teste de software (execução concólica) que
é tratado como um problema de CSP. A execução concólica se baseia no teste simbólico, o
qual extrai as decisões internas de um programa que formam uma restrição, também conhecidas
como Path Condition (PC). Estas restrições são formadas a partir das variáveis de entrada,
portanto, a solução de uma restrição determina as entradas necessárias para percorrer um determinado
caminho no software. As técnicas clássicas utilizam provadores de teoremas, os quais
são limitados a teoria suportada, e métodos de randomização, que geram valores aleatórios
para as variáveis, reduzindo a complexidade da restrição. A presente dissertação teve como
objetivo criar e analisar o desempenho de solucionadores baseados em algoritmos de busca
meta-heurística, sendo comparados às técnicas clássicas utilizadas neste contexto. Os resultados
mostraram que o uso de heurísticas de busca pode permitir a criação de novas técnicas de
resolução de restrição, no contexto de teste simbólico
Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufpe.br:123456789/1966 |
Date | 31 January 2009 |
Creators | TAKAKI, Mitsuo |
Contributors | PRUDÊNCIO, Ricardo Bastos Cavalcante |
Publisher | Universidade Federal de Pernambuco |
Source Sets | IBICT Brazilian ETDs |
Language | Portuguese |
Detected Language | Portuguese |
Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
Source | reponame:Repositório Institucional da UFPE, instname:Universidade Federal de Pernambuco, instacron:UFPE |
Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0021 seconds