Plano de Ensino

IDENTIFICAÇÃO

EMENTA

Linguagens, gramáticas e reconhecedores. Hierarquia de Chomsky. Linguagens regulares. Linguagens livres de contexto. Linguagens sensiveis ao contexto. Linguagens recursivamente enumeraveis. Automatos finitos. Automatos com pilha. Automatos limitados linearmente. Maquinas de Turing. Tese de Church-Turing. Problemas indecidiveis e os limites da computação convencional. Computabilidade: A tese de Church-Turing, Decidibilidade, Redutibilidade. Complexidade: de tempo, de espaço. Intratabilidade.

JUSTIFICATIVA

O curso tem como objetivo apresentar os fundamentos de Teoria da Computação e Linguagens Formais relevantes para os alunos de Engenharia de Computação.

OBJETIVO

PROGRAMA

1) Introdução

  a) Teoria de autômatos

  b) Strings e linguagens

  c) Gramáticas

  d) Algoritmos

  e) Linguagens formais

  f) Hierarquia de Chomsky

2) Linguagens Regulares

  a) Autômatos finitos

  b) Operações regulares

  c) Linguagens finitas e linguagens regulares

  d) Propriedades de fecho de linguagens regulares

  e) Autômatos finitos não determinísticos

  f) Expressões regulares

  g) Equivalência entre AFDs, AFNs e REX

  h) Minimização de AFs

  i) Linguagens não regulares

3) Linguagens Livre de Contexto

  a) Gramáticas livre de contexto

  b) Gramáticas linear à direita

  c) Forma Normal de Chomsky

  d) Autômatos de pilha

  e) Equivalências entre CFG e PDA

  f) Linguagens não livres de contexto

4) Teoria da Computabilidade

  a) Definição de algoritmo, critérios de Mal’cev

  b) Máquina de Turing

  c) Funções numéricas e Turing-computáveis

  d) A Tese de Church-Turing

  e) Máquina de Turing: Universal e não-determinísticas

5) Indecidibilidade

  a) Uso da diagonalização de Cantor

  b) O Problema da Parada

  c) Problemas indecidíveis

  d) Linguagens recursivas

6) Complexidade computacional.

  a) Classes e relações de complexidade

  b) Complexidade de tempo e de espaço

  c) Redutibilidade

METODOLOGIA

Distribuição das atividades:

• Carga-horária de atividades síncronas (aulas online): 25 horas

• Carga-horária de atividades assíncronas (listas de exercícios, trabalhos práticos, material complementar): 20 horas

Moodle:

- Todas as informações relativas à disciplina como materiais, trabalhos, vídeoaulas, entre outros, serão informadas no Moodle.

- Página da disciplina: https://www.moodle.ufu.br/course/view.php?id=5857

- Os alunos matriculados receberão a senha de acesso à disciplina no Moodle por email na primeira semana de aula.

Atividades:

- As aulas serão realizadas a cada semana através de links no Moodle, conforme o cronograma apresentado na tabela a seguir.

Atividades síncronas:

- Os encontros síncronos serão realizados todas às quartas-feiras, das 13:10 às 14:50, por meio de ferramentas como o Google Meet, Microsoft Teams, Zoom, ou MConf/RNP.

- Os links serão divulgados no início de cada semana no Moodle. 

Atendimento aos alunos:

- O atendimento aos alunos será realizado de forma remota durante as aulas na modalidade síncrona, ou através do Fórum de Dúvidas no Moodle.

Sobre a presença:

- A presença no curso será contabilizada semanalmente por chamada durante as aulas síncronas.

AVALIAÇÃO

Sistema de Avaliação

- A avaliação será constituída por 3 provas e 3 trabalhos práticos individuais, conforme apresentado na tabela a seguir.

* O enunciado de cada trabalho será disponibilizado 10 dias antes, e prazo para a entrega será até às 11h59 do dia especificado na tabela acima.

Sobre os trabalhos:

- Cada trabalho abordará um tema referente ao conteúdo apresentado até a semana correspondente.

- Os trabalhos serão propostos no modelo de programação para resolução de problemas e competições (ex: ICPC, OBI, maratona de programação da SBC) e serão avaliados por um sistema de correção automática e posteriormente verificados pelo professor.

- Caso haja a detecção de plágio em um trabalho, todos os envolvidos receberão nota zero.

Sobre as provas:

- As provas serão realizadas pelo Moodle de forma individual e sem consulta a materiais de apoio.

Distribuição da Pontuação da disciplina:

• Prova 1: valor de 30 pontos
• Prova 2: valor de 30 pontos
• Prova 3: valor de 30 pontos
• Trabalho 1: valor de 3 pontos
• Trabalho 2: valor de 3 pontos
• Trabalho 3: valor de 4 pontos

BIBLIOGRAFIA

Básica

1. HOPCROFT, J. E.; MOTWANI, R.; ULLMAN, J.D.: Introduc;ao a Teoria de Automatos, Linguagens e Computac;ao Ed. Campus, 2002.
2. SIPSER, M. Introduction to Theory of Computation, Boston, Thomson, 2003
3. Rosa, João Luís Garcia, Linguagens formais e autômatos, Rio de Janeiro: Livro Científicos, 2010.

Complementar

1. Lewis, H. R. Elementos de Teoria da Computação, S. Paulo, Bookman, 1998.
2. Kozen, D. C., Theory of Computation, Springer Verlag, 2006.
3. GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação: um moderno de matemática discreta. 5a ed. Rio de Janeiro: LTC - Livros Técnicos e Cien ISBN 9788521614227.
4. Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren. Matemática concreta: funda a ciência da computação. Rio de Janeiro: LTC, c1995. 475 p. ISBN 9788521610403.
5. Paulo Fernando Blauth Menezes, Linguagens formais e autômatos, 5a Edição, Porto A 2002.

APROVAÇÃO

Aprovado em reunião do Colegiado realizada em: ____/____/______

Coordenação do Curso de Graduação: _________________________

---

Documento assinado eletronicamente por Felipe Alves da Louza, Professor(a) do Magistério Superior, em 24/06/2021, às 17:47, conforme horário oficial de Brasília, com fundamento no art. 6º, § 1º, do Decreto nº 8.539, de 8 de outubro de 2015.

---

A autenticidade deste documento pode ser conferida no site https://www.sei.ufu.br/sei/controlador_externo.php?acao=documento_conferir&id_orgao_acesso_externo=0, informando o código verificador 2858758 e o código CRC 760025B6.

---