Dados Gerais do Componente Curricular
| Tipo do Componente Curricular: |
DISCIPLINA |
| Tipo de Disciplina: |
REGULAR |
| Forma de Participação: |
DISCIPLINA REGULAR |
| Unidade Responsável: |
PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO (11.01.06.27) |
| Código: |
CCM-104 |
| Nome: |
TEORIA DA COMPUTAÇÃO |
| Carga Horária Teórica: |
48 h. |
| Carga Horária Prática: |
0 h. |
| Carga Horária Estudo Individual: |
96 h. |
| Carga Horária Dedicada do Docente: |
0 h. |
| Carga Horária Total: |
144 h. |
| Pré-Requisitos: |
|
| Co-Requisitos: |
|
| Equivalências: |
|
| Excluir da Avaliação Institucional: |
Não |
| Matriculável On-Line: |
Sim |
| Horário Flexível da Turma: |
Não |
| Horário Flexível do Docente: |
Sim |
| Obrigatoriedade de Nota Final: |
Sim |
| Pode Criar Turma Sem Solicitação: |
Não |
| Necessita de Orientador: |
Não |
| Exige Horário: |
Sim |
| Permite CH Compartilhada: |
Não |
| Permite Múltiplas Aprovações: |
Não |
| Quantidade de Avaliações: |
2 |
| Ementa/Descrição: |
Linguagens Regulares: autômatos finitos determinísticos e não-determinísticos, expressões regulares. Linguagens livres de contexto: gramáticas livres de contexto e autômatos com pilha. Máquinas de Turing: decidibilidade e reconhecibilidade. O problema da parada. Redução. Classes de complexidade: P, NP e NP-completo. |
| Referências: |
1. SIPSER, Michael. Introduction to the Theory of Computation. 3. ed. Cengage Learning, 2013. ISBN 978-1-133-18779-0.
2. HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introduction to Automata Theory, Languages, and Computation. 3. ed. Addison-Wesley-Longman, 2006. (Addison-Wesley series in computer science). ISBN 978-0-321-46225-1.
3. LEWIS, Harry R.; PAPADIMITRIOU, Christos H. Elements of the Theory of Computation. 2. ed. Prentice Hall, 1998. ISBN 978-0-13-262478-7. |
|
|
|
|
