Resoluções paralelas de problemas intratáveis em processos industriais

• Processo: 15/18164-5
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Data de Início da vigência: 01 de dezembro de 2015
• Data de Término da vigência: 30 de novembro de 2017
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Carlos Alberto Alonso Sanches
• Beneficiário: Carlos Alberto Alonso Sanches
• Instituição Sede: Divisão de Ciência da Computação (IEC). Instituto Tecnológico de Aeronáutica (ITA). Ministério da Defesa (Brasil). São José dos Campos , SP, Brasil
• Assunto(s): Algoritmos Programação paralela
• Palavra(s)-Chave do Pesquisador: Gpu | Intractable Problems | knapsack problem | Multicores | parallel algorithms | Paralelismo

Resumo

O objetivo deste auxílio é a aquisição de equipamentos para implementação e testes de algoritmos paralelos para problemas intratáveis, ou seja, que não possuem resoluções de tempo polinomial em computadores sequenciais. O foco corrente é encontrar algoritmos eficientes para Knapsack Problem e Minimization of Open Stacks Problem, comuns em processos industriais, e suas implementações com processadores multicores e placas GPUs (Graphics Processing Units), dispositivos com alto grau de processamento paralelo, custo acessível e baixo consumo energético. Também se pretende adquirir computadores para confecção de artigos, participação em conferências e realização de reuniões a distância. Prevê-se orientações em diversos níveis discentes (Iniciação Científica, Trabalhos de Graduação, Mestrado e Doutorado), com a correspondente divulgação em veículos indexados (congressos e periódicos). (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

CURTIS, V. V.; SANCHES, C. A. A.. A low-space algorithm for the subset-sum problem on GPU. Computers & Operations Research, v. 83, p. 120-124, JUL 2017. (15/18164-5)

CURTIS, V. V.; SANCHES, C. A. A.. An improved balanced algorithm for the subset-sum problem. European Journal of Operational Research, v. 275, n. 2, p. 460-466, JUN 1 2019. (15/18164-5)

SANCHES, C. A. A.; SOMA, N. Y.. A general resolution of intractable problems in polynomial time through DNA Computing. BIOSYSTEMS, v. 150, p. 119-131, DEC 2016. (15/18164-5)