Graduando do IMPA Tech apresenta seminário sobre algoritmos
Vinicius Prestes abordou artigo classificado para concurso nacional da SBC
Troca de papéis. Acostumado a acompanhar os seminários acadêmicos do IMPA Tech, o graduando Vinicius Prestes, da turma 2024, assumiu o posto de palestrante nesta terça-feira (2). Ele apresentou o trabalho de iniciação científica “Sobre a Computação de um Set Cover Minimal Máximo: Algoritmos Exatos e Limites Inferiores baseados em (S)ETH” aos colegas. E foi a primeira vez que um aluno do bacharelado palestrou no ciclo de seminários.
O projeto foi realizado coletivamente durante os estudos dirigidos de "Algoritmos Exatos Exponenciais", orientados pelo professor Uéverton. Os alunos do bacharelado em Matemática da Tecnologia e Inovação Alan Santos, Cristiane Sampaio, Felipe Ribeiro, Lucas Fraga e Marcelo Alves também fazem parte do grupo de pesquisa.
Juntos, os graduandos analisaram 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.
Em maio, o artigo sobre o estudo 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). A competição, promovida pela Sociedade Brasileira de Computação (SBC), é a mais tradicional da área.
O seminário no IMPA Tech antecede a apresentação na fase final do concurso, que acontecerá em julho, em Gramado (RS), durante o Congresso da SBC (CSBC), principal encontro da comunidade de Computação da América Latina.
“A apresentação é de um trabalho de Iniciação Científica que já é premiado, pois está entre os três finalistas de 105 submissões. Esse seminário também funcionou como um treinamento para a apresentação. Os colegas puderam ver o que foi feito e quais foram os resultados”, destacou o professor Uéverton.
Para Ribeiro, um dos integrantes do grupo, o seminário simboliza a concretização de um trabalho que durou meses. “Participar desse processo de pesquisa foi muito importante, tanto no aspecto acadêmico como pessoalmente. A sensação de ter finalizado o artigo já era incrível, mas ter sido selecionado para um grande evento é muito gratificante. A apresentação de hoje mostra o grande potencial que temos no IMPA Tech”, disse.
