Vídeo 15 de 35

Introdução à Teoria da Computação

Formatos disponíveis

Assista a esse vídeo em: MP4 (1280 X 720 px) | MP4 (640 X 360 px)

Licença de uso

Sobre a aula

Este vídeo demonstra a conversão de autômatos com pilha não-determinísticos (APN) em gramáticas livres de contexto (GLCs), concluindo assim a demonstração da equivalência entre APNs e GLCs.

Disciplina

ACH2043-1 Introdução à Teoria da Computação

EMENTA

Computabilidade: noção intuitiva, modelos computacionais, equivalência entre modelos e tese de Church, funções não-computáveis e o problema da parada. Enumerabilidade e decidibilidade: problemas não-decidíveis e semi-decidíveis. Linguagens formais e autômatos: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares, autômatos com pilha, linguagens livres de contexto e gramáticas livres de contexto, hierarquia de chomsky.

Objetivo

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.

Índice de vídeos da disciplina

1. Aula 02 - vídeo 1: Formalização de conceitos básicos para autômatos
2. ACH2043 - ITC - Aula 10: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 1)
3. ACH2043 - ITC - Aula 09: Seção 1.3 - Expressões Regulares (Parte 2)
4. ACH2043 - ITC - Aula 08: Seção 1.3 - Expressões Regulares (Parte 1)
5. ACH2043 - ITC - Aula 07: Seção 1.2 - Não-Determinismo (Parte 3)
6. ACH2043 - ITC - Aula 06: Algoritmo de Simulação de Autômatos Finitos Não Determinísticos
7. Aula 10 - vídeo 1: Introdução a gramáticas livres de contexto
8. Aula 10 - vídeo 2: Aplicações de gramáticas livres de contexto
9. Aula 10 - vídeo 3: Análise sintática e ambiguidade
10. Aula 10 - vídeo 4: Mais sobre análise sintática e forma normal de Chomsky
11. Aula 10 - vídeo 5: Algoritmo CYK
12. Aula 12 - vídeo 1: Definição de Autômato com Pilha
13. Aula 12 - vídeo 2: Computação por um Autômato com Pilha
14. Aula 14 - vídeo 1: Conversão de GLC para APN
15. Aula 14 - vídeo 2: Conversão de APN para GLC
16. Aula 16 - vídeo 1: Máquinas de Turing - definição formal
17. Aula 16 - vídeo 2: Exemplo de Def. Formal de Máquina de Turing e Definições de Implementação e de Alto-Nível
18. Aula 16 - vídeo 5: Formalização de Funcionamento de Máquinas de Turing
19. Aula 16 - vídeo 6: Mais um exemplo
20. Aula 18 - vídeo 1 - Máquinas de Turing Multifita
21. Aula 18 - vídeo 2 - Máquinas de Turing Não Determinísticas
22. ACH2043 - Aula 20 - vídeo 1: Definição de Algoritmo
23. ACH2043 - Aula 20 - vídeo 3: O Problema de Hilbert
24. ACH2043 - Aula 20 - vídeo 4: Exemplo de Máquina de Turing para resolver problemas
25. ACH2043 - Aula 22 - vídeo 1: Linguagens Decidíveis (parte 2)
26. ACH2043 - Aula 22 - vídeo 2: Linguagens não-Turing reconhecíveis
27. ACH2043 - Aula 24 - vídeo 1: Problemas Indecidíveis - Contextualização e Motivação
28. ACH2043 - Aula 24 - vídeo 2: Problemas Indecidíveis - Redutibilidade informal
29. ACH2043 - Aula 26 - vídeo 1: Redutibilidade por mapeamento - Introdução
30. ACH2043 - Aula 26 - vídeo 2: Redutibilidade por mapeamento - Conceitos
31. ACH2043 - Aula 26 - vídeo 3: Redutibilidade por mapeamento - Exemplo EQmt
32. ACH2043 - Aula 28 - vídeo 1: Complexidade de tempo - conceitos básicos
33. ACH2043 - Aula 28 - vídeo 2: Complexidade de tempo - a classe P
34. ACH2043 - Aula 28 - vídeo 3: Complexidade de tempo - a classe NP
35. ACH2043 - Aula 28 - vídeo 4: Complexidade de tempo - a classe NP-completa

Vídeos relacionados