2CI1059 Introdução À Teoria Da Computação

SEI/UFPR - 1313060 - PROGRAD: FORMULÁ... https://sei.ufpr.br/sei/web/controlador.php?ac...
MINISTÉRIO DA EDUCAÇÃO
UNIVERSIDADE FEDERAL DO PARANÁ
SETOR DE CIÊNCIAS EXATAS
Departamento de Informática
Ficha 2 (variável)
Disciplina: Introdução à Teoria da Computação Código: CI1059
Natureza:
( x ) Obrigatória ( x ) Semestral ( ) Anual ( ) Modular
( ) Optativa
Pré-requisito: CI1055
/ CI1068 / CI1003 /
CMA111 / CM304 /
CI1056 / CI1210 / Modalidade: ( x ) Presencial ( ) Totalmente EAD ( ) CH
Co-requisito:
CI1001 / CMA211 em EAD: _______
/ CM303 / CI1057
/ CI1212 / CI1002 /
CI1237 / CE009 /
CH Total: 60 Estágio de
Prática
Padrão (PD): Laboratório Campo (CP): Estágio (ES): Orientada Formação
CH Semanal: 45 Especíﬁca (PE):
(LB): 15 0 0 (OR): 0 Pedagógica
4 0
(EFP): 0
EMENTA
Linguagens e máquinas. Máquinas e gramáticas para linguagens regulares, livres de contexto, sensíveis ao contexto,
recursivas e recursivamente enumeráveis. O relacionamento entre linguagens reconhecidas por máquinas e linguagens
geradas por gramáticas. A hierarquia de Chomsky. O problema da parada. Decidibilidade e Computabilidade.
Complexidade computacional. Tratabilidade e NP-completude.
PROGRAMA
1. Conceitos elementares
2. Linguagens Regulares
1. Autômatos Finitos Determinísticos e não Determinísticos
2. Equivalências
3. Linguagens que não são regulares e lema do bombeamento
4. Gramáticas Regulares
5. Relação entre Autômatos Finitos e Gramáticas Regulares
3. Linguagens Livre de Contexto
1. Autômatos com Pilha Determinísticos e não Determinísticos
2. Equivalências
3. Linguagens que não são livre de contexto e lema do bombeamento
4. Gramáticas Livre de Contexto
5. Formas Normais
6. Breve introdução ao Parsing
1 of 3 02/03/2020 15:28
7. Relação entre Autômatos com Pilha e Gramáticas Livre de Contexto

4. Linguagens Recursivamente Enumeráveis
1. Máquina de Turing Padrão
2. Máquinas de Turing que reconhecem linguagens. Modelos alternativos.
3. Equivalências
4. Linguagens que não são Recursivamente Enumeráveis. Teorema da Parada. Demonstração.
5. Gramáticas Irrestritas
6. Formas Normais
7. Relação entre Máquinas de Turing e Gramáticas Irrestritas
5. A hierarquia de Chomsky
6. Decidibilidade
1. Breve introdução ao conceito de decidibilidade
7. Computabilidade
1. Noções de complexidade de tempo e espaço
8. Tratabilidade e NP-Completude
1. Prova que SAT é NP-Completo
OBJETIVO GERAL
Apresentar ao estudante os conceitos fundamentais em Teoria da Computação, linguagens e máquinas.
OBJETIVO ESPECÍFICO
Caracterizar a computação como um modelo teórico e mostrar que é possível estudar algoritmos e computação apenas
usando modelos matemáticos.
PROCEDIMENTOS DIDÁTICOS
Aulas expositivas usando lousa e projeção de slides.
FORMAS DE AVALIAÇÃO
Média aritmética simples de três provas, a primeira sobre a parte 1, a segunda a parte 2 e a terceira as partes de 4 a 8.
BIBLIOGRAFIA BÁSICA (mínimo 03 títulos)
Thomas Sudkamp. Languages and Machines: An Introduction to the Theory of Computer Science. Third Edition. Addison-
Wesley, 2006.
John E. Hopcroft, Jeﬀrey D. Ullman e Rajeev Motwani. Introdução a Teoria de Autômatos, Linguagens e Computação.
Segunda Edição. Editora Campus, 2003.
Michael Sipser. Introduction to the Theory of Computation. Second edition. Course Technology, 2005.
BIBLIOGRAFIA COMPLEMENTAR (mínimo 05 títulos)
Newton José Vieira. Introdução aos Fundamentos da Computação. Pioneira Thomson Learning, 2006.
Harry F. Lewis e Christos H. Papadimitriou. Elementos de Teoria da Computação. 2a edição. Editora Bookman, 1998.
John C. Martin, Introduction to Languages and the Theory of Computation. second edition, McGraw-Hill Series in
Computer Science, 1997. ISBN: 0-07-040845-9
Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994 isbn: 0-201-53082-1
Paulo F. B. Menezes, Linguagens Formais e Autômatos, Sagra Luzatto, 2a edição, 1998 isbn: 85-241-0554-2
*OBS: ao assinalar a opção CH em EAD, indicar a carga horária que será à distância.
Documento assinado eletronicamente por MARCOS ALEXANDRE CASTILHO, PROFESSOR DO MAGISTERIO SUPERIOR, em 03/05/2019,
às 15:17, conforme art. 1º, III, "b", da Lei 11.419/2006.
2 of 3 02/03/2020 15:28
A autenticidade do documento pode ser conferida aqui informando o código verificador 1313060 e o código CRC A49D9DA9.
3 of 3 02/03/2020 15:28

2CI1059 Introdução À Teoria Da Computação

Enviado por

Direitos autorais:

Formatos disponíveis

2CI1059 Introdução À Teoria Da Computação

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

2CI1059 Introdução À Teoria Da Computação

Enviado por

Direitos autorais:

Formatos disponíveis

SEI/UFPR - 1313060 - PROGRAD: FORMULÁ... https://sei.ufpr.br/sei/web/controlador.php?ac...

UNIVERSIDADE FEDERAL DO PARANÁ

SETOR DE CIÊNCIAS EXATAS

Disciplina: Introdução à Teoria da Computação Código: CI1059

( x ) Obrigatória ( x ) Semestral ( ) Anual ( ) Modular

7. Relação entre Autômatos com Pilha e Gramáticas Livre de Contexto

Apresentar ao estudante os conceitos fundamentais em Teoria da Computação, linguagens e máquinas.

Aulas expositivas usando lousa e projeção de slides.

BIBLIOGRAFIA BÁSICA (mínimo 03 títulos)

BIBLIOGRAFIA COMPLEMENTAR (mínimo 05 títulos)

Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994 isbn: 0-201-53082-1

Você também pode gostar