Paralelismo como solução para redução de complexidade de problemas combinatoriais

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: Nobre, Ricardo Holanda
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Estadual do Ceará
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://siduece.uece.br/siduece/trabalhoAcademicoPublico.jsf?id=70961
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.