Algoritmos, Combinatória e Aplicações

As linhas de pesquisa conduzidas por Raphael Machado buscam obter avanços teóricos para problemas teóricos fundamentais e desenvolver modelos computacionais para problemas reais.

Conheça, a seguir, as principais linhas de pesquisa de Raphael, com referências e exemplos de problemas de pesquisa para alunos.

 

Coloração de Grafos

Descrição

  • O problema clássico de coloração de grafos busca uma associação de cores aos vértices de um grafo, de tal forma que vértices adjacentes possuam cores distintas. Diversas variantes do problema vem sendo estudadas na literatura, tais como coloração de arestas, coloração total, coloração de cliques, coloração de bicliques, dentre outras. Raphael tem trabalhado na classificação de problemas de coloração em classes restritas de grafos, obtendo algoritmos polinomiais ou resultados de NP-completude ou Σ2-completude.

Referências

Questões de pesquisa

  • Qual a complexidade dos diversos problemas de coloração (vértices, aresta, total, clique,…) nas diversas classes de grafos?

 

Diâmetro de Grafos

O diâmetro de um grafo é a maior das distâncias entre pares de vértices. Até hoje, não se sabe se é possível calcular o diâmetro de um grafo sem se calcular cada uma das distâncias entre os pares de vértices deste grafo. Uma vez que o mais eficiente algoritmo para determinar o diâmetro de um grafo em geral super-linear, muita pesquisa tem sido desenvolvida com o objetivo de desenvolver algoritmos lineares para encontrar o diâmetro aproximado em classes restritas de grafos. Raphael tem investigado o uso de algoritmos do tipo multi-sweep BFS para determinar o diâmetro a menos de erros aditivos em classes restritas de grafos.

 

Referências

Questões de pesquisa

  • Para que classes é possível desenvolver algoritmos do tipo multi-sweep BFS para determinar o diâmetro a menos de erros aditivos.

 

Grafos de disco unitário

Descrição

  • Grafos de disco unitário são grafos cujos vértices podem ser associados a pontos no plano de tal forma que vértices são adjacentes se os pontos correspondentes estão a distância no máximo 1. O reconhecimento de grafos de disco unitário é um problema reconhecidamente difícil – nem mesmo se sabe se o problema está em NP.

Referências

Questões de pesquisa

  • Desenvolvimento de heurísticas para o reconhecimento de grafos de disco unitário.
  • Estudo de grafos específicos (estrela dupla).
  • Desenvolvimento de algoritmos para grafos de disco unitário e classes relacionadas.

 

 

Grafos de Programa

Descrição

  • Grafos de programa são grafos que descrevem relações e propriedades de um programa de computador, como, por exemplo, o fluxo de execução ou chamadas de procedimentos. Saber processar grafos de programa tem diversos impactos práticos no desenvolvimento de ferramentas e métodos para segurança de software.

Referências

  • BENTO, LUCILA M.S. ; BOCCARDO, DAVIDSON R. ; Machado, Raphael C.S. ; PEREIRA DE SÁ, VINÍCIUS G. ; SZWARCFITER, JAYME LUIZ . On the resilience of canonical reducible permutation graphs. DISCRETE APPLIED MATHEMATICS, v. 234, p. 32-46, 2018.
  • BENTO, L. ; BOCCARDO, DAVIDSON ; Machado, R.C.S. ; MIYAZAWA, F. ; Vinícius G. P. de Sá ; SZWARCFITER, J. . Dijkstra graphs. DISCRETE APPLIED MATHEMATICS, p. 1, 2017.

 

Questões de pesquisa

  • Marcas d’água digitais são informações embarcadas em um objeto digital e que carregam alguma “informação” relacionada àquele objeto, sendo, idealmente, de difícil localização e remoção por parte de usuários maliciosos. Raphael tem investigado as formas de codificar informações nos grafos de fluxo e de chamada de programas de computadores, de modo a permitir a criação de marcas d’água em software que sejam, ao mesmo tempo, furtivas e resilientes.

 

Protocolos equilibrados de troca

Descrição

  • Protocolos de troca envolvem dois participantes que desejam enviar um item digital recebendo um (outro) item digital em troca. Um exemplo de tal protocolo é a assinatura de contrato: cada uma das parte assina o contrato e espera que a outra parte assine de volta. Caso apenas uma das partes assine o contrato, esta parte pode estar em “desvantagem” perante a outra parte, que pode desistir de assinar o contrato, conforme conveniência posterior. Raphael está interessado no desenvolvimento de protocolos chamados “equilibrados”, ou seja, que permitem a troca “simultânea” entre as partes, portanto, impedindo que uma das partes fique em desvantagem.

 

Referências

Questões de pesquisa

  • Desevolvimento de protocolos equilibrados para assinatura de contratos, troca de segredos, recibo de segredo e irrefutabilidade.

 

Aleatoriedade e Pseudo-Aleatoriedade

Descrição

  • Um fenômeno aleatório “real” é o resultado de um evento probabilístico. Uma sequência pseudo-aleatória é uma sequência que não pode ser diferenciada, por meio de um procedimento eficiente, de uma sequência gerada por um fenômeno aleatório. Aleatoriedade e pseudo-aleatoriedade possuem uma enorme quantidade de aplicações em Computação, em particular, em Segurança da Informação.

Referências

  • RIBEIRO, L. C. ; GONCALVES, D. ; CHAPETTA, W. ; MARCELINO, A. ; TARELHO, L. V. G. ; Machado, R.C.S. ; CORREA, L. ; GARCIA, G. ; SA, A. . True random number generators for batch control sampling in Smart Factories. In: IEEE INTERNATIONAL WORKSHOP ON Metrology for Industry 4.0 and IoT, 2018, Brescia. Proc. IEEE INTERNATIONAL WORKSHOP ON Metrology for Industry 4.0 and IoT 2018, 2018.

Questões de pesquisa

  • Todos os aspectos de aleatoriedade e pseudo-aleatoriedade, desde a investigação de fenômenos físicos aleatórios, passando pelo estudo de algoritmos geradores de sequências pseudo-aleatórias, até o desenvolvimento de protocolos de segurança baseados em aleatoriedade e pseudo-aleatoriedade

 

Algoritmos de comparação de genomas

Descrição

  • A comparação entre as cargas genéticas de espécies distintas é importante para compreender os graus de similaridade e parentesco entre tais espécies, com importantes aplicações tais como a reconstituição de árvores filogenéticas de espécies.

Referências

  • DA SILVA, POLY H. ; Machado, Raphael ; Dantas, Simone ; BRAGA, MARILIA D.V. . Genomic Distance with High Indel Costs. IEEE-ACM Transactions on Computational Biology and Bioinformatics, v. 14, p. 728-732, 2017.

Questões de pesquisa

  • Desenvolvimento de algoritmos que permitam calcular a distância genômica. Mais precisamente, dados dois genomas – tipicamente representados por conjuntos de sequências – e um conjunto de operações de mutação, deve-se encontrar o número mínimo de mutações que transforma um genoma em outro.