Alunos são finalistas de prêmio nacional de IC em computação
Trabalho foi selecionado entre 105 pesquisas para fase final de concurso da SBC
Artigo científico, fruto de pesquisa desenvolvida por estudantes do IMPA Tech, ficou entre os três melhores do Brasil e foi selecionado para apresentação oral no Concurso de Trabalhos de Iniciação Científica (CTIC) da Sociedade Brasileira de Computação (SBC), competição mais tradicional da área. O trabalho foi realizado coletivamente pelos alunos Alan Santos, Cristiane Sampaio, Felipe Ribeiro, Lucas Fraga, Marcelo Alves e Vinicius Prestes, sob a orientação do professor Uéverton Souza, durante os estudos dirigidos de "Algoritmos Exatos Exponenciais".
O artigo “Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH” analisa as limitações computacionais para a resolução de uma variante do clássico Set Cover, um problema fundamental em computação. A discussão sobre o assunto começou a partir da leitura coletiva dos capítulos do livro-texto Exact Exponential Algorithms, escrito por Fedor V. Fomin e Dieter Kratsch.
O grupo investigou uma versão max-min de um desafiador problema de minimização também conhecido como “Cobertura por Conjuntos”, que consiste em encontrar combinações eficientes de conjuntos de dados dentro de um grande volume de informações. O objetivo foi criar algoritmos e soluções matemáticas para resolver o problema no menor tempo possível. Enquanto o problema clássico consiste em encontrar a menor combinação para cobrir todos os elementos fornecidos, a pesquisa desenvolvida analisou a questão de computar a combinação minimal máxima para cobrir os elementos, uma variante natural para o tema.
“Investigamos propriedades sobre Set Cover, Vertex Cover, Dominating Set e Upper Domination que são problemas de cobertura em grafos e sistemas de conjuntos. Esses são problemas clássicos, que tem muitos estudos publicados, mas atacamos um problema que não tinha tantos estudos, que é o Set Cover Minimal Máximo, e tinha uma oportunidade interessante de fazer avanços. Mais especificamente, estudamos algoritmos para identificar essa estrutura minimal máxima em um sistema de conjuntos qualquer, e chegamos a vários resultados sobre qual algoritmo podemos usar”, explicou Prestes, aluno que representará a equipe no CTIC.
Como resultado, os graduandos conseguiram desenvolver uma solução que acelera o processamento de dados e, mais do que isso, provaram matematicamente quais são os limites intransponíveis dessa tarefa.
O CTIC seleciona trabalhos excepcionais desenvolvidos por alunos de graduação, que são premiados e publicados nos anais do CSBC bem como na Revista Eletrônica de Iniciação Científica em Computação (REIC) da SBC. A fase final do concurso, com a apresentação do artigo, acontecerá em julho, em Gramado (RS), durante o Congresso da SBC (CSBC), principal encontro da comunidade de Computação da América Latina.
Neste ano, o concurso registrou recorde de submissões, com 105 inscrições. “A seleção foi uma grande surpresa. É a primeira vez que participo de um artigo a ser publicado e escolhido para uma competição dessas. Foi legal ver que conseguimos fazer uma contribuição significativa para o conhecimento de alguma forma”, disse Prestes.
Para o professor Uéverton, o nível de maturidade científica demonstrado pelo grupo foi o grande diferencial. “É uma conquista e tanto. Os alunos foram sempre muito críticos e a pesquisa foi mudando de foco ao longo do processo. Discutimos diferentes possibilidades e manipulamos o problema de formas variadas, levando a resultados não triviais”, afirmou.
