Objetivos
São objetivos da disciplina:
- Apresentar modelos matemáticos para formalização, especificação e reconhecimento de lingua gens computacionais, capacitando para a compreensão e/ou desenvolvimento de software básico incluindo compiladores e linguagens de programação
- Estudar os principais fundamentos da teoria da computação associados à computabilidade e solucionabilidade de problemas, bem como formalização de programas, máquinas, computação e formalismos que os definem
Pré-requisitos
Embora os pré-requisitos não sejam obrigatórios, o seu domínio auxiliará muito na evolução do aprendizado:
- Estruturas de dados (Conjuntos, Listas, Grafos e Hashtables)
- Conhecimento intermediário da linguagem de programação Python
- Noções básicas de Git e Github
Competências trabalhadas
As competências trabalhadas na disciplina são:
- Tratar problemas computacionais de maneira formal
- Formalizar e especificar modelos matemáticos capazes de reconhecer linguagens com basenos conceitos teóricos da computação
- Desenvolver aplicações computacionais tais como compiladores, modelagem de sistemas e linguagens de programação
- Aprimorar aplicações computacionais já existentes
Unidades de Aprendizagem
As unidades de aprendizagem abordadas na disciplina são:
- Análise crítica sobre os diversos tipos de autômatos finitos como reconhecedores de linguagens
- Compreensão sobre os formalismos geradores de palavras para criação de uma linguagem de programação
- Análise reflexiva das diferentes propriedades das linguagens regulares
- Estudo e prática de forma colaborativa sobre as gramáticas livres de contexto, árvore de derivação e suas simplificações correlacionando e contextualizando com as fases de um compilador
- Visão sistêmica sobre as formas normais de Chomsky como ferramenta de padronização de geradores de linguagens
- Compreensão sobre os formalismos associados às linguagens livres de contexto para o seu reconhecimento com postura analítica
- Identificação e análise reflexiva acerca das propriedades de fechamento e lema do bombeamento das linguagens livres de contexto
- Análise crítica para aplicação da Máquina de Turing como reconhecedor de linguagem
- Realização de simulações e experimentos práticos de linguagens formais, solucionando problemas de forma individual e cooperativa
Estratégias metodológicas
Elaboração de artigos e trabalhos práticos individuais relacionados às unidades de aprendizagem.
Cronograma
| Grau |
Id |
Peso |
Resumo |
Entrega |
| G1 |
T1 |
4.0 |
Implementação de um programa para simulação de autômatos finitos determinísticos.
|
05/06 |
| G1 |
T2 |
4.0 |
Implementação de um programa para a conversão de autômatos finitos não-determinísticos em autômatos finitos determinísticos
|
05/06 |
| G1 |
T3 |
2.0 |
Resolução de exercícios de prova matemática para autômatos finitos.
|
05/06 |
| G2 |
T4 |
4.0 |
Elaboração de artigo sobre a definição de uma linguagem de programação utilizando gramáticas livres de contexto.
|
14/08 |
| G2 |
T5 |
4.0 |
Elaboração de artigo e apresentação sobre decidibilidade e a Máquina de Turing.
|
14/08 |
| G2 |
T6 |
2.0 |
Implementação de um simulador de Máquina de Turing.
|
14/08 |
Procedimento e critérios de avaliação
A nota final será composta por trabalhos práticos de implementação e elaboração de artigos.
O grau 1 será composto por G1 = T1(4.0) + T2(4.0) + T3(2.0)
O grau 2 será composto por G2 = T4(4.0) + T5(4.0) + T6(2.0)
A nota final será a média (M) dada pela regra M = (G1 + G2) / 2
Para obter a aprovação, o aluno deve obter uma média (M) igual ou superior a 6, com frequência mínima de 8 encontros presenciais.
Material Complementar
Bibilografia
- Menezes, Paulo Blath. Linguagens Formais e Autômatos. 6a ed. Bookman, 2011.
- Sipser, Michael. Introdução à Teoria da Computação. Tradução da 2a. ed. americana. Cengage Learning, 2005.