Introdução à Teoria da Computação

Calendário de Aulas e provas

• 03/09: Aula 1. Apresentação e motivação.. Slides.
• 05/09: Aula 2. Linguagens.
• Linguagens. Slides
• Primeiros operadores. Slides
• 10/09: Aula 3. Especificação finita de linguagens.
• Linguagens regulares. Slides
• Expressões regulares. Slides
• 12/09: Aula 4. Autômatos finitos determinísticos. Slides
• Autômatos Finitos Determinísticos - parte 1.
• Autômatos Finitos Determinísticos - parte 2.
• Autômatos Finitos Determinísticos - parte 3.
• Autômatos Finitos Determinísticos - parte 4.
• 17/09: Aula 5. Autômatos finitos não determinísticos. Slides
• Autômatos Finitos Não Determinísticos - Introdução.
• AFN com transições lambda.
• Remoção do não determinismo.
• Conclusão.
• 19/09: Aula 6. Minimização de autômatos finitos e o teorema de Kleene.
• Minimização de autômatos finitos. Slides
• O teorema de Kleene. Slides
• 24/09: SABER, não haverá aula.
• 26/09: SABER, não haverá aula.
• 01/10: Aula 7. Propriedades das linguagens regulares.
• Alguns teoremas. Slides
• O lema do bombeamento (introdução). Slides
• O lema do bombeamento (parte 2). Os slides são os mesmos do video anterior.
• O lema do bombeamento (parte 3). Os slides são os mesmos do video anterior.
• 03/10: Aula 8. Gramáticas Livres de contexto. Slides
• Introdução.
• Exemplos (parte 1).
• Exemplos (parte 2).
• 08/10: Aula 9. Gramáticas regulares. Slides
• Parte 1.
• Parte 2.
• Parte 3.
• Parte 4.
• 10/10: Aula 10. Introdução à análise sintática. Slides
• Parte 1.
• Parte 2.
• 15/10: Aula 11. Propriedades das GLC's. Slides
• Eliminação da recursividade do símbolo de partida.
• Variáveis que constituem produção vazia.
• Acréscimo de regras na gramática.
• Obtenção de gramática não contrativa.
• Eliminação de regras de cadeia.
• Eliminação de símbolos inúteis.
• 17/10: Aula 12. Formas normais. Slides
• Forma normal de Chomsky.
• Forma normal de Greibach.
• 22/10: Aula 13. Autômatos com pilha. Slides
• Introdução.
• Autômatos com pilha determinísticos.
• 24/10: Aula 14. Prova 1.
• 29/10: Aula 15. Autômatos com pilha não determinísticos. Slides
• Introdução.
• Critérios alternativos de aceitação.
• Provas das equivalências.
• 31/10: Aula 16. Relacionamento entre Gramáticas livre de contexto e Autômatos com pilha. Slides
• De gramáticas para autômatos com pilha.
• De autômatos com pilha para gramáticas.
• 05/11: Aula 17. Propriedades das linguagens livre de contexto. Slides
• Lema do bombeamento para Linguagens livre de contexto.
• Exemplos.
• Alguns teoremas sobre fechamento.
• 07/11: Aula 18. Máquinas de Turing padrão. Slides
• 12/11: Aula 19. Máquinas de Turing reconhecendo linguagens. Slides
• 14/11: Aula 20. Modelos alternativos de máquinas de Turing. Slides
• Aceitação por parada.
• Máquina de Turing multi trilhas.
• Máquina de Turing com fita infinita para os dois lados.
• Máquina de Turing multi fitas.
• Exemplos.
• 19/11: Aula 21. Máquinas de Turing não determinísticas e enumeradoras de linguagens. Slides
• Máquinas de Turing não determinísticas.
• Máquinas de Turing enumeradoras de linguagens.
• 21/11: Aula 22. Gramáticas irrestritas e a Hierarquia de Chomsky. Slides
• Gramáticas irrestritas.
• A Hierarquia de Chomsky.
• 26/11: Aula 23. Decidibilidade. Slides
• Motivação.
• O teorema da parada.
• 28/11: Aula 24. Complexidade computacional. Slides
• Introdução.
• Taxas de crescimento.
• Complexidade de MT's alternativas e complexidade de espaço.
• 03/12: Aula 25. Problemas tratáveis e não tratáveis. Slides
• Introdução.
• Circuito Hamiltoniano, versão determinística.
• Circuito Hamiltoniano, versão não determinística.
• 05/12: Aula 26. Classes de complexidade. Slides
• Introdução.
• NP-completude.
• Outras classes de complexidade.
• 10/12: Aula 27. SAT é NP-completo. Slides
• SAT está em NP.
• SAT é NP-difícil, parte 1.
• SAT é NP-difícil, parte 2.
• 12/12: Aula 28. Prova 2.
• 17/12: Prova final

---