Informações da Disciplina

 Preparar para impressão 

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


Escola de Artes, Ciências e Humanidades
 
Artes, Ciências e Humanidades
 
Disciplina: ACH2043 - Introdução à Teoria da Computação
Introduction to the Theory of Computing

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

Objetivos
Introduzir os conceitos de linguagens formais e autômatos e suas relações com linguagens de programação. Introduzir os conceitos básicos de computabilidade e complexidade, discutindo as limitações da ciência da computação.
 
 
 
Docente(s) Responsável(eis)
654070 - Ariane Machado Lima
1299170 - Marcelo de Souza Lauretto
3681080 - Marcio Moretto Ribeiro
 
Programa Resumido
Linguagens formais e autômatos. Conceitos básicos de computabilidade e complexidade.
 
 
 
Programa
Autômatos Finitos e Linguagens Regulares: sistemas de estados finitos, autômatos finitos, linguagens regulares, expressões regulares, gramáticas regulares. Autômatos de Pilha e Linguagens Livres de Contexto: autômatos com pilha, linguagens livres de contexto, gramáticas livres de contexto e hierarquia de Chomsky. Conceitos básicos das teorias da computabilidade e da complexidade: Máquinas de Turing, problema da parada, decidibilidade, as classes de problemas P e NP e NP-completude.
 
 
 
Avaliação
     
Método
Serão atribuídas notas a exercícios e trabalhos práticos, executados alguns em classe e outros fora de classe. A nota final será calculada pela média ponderada das notas obtidas pelo aluno nos trabalhos e provas, no decorrer do semestre.
Critério
Média ponderada das notas atribuídas às provas, exercícios e trabalhos práticos.
Norma de Recuperação
Avaliação baseada em provas e/ou trabalhos.
 
Bibliografia
     
Livros texto:  SIPSER, M. Introdução à Teoria da Computação Ed. Cengage Learning, 2005 Bibliografia complementar: • CARNIELLI, W. e EPSTEIN, R. Computabilidade, funções computáveis, lógica e os fundamentos da matemática. Ed. UNESP, 2009 • LEWIS, H. R.; PAPADIMITRIOU, C. H.. Elementos de Teoria da Computação. Ed. Bookman, 2000. 2 ed. • NEWTON, J. V. Introdução à Teoria da Computação: Linguagens e Máquinas, São Paulo: Pioneira Thomson Learning, 2006. • RAMOS, M. V. M.; NETO, J. J.; VEGA, I. S. Linguagens Formais: Teoria, Modelagem e Implementação. Ed. Bookman, 2009.
 

Clique para consultar os requisitos para ACH2043

Clique para consultar o oferecimento para ACH2043

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