CCT-UFCA/Ciência da Computação/Teoria da Computação
Programa do Componente Curricular
[editar | editar código]| Código: | CC0067 | ||||||||
| Componente Curricular: | Teoria da Computação | ||||||||
| Semestre de Oferta: | 6º Semestre | Tipo: | Disciplina | Caráter: | Obrigatória | ||||
| Unidade Acadêmica Responsável: | Centro de Ciências e Tecnologia - CCT | ||||||||
| Área: | Teoria da Computação | ||||||||
| Créditos: | 4 | Carga horária: | 64 | Teórica: | 64 | Prática: | 0 | Extensão: | - |
| Pré-requisito: | CC0066 - Autômatos e Linguagens Formais | ||||||||
| Co-requisito: | |||||||||
| Equivalência: | CC0028 | ||||||||
Objetivos
[editar | editar código]Fornecer ao aluno os subsídios para a definição formal de algoritmo, computação e problemas decidíveis. Fazendo-o capaz de compreender os limites da computação.
Ementa
[editar | editar código]Funções e relações recursivas. Computabilidade. Problema da Parada. Reduções. Máquinas de Turing. Tese de Church-Turing. Indecidibilidade. Máquinas de Turing universais.
Conteúdo
[editar | editar código]Máquinas de Turing:
[editar | editar código]- O que realmente é um algoritmo?
- Máquina de Turing
- Variantes de Máquinas de Turing
- Funções recursivas
- Relações recursivas
- Decidibilidade
- Indecidibilidade
Metodologia
[editar | editar código]A disciplina de Teoria da Computação é trabalhada principalmente de forma teórica, ou seja, as aulas são presenciais e o professor conduz as explicações sobre os conteúdos que estão no plano de ensino. Durante as aulas, o professor utiliza muitos conceitos abstratos e lógicos, ensinando desde a base da Teoria da Computação até temas mais avançados, como máquinas de Turing e indecidibilidade. Além das explicações, o professor também trabalha resolvendo exercícios em sala para ajudar os alunos a fixarem melhor o conteúdo. Os alunos devem acompanhar a bibliografia recomendada, principalmente o livro do Sipser, que é a base das aulas. O ritmo da disciplina exige bastante atenção e dedicação, já que o conteúdo é bem denso e teórico.
Avaliação
[editar | editar código]A avaliação da disciplina funciona da seguinte forma: os alunos farão três provas durante o semestre. Cada prova aborda partes específicas do conteúdo que foi estudado até aquele momento.
A primeira prova cobre tudo relacionado a máquinas de Turing, incluindo suas variações. Já a segunda prova trata de funções e relações recursivas, que são conceitos mais ligados à lógica matemática. A terceira prova é sobre decidibilidade e indecidibilidade, que são temas que mostram os limites da computação, ou seja, o que um computador é ou não capaz de resolver.
A média final do aluno é a média simples dessas três provas. Se a média for igual ou superior a 7, o aluno já está aprovado e não precisa fazer mais nada. Se a média for menor que 4, o aluno está automaticamente reprovado. Mas se a média ficar entre 4 e 7, o aluno tem direito de fazer uma prova final. Nesse caso, a nota final será a média entre a média das três provas e a nota da prova final, sendo necessário ter pelo menos 5 em ambas (média final e nota da final) para ser aprovado.
Além disso, para ter direito à prova final ou ser aprovado direto, o aluno precisa ter uma frequência mínima de 75% nas aulas. Se faltar mais que isso, reprova por falta, independente da nota.
Caso o aluno perca uma das provas, ele pode solicitar a segunda chamada, desde que apresente uma justificativa válida (como atestado médico, por exemplo) e envie o pedido por e-mail em até 3 dias úteis após a data da prova.
Bibliografia Básica
[editar | editar código]- SIPSER, M. Introduction to the Theory of Computation. 3a ed. Cengage Learning, 2012. ISBN 9781133187790.
- LEWIS, H.; PAPADIMITRIOU, C. H. Elementos de Teoria da Computação. 2a ed. Editora Bookman, 1999. ISBN 9788573075342
- LINZ, P.; RODGER, S. H. An Introduction to Formal Languages and Automata. 7 ed. Editora Jones & Bartlett Learning, 2022. 572p. ISBN-13: 978-1284231601
Bibliografia Complementar
[editar | editar código]- MENEZES, P. B. Linguagens Formais e Autômatos: Volume 3, UFRGS: Editora Sagra Luzzatto. 6ª. Edição. Editora Bookman, 2010. ISBN-13: 978-8577807659
- HOPCROFT, J. E.; ULLMAN, J. D.; MOTWANI, R. Introdução à Teoria de Autômatos, Linguagens e Computação. 2ª edição. Rio de Janeiro: Editora Elsevier, 2002. ISBN-13: 9788535210729
- CARNIELLI, W. A.; EPSTEIN, R. L. Computabilidade, funções computáveis, lógica e os fundamentos da matemática. Unesp, 2005.
- BARAK, B. Introduction to Theoretical Computer Science. Texto disponível em https://github.com/boazbk/tcs - Versão compilada em 7 de Agosto de 2021.
- RICH, E. A. Automata, Computability and Complexity: Theory and Applications. 1st edition. Prentice Hall, 2007.