Informações da Disciplina

 Preparar para impressão 

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


Instituto de Matemática e Estatística
 
Ciência da Computação
 
Disciplina: MAC0414 - Autômatos, Computabilidade e Complexidade
Automata, Computability and Complexity

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

Objetivos
Procuramos por respostas para questões sobre as limitações da computação. Que problemas podem ser
resolvidos por algoritmos? Como comparar problemas e algoritmos por alguma medida de dificuldade?
Como se pode provar que certos problemas que pedem um algoritmo não podem ser resolvidos? O que
se ganha e o que se perde com restrições no formato dos algoritmos?
 
We look for answers for questions on the limitations of computing. Which problems have an algorithmic solution? How to compare problems and algorithms along some measure of difficulty? How does one prove that some problems asking for an algorithm cannot be solved? What is gained and what is lost with restrictions on the format of algorithms?
 
 
Docente(s) Responsável(eis)
47490 - Arnaldo Mandel
91267 - Jose Coelho de Pina Junior
 
Programa Resumido
Alguns modelos de computação são apresentados, principalmente autômatos e máquinas de Turing. Com
autômatos são introduzidas a noção de não-determinismo, formalização de expressões regulares, e
caracterizações de linguagens regulares. Máquinas de Turing são usadas para modelar algoritmos, e
apresentar conceitos de computabilidade e complexidade computacional, bem como a existência de
problemas indecidíveis e de problemas NP-completos.
É desejável algum conhecimento prévio de Análise de Algoritmos e de Algoritmos em Grafo.
 
Some models for computation are presented, including automata and Turing machines. Automata are used to introduce non-determinism, formalization of regular expressions, and characterizations of regular languages. Turing machines are used to model algorithms and presentation of concepts of computability and computational complexity, as well as the existence of undecidable problems and NP-complete problems. Some prior knowledge of Analysis of Algorithms and Algorithms on Graphs is desirable.
 
 
Programa
1 - Problemas, linguagens, expressões regulares.; 2 - Linguagens regulares.; 3 - Autômatos
determinísticos e não determinísticos.; 4 - Teorema de Kleene.; 5 - Autômatos reduzidos.; 6 - Máquinas de
Turing e a tese de Church-Turing.; 7 - Problemas indecidíveis.; 8 - Complexidade de tempo, classes P e
NP.; 9 - Problemas NP-completos e o Teorema de Cook-Levin.; 10 - Tópicos opcionais: minimização de
autômatos, linguagens livres de contexto, Teorema da Recursão, complexidade de espaço. 
 
1 - Problems, languages, regular expressions.; 2 - Regular languages.; 3 - Deterministic and non-deterministic automata.; 4 - Kleene's Theorem.; 5 - Reduced automata.; 6 - Turing machines and the Church-Turing thesis.; 7 - Reducibility and undecidable problems.; 8 - Time complexity, classes P and NP.; 9 - NP-complete problems and the Cook-Levin Theorem.; 10 - Optional topics: automata minimization, context-free languages, The Recursion Theorem, space complexity.
 
 
Avaliação
     
Método
Média ponderada de exercícios e provas.
Critério
A média ponderada tem que ser maior ou igual a 5 para aprovação.
Norma de Recuperação
Em caso de média geral maior ou igual a 3 e menor que 5, a nova média geral consiste de uma média ponderada entre a média geral e uma prova de recuperação.
 
Bibliografia
     
Bibliografia Básica:
● H.R. Lewis, C.H. Papadimitriou, Elementos de Teoria da Computação, 2nd ed., Bookman, 2000.
● M. Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2012.
● J. Hefferon, Theory of Computation,https://hefferon.net/computation/index.html (download livre)
 

Clique para consultar os requisitos para MAC0414

Clique para consultar o oferecimento para MAC0414

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