*RAINDROP*

 COMBINATÓRIA E ALGORITMOS

Tópicos de pesquisa e equipe principal

Linhas de pesquisa

 O objetivo central da pesquisa proposta é investigar objetos combinatórios relevantes à matemática discreta e à teoria da computação, dando especial ênfase a aspectos estruturais clássicos, algorítmicos e não algorítmicos, e a aspectos envolvendo a complexidade dos objetos de interesse. Os aspectos específicos a serem abordados serão aqueles motivados (i) por seu interesse intrínseco, de acordo com a literatura da área de matemática discreta, e (ii) pela sua importância para o desenvolvimento de algoritmos eficientes para problemas computacionais combinatórios específicos ou para a identificação da complexidade computacional de tais problemas.

 Os problemas a serem abordados neste projeto pertencem às seguintes linhas de pesquisa:

  1. Problemas estruturais sobre grafos, hipergrafos e matróides
  2. Combinatória extremal, probabilística e assintótica
  3. Algoritmos sobre estruturas discretas e aplicações
  4. Problemas combinatórios em biologia computacional

 Certos aspectos das linhas de pesquisa acima são discutidos em uma seção separada à frente.

Algumas atividades nesta área mesclam-se com atividades em áreas correlatas como as áreas de otimização e probabilidade. Parte significativa da pesquisa a ser realizada em combinatória probabilística acontecerá no âmbito do NUMEC, Núcleo de Modelagem Estocástica e Complexidade, um Núcleo de Pesquisa da USP.

Equipe envolvida

A equipe da área de combinatória, algoritmos, e teoria da computação é constituída dos pesquisadores listados abaixo e seus colaboradores.

 Colaboradores, afiliação, titulação e especialidades:

Alair Pereira do Lago (USP), Arnaldo Mandel (USP), Arnaldo Vieira Moura (UNICAMP), Carlos Eduardo Ferreira (USP), Carlos Gustavo T. de A. Moreira (IMPA), Carlos Hoppen (USP, postdoc), Carlos Tomei (PUC Rio), Celina Miraglia Herrera de Figueiredo (UFRJ); Christiane Neme Campos (USP, postdoc), Cristina Gomes Fernandes (USP),  Eduardo Candido Xavier (UNICAMP), Eduardo Sany Laber (PUC Rio), Ernesto Julián Goldberg Birgin (USP), Flávio Keidi Miyazawa (UNICAMP), Jair Donadelli Júnior (UFPR), José Augusto Ramos Soares (USP), José Coelho de Pina Júnior (USP), Manoel Lemos (UFPE), Marcelo Henriques de Carvalho (UFMS), Maya Jakobine Stein (USP, postdoc), Nicolau Corção Saldanha (PUC Rio), Orlando Lee (UNICAMP), Paulo Feofiloff (USP), Renato José da Silva Carmo (UFPR), Ricardo Dahab (UNICAMP), Roberto Imbuzeiro Oliveira (IMPA), Sóstenes Lins (UFPE), Yoshiharu Kohayakawa (USP), Yoshiko Wakabayashi (USP),

Formação de recursos humanos

Esta equipe conta atualmente com 3 pós-doutores, 10 alunos de doutorado, 24 alunos de mestrado, e 15 alunos de iniciação científica. Objetivamos dobrar estes números ao longo dos 5 anos de vigência deste projeto.

Colaboradores estrangeiros e intercâmbio internacional

Colaboradores internacionais

 Os seguintes pesquisadores, amplamente reconhecidos, têm sistematicamente apoiado a pesquisa na área de combinatória, algoritmos, e teoria da computação no país:

  •  N. Alon (Tel Aviv U., Israel)
  • B. Bollobás (Cambridge)
  • M. Grötschel (TU Berlim e ZIB Berlim)
  • T. Luczak (Poznan, Polônia)
  • B. Reed (McGill, Montreal)
  • V. Rödl (Emory, Atlanta)
  • J. Spencer (Courant, NYU)
  • E. Szemerédi (Rutgers)

 Ademais, a nossa equipe conta com a colaboração dos seguintes destacados pesquisadores estrangeiros e de membros de seus grupos: R. Cordovil (IST, Lisboa), J. Correa (U. Chile, Santiago), L.H. Kauffman (U. Illinois, Chicago), M. Kiwi (U. Chile, Santiago), C.H.C. Little (Massey U., Nova Zelândia), A. Martin (T.U. Darmstadt), C. Mauduit (IML, Marselha), A.J. Menezes (U. of Waterloo), U.S.R. Murty (U. of Waterloo), J.G. Oxley (Louisiana State), D. Panário (Carleton U.), M. Scott (Dublin City U.), A. Taraz (T.U. Munique), M.-F. Sagot (INRIA, Rhône-Alpes), M. Schacht (Humboldt, Berlim), M. Simonovits (Instituto Rényi, Budapeste), A. Steger (ETH Zurique), A. Viola (U. de la República, Uruguai).

Intercâmbio internacional

Planejamos um fluxo contínuo de visitantes estrangeiros ao país e viagens dos membros da equipe aos centros dos colaboradores estrangeiros.

Encontros científicos

 Workshops

Pesquisadores desta área têm organizado workshops temáticos de forma regular, com freqüência próxima de dois workshops por ano. Sob este projeto, esta prática será continuada, aumentando o tamanho dos encontros, incluindo um maior número de alunos. Para o financiamento de tais workshops, solicitamos a este projeto 20 diárias nacionais por workshop, totalizando 200 diárias (nos 5 anos), parte considerável delas a ser usada para alunos de pós-graduação e iniciação científica.

Conferência internacional e PASI

Planejamos para o verão de 2011 um encontro de maior envergadura, conjugado com um instituto do programa PASI, Pan-American Advanced Studies Institutes Program, da NSF (EUA). O foco do PASI será em tópicos específicos da área de combinatória, algoritmos, e teoria da computação, e os coorganizadores estrangeiros serão Béla Bollobás (Cambridge) e János Simon (Chicago). 

Os números acima são um tanto modestos, pois levamos em conta a existência de outras fontes, como a FAPESP, FAPERJ, CNPq e CAPES.

Breve discussão das linhas de pesquisa

Nesta seção, descrevemos sucintamente certas facetas das linhas de pesquisas que esta equipe planeja investigar neste projeto. Observamos que, embora sejam de natureza central para esta equipe, os tópicos de pesquisa discutidos abaixo não esgotam os interesses e campos de atuação desta equipe.

Problemas estruturais sobre grafos, hipergrafos e matróides

Problemas estruturais fundamentais, de natureza variada, serão atacados nesse projeto.

A equipe inclui um especialista da área de conectividade de matróides, M. Lemos. Este parâmetro para matróides, definido por Tutte em 1960, aparece de maneira fundamental em teoremas de decomposição e em algoritmos envolvendo estas estruturas combinatórias. Os trabalhos deste pesquisador sobre aspectos estruturais de matróides envolvem várias propriedades ligadas à conectividade, e uma série de teoremas de remoção. Estes mostram que, sob hipóteses apropriadas e naturais, vários circuitos e elementos especiais podem ser removidos sem que a conectividade baixe. São resultados que apresentam uma estrutura indutiva não trivial para matróides de alta conectividade com implicações teóricas que merecem ampla investigação.

Será também objeto de estudo a estrutura de grafos pfaffianos (cuja definição omitimos; observamos apenas que o número de emparelhamentos perfeitos em grafos pfaffianos pode ser computado eficientemente).  A investigação dessa classe de grafos é uma área de pesquisa rica. Um resultado clássico é devido a Kasteleyn (1963), que provou que todo grafo planar é pfaffiano. Grafos bipartidos pfaffianos são hoje bem entendidos.  Um problema central nessa área é como testar eficientemente se um dado grafo genérico é pfaffiano.

 Combinatória extremal, probabilística e assintótica

Combinatória extremal estuda quão grande ou quão pequeno pode ser um objeto (uma seqüência, um grafo, uma configuração de pontos, etc.) que satisfaz certas restrições. Um exemplo clássico da teoria extremal dos grafos, que teve Paul Erdos como o seu principal expoente, é o teorema de Turán (1940), que diz qual é o maior número de arestas possível em um grafo com n vértices que não possui um dado subgrafo completo.

Uma arma poderosa no estudo de problemas extremais de grafos é o lema de regularidade de Szemerédi (1978) e suas diversas variantes. Os problemas específicos a serem estudados neste tópico são, na maioria, problemas envolvendo a inter-relação entre os vários lemas de regularidade desenvolvidos recentemente e algumas aplicações específicas desses lemas. Membros do grupo têm investigado aplicações e extensões deste lema estrutural fundamental de Szemerédi há vários anos. O vigor da pesquisa em torno do tópico que propomos é ilustrado por trabalhos recentes de Alon, Elek, Gowers, Lovász, Rödl, Schacht, Szegedy, e Tao, dentre outros.

Uma linha de pesquisa a ser investigada, relacionada com regularidade, consiste no estudo de noções adequadas para objetos limites de seqüências convergentes de grafos esparsos e suas aplicações. Tal estudo terá como ponto de partida trabalhos de Benjamini e Schramm e Elek.

Membros desta equipe têm investigado seqüências sobre alfabetos finitos sob o ponto de visto extremal e probabilístico. Mais recentemente, Mauduit e Moreira têm estudado conjuntos de seqüências infinitas sobre alfabetos finitos com complexidade limitada por uma certa função. São objetos de estudo propriedades geométricas e dimensões fractais generalizadas de tais conjuntos. Resultados nessa direção envolvem aspectos dinâmicos e combinatórios.

Algoritmos sobre estruturas discretas e aplicações

Na área de otimização combinatória, o desenvolvimento de algoritmos de aproximação e provas de inaproximabilidade de certos problemas é uma das linhas de pesquisa que mais cresceu ultimamente. Esta observação encontra respaldo na grande concentração de artigos de pesquisa nessa linha que surgiram nos últimos anos, e também de livros mostrando o amadurecimento dessa subárea, e o seu reconhecimento como uma disciplina importante.  Vários membros deste grupo trabalham há anos com algoritmos de aproximação. Assim, dando continuidade a esse trabalho, uma das linhas de pesquisa adotadas dentro deste tópico será a busca por tais algoritmos e, quando pertinente, por resultados de inaproximabilidade. Como ilustração, mencionamos dois problemas específicos que serão sob esta ótica: (1) Dado um grafo conexo, encontrar uma árvore geradora com número máximo de folhas. (2) Dado um grafo G e uma família de grafos F, encontre um subgrafo H de G tal que cada componente conexa de H seja um grafo da família F, e tal que H tenha o maior número possível de arestas.

Além de algoritmos de aproximação, algoritmos online e problemas algorítmicos na interface com a área de economia/teoria dos jogos (“teoria algorítmica dos jogos”) serão considerados, seguindo uma forte tendência na área de teoria da computação contemporânea.

Outra linha de pesquisa de interesse de membros desta esquipe relaciona-se com geometria computacional em dimensão alta e redução de dimensionalidade. Aqui estamos interessados na geometria de conjuntos de pontos, politopos e variedades alojados dentro de um espaço euclideano de dimensão alta. Em particular, estamos interessados em maneiras eficientes de representar tais conjuntos de forma sucinta ou em um número reduzido de dimensões sem que sua geometria seja excessivamente deformada. Tais métodos têm grande importância na resolução de problemas que poderiam ser afetados adversamente pelo número excessivo de

dimensões do espaço ambiente (curse of dimensionality) e também estão relacionados aos avanços recentes na teoria algorítmica de espaços métricos. Sob este projeto, vários pesquisadores do grupo investirão considerável energia nesta direção.

 Problemas combinatórios em biologia computacional

A combinatória das palavras têm ganhado bastante importância com o desenvolvimento de algoritmos que possibilitam a análise, processamento e extração de informações em seqüências cada vez mais compridas, sejam elas textos disponíveis na internet, bibliotecas digitais ou seqüências genômicas. Face às dimensões cada vez maiores destas seqüências, algoritmos eficientes (lineares e até sublineares) têm sido cada vez mais requisitados. De fundamental importância são certas estruturas de dados, como as árvores de sufixos. As árvores de sufixos e as tabelas necessárias à resolução do problema do menor ancestral comum são duas das estruturas de dados mais avançadas e importantes à elaboração de algoritmos eficientes que possam ser utilizados no estudo de seqüências extremamente compridas. Recentemente, Lago e Simon escreveram um livro que aborda novamente os dois problemas e que apresenta alguns algoritmos eficientes para a construção e uso eficiente destas estruturas.

Três são os algoritmos mais conhecidos que constrõem uma árvore de sufixos em tempo linear no comprimento da palavra: o de Weiner, o de McCreight e o algoritmo on-line de Ukkonen. O algoritmo de construção em tempo linear da árvore de sufixos como é reapresentado por Lago e Simon baseia-se no de McCreight, de forma a incluir duas generalizações em relação ao que é encontrado na literatura: (1) a palavra cuja árvore de sufixos é construída pode possuir a última letra que não é distinta das anteriores; (2) os sufixos são tomados de um conjunto de várias palavras. Numa das aplicações apresentadas, o problema da busca de padrões de comprimento m com até k erros (mismatches) num texto de comprimento n, é resolvido em tempo O(kn) (em contraposição a uma solução ingênua O(mn)) envolvendo as duas estruturas de dados acima mencionadas.

Dentro deste tópico, pesquisadores deste projeto têm como objetivo a ampliação da referida abordagem feita em relação às árvores de sufixos de forma a incluir duas melhorias, sem detrimento das generalizações anteriores: (1) aproveitando-se de idéias de Ukkonen, alterar o algoritmo de construção em tempo linear de forma que o mesmo seja online; (2) dado um conjunto dos sufixos da(s) palavra(s) em questão, construir em tempo linear ao tamanho do conjunto uma árvore de sufixos em que sejam soletráveis a partir da raiz apenas os sufixos presentes neste conjunto. Planeja-se também o estudo de representações eficientes dos autômatos que permeiam os algoritmos ora comentados.