Teoria da Computação

A área de Teoria da Computação visa fornecer fundamentos matemáticos rigorosos para as diversas áreas da Informática. O grupo de pesquisadores que a compõem no Departamento está envolvido em projetos que vão desde a lógica formal até a semântica denotacional, os cálculos de construção de programas e o projeto e análise de algoritmos sequenciais e paralelos. Na área da lógica formal tem-se obtido resultados significativos sobre generalizações dos conceitos de extensão, interpretação e implementação entre teorias para lógicas quaisquer. Na área de lógica algébrica desenvolveu-se uma álgebra relacional estendida, conhecida como Fork-Álgebra – a primeira álgebra finitamente axiomatizável da lógica de primeira ordem com igualdade. Na área da semântica de linguagens tem-se desenvolvido diferentes lambda-calculi baseados em lógicas subestruturais com modelos topológico-categóricos, tendo como principal objetivo uma caracterização estrutural de concorrência/paralelismo. Já na área de construção formal de programas foram desenvolvidos tanto um cálculo de programação não determinístico como diversos modelos formais do processo de desenvolvimento de software e ferramentas para apoiá-los. Na área de projeto e análise de algoritmos dedica-se especial atenção ao desenvolvimento de algoritmos seqüenciais e paralelos para problemas de otimização combinatória, teoria dos grafos e programação linear/inteira/dinâmica, envolvendo freqüentemente aplicações em problemas práticos em computação, automação e engenharia.