Carregando

Aula 7 - continuação

por Ariane Machado Lima

Recomendar
     
Gostei (0)

Licença de uso

Sobre a aula

Essa é a continuação da aula síncrona 7.

Disciplina

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

EMENTA

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.

Objetivo

Introduzir os conceitos de linguagens formais e autômatos e suas relações com linguagens de programação. Introduzir os conceitos básicos de computabilidade e complexidade, discutindo as limitações da ciência da computação.

Índice de vídeos da disciplina

  1. ACH2043 - ITC - Aula 14: Seção 2.2 - Autômato com Pilha (Parte 1)
  2. ACH2043 - ITC - Aula 13: Algoritmo CYK (Cocke–Younger–Kasami)
  3. ACH2043 - ITC - Aula 12: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 3)
  4. ACH2043 - ITC - Aula 11: Seção 2.1 - Gramáticas Livres-do-Contexto (Parte 2)
  5. Aula 8 - vídeo 1: Introdução a gramáticas e hierarquia de Chomsky
  6. Aula 8 - vídeo 2: Gramáticas regulares
  7. Aula 7 - continuação
  8. Aula 8 - vídeo 3: Equivalência entre gramáticas regulares e autômatos finitos
Pró-Reitoria de Graduação
Telefone: +55 11 3091-9942