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
Capacitar o aluno a compreender e utilizar as principais técnicas da Teoria da Computação, possibilitando ao mesmo analisar, resolver e tratar problemas com uso de formalismos da Computação; compreender e utilizar notação formal; aprender as principais técnicas de computação teórica e sua aplicação na análise e resolução de problemas; aplicar técnicas da computação teórica para analisar problemas quanto a sua decidibilidade.


C) BASES TECNOLÓGICAS (CONTEÚDO PROGRAMÁTICO)
1. Introdução
1.1. Teoria dos autômatos
1.2. Teoria da computabilidade
1.3. Teoria da complexidade
2. Noções matemáticas e terminologia
2.1. Conjuntos e subconjuntos
2.2. Relações e funções
2.3. Sequências e uplas
2.4. Diagrama Sagital (Grafos) e Árvores
3. Conceitos centrais da teoria dos autômatos
3.1. Alfabeto
3.2. Cadeia
3.3. Linguagem
3.4. Gramática
3.4.1. Reconhecedores
3.4.2. Regras de produção
3.4.3. Definição da gramática
3.4.4. Classes gramaticais (hierarquia de Chomsky)
4. Linguagem e Autômato
4.1. Definição de linguagem
4.2. Linguagem regular
4.2.1. Propriedades
4.2.2. Lei do bombeamento em linguagem regular
4.3. Autômatos finitos
4.3.1. Funcionamento de um autômato finito
4.3.2. Autômatos finitos determinísticos (AFD)
4.3.3. Autômatos não determinísticos (AFN)
4.3.4. Equivalência entre os autômatos AFD e AFN
4.3.5. Procedimento para obter AFD equivalente
4.3.6. Redução de estados de um autômato finito
4.3.7. Procedimento para obter o AFD mínimo
4.4. Aplicação: busca de texto
4.4.1. Encontrando strings em texto
4.4.2. Autômatos finitos não determinísticos para busca de texto
4.4.3. Um AFD para Reconhecer um Conjunto de Palavras-Chave
4.5. Aplicação de máquina de estado em jogos e outras áreas
5. Expressões e gramáticas regulares
5.1. Definição de expressões regulares
5.1.1. Converter expressão regular em autômato finito
5.2. Gramática regular
5.2.1. Definição de gramática regular
5.2.2. Obter um AFD a partir de uma gramática regular
5.2.3. Obter uma gramática regular a partir de um AFD
5.3. Linguagens não regulares
5.3.1. Lema do bombeamento para linguagens não regulares
6. Linguagem livre do contexto
6.1. Gramática livre de contexto
6.2. Árvore de derivação
6.2.1. Propriedades da árvore de derivação
6.3. Representação na forma Backus-Nahur (BNF)
6.4. Forma Normal de Chomsky
6.4.1. Transformação para obter AFN
6.5. Autômatos com pilha
6.5.1. Execução do autômato com pilha
6.5.2. Linguagem não livre de contexto
6.5.3. Lei do bombeamento para linguagens livres de contexto
7. Linguagem sensível ao contexto
7.1. Gramática sensível ao contexto
7.2. Máquina de Turing
7.2.1. Funcionamento da máquina de Turing
7.2.2. Variantes da máquina de Turing
7.2.3. Terminologia para descrever máquina de Turing
7.3. Autômato linearmente limitado
7.3.1. Execução do autômato linearmente limitado
8. Teoria da Computabilidade
8.1. Definição da computabilidade
8.2.Tese de Church-Turing
8.3. Máquina universal de Turing
8.4. Problemas computáveis e não computáveis
8.5. Decidibilidade
8.5.1. Problemas decidíveis
8.5.2. Linguagens recursivas
8.5.3. Linguagens recursivamente enumeráveis
8.5.4. Problemas indecidíveis da teoria da linguagem
8.6. Redutibilidade
8.6.1. Redutibilidade por mapeamento
9. Teoria da complexidade
9.1. Complexidade de tempo
9.1.1. Definição da complexidade
9.1.2. Calculando a complexidade
9.1.3. Classe P
9.1.4. Classe NP
9.1.5. Classe NP completa

D) ATIVIDADES DISCENTES
1. Frequência às aulas
2. Exercícios
3. Trabalhos
4. Seminários

E) AVALIAÇÃO
1. Duas ou mais provas semestrais
2. Participação em aula
3. Trabalhos
4. Seminários

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.
SIPSER, Michael. Introdução à Teoria da Computação: Trad. 2ª ed. norte-americana. Porto Alegre: +A Educação - Cengage Learning Brasil, 2007. E-book. p.II. ISBN 9788522108862. Disponível em: https://integrada.minhabiblioteca.com.br/reader/books/9788522108862/. Acesso em: 19 fev. 2025.
PAPADIMITRIOUS Christos H. e LEWIS, Harry R. Elementos da Teoria da Computação. Porto Alegre: Bookman, 2004.

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

MATERIAL DIDÁTICO E APOSTILAS
NITTO, Marisa Atsuko. Material didático sobre Teoria da Computação, 2025. disponível em https://moodle.fema.edu.br