Objetivos:
- Introduzir o conceito de complexidade dos algoritmos e conscientiza-lo das limitações da ciência da computação, habilitando-o a melhor resolver problemas com o auxílio do computador.
- Introduzir os conceitos de linguagem formal e autômatos, para auxiliar a resolver outra classe de problemas relacionados às linguagens de programação.
Programa:
- Autômatos Finitos e Linguagens Regulares: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares.
- Autômatos de Pilha e Linguagens Livres de Contexto: autômatos com pilha, linguagens livres de contexto, gramáticas livres de contexto e hierarquia de Chomsky.
- Conceitos básicos das teorias da computabilidade e da complexidade: Máquinas de Turing, problema da parada, decidibilidade, as classes de problemas P e NP e NP-completude.
- Docente: Marcelo de Souza Lauretto