PARTE I - RESUMO DOS DADOS BÁSICOS DO NÚCLEO DE PESQUISA E DO PROJETO

DADOS PESSOAIS DO COORDENADOR DO NÚCLEO

• Nome completo (sem abreviações): Yoshiharu Kohayakawa

• Endereço Funcional: IME-USP, Rua do Matão 1010, Cidade Universitária

• Bairro: Butantã Cidade: São Paulo UF: SP

• CEP: 05508-900

• Fone: (011) 818-6135 Ramal:

• Fax: (011) 818-6134

• E-mail: yoshi@ime.usp.br

DADOS SOBRE OS PESQUISADORES PRINCIPAIS DO NÚCLEO

NOME  TITULAÇÃO
Sóstenes Luiz Soares Lins (UFPE)  Ph.D.  Pesq. CNPq Nível 1B
Cláudio L. Lucchesi (UNICAMP)  Ph.D.  Pesq. CNPq Nível 1C
Yoshiko Wakabayashi (USP)  Dr. rer. nat. Pesq. CNPq Nível 1C
Yoshiharu Kohayakawa (USP)  Ph.D.  Pesq. CNPq Nível 2A
Manoel José M. Soares Lemos (UFPE)  D.Phil.  Pesq. CNPq Nível 2A
Celina Miraglia H. Figueiredo (UFRJ)  Ph.D.  Pesq. CNPq Nível 2B
João Meidanis (UNICAMP)  Ph.D.  Pesq. CNPq Nível 2C

DADOS DO NÚCLEO DE PESQUISA

• Grande Área do Conhecimento predominante nas atividades desenvolvidas pelo núcleo: Ciências da Vida X Ciências Exatas e da Terra Ciências Humanas e Sociais Ciências da Vida

• Área do Conhecimento predominante nas atividades desenvolvidas pelo núcleo:

Combinatória (Teoria da Computação e Matemática)

DADOS DA INSTITUIÇÃO SEDE

(INSTITUIÇÃO QUE SE RESPONSABILIZA PELO NÚCLEO)

• Nome completo e Sigla: Universidade de São Paulo (USP)

• CGC: 63.025.530/0008-80

• Órgão (instituto, faculdade): Instituto de Matemática e Estatística

• Unidade (departamento, divisão, laboratório): Departamento de Ciência da Computação

• Nome do dirigente responsável pela Instituição: Carlos Alberto de Bragança Pereira

• Cargo: Diretor DADOS DA INSTITUIÇÃO CONVENENTE

(PESSOA JURÍDICA HABILITADA A FIRMAR O CONVÊNIO)

• Nome completo e Sigla: Instituto de Matemática e Estatística da Universidade de São Paulo (IME/USP)

• CGC: 63.025.530/0008-80

• Tipo: Privada Municipal X Estadual

• Endereço: Rua do Matão 1010 – Cidade Universitária Bairro: Butantã

• CEP: 05508-900  Cidade: São Paulo  UF: SP
• Caixa Postal:  Telefone: (011) 818-6135  Fax: (011) 818-6134

• Nome do dirigente: Carlos Alberto de Bragança Pereira

• CPF no. 185395568/04 Identidade: 5383251 Órgão Expedidor: SSP/SP

DADOS DAS DEMAIS INSTITUIÇÕES PARTICIPANTES

• Nome Completo e Sigla: Universidade Estadual de Campinas (UNICAMP)

• CGC: 46.068.425/0001-33

• Órgão (instituto, faculdade): Instituto de Computação

• Unidade (departamento, divisão, laboratório):

• Nome do dirigente responsável pela Instituição: Tomasz Kowaltowski

• Cargo: Diretor

• Nome Completo e Sigla: Universidade Federal de Pernambuco (UFPE)

• CGC: 24.134.488/0001-08

• Órgão (instituto, faculdade): Centro de Ciências Exatas e da Natureza

• Unidade (departamento, divisão, laboratório): Departamentos de Informática e de Matemática • Nome do dirigente responsável pela Instituição: Cid Bartolomeu de Araujo

• Cargo: Diretor do Centro de Ciências Exatas e da Natureza

• Nome Completo e Sigla: Universidade Federal do Rio de Janeiro (UFRJ)

• CGC: 33663683/001-16

• Órgão (instituto, faculdade): Instituto de Matemática

• Unidade (departamento, divisão, laboratório): Departamento de Ciência da Computação

• Nome do dirigente responsável pela Instituição: Luis Paulo Braga

• Cargo: Diretor

• Nome Completo e Sigla: Universidade Federal de Mato Grosso do Sul (UFMS)

• CGC: 15.461.510/00001-33

• Órgão (instituto, faculdade): Centro de Ciências Exatas e Tecnologia

• Unidade (departamento, divisão, laboratório): Departamento de Computação e Estatística

• Nome do dirigente responsável pela Instituição: Jorge João Chacha

• Cargo: Reitor APRESENTAÇÃO CONCISA DO NÚCLEO E DO PROJETO DE PESQUISA

Título do Projeto

Complexidade de Estruturas Discretas

I - Descrição clara do Núcleo e de sua origem

O Núcleo é formado por 25 pesquisadores, sendo 9 da USP, 6 da UNICAMP, 4 da UFPE, 3 da UFRJ e 3 da UFMS. Dezesseis desses pesquisadores fizeram o doutorado no exterior em instituições de grande prestígio, entre as quais destacamos a Universidade de Cambridge, Waterloo, Chicago, Wisconsin, Oxford e TU Berlin. Quatro desses pesquisadores obtiveram o doutorado no Brasil; e os três outros são mestres, engajados em programas de doutorado.

Traçando um histórico sobre a formação desse grupo, que praticamente coincide com a formação do grupo de Combinatória no país, cabe aqui mencionar o papel importante que o Departamento de Combinatória da Universidade de Waterloo teve neste processo.

Cinco dos pesquisadores deste grupo (Lucchesi, Mandel, Lins, Feofiloff e Dahab) fizeram o doutorado na Universidade de Waterloo, um dos centros internacionais mais prestigiados na área de Combinatória. Trabalharam sob a orientação de D. Younger e J. Edmonds, trazendo grandes contribuições à área de combinatória.

O célebre Teorema de Lucchesi–Younger (de 1976), um dos teoremas min-max mais citados na área de combinatória; o trabalho internacionalmente reconhecido de A. Mandel em matróides orientados (1982); e os livros de S. Lins sobre variedades (um pela editora da Universidade de Princeton e outro pela World Scientific), que tiveram grande receptividade junto à comunidade internacional da área, são motivos de grande orgulho para nós, pesquisadores brasileiros, pelo respeito que esses pesquisadores angariaram para a nossa comunidade.

Esse contato com a Universidade de Waterloo tem trazido benefícios contantes à comunidade brasileira, na forma de visitas periódicas de pesquisadores dessa instituição, que através desse grupo inicial, passaram a manter um contato mais estreito com nossas instituições.

Cláudio Lucchesi, juntamente com Imre Simon (USP) —que também se doutorou em Waterloo— e Jayme Szwarcfiter (UFRJ), podem ser considerados os pioneiros no Brasil, na área de Combinatória. I. Simon, reconhecido internacionalmente por seus trabalhos na área de Autômatos Finitos, foi um dos fundadores do Departamento de Computação da USP, tendo sido o orientador de mestrado de quatro dos pesquisadores do Núcleo: A. Mandel, P. Feofiloff, Y. Wakabayashi e M.A. Gurgel. (J. Szwarcfiter participa atualmente do ProNex-I, razão de sua ausência neste grupo. Formou os 3 pesquisadores da UFRJ que integram este projeto, C.M.H. Figueiredo, S. Klein, M.R. Cerioli, e participou ativamente das atividades desenvolvidas por um subgrupo do Núcleo no projeto ProComb do ProTeM-CC-II/CNPq.)

Excetuando esse grupo formado em Waterloo, houve uma grande diversificação quanto aos centros onde se formaram os demais pesquisadores. Y. Kohayakawa, o coordenador deste projeto, foi orientado por A. Mandel no mestrado, e obteve o seu doutorado em Cambridge, sob a orientação de B. Bollobás, um dos pesquisadores de maior prestígio em Teoria Extremal e Grafos Aleatórios. Y. Kohayakawa tem a sua formação calcada na tradição da escola húngara (centrada na figura de P. Erdős), e como todos os seus seguidores, tem uma produção científica respeitada e altamente prolífera.

Na área de Otimização Combinatória, quatro pesquisadores (Wakabayashi, Ferreira, Pina Jr e Souza) trabalharam sob orientação de grandes expoentes nessa área: M. Grötschel, A. Schrijver e L. Wolsey, todos eles reconhecidos internacionalmente e detentores de prêmios pelas suas contribuições científicas (Fulkerson Prize, Leibnitz Prize, Lanchester Prize). O treinamento que esses pesquisadores obtiveram os colocam entre os pioneiros na área de Combinatória Poliédrica no Brasil.

O pesquisador M. Lemos (UFPE), que trabalhou em Matróides, foi orientado por J. Oxley, em Oxford; J.A.R. Soares (USP) foi orientado por L. Babai em Teoria da Computação; ambos os orientadores, especialistas competentíssimos em suas áreas. Por uma questão de espaço, não nos estenderemos mais a respeito dos demais pesquisadores, mas cumpre ressaltar que todos eles foram orientados por pesquisadores de grande renome.

A maioria dos integrantes do Núcleo são pesquisadores de Departamentos ou Institutos de Ciência da Computação, sendo que os demais são pesquisadores pertencentes a Departamentos de Matemática. De fato, a pesquisa em Combinatória realizada pelo grupo se situa na fronteira da Teoria da Computação e Matemática.

Problemas de caráter combinatório ocorrem freqüentemente em várias áreas da Matemática e são fundamentais em essencialmente todas as áreas da Teoria da Computação. A Teoria da Computação, por sua vez, dá o fundamento teórico sobre o qual a Ciência da Computação se apóia, e é de fato a existência de tal fundamento sólido que a caracteriza como uma ciência. Ademais, é a teoria que proporciona à Ciência da Computação uma robustez capaz de absorver o rápido desenvolvimento da tecnologia de forma mais eficiente possível.

Como reflexo dessa forte relação entre a Combinatória e Computação, o crescimento da área de Combinatória no Brasil coincide com o fortalecimento da área de Computação, que nas últimas décadas recebeu um grande impulso. De fato, a maioria dos integrantes do Núcleo, surgiram nos departamentos de Computação: na USP cresceram sob a liderança de I. Simon; na UNICAMP, sob a liderança de C. Lucchesi; na UFPE, sob a liderança de S. Lins; e na UFRJ, sob a liderança de J. Szwarcfiter.

A presença marcante dos integrantes deste projeto no cenário nacional, pode ser notada pelas suas contribuições na publicação de textos e mini-cursos em eventos tradicionais como o Colóquio Brasileiro de Matemática (CBM) e Escola de Computação (EC). Só para citar alguns textos, cabe aqui mencionar Lucchesi et al. (“Aspectos Teóricos da Computação”, CBM, 1977), Lins (“Princípios de Enumeração”, CBM, 1981),Mandel (“Sistemas de Desigualdades Lineares”, CBM, 1983), Lucchesi e Feofiloff (“Algoritmos para Igualdades Minimax em Grafos”, EC, 1988), Meidanis e Setubal (“Uma Introdução à Biologia Computacional”, EC, 1994), Kohayakawa e Soares (“Demonstrações Transparentes e a Impossibilidade de Aproximações”, CBM, 1995), Ferreira e Wakabayashi (“Combinatória Poliédrica e Planos-de-Cortes Faciais”, EC, 1996).

Lembramos que as já tradicionais Sessão de Combinatória dos Colóquios Brasileiros de Matemática e eventos como o Workshop Internacional de Combinatória (UNICAMP, UFRJ) e Semana da Combinatória na USP, têm sido sistematicamente organizados por pesquisadores do Núcleo. Alguns desses pesquisadores também já organizaram eventos como a Escola de Computação e LATIN (Latin American Theoretical INformatics).

A presença atuante dos integrantes deste projeto no cenário nacional, mostra que se trata de fato de um grupo de excelência na área de combinatória, que tem trazido grandes contribuições ao país, atuando na formação de recursos humanos de alta qualidade e obtenção de resultados científicos de grande relevância.

Essa atuação tem sido quase sempre às custas de esforço individual, tendo exigido constantes pedidos de auxílios às agências financiadoras (CNPq, CAPES, FAPESP) para viabilizar visitas e organização de eventos. Parte desse quadro mudou com a participação de uma boa parte desses pesquisadores (16) no projeto ProComb, subvencionado pelo ProTeM-CC-II-CNPq (jan/95 a abr/97).

Cabe aqui ressaltar que o Núcleo deste projeto tem como base os integrantes do projeto ProComb (veja em http://www.ime.usp.br/mac/procomb/). Sob a coordenação de Y. Wakabayashi, o ProComb, constituído por 20 pesquisadores (USP, UNICAMP, UFRJ e PUC-RJ), permitiu uma maior integração desse grupo, mostrando que projetos dessa natureza vêm de encontro às necessidades da comunidade acadêmica. Através do ProComb foram organizados 3 Oficinas Nacionais e um Workshop Internacional de Combinatória. Seus integrantes puderam viajar no país e ao exterior (para congressos e visitas mais longas) e trazer visitantes. Esse projeto foi importantíssimo para uma maior integração dos pesquisadores na área de Combinatória. Acreditamos porém, que apenas começamos a colher os primeiros frutos dessa integração. É essencial que haja um incentivo contínuo dessa natureza, para consolidar o grupo e a área.

Os resultados altamente positivos dessa integração podem ser deduzidos da produção científica decorrente desse projeto: mais de 30 artigos em periódicos internacionais com arbitragem, 4 livros e cerca de 30 publicações em anais de congressos nacionais e internacionais,

A adesão de novos membros à equipe do ProComb (Lucchesi – UNICAMP; S. Lins, M. Lemos, C. Martins e K. Guimarães – UFPE) se justifica plenamente, pelo contato pré-existente e pela área de atuação. Esses pesquisadores participaram de eventos organizados pelo ProComb, e têm mantido contato convidando e sendo convidados para participar de bancas de mestrado ou doutorado de seus alunos.

Essa adesão vem simplesmente concretizar um contato já existente, e a vontade expressa por esses pesquisadores de participar conjuntamente em um projeto nos moldes do ProComb, que se mostrou altamente positivo.

Com relação à UFMS, uma instituição emergente, é com muita satisfação que contamos com essa adesão. A UNICAMP, a USP e a UFRJ têm uma forte ligação com essa instituição na área de Combinatória, tendo formado vários mestres que se graduaram na UFMS. Um dos representantes da UFMS (Marcelo Henriques de Carvalho), fez o seu mestrado na USP e terminou recentemente o seu doutorado na UNICAMP; Nalvo Franco de Almeida Jr fez o mestrado na UFRJ e é doutorando da UNICAMP; Fábio H. Viduani Martinez fez o mestrado na USP e voltou recentemente para a UFMS, devendo se engajar num programa de doutorado em uma dessas instituições; na USP temos ainda um outro doutorando da UFMS.

II - O foco e a articulação das atividades de pesquisa propostas

O foco deste projeto é o estudo de aspectos estruturais e algorítmicos de objetos combinatórios. Esta área de pesquisa se justifica pelo seu interesse intrínseco (visto como um tópico de Matemática) e pela sua importância no desenvolvimento de algoritmos eficientes para problemas computacionais combinatórios, e na análise da complexidade computacional de tais problemas.

Vários dos pesquisadores do Núcleo participaram do projeto ProComb – Problemas Combinatórios: Teoria, Algoritmos e Aplicações, e vivenciaram o impacto positivo acarretado pela maior integração entre diversas instituições. Durante a realização do ProComb foram realizadas três oficinas nacionais; ocasiões em que praticamente todos os participantes se reuniram para discutir temas de pesquisa de interesse comum. Este tipo de atividade mostrou-se altamente produtivo. Visamos com este projeto dar continuidade à experiência adquirida com o ProComb, desta vez englobando novas instituições: Departamentos de Informática e de Matemática da Universidade Federal de Pernambuco e Departamento de Ciência da Computação da Universidade Federal de Mato Grosso do Sul.

Dentro de cada uma das instituições participantes a integração dos membros da equipe já é bastante intensa. Prova disso é, por exemplo, o ciclo de seminários em Combinatória realizados pelo Departamento de Matemática da UFPE, ou o projeto temático financiado pela FAPESP para os membros do Departamento de Ciência da Computação do IME–USP. Além de dar continuidade a essas atividades locais, regulares, pretendemos fomentar (através de visitas e oficinas) um maior intercâmbio entre as instituições para que os temas de interesse individual ou institucional passem a se beneficiar de uma interação maior com outras instituições.

Com relação aos tópicos de pesquisa contemplados, há que se ressaltar que os mesmos estão fortemente ligados pelas técnicas e abordagens inerentes ao aspecto em questão. Assim, por exemplo, ao se considerar o estudo da presença de certas estruturas em objetos combinatórios, podemos por um lado, estar interessados na existência ou na enumeração dessas estruturas, ou em algoritmos eficientes para se encontrá-las, ou ainda na análise da complexidade computacional de problemas relacionados a essas estruturas.

Há no Núcleo pesquisadores que, pela sua formação, atuam na linha mais teórica; outros, na busca de algoritmos, sejam determinísticos ou probabilísticos. Essa diversidade na formação específica, apoiada numa formação básica geral, que torna este grupo coeso, justifica a submissão deste projeto. O que esperamos aqui, é que essa diversidade venha a contribuir positivamente para que surjam novas colaborações, num processo dinâmico que transpõe as fronteiras institucionais.

III - Os avanços científicos ou tecnológicos decorrentes dos resultados esperados

A teoria é a principal ferramenta em que os avanços tecnólogicos se baseiam. O desenvolvimento de pesquisa científica em áreas como a Combinatória é de fundamental importância para o crescimento de outras áreas mais aplicadas da Ciência da Computação, como Computação Gráfica, Processamento de Sinais, Projeto de Redes Seguras, etc.

Com este projeto pretendemos integrar ainda mais fortemente os diversos grupos de pesquisa do país que trabalham com Combinatória. Esta integração agregará pesquisadores de todas as regiões do Brasil, e será uma mola propulsora da pesquisa na área. Diversos trabalhos conjuntos de pesquisadores envolvidos neste projeto mostram o potencial da equipe, e a enorme capacidade de trabalho em conjunto. Aumentar esta integração terá grande impacto na produção científica dos diversos grupos e na formação de pessoal na área.

Em resumo, objetivamos com o projeto uma maior integração dos pesquisadores da área no Brasil, o que favorecerá o aumento da quantidade de alunos formados em Combinatória que passarão a atuar em outras regiões do país. Outro impacto do projeto será o aumento da produção científica do grupo, que ocasionará destaque ainda maior do grupo nas comunidades científicas das áreas de Matemática e Ciência da Computação.

IV - A adequação da equipe para a realização do projeto

A equipe deste projeto tem como núcleo os integrantes do projeto ProComb (“Problemas Combinatórios: Teoria, Algoritmos e Aplicaçoes”– Processo 680065/94-6) dentro do ProTeM-CC-II/CNPq. Dos 25 pesquisadores, 16 deles participaram do ProComb. Esse projeto teve início em janeiro/95 e encerrou-se em abril/97.

A esse grupo do ProComb, juntaram-se alguns pesquisadores da UFPE (Sóstenes Lins, Manoel Lemos, Cleide Martins e Katia Guimarães), o pesquisador Cláudio Lucchesi, da UNICAMP, e os pesquisadores Marcelo Henriques de Carvalho, Nalvo Franco de Almeida Jr e Fábio Viduani Martins da UFMS.

A adequação da equipe para a realização do projeto pode ser justificada pelo entrosamento desse grupo durante a vigência do ProComb e os resultados altamente positivos dessa integração. Este projeto trouxe uma tranqüilidade financeira, no sentido de viabilizar oficinas regulares, vinda de pesquisadores estrangeiros, participação em eventos nacionais e internacionais, tendo dessa forma, contribuído decisivamente para o desenvolvimento da pesquisa nessa área.

A participação desses pesquisadores num projeto conjunto mostrou que um fator importante para que haja integração é a formação básica dos participantes. É essa formação básica que dá uma identidade ao grupo, destacando-a como uma entidade coesa, cujos membros se entendem e se comunicam através da mesma linguagem de pesquisa. O fato de o grupo se constituir numa audiência adequada para a divulgação da pesquisa que cada qual está realizando, e a organização de oficinas regulares onde todos se reúnem, trazem como benefício não apenas contribuições na forma de idéias e sugestões, mas motiva cada participante a contribuir com a sua parcela, num processo de auto-cobrança e de contágio pelo entusiasmo de outros participantes. Isto é altamente positivo.

Salientamos também que, não consideramos essencial que cada um dos integrantes trabalhe conjuntamente com um outro membro da equipe, para se concluir que há de fato uma colaboração. Isto certamente ocorre com a maioria dos integrantes, mas cabe-nos notar que, ainda que essa colaboração nao se traduza na forma de artigos conjuntos, o presente grupo tem uma unidade e um histórico que justifica a sua formação (veja o Item I).

Considerando-se a formação da equipe e e os laços existentes entre os seus integrantes, pode-se dizer que se trata de uma equipe com um alto potencial para alcançar os objetivos propostos. Esta certeza se apoia nos resultados que foram alcançados pelo projeto ProComb, cujos integrantes formam a base do Núcleo atual.

Mencionamos também que a ex-coordenadora do ProComb, Y. Wakabayashi, foi recentemente indicada para participar do Comitê Assessor de Ciência da Computação do CNPq. E que, outros membros do Núcleo, Cláudio Lucchesi e Sóstenes Lins, também já participaram desse Comitê. Lembramos também que Lucchesi faz parte do Comitê Assessor de Computação da FAPESP. Isso nos permite dizer que o grupo conta com uma liderança que vem trabalhando ativamente em prol da comunidade da área de Computação no país.

O coordenador desse projeto, Yoshiharu Kohayakawa, apesar de bastante jovem, já é livre-docente na USP e tem experiência em coordenar projetos de pesquisa. É coordenador de um projeto temático da FAPESP, de um projeto do PROBRAL (CAPES-DAAD) e de um projeto da Pró-Reitoria da USP, o ProInter (mais detalhes em seu curriculum vitae). Também tem sido o responsável pela organização de vários eventos na área.

Com o seu prestígio, tem conseguido atrair ao Brasil visitantes de grande renome na área de Combinatória (veja o Item Intercâmbio). Ressaltamos aqui apenas a visita de Paul Erdős, que nos honrou com a sua presença (por 3 semanas); sua visita ao Brasil foi a única a um país da América Latina. Essa visita contribuiu para que Y. Kohayakawa publicasse um artigo em co-autoria com P. Erdős, tornando-se assim o único brasileiro com Erdős–number 1. Os demais pesquisadores da equipe, excetuando os recémdoutores, são detentores de Erdős–number 2, 3 ou 4. Este fato, corrobora a presença marcante desse grupo na área de combinatória.

O grupo da USP é uma equipe cujos integrantes atuam nas três linhas de pesquisa deste projeto (veja Item “Estado-da-arte e objetivos”). Trata-se de um grupo que vem se reunindo regularmente em Seminários de Combinatória do departamento, tendo uma tradição em receber pesquisadores estrangeiros dessa área e organizar eventos dessa natureza. Conta atualmente com um visitante, o pesquisador Bruce Reed, que, pela sua versatilidade, certamente trará grandes contribuições ao projeto. Os pesquisadores deste grupo, C.E. Ferreira e Y. Wakabayashi, têm mantido contatos estreitos com o pesquisador C.C. de Souza, da UNICAMP. Este grupo vem atuando seriamente na formação de doutores, contando atualmente com 5 doutorandos.

O grupo da UNICAMP, formado sob a liderança de Lucchesi, tem uma forte interação com o grupo da UFRJ. Pesquisadores dessas duas instituições têm diversos trabalhos em conjunto (notadamente, Meidanis, Piccinin, Lucchesi, Figueiredo, Klein e Cerioli). O grupo da UFRJ tem contatos estreitos com os pesquisadores F. Maffray (França) e H. Everett (Canadá).

A equipe da UFPE é constituída por quatro pesquisadores que realizaram o doutorado em renomadas universidades no exterior. Como já mencionamos, um dos membros do Núcleo, publicou dois livros que foram muito bem recebidos pela comunidade matemática internacional. Completam a equipe os alunos, nos diversos níveis, orientados por pesquisadores vinculados ao Núcleo, que contribuirão na execução do projeto, em especial os doutorandos.

No primeiro ano de execução do projeto, o grupo da UFPE contará com o reforço de J.A. Bondy, que manifestou o interesse de visitar o Departamento de Matemática por um período de um ano. Sua área de pesquisa tem uma forte conexão com o trabalho realizado pelos membros da UFPE. Essa visita certamente trará grandes contribuições ao projeto, pois esse pesquisador poderá interagir também com outros pesquisadores do Núcleo.

Quanto aos pesquisadores da UFMS, destacamos a presença de Marcelo H. Carvalho, que fez uma tese de doutorado de altíssima qualidade (na UNICAMP), mostrando ter um potencial enorme como pesquisador, vindo provavelmente a assumir uma posição de liderança na área de Combinatória em sua instituição.

Para finalizar, ressaltamos que os pesquisadores do Núcleo têm um grande número de artigos publicados nas melhores revistas da área, dentre os quais mencionamos: Journal of Combinatorial Theory, Journal of Graph Theory, Discrete Mathematics, Discrete Applied Mathematics, Mathematical Programming, Combinatorica, Random Structures and Algorithms, Graphs and Combinatorics, European Journal of Combinatorics, SIAM J. on Discrete Mathematics e Algorithmica.

V - Infra-estrutura de apoio já existente

Manter uma infra-estrutura de apoio atualizada é uma tarefa difícil e contínua. A renovação dos laboratórios, acervos bibliográficos e outros recursos de infra-estrutura deve ser permanente, sob risco de que o material de apoio atrasado ou desatualizado impeça o bom desenvolvimento da pesquisa científica. Ainda que hoje algumas das instituições envolvidas disponham de bons recursos (o que até as qualificam como instituições de excelência), é preocupação de todos nós a necessidade de constante renovação destes recursos (isto está contemplado no orçamento deste projeto). A seguir, listamos os recursos disponíveis nas várias instituições participantes do Núcleo.

O grupo de pesquisa do IME/USP compartilha a rede local do Instituto, com cerca de 30 estações de trabalho, três servidores SunSPARC 20, duas Sun Enterprise 3000 e 32 X-terminais. Além disso o Departamento de Ciência da Computação possui um servidor SPARCServer 1000, e um laboratório de computação paralela e distribuída, com 5 estações de trabalho e um computador paralelo Parsytec Power Xplorer com 16 nós.

Também está acessível um laboratório de cerca de 100 microcomputadores, usado por alunos de graduação e pós-graduação.

A rede local do IME está conectada ao backbone FDDI do campus da Cidade Universitária, o qual está conectado à Internet. Há acesso direto ao IME através de linhas discadas.

Os alunos de pós-graduação têm acesso a um banco de dados contendo informações sobre os acervos bibliográficos de todas as bibliotecas das USP, através do sistema de consultas DEDALUS. O acesso ao banco de dados pode ser feito através das estações de trabalho ou diretamente nos terminais existentes na biblioteca.

O IME é assinante do banco de dados MathSci Disc em CD-ROM, produzido pela American Mathematical Society, e também tem acesso online via WWW. Esse banco de dados, atualizado anualmente, contém aproxidamente 1.300.000 itens com mais de 700.000 “reviews” de artigos de periódicos, livros e artigos de conferências.

A biblioteca do IME/USP conta com um excelente acervo em livros e periódicos das várias áreas de Ciência da Computação. Com seu acervo, a biblioteca do Instituto atende também a pesquisadores e estudantes de pós-graduação de outros cursos, como os das Faculdades de Engenharia, de Economia e Administração, etc. além de atender o País todo através do programa COMUT.

O Instituto de Computação da UNICAMP está instalado numa área de aproximadamente 2.300 m^{2}, onde funcionam as salas de professores, administração, laboratórios de ensino, pesquisa, salas de estudos de alunos de pós-graduação, serviços básicos de manutenção da planta física e eletrônica, administração dos sistemas computacionais e uma sala de aula e um auditório para 42 pessoas. O IC divide sua biblioteca com o Instituto de Matemática, Estatística e Computação Científica (IMECC).

O IC conta com equipamento básico para apresentações audiovisuais como retroprojetores, plataforma de data-show, microfones, PC-laptop, mas em número insuficente para a demanda ou reposição rápida. Conta também com 10 linhas telefônicas.

O seguinte parque computacional está à disposição da comunidade do IC:

• Servidoras de Rede: Plataforma Solaris: 4 Sparc 10 (2 com 1 CPU, 2 com 2 CPU’s), 4 SPARC 20 (1, 2, 4 e 4 CPU’s), 3 Sparc 1000 (1 Sunsite) (2, 2 e 8 CPUs), totalizando cerca de 100 Gb de espaço em disco, além de várias estações servidoras (Sparc 2 e 4) de menor porte. Plataforma Windows e MacIntosh: 7 servidoras.

Foram adquiridas, com previsão de instalação em dois meses, 6 servidoras Enterprise que devem adicionar cerca de 120 Gb de espaço em disco, além de servidores para plataforma Windows mais potentes.

O IC conta ainda com 1 roteador CISCO, 6 switches ATM, e uma servidora Silicon Graphics Indigo-2, com cerca de 5 Gb de espaço em disco.

Assentos Individuais: O IC conta, pra uso de toda sua comunidade, com cerca de 200 assentos, distribuídos entre X-terminals, máquinas Intel-Pentium e 486, Mac-Intosh e estações de trabalho Sun-Sparc 2 e 4.

Na UFRJ, três bibliotecas principais estão à disposição dos pesquisadores. A biblioteca do Núcleo de Computação Eletrônica, especializada em Informática, conta com um acervo de mais de 4000 livros e 273 títulos de periódicos assinados. A biblioteca do Instituto de Matemática possui um acervo destinado à pós-graduação nas diversas áreas da Matemática. A biblioteca do Centro de Tecnologia serve todos os programas da COPPE.

O Departamento de Ciência da Computação do IM/UFRJ possui um laboratório com 21 estações de trabalho IBM RISC/6000, com servidor UNIX, 40 micro-computadores Pentium e 33 micro-computadores 486, ligados em rede com servidores Novell e Unix.

A COPPE-Sistemas possui em torno de 60 estações de trabalho RISC (IBM e SUN) ligados em rede com servidor Unix, 25 micro-computadores Pentium e 20 micro-computadores 486, ligados em rede com servidores Novell e Unix. Além disso temos 10 impressoras, sendo 5 a laser e 5 de jato de tinta. Esse equipamento está distribuído parte em laboratórios e parte em sala de professores e de alunos de pós-graduação.

O Departamento de Matemática da Universidade Federal de Pernambuco conta com um laboratório de computação, com nove estações de trabalho. Há necessidade de se adquirir equipamento de maior capacidade de memória, para permitir a execução de programas com maior demanda.

A biblioteca do instituto dispõe de vários periódicos na área, ainda que alguns dos periódicos mais recentes ainda não estejam presentes no acervo, e alguns dos clássicos possuem lacunas que necessitam ser preenchidas.

Os pesquisadores do departamento contam com salas e gabinetes climatizados.

Além disso, o departamento dispõe de um corpo de funcionários altamente motivados e qualificados, que auxilia no gerenciamento e manutenção das suas atividades.

O parque computacional do Departamento de Computação e Estatística da UFMS é constituído de um Laboratório de Computação, com 5 salas, contendo 25 microcomputadores PC Pentium, 60 microcomputadores PC 486, 30 microcomputadores PC 386 e um microcomputador Apple Macintosh Classic. Além deste laboratório, o departamento também conta com um Laboratório de Pesquisa com 1 servidor SUN SPARC 10, 2 estações de trabalho SUN ULTRA SPARC, 2 estações de trabalho SUN SPARC 20, 4 estações de trabalho SUN SPARC Classic, 10 estações de trabalho SUN SPARC X terminal, 2 estações IBM RISC 6000 (380/390) (servidoras), 10 estações gráficas IBM RISC 6000 (410/250), 6 microcomputadores PC Pentium e 11 microcomputadores PC 486.

O acervo da biblioteca central da UFMS conta atualmente com cerca de 1.000 livros e 20 periódicos nas áreas de Computação e Estatística, e precisa ser ampliado urgentemente. A participação em projetos como este será fundamental para a melhoria da infra-estrutura do Departamento, tendo como conseqüencia melhores condições de trabalho para os pesquisadores desenvolverem suas pesquisas.

Orçamento Global, para 4 anos

(EM REAIS MIL) (todas as fontes de financiamento)

R$ 1.000,00

Discriminação PRONEX Outras Fontes

Total

Custeio  1.156,8  4.433,8  5.590,6
Capital  454,2  273,5  727,7
Total  1.611,0  4.707,3  6.318,3

PARTE II - ROTEIRO PARA APRESENTAÇÃO DO PROJETO

(Apresentação detalhada das atividades de pesquisa a serem desenvolvidas. Para pesquisas em andamento, deverá haver uma seção onde sejam descirtas as etapas realizadas)

Título do Projeto:

Complexidade de Estruturas Discretas

ESTADO-DA-ARTE E OBJETIVOS DO PROJETO

Uma fotografia bastante fiel do estado-da-arte da Combinatória pode ser encontrado no Handbook of Combinatorics, editado por R.L. Graham, M. Grötschel e L. Lovász (North-Holland, 1995). Em particular, os temas de maior interesse deste projeto são discutidos nos seguintes capítulos do Handbook: Combinatorial Optimization (M. Grötschel e L. Lovász), Combinatorics in Computer Science (L. Lovász, D.B. Shmoys e É. Tardos), Computational Complexity (D.B. Shmoys e É. Tardos), Extremal Graph Theory (B. Bollobás), Polyhedral Combinatorics (A. Schrijver), Probabilistic Methods (J. Spencer), Ramsey Theory (J. Nesetril) e Random Graphs (M. Karoński).

Entre os periódicos especializados de maior destaque que publicam trabalhos nas áreas de interesse deste projeto estão os seguintes:

Algorithmica  Graphs and Combinatorics
Combinatorica  Journal of Algorithms
Combinatorics, Probability and Computing J. Combinatorial Theory A and B
Discrete Applied Mathematics  J. Graph Theory
Discrete Mathematics  Mathematical Programming
Discrete Mathematics and Applications  Random Structures and Algorithms
Discrete and Computational Geometry  SIAM Journal on Computing
Diskretnaja Matematika  SIAM Journal on Discrete Mathematics
European Journal Combinatorics  SIAM Journal on Optimization

Os pesquisadores deste projeto têm especial interesse pelos seguintes subtemas:

1. Propriedades assintóticas de estruturas combinatórias, investigadas através de métodos combinatórios e extra-combinatórios, como métodos probabilísticos, algébricos e topológicos;

2. Propriedades estruturais de grafos, hipergrafos e estruturas correlatas;

3. Métodos e problemas geométricos em Combinatória, com especial ênfase em métodos poliédricos em otimização combinatória.

O principal objetivo do projeto é fomentar a integração dos diversos centros de pesquisa interessados na área de Combinatória, ampliando o grau de interação iniciado pelo projeto ProComb (que integrou diversos pesquisadores deste projeto e foi financiado pelo ProTem-CC-II do CNPq). Visamos ao aumento da produção científica do grupo através de uma maior quantidade de publicações em revistas internacionais de primeira linha, assim como uma maior participação da equipe em congressos realizados no exterior e no país. É nosso interesse também aumentar a participação da equipe na comunidade nacional de Ciência da Computação e Matemática. Em particular, jovens pesquisadores da UFMS, formados por integrantes do Núcleo, também fazem parte do projeto, garantindo o fortalecimento deste grupo emergente na área de Combinatória. Finalmente, pretendemos ampliar ainda mais a formação de profissionais na área, atraindo, através de maior divulgação das atividades da equipe, mais estudantes de doutorado, mestrado e iniciação científica.

A seguir, detalhamos alguns tópicos que vêm sendo estudados por participantes do Núcleo. A lista abaixo não pretende ser completa, mas apenas um apanhado ilustrativo de nossos interesses.

1. Problemas numéricos em teoria de Ramsey Sejam G e H dois grafos dados. Escrevemos G → H se em qualquer 2-coloração das arestas de G podemos encontrar um subgrafo monocromático em G isomorfo a H. Se exigimos ainda que o subgrafo encontrado seja um subgrafo induzido de G, escrevemos G⟶^{ind}H. Assim, o bem conhecido teorema de Ramsey implica que, para qualquer grafo H, temos G → H desde que G seja um grafo completo suficientemente grande. Por outro lado, um resultado clássico provado independentemente por Deuber, Erdős, Hajnal, e Pósa, e Rödl afirma que para qualquer grafo H existe um grafo G tal que G⟶^{ind}H. Aqui estamos interessados em problemas numéricos que surgem quando as duas relações → e ⟶^{ind} são consideradas.

Dado um grafo G, como de usual, a ordem |G| de G é o número de vértices em G, e o seu tamanho e(G) é o número de arestas em G. Fixe um grafo H. Seja r(H) a menor ordem possível de um grafo G satisfazendo G → H, e r_{e}(H) o menor tamanho possível de um tal grafo G. Assim r(H) = min{|G| G → H} e r_{e}(H) = min{e(G) G → H}. Substituindo-se a relação → por ⟶^{ind}, obtemos os parâmetros r^{ind}(H) e r_{e}^{ind}(H). Vários problemas importantes em teoria de Ramsey tratam da investigação destes parâmetros.

2. Estudo de variedades e matróides Nossos objetivos neste estudo são:

• Melhorar a compreensão a respeito de variedades tri-dimensionais, através da obtenção de novos invariantes, que sejam computáveis de maneira eficiente a partir de um grafo associado com esta variedade. Além de novos grupos e polinômios, serão procurados invariantes que possuem outras estruturas, como por exemplo matróides, já que estas são um invariante natural para uma classe de variedades, que foram chamadas de planares por Lins.

• Investigar a estrutura de grafos e matróides com uma certa conectividade, e no caso de matróides 3-conexas compreender a estrutura fora de uma configuração fixa, estendendo resultados conhecidos de Lemos, Oxley, Seymour e Tutte. Desenvolver técnicas para estudar matróides que são minimalmente n-conexas para n ≥ 4, já que quase nada é conhecido para esta classe de matróides, e muito é conhecido no caso de grafos: teoremas de Halin e Mader.

• Melhorar significativamente algumas relações envolvendo os diversos invariantes para grafos e matróides, em especial aqueles que lidam com a circunferência ou o grau mínimo.

• Estudar o problema da reconstrução de um grafo a partir do hipergrafo associado com uma família fixa de grafos, quando o grafo que deseja-se reconstruir tem a k-propriedade, onde k+1 é igual ao número máximo de vértices em um grafo na família fixa. Uma possível consequência dos resultados obtidos nesta direção, será garantir reconstruividade com probabilidade um, independentemente da família de grafos fixa, produzindo uma prova, puramente combinatória, de um resultado de Cameron e Martins. Outros resultados em problemas de reconstrução também deverão ser obtidos, como por exemplo o de reconstruir um matróide conexo a partir de sua função conectividade. Apesar de nem sempre ser possível, como conjecturou Cunningham, em alguns casos o é como foi demonstrado por Lemos e Seymour.

3. Enumeração de grafos com subgrafos proibidos Seja dado um grafo H. Denotamos por f(H, n, m) o número de grafos livres de H de ordem n e tamanho m, e pomos g(H, n) = ∑_{m} f(H, n, m). Analogamente, denotamos por f_{ind}(H, n, m) o número de grafos de ordem n e tamanho m livres de cópias induzidas de H, e pomos g_{ind}(H, n) = ∑_{m} g_{ind}(H, n, m). O estudo das funções f, g, f_{ind}, g_{ind} é de natureza fundamental.

Seja P uma propriedade hereditária qualquer de grafos, i.e., uma propriedade que é fechada com respeito à operação de se tomar subgrafos induzidos. Alekseev e, independentemente, Bollobás e Thomason provaram que o número f_{P}(n) de grafos de ordem n com a propriedade P satis-

faz log_{2} f_{P}(n) = (1 − 1/r + o(1)) ( \begin{matrix}n \\ 2 \end{matrix} ) conforme n → ∞, onde r = r(P) ≥ 1 é um inteiro que

pode ser descrito explicitamente em termos de P. Um problema desafiador é o de generalizar este resultado para hipergrafos.

Problema Seja P uma propriedade de hipergrafos r-uniformes (r ≥ 3). Descreva os valores

possíveis de lim ( \begin{matrix}n \\ r \end{matrix} )^{−1} log_{2} f_{P}(n), onde f_{P}(n) é o número de hipergrafos r-uniformes de

ordem n satisfazendo P.

Nos problemas acima, seria de grande interesse especificar não apenas a ordem mas também o tamanho dos grafos e hipergrafos que estamos enumerando. Os problemas que obtemos com estas condições extras são, entretanto, muito mais difíceis de serem tratados. De fato, o que se conhece atualmente sobre o comportamento das funções f e f_{ind} é muito mais fraco do que o que sabemos sobre g e g_{ind}. Um resultado recente de Prömel e Steger estabelece o comportamento assintótico fino da função f(K^{3}, n, m) para uma ampla gama da função m = m(n), mas determinar o comportamento desta função para todo m = m(n) parece ainda elusivo.

Encerramos este parágrafo com um problema específico sobre a função f. Considere a probabilidade P_{ℓ,n,m} de um grafo de ordem n e tamanho m, escolhido uniformemente ao acaso, ser livre de C^{2ℓ}.

Assim P_{ℓ,n,m} = f(C^{2ℓ}, n, m)( \begin{matrix}( & \begin{matrix}n \\ 2 \end{matrix} & ) \\ & m \end{matrix} )^{−1}.

Problema É verdade que

lim_{n→∞} \frac{1}{m} log P_{ℓ,n,m} = 0

para toda função m = m(n) = ωn^{1+1/(2ℓ−1)}, onde ω = ω(n) → ∞ conforme n → ∞ e ω =

o(n^{1/2(ℓ−1)(2ℓ−1)}) ?

Para o caso ℓ = 2, veja Füredi. Mais genericamente, em Kohayakawa, Kreuter, e Steger, uma variante do problema acima é estudada para ℓ genérico, e, como conseqüência de um resultado de enumeração assintótica, é resolvido no caso em que H = C^{2ℓ} e p = p(n) pertence a um intervalo polinomial suficientemente pequeno em torno do limiar n^{−1+1/(2ℓ−1)}. Este resultado implica em particular que existem grafos extremamente esparsos com a propriedade de que qualquer fração positiva de suas arestas geram um circuito de comprimento par pré-determinado.

4. Grafos de comparabilidade Pesquisadores têm colocado seus esforços na busca de algoritmos eficientes que atribua orientação transitiva às arestas de um grafo, se tal atribuição for possível. Grafos que admitem uma orientação transitiva são denominados grafos de comparabilidade.

Neste ano, R. M. McConnell e J. Spinrad mostraram para a comunidade científica um algoritmo que atribui orientação transitiva às arestas de um grafo de comparabilidade em tempo linear. Os algoritmos anteriores a este, conhecidos a partir de 1962, têm tempo O(n^{2}) (1985), O(n + m log n) (1994) e O(Δm) (1962).

Numa orientação transitiva podemos destacar vértices que são fontes ou sumidouros, isto é, vértices com grau de entrada nulo (fontes) ou grau de saída nulo (sumidouro). Nem todo vértice de um grafo de comparabilidade é fonte de alguma orientação transitiva. Olariu e Gimbel caracterizaram vértices de um grafo de comparabilidade que são fontes de alguma orientação transitiva. Em um primeiro trabalho nessa classe descrevemos propriedades que relacionam fontes com as cliques maximais do grafo. Posteriormente, J. Szwarcfiter, J. Meidanis e C. de Figueiredo, caracterizaram conjunto fonte (um conjunto de vértices que são fontes de alguma orientação transitiva).

Uma questão natural que surgiu como conseqüência destes trabalhos é a busca por uma orientação transitiva com conjunto fonte de cardinalidade máxima. Em uma primeira abordagem, Andrielli e Mello elaboraram um algoritmo que resolve este problema em tempo O(n^{2}). A técnica usada foi a mesma empregada por Spinrad e a complexidade advém dessa técnica. Nosso objetivo, agora, é diminuir essa complexidade, dada a existência de um algoritmo de tempo linear que orienta transitivamente as arestas de um grafo de comparabilidade.

5. Investigação poliédrica de problemas combinatórios No tocante aos métodos poliédricos, é nosso objetivo desenvolver algoritmos baseados na estratégia branch and cut para alguns problemas difíceis de otimização combinatória (por exemplo, problemas de partição de grafos e hipergrafos, cobertura de grafos por caminhos, problemas de cortes com terminais). A subárea em que se insere esta pesquisa é conhecida como combinatória poliédrica. A literatura nessa subárea tem crescido enormemente nos últimos anos, tendo nossa equipe acompanhado os avanços da pesquisa de ponta que tem sido feita nessa área.

Tal estratégia tem obtido cada vez maior aceitação na comunidade internacional, sendo responsável pelo surgimento de grupos em vários centros do exterior que fazem pesquisa nesta linha (TU e ZIB Berlim, CORE–Louvain, IASI–Roma). Esta abordagem tem sido considerada especialmente indicada para resolver problemas reais de grande porte.

É fundamental a obtenção de resultados teóricos a respeito da estrutura facial dos poliedros associados aos problemas em questão. Além disso, o estudo da complexidade computacional bem como o desenvolvimento de algoritmos heurísticos eficientes para os problemas de separação relativos a tais poliedros constituem objetivos principais de nossa pesquisa. Trabalharemos também no desenvolvimento e na implementação de algoritmos baseados nesta abordagem.

Dentre os problemas de interesse que serão pesquisados mencionamos o problema de reconstrução de fragmentos de DNA, problemas de decomposição de matrizes, partição de polígonos retangulares, triangulações de conjuntos de pontos no plano e fatoração de grafos.

6. Geometria computacional Geometria Computacional é um ramo da ciência da computação que estuda algoritmos para resolver problemas geométricos. Algoritmos geométricos exercem um importante papel em muitas áreas da ciência da computação, incluindo computação gráfica, projeto auxiliado por computador, projeto VLSI (Very Large Scale Integrated circuit) e robótica. Uma vez que o tamanho da entrada para estes problemas pode ser bastante grande, torna-se essencial o desenvolvimento de algoritmos eficientes para resolvê-los. A partição de polígonos é um dos problemas fundamentais em geometria computacional. Neste projeto, estaremos particularmente interessados em estender resultados obtidos anteriormente para os problemas de Partição de Polígonos Retangulares e Triangulações de conjuntos de pontos no plano.

7. Cortes e empacotamentos Estudo de problemas de empacotamento bi e tridimensional, com especial ênfase no desenvolvimento de algoritmos de aproximação.

8. Biologia computacional As atividades de pesquisa atualmente em curso nesta área são as seguintes: estudos diversos sobre comparação de seqüências, incluindo (i) uma abordagem uniforme para diversos problemas deste tipo (ii) a aplicação de paralelismo na sua resolução e (iii) novos algoritmos para o problema do alinhamento múltiplo de seqüências. Nestas atividades estão atualmente envolvidos dois alunos de mestrado e um aluno de iniciação científica. Outro tópico de pesquisas tem sido o reconhecimento de estruturas em genes. Nesta atividade o principal responsável é o aluno de doutorado e membro do núcleo Nalvo Franco de Almeida Jr., atualmente realizando estágio de bolsa-sanduíche na University of Washington, EUA.

Os pesquisadores do Núcleo, J. Meidanis e J. Setubal, tem desenvolvido pesquisas nesta área. Dessa coloboração resultou um livro recentemente publicado nos EUA.

9. Algoritmos e teoria dos jogos Este tópico de pesquisa procura relacionar o projeto de algoritmos para problemas combinatórios com a teoria dos jogos. Especificamente pretende-se estudar algoritmos para o problema árvore espalhada (ou geradora) mínima numa situação em que os vários algoritmos competem entre si para determinar a melhor solução. A partir deste enfoque aparecem diversos problemas interessantes do ponto de vista combinatório e de experimentação algorítmica.

RESULTADOS ESPERADOS E SUA RELEVÂNCIA

Como conseqüência de nossas atividades de pesquisa dentro deste projeto, objetivamos ter, como resultado concreto uma maior integração entre os diversos grupos no país interessados em Combinatória. Esta integração virá a causar:

1. maior número de publicações em periódicos internacionais de primeira linha; publicações de autoria dos participantes do projeto nas atas das oficinas;

2. aumento das atividades de intercâmbio nacional e internacional mantidas por membros da equipe, com especial atenção à participação mais ativa do grupo em simpósios onde hoje a atuação da equipe não é tão intensa (como os Congressos da Sociedade Brasileira de Computação e Congresso Nacional de Matemática Aplicada e Computacional);

3. atração de pós-doutorandos da oferta internacional;

4. formação de um grupo maior de alunos de doutoramento, mestrado e de iniciação científica;

5. fortalecimento de grupos na área de Combinatória de instituições emergentes;

6. colaboração na formação teórica de graduados em computação nas várias instituições.

O fortalecimento do grupo de pesquisadores envolvidos neste projeto é o principal resultado esperado, e terá como conseqüencia, a formação de recursos humanos altamente qualificados e preparados para contribuir para a capacitação tecnológica do país em várias áreas do conhecimento, já que pessoal formado pelos pesquisadores do núcleo hoje atuam em diversas instituições do país (como o Mato Grosso do Sul, Paraná, Bahia, etc), especialmente na formação teórica básica de estudantes de graduação e pósgraduação.

A área de Combinatória tem lugar destacado na Teoria da Computação, sendo um dos seus pilares fundamentais. A descoberta de algoritmos eficientes, ou mesmo a identificação da complexidade computacional de problemas estão intrinsecamente relacionados com esta área, e constituem de base fundamental para diversas aplicações em ciência da computação.

Note-se que os principais resultados devem ser esperados a médio e longo prazos. Nosso projeto conta com uma grande maioria de participantes com doutorado recente (últimos cinco anos). Esperamos que através do projeto consigamos o entrosamento desse contingente altamente motivado de pesquisadores, colaborando para a consolidação e ampliação dos núcleos de pesquisa em Combinatória.

Um outro aspecto que justifica a relevância desta proposta, é o do reconhecimento dos centros de pesquisa brasileiros em termos internacionais. Tal fato facilita sobremaneira o intercâmbio de nossas instituições com os grandes centros de pesquisa internacionais, propiciando um constante acompanhamento de novas áreas e tendências em Combinatória, além de facilitar o envio de estudantes brasileiros para serem formados nesses centros.

Como último resultado esperado, mas não menos importante, mencionamos que é fundamental termos no Brasil condições profícuas para o desenvolvimento de pesquisa. É importante mostrar ao estudante brasileiro que está se formando no exterior que é possível e viável fazer pesquisa de qualidade no país. Com isso esperamos diminuir a “taxa de evasão” de recém-doutores, ou seja, daqueles que, muitas vezes após terem sido financiados por agências brasileiras de fomento à pesquisa, decidem não voltar ao país por acharem que não terão aqui condições de progredir profissionalmente. Mais que isso, poderemos formar no país pólos potenciais de atração de pesquisadores estrangeiros, intensificando o intercâmbio das instituições participantes com centros de excelência no exterior.

DESCRIÇÃO DA EQUIPE

(Apenas os envolvidos com o projeto de pesquisa proposto. Bolsistas de Graduação, Mestrado e Doutorado incluir em “Estudantes”)

Pesquisadores e Técnicos

N^{ō}

Nome Titulação Função no projeto

Dedicação

USP

1 Arnaldo Mandel  Ph.D. Waterloo  Pesquisador (nível 1C) Integral
2 Carlos Eduardo Ferreira  Dr.rer.nat. Berlin  Pesquisador (nível 2C) Integral
3 Cristina Gomes Fernandes  Ph.D. Atlanta  Pesquisador  Integral
4 José Augusto R. Soares  Ph.D. Chicago  Pesquisador (nível 2C) Integral
5 José Coelho de Pina Jr.  Doctor Amsterdam Pesquisador  Integral
6 Maria Angela C. Gurgel  Doutor USP  Pesquisador  Integral
7 Paulo Feofiloff  Ph.D. Waterloo  Pesquisador (nível 2C*) Integral
8 Yoshiharu Kohayakawa  Ph.D. Cambridge  Pesquisador (nível 2A) Integral
9 Yoshiko Wakabayashi  Dr.rer.nat. Augsburg Pesquisador (nível 1C) Integral

UNICAMP

10 Célia Picinin de Mello  Doutora UFRJ  Pesquisador (nível 2C) Integral
11 Cid Carvalho de Souza  Ph.D. Louvain  Pesquisador (nível 2C) Integral
12 Cláudio Leonardo Lucchesi  Ph.D. Waterloo  Pesquisador (nivel 1C) Integral
13 João Carlos Setubal  Ph.D. Washington  Pesquisador (nível 2C) Integral
14 João Meidanis  Ph.D. Wisconsin  Pesquisador (nivel 2C) Integral
15 Ricardo Dahab  Ph.D. Waterloo  Pesquisador (nível 2C) Integral

UFPE

16 Sóstenes Luiz Soares Lins  Ph.D. Waterloo  Pesquisador (nivel 1B) Integral
17 Manoel José M. S. Lemos  D.Phil. Oxford  Pesquisador (nivel 2A) Integral
18 Cleide S. Martins Gomes  Ph.D. Londres  Pesquisador  Parcial
19 Katia Silva Guimarães  Ph.D. Maryland  Pesquisador (nivel 2C) Integral

UFRJ

20 Celina M. H. Figueiredo  Doutor UFRJ  Pesquisador (nível 2B) Integral
21 Sulamita Klein  Doutor UFRJ  Pesquisador (nível 2C) Integral
22 Márcia Rosana Cerioli  Mestre UFRJ  Pesquisador  Integral

UFMS

23 Fabio H. Viduani Martinez  Mestre USP  Pesquisador  Integral
24 Nalvo Franco de Almeida Jr.  Mestre UFRJ  Pesquisador  Integral
25 Marcelo Henriques de Carvalho Doutor UNICAMP  Pesquisador  Integral

(*) não vigente

Pesquisadores que estarão visitando o Núcleo durante o primeiro ano do projeto

N^{ō}

Nome Titulação Função no projeto

Duração

1 Bruce Reed Ph.D. McGill Pesquisador 1 ano
2 John Adrian Bondy D.Phil. Oxford Pesquisador  1 ano

Estudantes

(Agrupar por nível: graduação, mestrado e doutorado)

N^{ō}

Nome Nível Ag. Financiadora

Dedicação

USP

1 Estela Maris Rodrigues  doutorado  CNPq  Integral
2 Flávio Keidi Miyazawa  doutorado  CNPq  Integral
3 Jair Donadelli Junior  doutorado  Integral
4 Liliane Rose B. Salgado  doutorado(*)  Integral
5 Orlando Lee  doutorado  CAPES  Integral

UNICAMP

6 Maria E. M. Telles Walter doutorado CAPES-PICD Integral

UFPE

7 Bráulio Maia Junior  doutorado  CAPES  Integral
8 Sérgio Mota Alves  doutorado  Integral
9 Marcelo Gama  doutorado  Integral
10 Haroldo G. Benatti  doutorado  Integral

UFRJ

11 Fabio Protti  doutorado  CNPq  Integral
12 Luerbio Faria  doutorado  CAPES  Integral
13 Joisa de Souza Oliveira  doutorado  CAPES  Integral
14 Rommel Melgaco Barbosa  doutorado  CAPES  Integral

USP

15 Armando Ramos Gouveia  mestrado  Integral
16 Claus Akira Matsushigue  mestrado  Integral
17 Edésio Ramos Sibrão  mestrado  CNPq  Integral
18 Francisco E. S. de Araújo  mestrado  CAPES  Integral
19 Glauber Ferreira Cintra  mestrado  Integral
20 Marco Aurélio Stefanes  mestrado  CNPq  Integral

UNICAMP

21 Christiane Neme Campos  mestrado  CNPq/FAPESP  Integral
22 Marcelo Marcos Barbosa  mestrado  CNPq  Integral
23 Fabiano Silva  mestrado  PET/CAPES  Integral
24 Vagner Okura  mestrado  Integral
25 Guilherme Pimentel Telles  mestrado  FAPESP  Integral

UFPE

26 Pedro Mário Cruz e Silva mestrado CNPq Integral

USP

27 Alexandre C. Garcia Leite  graduação  Parcial
28 Bruno Benjamin Ohana  graduação  Parcial
29 Cassio Polpo de Campos  graduação  Parcial
30 Dan Faccio  graduação  CNPq  Parcial
31 Eduardo Garcia de Freitas  graduação  Parcial
32 Luciano Michelleti Hespanhol  graduação  CNPq  Parcial
33 Rogerio Theodoro de Brito  graduação  CNPq  Parcial
34 Sergio Gabriel Tavares  graduação  CNPq  Parcial

UFPE

35 Luciano Brandão de Souza  graduação  CNPq  Integral
36 Mônica Gonçalves Melo  graduação  CNPq  Integral

UFRJ

37 Fabricio Chalub graduação CNPq Parcial

(*) Início em agosto/97.

Pessoal Recrutado

(Descrever o perfil do pessoal que possa eventualmente vir a ser recrutado para o núcleo)

Serão usados serviços de assessoria para a administração financeira dos recursos do projeto. Não se pretende recrutar pessoal técnico e administrativo para o núcleo. Outras atividades de manu-

tenção e administração do núcleo serão desempenhadas pelo pessoal administrativo das instituições.

As pesquisas serão desenvolvidas pelos pesquisadores das instituições participantes e por estudantes de doutorado, mestrado e iniciação científica. Pequenos serviços de apoio (programação, organização de eventos, etc) poderão ser contratados no decorrer do projeto.

METODOLOGIA

• Pesquisa bibliográfica

Atualmente a rede Internet torna acessível os bancos de dados bibliográficos sempre recentes, o que possibilita uma rápida referenciação dos trabalhos em andamento internacionalmente. A nossa intenção é utilizar e passar para aos estudantes a experiência já adquirida em usufruir tais serviços para aumentar substancialmente a qualidade e a atualidade do desenvolvimento do projeto.

Além disso, nas bibliotecas das instituições participantes (de acervo constantemente renovado) os integrantes do projeto e seus alunos terão acesso a obras de referência na área.

• Atividades de Treinamento e Intercâmbio

A participação de pesquisadores em congressos internacionais e as visitas a outras instituições são de fundamental importância para a divulgação dos resultados obtidos no projeto e para a atualização destes pesquisadores com realização aos últimos resultados obtidos na área em todo o mundo.

Queremos incluir aqui também estudantes ligados às instituições do núcleo. A participação de alunos de doutorado em congressos internacionais é uma experiência fundamental para sua formação, que dificilmente encontra financiamento junto às agências de fomento.

Tais participações (tanto dos pesquisadores do núcleo como de seus alunos) reverterão em benefícios para todos os participantes do projeto através de relatórios disponíveis para os membros e também através das oficinas regulares, em que os pesquisadores poderão trocar idéias e experiências.

• Semanas de Combinatória

Para um aproveitamento pleno da eventual visita dos pesquisadores estrangeiros pela comunidade brasileira de pesquisadores em Combinatória e em Teoria da Computação, prevemos a organização de Semanas de Combinatória, nos moldes das semanas organizadas na ocasião da visita de B. Bollobás em 1992 e de P. Erdős em 1994. Prevemos a organização de pelo menos duas Semanas durante a vigência deste projeto.

• Oficinas de Combinatória

Pretendemos realizar durante este projeto uma Oficina de Combinatória a cada ano, sendo que algumas dessa oficinas deverão contar com a presença de pesquisadores estrangeiros.

Com isto pretendemos repetir a experiência bem sucedida que muitos dos pesquisadores do Núcleo tiveram durante o projeto ProComb – Problemas Combinatórios: Teoria, Algoritmos e Aplicações – financiado pelo Programa Temático Multi-Institucional do CNPq, ProTeM-CC-II.

Estas oficinas contarão com a presença dos pesquisadores do Núcleo e de seus estudantes — principalmente os de doutorado e mestrado. Incentivaremos também a participação de pesquisadores de outros centros emergentes, com quem desejamos estabelecer contato. Isso acarretará mais integração destes pesquisadores e maior disseminação dos resultados obtidos.

As oficinas deverão ser compostas de sessões de problemas e sessões de palestras. Nas sessões de problemas os pesquisadores expõem os problemas em que vêm trabalhando e o restante do grupo discute alternativas para solucionar tais problemas. É comum observar que pessoas de subáreas diversas conhecem métodos diferentes de solução de problemas. Tais sessões podem ser extremamente produtivas, gerando trabalhos em co-autoria. As palestras visam a informar o grupo sobre trabalhos já concluídos ou, pelo menos, bem encaminhados. Acreditamos que essas oficinas serão muito produtivas cientificamente e deverão produzir uma grande integração do Núcleo, além, é claro, de constituírem uma experiência única para os estudantes participantes.

Preferencialmente, as oficinas devem ocorrer em algum lugar onde todos os pesquisadores possam se dedicar plenamente aos problemas de pesquisa apresentados, longe de outras atividades administrativas, docentes, etc.

A exemplo do ocorrido no projeto ProComb, pretendemos que algumas dessas oficinas tenham a participação de pesquisadores estrangeiros convidados. No caso do projeto ProComb, foi realizado no Rio de Janeiro entre 2 e 4 de outubro de 1996 o Workshop Internacional de Combinatória que contou com a participação dos seguintes pesquisadores estrangeiros de renome e reconhecimento internacional: J.A. Bondy (Université Claude-Bernard, Paris), A.M.H. Gerards (Centrum voor Wiskunde en Informatica, Amsterdam), P. Hansen (École des Hautes Études Commerciales, Montreal), M. Gutierrez (Universidad de La Plata, La Plata), F. Maffray (CNRS e Université Joseph Fourier, Glenoble), C. Papadimitriou (University of California, Berkeley), H.-J. Prömel (Humbolt-Universität, Berlin), B. Reed (CNRS e Université Pierre et Marie Curie, Paris).

As oficinas serão os pontos básicos para a apresentação dos resultados até então obtidos e o acompanhamento do andamento do projeto. Com as atividades de intercâmbio descritas acima, todos terão uma visão clara do estado do projeto ao longo de sua vigência. Além disso, novas direções de desenvolvimento poderão ser discutidas, garantindo a auto-avaliação e realimentação necessárias para o bom cumprimento do projeto.

• Mini-cursos em Centros Emergentes

Eventos e mini-cursos já vêm sendo realizados por docentes do IC/UNICAMP na Universidade Federal de Mato Grosso do Sul. Com este projeto estenderemos este tipo de iniciativa a outros centros emergentes como, por exemplo, a Universidade Federal do Paraná (onde temos contato com o docente Renato José da Silva Carmo) e a Universidade Estadual de Feira de Santana (onde temos contato com o docente Haroldo G. Benatti). Os Mini-cursos deverão ser oferecidos durante os meses de ferias escolares (janeiro,fevereiro e julho).

TRANSFERÊNCIA DE RESULTADOS ESPERADOS PARA A SOCIEDADE

A transferência de resultados para a sociedade se dará de maneira indireta através da formação de recursos humanos altamente qualificados, que será certamente absorvida pelas universidades brasileiras ou por qualquer outro órgão que necessite de um profissional em pesquisa operacional.

Este projeto certamente fortalecerá o grupo emergente em Combinatória da UFMS. Além desse grupo, pretendemos que outros grupos emergentes em Combinatória sejam também fortalecidos, como por exemplo o grupo do docente Renato José da Silva Carmo da Universidade Federal do Paraná, que participou (junto com os estudantes da UFPR) de duas das quatro Oficinas de Problemas Combinatórios realizadas durante a vigência do projeto ProComb.

A pesquisa que será realizada neste projeto certamente contribuirá para o aumento do nível científico e do nível de publicações das instituições envolvidas, trazendo como conseqüência uma divulgação maior das instituições, tanto em termos nacional quanto internacional.

Apesar de não se poder dizer que um projeto como este, cuja proposta é fazer pesquisa de caráter mais teórico em Ciência da Computação, tenha o potencial para causar impacto econômico ou social — pelo menos a curto prazo — acreditamos que teoria da computação é a base do desenvolvimento dos avanços tecnológicos.

FORMAÇÃO DE RECURSOS HUMANOS

No presente projeto, participam cerca de 40 estudantes, a maioria de pós-graduação. Uma das metas do projeto é a formação de recursos humanos de qualidade. Espera-se que as pesquisas propostas resultem em dissertações de mestrado e teses de doutorado. Em especial, alunos de instituições emergentes serão formados, fortalecendo o estabelecimento destas instituições na comunidade nacional da área. Através dos recursos solicitados, os próprios pesquisadores do projeto aperfeiçoarão a sua formação, visando sempre a uma melhor produtividade nas suas atividades de pesquisa e ensino.

Para isso, torna-se necessário não apenas melhorar e atualizar a infra-estrutura dos vários laboratórios e bibliotecas, mas sobretudo dar aos participantes do projeto amplas oportunidades no sentido de incrementar ainda mais o intercâmbio com outros núcleos e grupos de pesquisa no país e no exterior. Por esse motivo, o projeto contempla um orçamento que inclui rubricas de equipamento para infra-estrutura de pesquisa e despesas de custeio para viabilizar as viagens de pesquisadores e alunos a outros centros e a vinda de pesquisadores visitantes.

Também acreditamos que este projeto trará um impacto positivo nos cursos de graduação de cada um das instituições participantes. Os estudantes de graduação serão expostos a Iniciações Científicas motivantes e cursos de Combinatória e Teoria da Computação de alta qualidade.

Um outro aspecto que vale a pena ressaltar diz respeito ao fato de que pesquisadores motivados e envolvidos em pesquisas de ponta certamente atrairão alunos interessados em suas pesquisas, contribuindo assim para a formação de recursos humanos de alta qualidade nesta área.

ATIVIDADES DE EXTENSÃO

O Núcleo já mantém uma série de atividades de extensão que visam a difusão do conhecimento na comunidade. Essas atividades serão mantidas durante a vigência do projeto. A seguir listamos algumas destas atividades.

• O DCC/USP, DI/UFPE, DM/UFPE e IC/UNICAMP promovem cursos de extensão que visam atender à basicamente dois segmentos:

– estudantes ou profissionais interessados em complementar sua formação;

– estudantes interessados em fazer pós-graduação (seja em nível de mestrado ou de doutorado).

Esses curso são ministrados principalmente durante os meses de janeiro e fevereiro. Nestas atividades participam igualmente todos os docentes das instituições.

Mais informações podem ser obtidas via http://www.dmat.ufpe.br/verao.html,
http://www.ime.usp.br/~verao/.

• Com o CPqD/Telebrás, o IC mantém atividades em duas frentes: (i) cursos básicos e avançados em Computação para os funcionários do CPqD; (ii) contratos de pesquisa e desenvolvimento em gerenciamento de telecomunicações e software básico. Nestes participam igualmente todos os docentes do IC.

• Com a Itautec/Philco, o IC manteve contratos de pesquisa e desenvolvimento durante os anos de 1994 a 1996. Um dos contratos gerou um corretor ortográfico incorporado aos produtos da Itautec, e pelo qual os autores, um deles pesquisador principal do grupo proponente, Prof. Cláudio L. Lucchesi, ganharam um dos prêmios COMPAQ de Software de 1996.

Mais informações podem ser obtidas via http://www.dcc.unicamp.br/dicio/ortho.html.

Além dessas atividades pretendemos:

• Disponibilizar o resultados científicos obtidos na internet através de páginas WWW. Tais páginas serão atualizadas periodicamente.

• Oferecer mini-cursos em centros emergentes (veja item metodologia).

INTERCÂMBIOS

a) Com outros núcleos/grupos/equipes/instituições, no país e no exterior.

Participantes do Núcleo vêm mantendo intercâmbio constante e regular com outros grupos de pesquisa no país e no exterior, com convênios e realização de missões tanto de pesquisadores do núcleo ao exterior como vinda de pesquisadores visitantes.

O Núcleo conta com a colaboração sólida e regular dos seguintes bem-conhecidos pesquisadores estrangeiros e de membros de seus grupos: B. Bollobás (Cambridge), J.A. Bondy (Université Claude-Bernard, Paris), H. Everett (Université du Quebéc, Montréal), P. Hell (Simon Fraser University, Canada), Frédéric Maffray (IMAG, Grenoble), U.S.R. Murty (University of Waterloo, Waterloo), B. Reed (CNRS e Université Pierre et Marie Curie, Paris), M. Grötschel (TU Berlim e ZIB Berlim), H. Karloff (Georgia Institute of Technology, Atlanta), T. Łuczak (Poznań, Polônia), J.G. Oxley (Louisiana State University, Louisiana), H.-J. Prömel (Humboldt-Universität, Berlim), V. Rödl (Emory University, Atlanta), L.A. Wolsey (CORE, Bélgica), e D. Younger (Waterloo).

Mencionamos ainda que o nosso Núcleo já teve contatos com os seguintes pesquisadores e membros de seus grupos, em níveis variados, e que gostaríamos de estreitar nossos laços de colaboração com eles durante a vigência deste projeto: N. Alon (Tel Aviv), R. Baeza-Yates (Chile), R. Bixby (Rice), G.R. Brightwell (London), A. Frieze (Carnegie Mellon), R.L. Graham (Bell Labs), P. Haxell (Waterloo), Kyriakos Kilakos (London), H. Lefmann (Dortmund), A. Menezes (Auburn U., EUA) C. McDiarmid (Oxford), J. Nešetřil (Praga), J.H. Spencer (Nova York), E. Szemerédi (Rutgers e Budapest), K. Vušković (University of Kentucky) e A. Wigderson (Jerusalém).

Atualmente (ou em um futuro próximo) visitam instituições participantes do projeto os seguintes pesquisadores: B. Reed (um ano), J.A. Bondy (um ano), V. Rödl (três semanas), E. Szemerédi (três semanas), e L.A. Wolsey (três semanas).

Centros com os quais pesquisadores do núcleo mantêm intercâmbio incluem: ZIB e TU - Berlim, Universidade Adam Mickiewicz de Poznań, Emory University - Atlanta, Humboldt-Universität, Bonn Universität, Université Catholique de Louvain, University of Washington, e University of Waterloo.

O Núcleo também mantém contatos com a pesquisadora Cláudia Linhares Sales da Universidade Federal Fluminense e pretende ampliá-lo, tanto em termos de realização de pesquisa conjunta, quanto na troca de experiências no ensino e na formação de recursos humanos.

Vale destacar ainda o intercâmbio entre o Núcleo e vários grupos emergentes, particularmente com a Universidade Federal de Mato Grosso do Sul (que tem a participação neste projeto dos docentes Fábio H. Viduani Martinez, Nalvo Franco de Almeida Jr., e Marcelo H. de Carvalho), com a Universidade Estadual de Feira de Santana através do docente Haroldo G. Binatti (doutorando no DI/UFPE), e com a Universidade Federal do Paraná através do docente Renato José da Silva Carmo.

Uma outra colaboração do núcleo com grupos emergentes é na formação de recursos humanos para ensino e pesquisa, como a Universidade Estadual de Feira de Santana, Universidade Federal da Bahia, Universidade de Federal do Mato Grosso do Sul (UFMS), e Universidade Federal do Paraná. Docentes da UFMS são regularmente enviados aos centros dos pesquisadores do núcleo para seus programas de pós-graduação. Os seguintes egressos da UFMS concluíram ou realizam o mestrado e doutorado em instituições participantes do núcleo: Emerson Yoshiteru Hosokawa (atual mestrando), Fábio Henrique Viduani Martinez (mestrado em 1996), Flávio Keidi Miyazawa (mestrado em 1993, atual doutorando), Henrique Mongelli (mestrado em 1995, atual doutorando), Marcelo Henriques de Carvalho (mestrado em 1988, doutorado em 1996), Marcelo de Souza Lauretto (mestrado em 1996), Marcos Alves (atual mestrando), Marco Aurélio Stefanes (atual mestrando), e Nalvo Franco de Almeida Junior (mestrado em 1993, atual doutorando).

Com isso, evidencia-se a capacidade aglutinadora do Núcleo pela sua integração com pesquisadores ligados a outros grupos, particularmente estrangeiros e emergentes.

b) Aqueles que visam nuclear ou fortalecer grupos emergentes na área de atuação do Núcleo.

O Núcleo possui experiências muito positivas em nuclear e fortalecer grupos emergentes. Exemplos disso são os centros da Universidade Estadual de Feira de Santana, Universidade Federal da Bahia, Universidade de Goiás, Universidade Federal de Mato Grosso do Sul, Universidade Federal do Paraná, e Universidade Federal de Viçosa, de onde recebemos regularmente estudantes para seus estudos de pós-graduação, além de outros em números menores, de todas as regiões do país.

O Núcleo mantém contatos com docentes da Universidade Estadual de Feira de Santana (Haroldo G. Benatti — mestre USP e atual doutorando UFPE), Universidade Federal do Paraná (Renato José da Silva Carmo — mestre USP) e da Universidade Federal Fluminense (Cláudia Linhares Sales), e pretende ampliá-los, tanto em termos de realização de pesquisa conjunta, quanto na troca de experiências no ensino e na formação de recursos humanos (discussão de grades curriculares e conteúdo programático de cursos).

Um dos grupos participantes do presente projeto é o grupo emergente representado pelos professores Fabio H. Viduani Martinez, Nalvo Franco de Almeida Jr., e Marcelo Henriques de Carvalho da Universidade Federal do Mato Grosso do Sul. O Núcleo contribuiu para formar estes docentes: Fabio realizou o seu mestrado no DCC/USP, Nalvo completou seu mestrado na COPPE/UFRJ e atualmente esta fazendo doutorado sanduiche no IC/UNICAMP e University of Washington (sob a orientação de João Carlos Setubal) e Marcelo tem o seu metrado pelo DCC/USP e o seu doutorado pelo IC/UNICAMP (sob a orientação de Claudio L. Lucchesi, um dos pesquisadores principais deste projeto). Eventos e minicursos também vêm sendo realizados nesta instituição por docentes do IC/UNICAMP.

O Núcleo pretende continuar não só mantendo contatos com as intituições acima mencionadas, mas também ampliar esses contatos, procurando fortalecer outros grupos. Para concretizar esses planos, o Núcleo pretende ministrar mini-cursos (nas férias) em instituições emergentes, tendo já mantido contatos com grupos do IBILCE/UNESP e da UFPR (veja item metodologia).

PLANO DE METAS

Plano de metas e indicadores de progressos anuais ou cronograma físico das atividades a serem desenvolvidas

A seguir listamos as atividades que serão desenvolvidas durante a vigência do projeto.

• Elaboração e acesso a páginas WWW do projeto

Um dos nossos objetivos é disponibilizar os resultados científicos obtidos na Internet através de páginas WWW. Tais páginas serão atualizadas periodicamente.

• Realização de oficinas

Oficinas congregando os pesquisadores do projeto, alunos e outros convidados serão realizadas anualmente. Serão incentivos para realimentação e interação entre as várias instituições participantes. Essas oficinas servirão também para avaliar o andamento do projeto, eventualmente indicando possíveis redirecionamentos a serem feitos. Nestas ocasiões, divulgaremos amplamente estes encontros, convidando especialmente pesquisadores de centros emergentes com os quais desejamos estreitar contatos. Em particular, o projeto terá como subproduto certo atas com publicações deste grupo de pesquisa e com contribuições de autores nacionais e internacionais convidados.

As datas de realização destas serão discutidas por via eletrônica e serão acertadas com todos os participantes do Núcleo. Para facilitar essa troca de mensagens, a exemplo do que foi feito no projeto ProComb, será criada uma lista eletrônica de todos os participantes, bem como uma conta na rede de computadores da instituição sede, onde serão armazenadas as publicações do Núcleo e outras informações relevantes.

• Intercâmbios com outros centros de pesquisa

Consideramos de extrema importância que os pesquisadores deste projeto realizem visitas a outros centros e também recebam visitantes do exterior. Essa troca de experiências é essencial no direcionamento das pesquisas. Estão previstas várias visitas de intercâmbio que ocorrerão sistematicamente durante a vigência deste projeto.

• Participação em congressos

Para que os pesquisadores se mantenham atualizados quanto ao estado-da-arte da área em que atuam é essencial que participem de congressos de primeira linha na sua área. Consideramos essa atividade de suma importância para o bom andamento deste projeto. No orçamento deste projeto estão previstas verbas para este tipo de atividade.