Karla Roberta Pereira Sampaio Lima.

Programa Unificado de Bolsas

O desenvolvimento de ferramentas baseadas em modelos matemáticos robustos para lidar com problemas reais e computacionalmente intratáveis tem se alinhado cada vez mais às técnicas de otimização combinatória e à programação linear inteira devido ao enorme avanço tecnológico e a real necessidade de tratar grandes volumes de dados. Esses problemas intratáveis emergem da medicina, da bioinformática, da indústria, da logística e naturalmente recorrem à ciência da computação como meio para solucionar problemas de alta complexidade. A maioria dos problemas computacionais envolvidos na análise de dados biológicos, por exemplo, são de difícil resolução, conhecidos como problemas NP-difíceis, o que a priori fazem com que os pesquisadores se sintam desmotivados e limitados na busca por resultados satisfatórios. Em contrapartida, o uso das técnicas de Otimização Combinatória na análise de tais dados com a finalidade de reconhecer determinados padrões estruturais, tem proporcionado grandes conquistas no campo da bioinformática. Neste projeto, será investigado o problema de busca por padrões estruturais específicos em redes que podem representar interações biológicas, tais como redes metabólicas, neurológicas, de interação entre proteínas (PPI), dentre outras. Os objetivos consistem em desenvolver modelos matemáticos bem delimitados, implementar cada modelo proposto com a associação de técnicas algorítmicas da combinatória poliédrica e avaliar a qualidade de cada modelo tanto do ponto de vista teórico, com o desenvolvimento de algoritmos de aproximação, algoritmos exatos, construção de provas da corretude do modelo, quanto do ponto de vista prático com a implementação dos modelos e algoritmos propostos com intuito de obter soluções ótimas para instâncias reais de grande porte. O alcance final do projeto consiste em entregar uma ferramenta baseada em programação linear inteira e incorporada de técnicas e algoritmos da otimização combinatória que possa ser interpretada e viabilizada para o uso de problemas reais da bioinformática.

Diversos problemas reais podem ser modelados por meio de estruturasdiscretas, tais como grafos, ou por programas de programação linearinteiros ou mistos. Por exemplo, é possível modelar a relação deparentesco em comunidades indígenas por meio de grafos mistos e, daspropriedades destes grafos, extrair informações interessantes sobre ocomportamento destas comunidades. Pode-se modelar a dispersão desementes por aves no meio-ambiente através de um grafo bipartido, e aidentificação de padrões repetidos nestes grafos pode melhorar o nossoentendimento de como florestas se regeneram, e eventualmente podeajudar na identificação de fatores que interferem com essaregeneração.Otimização é uma área que se encontra na intersecção da matemática coma ciência da computação e que vem se desenvolvendo rapidamente desde adescoberta do método simplex para programação linear na década de1940. Métodos de otimização têm aplicações em diversas áreas, dentreas quais destacamos economia, biologia computacional, estudo de redessociais, logística, etc.O objetivo principal desse projeto é o estudo de estruturas discretase a investigação de diversos problemas de otimização, com ênfase nodesenvolvimento de técnicas e algoritmos, e no tratamento de questõesde natureza teórica a respeito desses problemas e estruturas. Dentreas técnicas que investigaremos destacam-se o uso de algoritmos deaproximação, algoritmos enumerativos, métodos probabilísticos,programação linear mista ou inteira, combinatória poliédrica, eprogramação semidefinida.

O principal objetivo do projeto é a aplicação de técnicas de otimização a diversos problemas, teóricos e práticos, com destaque ao uso de ferramentas de programação semidefinida, programação mista, combinatória poliédrica e algoritmos de aproximação. Nossas investigações contribuirão para avançar o estado-da-arte em otimização combinatória e em áreas correlatas.

A área de Ciência da Computação experimenta hoje um crescimento vertiginoso. Novidades tecnológicas surgem e tornam-se obsoletas em um ou dois anos de existência. Novas abordagens surgem com enorme rapidez. Tal desenvolvimento se dá por necessidades criadas em outras áreas do conhecimento de novas técnicas para resolver problemas cada vez mais complexos. Hoje em dia é impossível imaginar um pesquisador de qualquer área do conhecimento que possa desenvolver suas atividades sem o apoio de métodos, técnicas ou tecnologia desenvolvida por pesquisadores de Ciência da Computação. É evidente que os mais bem sucedidos avanços tecnológicos em Ciência da Computação estão fundamentados em resultados teóricos. Áreas como mineração de dados e reconhecimento de padrões, para citar apenas duas, têm seus métodos fortemente baseados em técnicas desenvolvidas em Teoria da Computação. Nosso objetivo neste projeto é o estudo de estruturas combinatórias e diversas formas de abordar problemas relacionados com tais estruturas: métodos algébricos, geométricos, probabilísticos, combinatórios, etc. Uma melhor compreensão destes objetos pode resultar em novas estratégias e algoritmos mais eficientes para resolver problemas a eles relacionados. A equipe proponente tem pesquisadores com grande experiência que cobrem uma ampla gama de subáreas de Teoria da Computação, permitindo uma maior sinergia para a solução dos problemas abordados. As principais contribuições esperadas neste projeto são a publicação de artigos científicos em conferências e periódicos bem estabelecidos, com alta circulação e de seletiva política editorial. Desejamos também intensificar o intercâmbio internacional do grupo e a formação de alunos nos vários níveis (de iniciação científica a pós-doutorandos). Pretendemos ainda, durante a execução do projeto, realizar uma Escola Avançada de Ciências na área de Teoria da Computação.