Paralelismo como solução para redução de complexidade de problemas combinatoriais
Autor(es):
Nobre, Ricardo Holanda
Palavras Chaves:
Não informado
Ano de Publicação:
2011
Resumo:
A constante demanda por alto desempenho computacional tem ganhado espaço, acelerada pelos mais diversos setores da atuação humana, que buscam na computação a resolução de problemas até então considerados insolúveis ou cuja resolução exige um grande esforço computacional, principalmente devido à complexidade matemática inerente aos mesmos. Não obstante a isso, a resolução de um problema através de sistemas computacionais exige cada vez mais capacidade de processamento, o que, por sua vez, constitui um limite nos atuais processadores, aliado ao fato de que os sistemas computacionais convencionais não resolvem determinadas classes de problemas em tempo polinomial, como é o caso do problema da mochila da otimização combinatória. O presente trabalho analisa a utilização massiva do paralelismo como uma solução viável e factível, em si mesma, para reduzir a complexidade de tempo de vários tipos de problemas, dentre eles os problemas combinatórios, quando a dimensão dos dados de entrada é menor ou igual ao número de processadores paralelos. Aborda-se esta temática sobre o prisma do ''pensar em paralelo'', em contraponto a construção seqüencial dos algoritmos, culminando na propositura de um novo algoritmo para o problema da mochila (0-1), idealizado originalmente para ser executado em paralelo, e cuja complexidade de tempo é bem superior aos atuais algoritmos exatos existentes.Palavras-chaves: Paralelismo, redução de complexidade, problemas combinatoriais, arquitetura massivamente paralela, GPU Computing, CUDA, mochila booleana.
Abstract:
Ver documento original.
Tipo do Trabalho:
Dissertação
Referência:
Nobre, Ricardo Holanda. Paralelismo como solução para redução de complexidade de problemas combinatoriais. 2011. 203 f. Dissertação (Mestrado Acadêmico ou Profissional em 2011) - Universidade Estadual do Ceará, , 2011. Disponível em: Acesso em: 29 de abril de 2024
Esse
Trabalho não possui arquivo digital
Universidade Estadual do Ceará - UECE | Departamento de Tecnologia da Informação e Comunicação - DETIC
Política de Privacidade e Segurança Build 1
