Carlos Eduardo Ferreira
Em uma cidade enorme como, por exemplo, São Paulo, que possui uma variedade gigantesca de ruas e caminhos, como é possível calcular o menor percurso entre dois pontos? Na linha de produção de uma empresa que corta ferro para produzir vigas, qual o melhor corte na matéria-prima que resulta na menor sobra possível de material? São esses e outros tipos de problemas matemáticos que podem ser resolvidos pelo grupo de Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, do Instituto de Matemática e Estatística (IME) da USP.
O projeto temático é liderado pelo professor Carlos Eduardo Ferreira e nele são estudadas estruturas combinatórias a partir da Teoria dos Grafos. “Um grafo é um objeto matemático capaz de representar situações de estruturas combinatórias como, por exemplo, uma mesa em torno da qual estão sentadas seis pessoas que se conhecem. Nessa situação, necessariamente, três dessas pessoas serão ou amigas ou inimigas entre si”, afirma Ferreira. Veja abaixo o motivo.
Todos esses problemas – o caso das 6 pessoas, ou o menor caminho entre dois pontos de uma cidade – são questões comuns do dia a dia, mas que podem ser traduzidas para a linguagem matemática. Sendo assim, muitas situações podem ser analisadas por estruturas combinatórias, e é por isso que o grupo presta assistência a pesquisadores de outros institutos que precisem analisar algum problema matemático. “Quando alguém nos apresenta um novo problema, ou nós desenvolvemos uma teoria sobre o assunto – na qual analisamos se é possível ou não resolver essa questão matematicamente – ou propomos um algoritmo”, comenta.
Um algoritmo é apenas a transcrição de uma ideia para resolver um problema matemático. O mais importante é sempre a ideia, e apenas em seguida essa solução é traduzida para a fórmula matemática, que nada mais é que uma linguagem para o computador entender.
Ferreira conta, inclusive, que para algumas situações – como uma empresa que quer encontrar o melhor corte de uma matéria-prima para não perder muito material na sobra – a forma ideal de resolução seria enumerar todas as possibilidades. “Isso demoraria muito tempo e o computador ficaria rodando durante anos para resolver apenas essa questão. Então nós também temos que prever situações como essa para que, do ponto de vista prático, seja possível resolver os problemas. Para isso, existem os algoritmos de aproximação. São soluções que não dão o melhor jeito possível, mas dão um resultado aproximado com um erro percentual mínimo controlado”, diz.
Em busca de padrões
Uma das linhas de pesquisa do grupo diz respeito à mineração de dados e busca de padrões. Quando, por exemplo, usamos no computador uma ferramenta de busca para encontrar uma palavra específica – seja em um texto acadêmico, ou no catálogo de uma biblioteca – estamos usando o princípio aplicado da análise combinatória. A palavra que estamos buscando constitui um padrão que se repete em meio ao texto, e o algoritmo é capaz de encontrá-lá. Nesse exemplo, o padrão é muito bem definido – afinal, é apenas uma palavra –, mas o professor conta que é possível encontrar padrões muito mais sofisticados.
Mineração de dados significa elaborar uma maneira matemática de olhar para todas as informações levantadas e extrair os padrões que lá houverem.
Em uma parceria com alguns biólogos do Instituto de Biociências (IB), o grupo do IME desenvolveu um algoritmo para encontrar padrões nas proteínas de DNA entre seres vivos diferentes. A pesquisa dos biólogos tinha a intenção de determinar quão distante da cadeira evolutiva um ser vivo estava do outro, e para traçarem essa árvore genealógica buscaram a ajuda do IME.
“Havia na pesquisa a hipótese dos biólogos de que quando as proteínas do DNA eram mais parecidas, esses seres apresentavam ancestrais mais próximos. Nosso papel, então, foi de elaborar uma maneira matemática de olhar para todos os dados levantados pelos biólogos e extrair os padrões que havia lá. Isso é o que chamamos de mineração de dados. Em seguida, os padrões encontrados pelos algoritmos que criamos podem tanto reforçar aquela teoria, quanto contestá-la”, diz.
Algoritmos e equipamentos
Um algoritmo é apenas a transcrição de uma ideia para resolver um problema matemático. O mais importante é sempre a ideia, e apenas em seguida essa solução é traduzida para a fórmula matemática, que nada mais é que uma linguagem para o computador entender. Sendo assim, embora seja parte das ciências exatas, as estruturas combinatórias exigem muita criatividade dos matemáticos, pois cada problema, e cada solução, são únicos.
“A ideia é que é a essência do algoritmo. Nós da matemática costumamos brincar que só precisamos de papel, lápis e lata de lixo para resolver um problema. Boa parte da nossa pesquisa é no papel, fazendo rascunhos de algoritmos. Passá-lo depois para o computador já é algo trivial. O difícil é ter a certeza de que aquela fórmula vai ser capaz de realizar todas as funções que se espera”, conta Ferreira.
Mais informações: email cef@ime.usp.br