|
UNIVERSIDADE FEDERAL DE UBERLÂNDIA Av. João Naves de Ávila, 2121, Bloco 3N - Bairro Santa Mônica, Uberlândia-MG, CEP 38400-902 |
|
Plano de Ensino
IDENTIFICAÇÃO
Componente Curricular: |
|||||||||
Unidade Ofertante: |
|||||||||
Código: |
Período/Série: |
Turma: |
|||||||
Carga Horária: |
Natureza: |
||||||||
Teórica: |
Prática: |
Total: |
Obrigatória: |
Optativa: |
|||||
Professor(A): |
Ano/Semestre: |
||||||||
Observações: |
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
Objetivo Geral: |
|
Objetivos Específicos: |
Ao completar a unidade curricular, espera-se que os estudantes sejam capazes de:
|
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 assíncronas (videoaulas, listas de exercícios): 9 horas-aulas
Moodle:
Todas as informações relativas à disciplina estarão 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.
Cronograma:
Serão realizadas aulas presenciais expositivas com uso de projetor, quadro negro, e demais materiais, conforme o cronograma apresentado na tabela a seguir.
Semana |
Conteúdo |
1 |
Introdução; Conceitos básicos; |
2 |
Linguagens Regulares (LR); Autômatos Finitos (AF); Não determinismo (AFN); |
3 |
Transição vazia; Expressões Regulares (ER); Equivalência entre ER e AF; |
4 |
Lema do Bombeamento para LRs; Operações Regulares; Outras operações sobre linguagens; |
5 |
Gramáticas; Hierárquia de Chomsky; Gramáticas Regulares; |
6 |
Linguagens Livres de Contexto; Árvores de derivação; Ambiguidade; Formas normais; |
7 |
Prova 1 |
8 |
Autômatos de Pilha (AP); |
9 |
Equivalência entre AP e Gramáticas Livres de Contexto; |
10 |
Máquinas de Turing; Autômatos Limitados Linearmente e Linguagens Sensíveis ao Contexto; |
11 |
A tese de Church-Turing; |
12 |
Decidibilidade; |
13 |
Teoria de Complexidade; |
14 |
Prova 2 |
15 |
Recuperação |
Atendimento aos alunos:
O atendimento aos alunos será realizado uma vez por semana na sala do professor na modalidade presencial, ou através do Fórum de Dúvidas no Moodle.
AVALIAÇÃO
Sistema de Avaliação
Serão realizadas 02 provas individuais e 10 provinhas individuais, conforme apresentado na tabela a seguir.
Provas |
Data |
Peso |
1 |
19/09 |
0,4 |
2 |
07/11 |
0,5 |
As provinhas serão realizadas ao longo do curso, durante o início de cada aula (15 minutos), e cada provinha terá peso 0,01 na nota final; Não haverá provinhas nas duas primeiras aulas.
Distribuição da Pontuação da disciplina:
A nota final NF será calculada da seguinte forma:
Obs.: cada provinha pi vale 1 ponto na média
Avaliação de recuperação:
Será oferecida uma avaliação de recuperação para os discentes que não obtiverem o rendimento mínimo para aprovação e com frequência mínima de 75%.
A avaliação de recuperação será composta por uma prova escrita no dia 21/11/2023, e será cobrado todo o conteúdo ministrado.
A nota da recuperação valerá 10 pontos e será somada à nota final obtida pelo estudante.
O estudante que realizar a atividade de recuperação e for aprovado terá limitada a sua nota final em 60 pontos.
BIBLIOGRAFIA
Básica
Complementar
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 05/08/2023, às 05:59, 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 4710637 e o código CRC F0ED7F97. |
Referência: Processo nº 23117.054632/2023-86 | SEI nº 4710637 |