Carregando

ACH2043 - ITC - Aula 04: Seção 1.2 - Não-Determinismo (Parte 1)

por Marcelo de Souza Lauretto

Recomendar
     
Gostei (0)

Licença de uso

Acesso Aberto (Verde)
Esta licença permite ao usuário copiar o conteúdo do e-Aulas USP, porém veta qualquer alteração e/ou sua utilização para fins comerciais ou não educacionais, autorizando seu compartilhamento sob licença com as mesmas características, desde que se atribua crédito aos autores. Esta licença permite o download do vídeo para usuários logados no sistema.

Sobre a aula

Nesta aula iniciamos a Seção 1.2 do Livro de Michael Sipser, "Introdução à Teoria da Computação".
Os tópicos abordados são:
a) Definição formal de um autômato não determinístico (AFN)
b) Computação de um AFN
c) Exemplos de AFNs.

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. ACH2043 - ITC - Tutorial JFLAP - AFD V01
  8. ACH2043 - ITC - Projetando autômatos finitos: exemplos
  9. ACH2043 - ITC - Aula 05: Seção 1.2 - Não-Determinismo (Parte 2)
  10. ACH2043 - ITC - Aula 04: Seção 1.2 - Não-Determinismo (Parte 1)
  11. ACH2043 - ITC - Aula 03: Seção 1.1 - Autômatos Finitos e Linguagens Regulares (Parte 2)
  12. ACH2043 - ITC - Aula 02: Seção 1.1 - Autômatos Finitos e Linguagens Regulares
  13. Aula 01: fim da aula de introdução
  14. ACH2043 - ITC 2020 T04 - Aula 01: Apresentação da disciplina
  15. Aula 02 - vídeo 2: Definição formal de Autômatos Finitos Determinísticos (AFDs)
  16. Aula 02 - vídeo 3: Definição de computação por um autômato
  17. Aula 4 - vídeo 1: Equivalência entre AFD e AFN - Introdução
  18. Aula 02 - vídeo 4: Linguagem Regular e Projeto de Autômato
  19. Aula 4 - vídeo 2: Equivalência entre AFD e AFN - Parte 1
  20. Aula 4 - vídeo 3: Equivalência entre AFD e AFN - Parte 2
  21. Aula 4 - vídeo 4: Equivalência entre AFD e AFN - Exemplo de Conversão
  22. Aula 4 - vídeo 5: Equivalência entre AFD e AFN - Últimos comentários
  23. Aula 6 - vídeo 1: Definição de Expressões Regulares
  24. Aula 6 - vídeo 2: Autômatos Finitos Não-Determinísticos Generalizados
  25. Aula 6 - vídeo 3: Equivalência entre expressões regulares e autômatos finitos (Parte 1)
  26. Aula 6 - vídeo 4: Equivalência entre expressões regulares e autômatos finitos (Parte 2)
  27. Aula 10 - vídeo 1: Introdução a gramáticas livres de contexto
  28. Aula 10 - vídeo 2: Aplicações de gramáticas livres de contexto
  29. Aula 10 - vídeo 3: Análise sintática e ambiguidade
  30. Aula 10 - vídeo 4: Mais sobre análise sintática e forma normal de Chomsky
  31. Aula 10 - vídeo 5: Algoritmo CYK
  32. Aula 12 - vídeo 1: Definição de Autômato com Pilha
  33. Aula 12 - vídeo 2: Computação por um Autômato com Pilha
  34. Aula 14 - vídeo 1: Conversão de GLC para APN
  35. Aula 14 - vídeo 2: Conversão de APN para GLC
  36. Aula 16 - vídeo 1: Máquinas de Turing - definição formal
  37. 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
  38. Aula 16 - vídeo 5: Formalização de Funcionamento de Máquinas de Turing
  39. Aula 16 - vídeo 6: Mais um exemplo
  40. Aula 18 - vídeo 1 - Máquinas de Turing Multifita
  41. Aula 18 - vídeo 2 - Máquinas de Turing Não Determinísticas
  42. ACH2043 - Aula 20 - vídeo 1: Definição de Algoritmo
  43. ACH2043 - Aula 20 - vídeo 3: O Problema de Hilbert
  44. ACH2043 - Aula 20 - vídeo 4: Exemplo de Máquina de Turing para resolver problemas
  45. Aula 23 - vídeo 1: Linguagens Decidíveis (parte 2)
  46. Aula 23 - vídeo 2: Linguagens não-Turing reconhecíveis
  47. Aula 25 - vídeo 1: Problemas Indecidíveis - Contextualização e Motivação
  48. Aula 25 - vídeo 2: Problemas Indecidíveis - Redutibilidade informal
  49. Aula 27 - vídeo 1: Redutibilidade por mapeamento - Introdução
  50. Aula 27 - vídeo 2: Redutibilidade por mapeamento - Conceitos
  51. Aula 27 - vídeo 3: Redutibilidade por mapeamento - Exemplo EQmt
  52. Aula 29 - vídeo 1: Complexidade de tempo - conceitos básicos
  53. Aula 29 - vídeo 2: Complexidade de tempo - a classe P
  54. Aula 29 - vídeo 3: Complexidade de tempo - a classe NP
  55. Aula 29 - vídeo 4: Complexidade de tempo - a classe NP-completa
Pró-Reitoria de Graduação
Telefone: +55 11 3091-9942