Dar ao aluno noção formal de algoritmo, computabilidade e do problema de decisão, de modo a deixá-lo consciente das limitações da ciência da computação. Aparelhá-lo com as ferramentas de modo a habilitá-lo a melhor enfrentar a solução de problemas com o auxílio do computador. Dar subsídios para o aluno poder definir linguagens de programação, isto é, sua sintaxe e semântica, através do estudo das gramáticas formais.
Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares; Linguagens Livres de Contexto: Gramáticas Livres de Contexto; autômatos de pilha; Linguagens Sensíveis ao Contexto e Linguagens Recursivamente Enumeráveis: Máquinas de Turing. Tese de Church-Turing. Indecibilidade: Máquinas de Turing Universais.
Linguagens Regulares: Autômatos finitos determinísticos e não-determinísticos; expressões regulares; técnicas para identificar e descrever linguagens regulares; técnicas para mostrar que uma linguagem não é regular; propriedades de tais linguagens. Linguagens Livres de Contexto: Gramáticas Livres de Contexto; derivações; árvores de derivação; ambigüidade; autômatos de pilha; propriedades de tais linguagens; técnicas para mostrar que uma linguagem não é livre de contexto. Linguagens Sensíveis ao Contexto e Linguagens Recursivamente Enumeráveis: Máquinas de Turing; definições básicas e sua relação com a noção de um algoritmo/programa. Poder das Máquinas de Turing e Tese de Church-Turing. Indecibilidade: Máquinas de Turing Universais; Limitações sobre a nossa habilidade de computar; problemas indecidíveis. Teoria de Complexidade: Complexidade de Tempo, Complexidade de Espaço, Intratabilidade. Atividades de Extensão: Produção de vídeos disponibilizados publicamente sobre a história da ciência e, considerando a grande relevância da Informática no mundo, sobre questões que possam ser de interesse da sociedade. Também podem ser promovidos seminários abertos sobre esses assuntos. Carga Horária: 10 horas.
· Livro Texto: - John E. HOPCROFT, Jeffrey D. ULLMA, Rajeev MOTWANI. Introdução à teoria de autômatos, linguagens e computação. Editora Campus, 2003. - SIPSER, M. Introdução à teoria da computação. Thomson Learning, 2005. - ROSA, J. L. G. Linguagens Formais e Autômatos. Editora LTC, 2010. Bibliografia Complementar: - HAREL, D. Algorithmics – The Spirit of Computing. Addison-Wesley, 2. ed., 1992. - SIPSER, M. Introduction to the Theory of Computation. - GAREY & JOHNSON Computers and Intractability – a guide to the Theory of NP-Completeness, W.H. Freeman and Company, New York, 1979. - CORMEN, T.H.; LEISERSON, C.E.; RIVEST, R.L. Introduction to Algorithms. The Mit Press. 1. ed., 1990. - DIVÉRIO & MENEZES Teoria da Computação – Máquinas Universais e Computabilidade. Série Livros Didáticos 5, IF UFRGS, 2. ed., 2000, Sagra Luzzatto - MENEZES, P.B. Linguagens Formais e Autômatos, Série Livros Didáticos 3, IF UFRGS, 4. ed., 2001, Sagra Luzzatto - TOSCANI & VELOSO Complexidade de Algoritmos, Série Livros Didáticos 13, IF UFRGS, 1. ed., 2001, Sagra Luzzatto.