Resumo
O tema central deste projeto é a investigação de diversos problemas sobre objetos de natureza discreta, tendo como foco o estudo de algoritmos e de questões estruturais e teóricas sobre esses objetos. Daremos ênfase ao tratamento de "problemas difíceis"(formalmente conhecidos como problemas NP-difíceis), mas não nos restringiremos a esta classe de problemas. Consideraremos também problemas pertencentes a outras classes de complexidade, bem como problemas onde a dificuldade de se resolvê-los eficientemente está na falta de informação ou mesmo na descentralização das decisões de diferentes usuários, em contextos onde a decisão de um usuário afeta a decisão dos demais. Os estudos de natureza algorítmica que serão contemplados incluem projetos de algoritmos eficientes e práticos (quando possível, com garantia de desempenho), desenvolvimento de novas técnicas, e classificação de diversos problemas com relação à sua pertinência a diferentes classes de complexidade computacional. As questões estruturais sobre os objetos combinatórios que investigaremos incluem sua caracterização, propriedades, condições para sua existência, quantificação e construção dos mesmos. Os tópicos e técnicas que investigaremos estão inter-relacionados e são aplicáveis a diversas áreas como biologia computacional, otimização discreta, teoria dos grafos, logística e economia. Esperamos que a execução deste projeto tenha como fruto a obtenção de resultados relevantes, que contribuam para o avanço do estado da arte da área de conhecimento em que se inserem. Também esperamos que este projeto contribua para a formação e qualificação de novos pesquisadores. Ao fim do projeto, também esperamos um aumento da pesquisa em áreas ainda pouco estudadas no Brasil, mas para as quais há intensa atividade nos principais centros de pesquisa no exterior. (AU)
| Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio: |
| Pós-doutorado em otimização combinatória na Unicamp |
| Bolsas FAPESP de pós-doutorado em Ciência da Computação |