Aulas Teóricas: 156

A) EMENTA
Estudo de modelos teóricos da computação: Máquina de Turing, Máquinas Universais, Funções Recursivas, Teoria dos Autômatos, Tese de Church e Linguages Formais.

B) OBJETIVOS / COMPETÊNCIAS
Dar ao aluno noção formal de algoritmo, computabilidade e do problema de decisão, de modo a deixá-lo consciente das limitações da ciência da computação. Aparelhá-lo com as ferramentas de modo a habilitá-lo a melhor enfrentar a solução de problemas com o auxílio do computador. Dar subsídios para o aluno poder definir linguagens de programação, isto é, sua sintaxe e semântica, por meio do estudo das linguagens formais.


C) BASES TECNOLÓGICAS (CONTEÚDO PROGRAMÁTICO)
1. Noções Básicas
2. Programas, Máquinas e Computações
2.1. Programas
2.2. Máquinas
2.3. Computação e Função computada
2.4. Equivalência de programas e máquinas
3. Máquinas Universais
3.1. Máquina de Norma
3.2. Máquina de Turing
3.3. Máquina de Post
3.4. Máquina de Pilhas
3.5. Autômatos com duas Pilhas
3.6. Modificações sobre Máquinas Universais
3.7. Hierarquia de Classe de Máquinas
3.8. Hipótese de Church
4. Funções Recursivas
4.1. Linguagem Lambda
4.2. Funções Recursivas de Kleene
4.3. Definições Recursivas de Bird
4.4. Importância das Funções Recursivas
5. Computabilidade
5.1. Classes de Solucionabilidade de Problemas
5.2. Problemas de Decisão
5.3. Problema da Auto-Aplicação
5.4. Princípio da Redução
5.5. Problema da Parada
5.6. Outros Problemas de Decisão
5.7. Problema P e NP
6. Linguagens Regulares
6.1. Sistemas de Estados Finitos
6.2. Autômatos Finitos Determinísticos
6.3. Autômatos Finitos Indeterminísticos
6.4. Autômatos Finitos Indeterminísticos com transições espontâneas.
6.5. Expressão Regular
6.6. Gramática Regular
6.7. Propriedades de Linguagens Regulares
6.8. Máquinas de Mealy e Moore
7. Linguagens Livres de Contexto
7.1. Conceitos de Linguagens Livres de Contexto
7.2. Propriedades de Linguagens Livres de Contexto
7.3. Autômatos Pilhas deterministicos e indeterministicos
7.4. Gramáticas Livres de Contexto
7.5. Simplificação de Gramáticas Livres de Contexto
7.6. Normalização de Gramáticas Livres de Contexto
7.7. Algoritmos para reconhecimento de Gramáticas Livres de Contexto


D) ATIVIDADES DISCENTES
1. Provas
2. Trabalhos
3. Listas de exercícios
4. Aulas práticas em Laboratório
5. Apresentação de Seminários


E) AVALIAÇÃO
O aluno será avaliado na forma de:
1. Prova escrita
2. Seminários
3. Prova oral
4. Trabalhos práticos


F) BIBLIOGRAFIA BÁSICA
HOPCROFT, John E. et al., Introdução a teoria dos autômatos, linguagens e computação. São Paulo: Campus, 2002.
MENEZES, Paulo Fernando Blauth. Linguagens Formais e Autômatos. 2ª ed. Porto Alegre: Sagra Luzzatto, 1998.
PAPADIMITRIOUS Christos H. e LEWIS, Harry R. Elementos da Teoria da Computação. Porto Alegre: Bookman, 2004.
TIARAJU, Asmuz Diverio e MENEZES, Paulo Fernando Blauth, Teoria da Computação:Máquinas Universais e Computabilidade. Porto Alegre: Sagra Luzzatto, 1999.
Vieira, Newton José. Introdução aos fundamentos da computação: Linguagens e Máquinas. São Paulo: Editora Pioneira Thomson Learning, 2006.

BIBLIOGRAFIA COMPLEMENTAR
EPSTEINT, Richard e CARNIELLI, Walter, Computabilidade, funções Computáveis, lógica e os fundamentos da Matemática, São Paulo: Editora Unesp, 2006.
KENNETH, LOUDEN C. Compiladores: princípios e práticas. Rio de Janeiro: Thomnon Pioneira, 2004.
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro: Livros Técnicos Científicos, 1993.
SCHEINERMAN, Edward R., Matemática discreta uma introdução. 5ª ed., Rio de Janeiro: Thomson Pioneira, 2004.

APOSTILAS E MATERIAIS DIVERSOS:
Site da Disciplina contendo material didático disponível em https://moodle.fema.edu.br