Informações da Disciplina

 Preparar para impressão 

Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação


Escola Politécnica
 
Engenharia de Comp e Sist Digitais
 
Disciplina: PCS3556 - Lógica Computacional
Computational Logic

Créditos Aula: 4
Créditos Trabalho: 0
Carga Horária Total: 60 h
Tipo: Semestral
Ativação: 01/01/2018 Desativação:

Objetivos
Apresentar uma introdução aos fundamentos matemáticos da Ciência da Computação, com ênfase em linguagens, reconhecedores (autômatos) e geradores (gramáticas). Enfatiza-se o estudo de dois tipos de questões no nível teórico: (I) Quais computações podem ser feitas em um computador? (II) Quão eficientemente podem ser realizadas?
 
An introduction to the mathematical foundations of Computer Science, with emphasis on languages, recognizers (automata) and generators (grammars). The study emphasizes the study of two types of questions at the theoretical level: (I) Which computations can be performed in one computer? (II) How efficiently can they be performed?
 
 
Docente(s) Responsável(eis)
48341 - João José Neto
1846990 - Ricardo Luis de Azevedo da Rocha
 
Programa Resumido
Elementos de linguagens formais, cadeias, alfabetos, linguagens, gramáticas e reconhecedores. Hierarquia de Chomsky. Expressões regulares, autômatos finitos. Autômatos de pilha, Gramáticas livres de contexto. Relação entre autômatos e linguagens. Máquinas de Turing. Computabilidade. Complexidade computacional. Decidibilidade. Aplicações dos elementos da teoria à Engenharia de Computação.
 
Elements of formal languages, strings, alphabets, languages, grammars and recognizers. Chomsky hierarchy. Regular expressions, finite automata. Pushdown automata. Context-free grammars. Relation between automata and languages. Turing machines. Computability. Computational complexity. Decidability. Applications of the elements of the theory to Computing Engineering.
 
 
Programa
1.	Revisão de matemática discreta.
2.	Linguagens, cadeias, alfabetos, conjuntos regulares.
3.	Hierarquia de Chomsky. Expressões regulares.
4.	Autômatos de estados finitos.
5.	Autômatos de pilha.
6.	Gramáticas livres de contexto.
7.	Máquinas de Turing. Computabilidade.
8.	Decidibilidade.
9.	Aplicações à Engenharia de Computação.
 
1. Discrete math review. 2. Languages, strings, alphabets, regular sets. 3. Chomsky hierarchy. Regular expressions. 4. Finite-state automata. 5. Pushdown automata. 6. Context-free grammar. 7. Turing machines. Computability. 8. Decidability. 9. Applications to Computing Engineering.
 
 
Avaliação
     
Método
Provas, atividades em sala de aula e projeto.
Critério
A = (P1 + 2*P2 + E) / 4 onde: P1, P2: são provas, e E: é o conceito relativo ao desempenho em atividades práticas, incluindo o projeto e os trabalhos desenvolvidos em classe. OBS: Para haver aprovação é necessário que o projeto esteja completamente desenvolvido, documentado e operante.
Norma de Recuperação
Prova escrita.
 
Bibliografia
     
1.	HOPCROFT; ULLMAN, J.D. Introduction to formal languages and automata theory, Addison-Wesley,1976.
2.	LEWIS, H.R.; PAPADIMITRIOU, C.H. Elements of the theory of computation, Prentice-Hall Inc., 1981, ISBN: 0-13-273417-6.
3.	JOHNSONBAUGH, R. Discrete Mathematics, Prentice-Hall Inc., 1997, ISBN: 0-13-518242-5.
4.	HARRISON, M.A. Introduction to formal language theory, Addison-Wesley, 1978.
5.	SIPSER, M. Introdução à Teoria da Computação, 2a ed. norte-americana, Editora Thomson Pioneira, 2007.
6.	RAMOS, M.V.M.; JOSÉ NETO, J.; VEGA, I.S. Linguagens Formais, Bookman, 2009.
 

Clique para consultar os requisitos para PCS3556

Clique para consultar o oferecimento para PCS3556

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP