Procuramos por respostas para questões sobre as limitações da computação. Que problemas podem ser
resolvidos por algoritmos? Como comparar problemas e algoritmos por alguma medida de dificuldade?
Como se pode provar que certos problemas que pedem um algoritmo não podem ser resolvidos? O que
se ganha e o que se perde com restrições no formato dos algoritmos?

Alguns modelos de computação são apresentados, principalmente autômatos e máquinas de Turing. Com
autômatos são introduzidas a noção de não-determinismo, formalização de expressões regulares, e
caracterizações de linguagens regulares. Máquinas de Turing são usadas para modelar algoritmos, e
apresentar conceitos de computabilidade e complexidade computacional, bem como a existência de
problemas indecidíveis e de problemas NP-completos.
É desejável algum conhecimento prévio de Análise de Algoritmos e de Algoritmos em Grafo.

1 - Problemas, linguagens, expressões regulares.; 2 - Linguagens regulares.; 3 - Autômatos
determinísticos e não determinísticos.; 4 - Teorema de Kleene.; 5 - Autômatos reduzidos.; 6 - Máquinas de
Turing e a tese de Church-Turing.; 7 - Problemas indecidíveis.; 8 - Complexidade de tempo, classes P e
NP.; 9 - Problemas NP-completos e o Teorema de Cook-Levin.; 10 - Tópicos opcionais: minimização de
autômatos, linguagens livres de contexto, Teorema da Recursão, complexidade de espaço.