Realizado pelo Departamento de Ciência da Computação do Instituto de Matemática e Estatística (IME) da Universidade de São Paulo (USP) com o apoio do programa FAPESP Escola São Paulo de Ciência Avançada (ESPCA), o evento oferece a 150 jovens pesquisadores e estudantes de instituições de 20 países aulas, palestras e outras atividades sobre algoritmos, combinatória e otimização, ramos inter-relacionados da Matemática e da Ciência da Computação com inúmeras aplicações tecnológicas.
“Enquanto os algoritmos são sequências finitas de instruções para a realização de determinadas atividades, a combinatória e a otimização atuam, respectivamente, na análise das possiblidades e nos esforços para que as soluções sejam mais eficientes. O que os pesquisadores selecionados para o curso buscam em seus países e instituições de origem é trabalhar com algoritmos para atender as diversas e crescentes demandas tecnológicas globais, exigindo que novas técnicas sejam desenvolvidas para resolver problemas cada vez mais complexos”, disse Yoshiko Wakabayashi, coordenadora do curso.
Wakabayashi é uma das pesquisadoras principais do projeto temático Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, que, com o apoio da FAPESP, busca desenvolver novos algoritmos e estratégias para a resolução de problemas de diferentes áreas do conhecimento.
Foi dessa forma que seu grupo avançou no tratamento de um problema persistente na análise de dados de árvores filogenéticas – representações gráficas, em forma de árvores, das relações evolutivas entre várias espécies ou outros seres vivos que possam ter um ancestral comum.
“Essas árvores são representadas por grafos, conjuntos de pontos, chamados de vértices, conectados por arestas, que modelam matematicamente diversos fenômenos – no caso do nosso estudo, as características compartilhadas por indivíduos de uma mesma espécie. A análise das relações entre esses vértices e arestas permite descobrir, matematicamente, se há alguma cadeia biológica que indica, por exemplo, parentesco entre um indivíduo e outro”, explicou Karla Roberta Pereira Sampaio Lima, da Escola de Artes, Ciências e Humanidades (EACH) da USP.
Mas a análise dessas relações, feita por computadores, não é tarefa fácil. Um grafo de 50 vértices – no caso de uma árvore filogenética, 50 indivíduos de uma mesma espécie – precisaria de cerca de 17 horas para ser analisado e ter uma pergunta sobre suas relações respondida. Os pesquisadores utilizaram técnicas de programação e métodos de otimização para encurtar o processo, eliminando soluções que não interessam e fazendo com que o sistema focasse em respostas ótimas.
Os experimentos mostraram que o algoritmo desenvolvido a partir da pesquisa pode ser usado para resolver grafos com 1.500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. Um artigo com os resultados foi publicado por Manoel Campêlo, Alexandre S. Freire, Karla R. Lima, Phablo F. S. Moura e Yoshiko Wakabayashi na revista Mathematical Programming, disponível em link.springer.com/article/10.1007%2Fs10107-015-0880-7.
O problema do secretário
A ciência da computação tem um problema, na avaliação de especialistas. Na verdade, vários, mas um que, uma vez resolvido, ajudaria a solucionar os demais com maior eficiência: a questão P versus NP, que, em termos gerais, busca averiguar quais problemas computacionais podem ser resolvidos eficientemente por algoritmos “espertos” (P) e quais, aparentemente, só podem ser resolvidos testando-se uma a uma as respostas possíveis (NP).
O que o algoritmo desenvolvido no IME faz para a análise de uma árvore filogenética é eliminar, entre certos algoritmos “espertos”, as possíveis respostas que não têm chance de ser a melhor solução.
“Trata-se de um esforço de muitos pesquisadores, que trabalham para desenvolver algoritmos para problemas para os quais ainda não se conhecem algoritmos eficientes. Cada vez que um pesquisador descobre uma solução eficiente, aumenta a quantidade de problemas que sabemos estar na classe P, mostrando que certos problemas computacionais admitem soluções eficientes”, contou Yoshiharu Kohayakawa, também do IME, membro da comissão organizadora da São Paulo School of Advanced Science on Algorithms, Combinatorics and Optimization.
Entre os mais eminentes pesquisadores dedicados a encontrar soluções ótima para problemas complexos está Robert Kleinberg, da Cornell University, nos Estados Unidos, que ministra ao longo do curso aulas sobre busca estocástica combinatória, campo da Matemática usado para modelar sistemas que se comportam de forma aleatória, mas seguindo as leis da probabilidade.
“As aulas se concentram em problemas que envolvem projetar algoritmos para decisões em face de incertezas sobre futuras entradas e restrições combinatórias. Um exemplo disso é o clássico ‘problema do secretário’, estudado extensivamente nos campos de probabilidade aplicada, estatística e teoria da decisão”, disse Kleinberg.
O problema propõe um cenário em que um administrador pretende contratar o melhor secretário entre todos os candidatos disponíveis. A decisão sobre cada candidato deve ser tomada imediatamente após a entrevista e, uma vez rejeitado, o requerente não pode ser recuperado. O administrador pode classificá-lo com base nas entrevistas anteriores, mas não tem conhecimento das qualidades dos candidatos que ainda não foram entrevistados.
“Que estratégias adotar, então, para saber a hora de encerrar as entrevistas sem diminuir a probabilidade de selecionar o melhor candidato? Se a decisão pudesse ser adiada até que todos fossem entrevistados, o algoritmo para se chegar a uma resposta ótima seria simples, considerando que as qualidades de todos os candidatos são conhecidas. No caso de precisar contratar a pessoa imediatamente, o algoritmo ótimo opera no sentido de privilegiar o melhor candidato com base na quantidade de entrevistas que serão feitas: se você entrevistar apenas três candidatos, a melhor solução é se basear no segundo concorrente – se ele for melhor que o primeiro, você o contrata; se não for, contrata o terceiro e último candidato. Caso sejam cinco pessoas, você precisa esperar até a terceira para começar a formar sua decisão, e assim por diante”, explicou.
As aulas de Kleinberg e dos demais pesquisadores que compõem a programação da São Paulo School of Advanced Science on Algorithms, Combinatorics and Optimization seguem até o dia 29 de julho, no Centro de Difusão Internacional da USP, no campus da capital paulista.
“O curso é mais um dos esforços da FAPESP para promover interações entre os pesquisadores e as instituições de pesquisa no Estado de São Paulo com a comunidade científica internacional, apresentando ao mundo as grandes contribuições e os potenciais locais e também atraindo jovens e brilhantes pesquisadores de todos os continentes para trabalhos em parceria”, disse Carlos Henrique de Brito Cruz, diretor científico da Fundação, na abertura da programação.
O reitor da USP, Marco Antonio Zago, destacou na ocasião a importância do fomento ao intercâmbio científico promovido pelo curso. “A FAPESP tem contribuído para tornar ainda mais diversos o universo acadêmico e a pesquisa realizada no Estado de São Paulo ao apoiar a realização de cursos como este e também por meio de outras modalidades de apoio. A USP está de portas abertas”, declarou.
Além de Zago e Brito Cruz, participaram da abertura Clodoaldo Grotta Ragazzo, diretor do IME, Marcelo Viana, diretor-geral do Instituto Nacional de Matemática Pura e Aplicada (Impa), e Roberto Marcondes César Junior, da Coordenação Adjunta de Ciências Exatas e Engenharias da FAPESP.
Mais informações sobre a São Paulo School of Advanced Science on Algorithms, Combinatorics and Optimization estão disponíveis em sp-school2016.ime.usp.br.
Agência FAPESP
