Busca avançada
Ano de início
Entree

Algoritmos exatos e heurísticos para o problema Perfect Awareness

Processo: 19/22297-1
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de julho de 2020
Vigência (Término): 28 de fevereiro de 2021
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Pedro Jussieu de Rezende
Beneficiário:Felipe de Carvalho Pereira
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória   Programação linear inteira   Programação heurística   Algoritmos

Resumo

Apresentamos uma proposta de pesquisa a ser desenvolvida durante o curso de mestrado em Ciência da Computação do Instituto de Computação da Unicamp. O tópico de pesquisa envolve o estudo de um problema de otimização combinatória NP-difícil denominado perfect awareness. Neste problema, considera-se uma rede social na qual uma informação é propagada entre indivíduos conectados. O objetivo é selecionar um conjunto inicial de disseminadores de menor tamanho possível, de modo que, ao fim do processo de propagação, todos os indivíduos sejam conhecedores da informação. Esta proposta traz uma contextualização do problema, assim como sua definição formal e uma revisão bibliográfica. É descrita ainda uma metodologia de trabalho que visa solucionar o problema através de algoritmos heurísticos baseados na meta-heurística GRASP e por meio de algoritmos exatos via programação linear inteira. Neste documento, também são elencados os objetivos do trabalho, os resultados preliminares e os esperados, e um cronograma de atividades.Um conjunto de experimentos inicial foi realizado e os resultados mostraram-se promissores, uma vez que uma das heurísticas implementadas superou o único algoritmo proposto na literatura para o problema até o momento. Diante disso, o principal objetivo deste trabalho é desenvolver novos algoritmos para resolver o problema perfect awareness e submetê-los a experimentos computacionais para que os resultados obtidos sejam comparados com os melhores algoritmos conhecidos para o problema. (AU)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
PEREIRA, Felipe de Carvalho. Um estudo computacional do Problema do Gnosticismo Perfeito. 2021. 94 f. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.