Plano de Trabalho

As diversas tarefas do ProComb descritas nos Itens 3, 4 e 6 foram separadas em três grandes grupos, a saber:

• Problemas estruturais e algorítmicos em grafos. Os problemas deste grupo são de dois tipos. No primeiro tipo estudam-se propriedades bem como condições necessárias e/ou suficientes para que um grafo tenha certas estruturas particulares. Também procura-se reconhecer classes de grafos com estruturas especiais para os quais diversos parâmetros de interesse podem ser determinados (por exemplo, número de estabilidade, número cromático). No segundo tipo enquadram-se problemas relacionados à busca eficiente de certas estruturas em grafos. Procura-se decidir a existência ou não de tais estruturas ou a determinação dessas estruturas que satisfaçam algum critério de otimalidade.

• Estudo de métodos poliedrais e multi-algorítmicos para problemas combinatórios NP -difíceis. Sob este tópico reunimos o estudo de métodos exatos e heurísticos aplicados a problemas NP -difíceis. Esses métodos são de diversos tipos, tais como, métodos poliedrais (branch and cut), métodos de busca tabu, times assíncronos, entre outros.

• Investigação de métodos probabilísticos em combinatória e teoria da computação. No Item 3, Estado da arte e justificativas, descrevemos em termos gerais em que contexto se localizam os tópicos mais específicos em que temos trabalhado, e em que iremos trabalhar dentro deste projeto sob este problema. Aqui destacamos os seguintes subprojetos: continuaremos o nosso estudo sistemático de subgrafos aleatórios do hipercubo n-dimensional assim como o de problemas numéricos e estruturais em teoria de Ramsey; estudaremos problemas extremais tipo Turán, com especial ênfase em problemas relativos a subgrafos extremais de grafos aleatórios; investigaremos derandomization de algoritmos, e ainda iniciaremos estudos sistemáticos de algoritmos probabilísticos e da teoria abstrata moderna de complexidade (provas com informação zero, provas interativas, verificação aleatória, etc).

Na tabela abaixo descrevemos as tarefas relacionadas a cada um dos problemas descritos acima, como referido nos Itens 3, 4 e 6. Além disso, indicamos os parceiros envolvidos em cada problema, e a respectiva dedicação na execução das tarefas.

Um dos objetivos de nosso projeto é fomentar a maior integração das instituições participantes. Para isso, programamos quatro grandes encontros dos pesquisadores envolvidos, na forma de três oficinas nacionais e um workshop internacional. Essas oficinas serão realizadas em dezembro de 1994, setembro de 1995 e outubro de 1996, e o workshop internacional está programado para abril de 1996.

Além do contato permanente entre os pesquisadores nacionais, a participação de pesquisadores estrangeiros convidados e as viagens de pesquisadores nacionais para instituições de ponta no exterior são de fundamental importância para trocas de idéias e conhecimentos. Assim, programamos visitas de 30 dias de seis pesquisadores estrangeiros espalhadas pelos dois anos, com dois pesquisadores para cada região geográfica envolvida (São Paulo, Rio e Campinas). Visitas a centros de pesquisa internacionais com a duração de 30 dias para 6 pesquisadores deste grupo estão também previstas dentro deste projeto. Ainda com relação a viagens de pesquisadores do grupo ao exterior, prevemos dentro destre projeto uma viagem a um congresso internacional para cada membro do grupo durante os dois anos de vigência do projeto.

Finalmente, não é possível mantermo-nos atualizados se não tivermos acesso à literatura mais recente, e se não acompanharmos as mudanças dos equipamentos de computação do mercado. Nenhuma área sofre de mudanças tão rápidas e freqüentes quanto a computação. Assim, incluímos em nosso pedido uma verba a fim de fornecer aos nossos pesquisadores bibliografia e equipamentos adequados para a execução das tarefas acima citadas.