DC-UFRPE/Licenciatura Plena em Computação/Teoria da Computação
Aspeto
Programa da Disciplina
[editar | editar código-fonte]Nome: Teoria da Computação | Código: 06223 |
Departamento: Departamento de Computação - (DC) | Área: Computação |
Carga-horária total: 60 horas | Créditos: 4 |
Carga-horária semanal: 4 horas (teóricas: 4; práticas: 0; EAD*: 0) | |
Pre-requisitos: MATEMÁTICA DISCRETA I e MATEMÁTICA DISCRETA II | |
Co-requisitos: Nenhum | |
Horários: Segunda-Feira: 20:10 as 21:50 e Quinta-Feira: 18:30 as 20:10 |
Ementa
[editar | editar código-fonte]Propriedades e operações com linguagens. Expressões regulares e gramáticas. Modelos clássicos de reconhecedores: autômatos finitos, autômatos a pilha, autômatos linearmente limitados, máquinas de Turing. Teorema de Kleene, equivalência entre autômatos à pilha e gramáticas. Hierarquia de Chomsky: linguagens regulares, livre de contexto, sensíveis ao contexto e recursivas. Propriedades de linguagens e funções recursivas. Tese de Church. Problemas indecidíveis: problema da parada, problema da correspondência de Post, redução entre problemas. Classes de problemas: P, NP, NP-Completo.
Prática como componente curricular
[editar | editar código-fonte]Não possui.
Metodologia de Aula
[editar | editar código-fonte]- Notas de aula divulgadas pelo professor Pablo Sampaio.
- Aulas Presenciais.
- Atividades semanais no Google Classroom.
- Extra: Videoaulas gravadas de semestre anteriores. Disponíveis no Youtube através do link: https://www.youtube.com/watch?v=x8DZUnBozik&list=PLIltuXQwfJd5ape9BY-PJcMzAD_Qf36Qn&index=1
Método Avaliativo
[editar | editar código-fonte]1VA
- Prova escrita (70% da nota da 1VA) + Listas de Exercícios Semanais (30% da nota da 1VA).
2VA
- Prova escrita (70% da nota da 2VA) + Listas de Exercícios Semanais (30% da nota da 2VA).
3VA
- Prova escrita.
FINAL
- Prova escrita.
Objetivos
[editar | editar código-fonte]- Capacitar o aluno na elaboração de algoritmos através do desenvolvimento do raciocínio lógico aplicado à solução de problemas computacionais, tornando-o capaz de resolver problemas simples de forma teórica e aplicá-los na prática em uma linguagem de programação.
- Apresentar os comandos de entrada e saída e suas utilizações.
- Apresentar os conceitos de variáveis e constantes e suas utilizações.
- Apresentar os operadores aritméticos e seu comportamento.
- Apresentar os operadores relacionais e lógicos e seu comportamento.
- Desenvolver a habilidade de construção de expressões e sua utilização.
- Apresentar o conceito de modularização.
- Desenvolver a habilidade de modularizar problemas em unidade menores.
Conteúdo Programático
[editar | editar código-fonte]- 1. Conceitos básicos
- 2. Linguagens Regulares
- 3. Linguagens Livres de Contexto
- 3.1 Gramáticas Livres de Contexto (GLC)
- 3.2 Autômatos de pilha (AP)
- 3.3 Equivalência entre GLCs e APs
- 4. Linguagens Sensíveis a Contexto
- 4.1 Autômatos Linearmente Limitados (ALLs)
- 5. Máquinas de Turing e Decidibilidade
- 5.1 Definição de Máquinas de Turing (MTs)
- 5.2 Variantes das MTs equivalentes
- 5.3 Tese de Church-Turing
- 5.4 Problemas decidíveis
- 5.5 Máquinas de Turing universais
- 5.6 Problema da parada em MTs
- 5.7 Outros problemas indecidíveis
- 6. Complexidade de Tempo
- 6.1 Avaliando tempo de execução de MTs
- 6.2 Classes P e NP 6.2 Problemas NP-Completos
- 6.3 Problema P =? NP
- 6.4 Relacionamentos entre as classes
Links úteis:
[editar | editar código-fonte]- JFLAP para simulação de autômatos
- Exemplo de lista de exercícios
- Notas de Aulas do Professor Pablo Sampaio
Vídeos Complementares
[editar | editar código-fonte]- Math's Fundamental Flaw, disponível no Youtube.
Bibliografia
[editar | editar código-fonte]Bibliografia básica:
[editar | editar código-fonte]- LOPES, Anita; GARCIA, Guto. Introdução à programação: 500 algoritmos resolvidos. Rio de Janeiro: Campus, 2002. 469p.
- Ziviani, Nivio. Projeto de Algoritmos. Editora Nova Fronteira, 2007.
- Sebesta, Robert W. Conceitos de Linguagens de Programação. Bookman, 2005.
- MENEZES, Nilo Ney Coutinho. Introdução à programação com Python: algoritmos e lógica de programação para iniciantes. 2.ed. rev. ampl. São Paulo: Novatec Editora, 2014. 328 p.
- SIPSER, M. Introdução a Teoria da Computação. 2a Edição Americana. Thomson, 2007.
- HOPCROFT, J. E.; MOTWANI, R.; e ULLMAN, J. D. Introdução à Teoria de Autômatos, Linguagens e Computação. Tradução da 2a Edição Americana. Editora Campus, 2002.
- LEWIS, Harry R; PAPADIMITRIOU, Christos H. Elementos de teoria da computação. 2. ed. Porto Alegre: Bookman, 2000
Bibliografia Complementar:
[editar | editar código-fonte]- MENEZES, Paulo Blauth. Linguagens formais e autômatos. 5. ed. Porto Alegre, RS: Bookman, 2008.
- DIVERIO, T. A.; MENEZES, P. B. Teoria da Computação: Máquinas Universais e Computabilidade. 3a edição. Bookman, 2011.
- GERSTING, J. L. Fundamentos Matemáticos para a Ciência da Computação. Quinta Edição. Rio de Janeiro: LTC, 2004.
- RAMOS, Marcus Vinícius Midena; JOSÉ NETO, João; VEGA, Ítalo Santiago. Linguagens formais: teoria, modelagem e implementação. Porto Alegre: Bookman, 2009.
- PAPADIMITRIOU, Christos M. Computational complexity. New York: Addison Wesley Longman,