DC-UFRPE/Bacharelado em Ciência da 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 |
Pré-requisitos: | 14203 - MATEMÁTICA DISCRETA I 14203 - MATEMÁTICA DISCRETA II |
Ementa
[editar | editar código-fonte]Propriedades e operações com linguagens. Expressões regulares e gramáticas. Modelos 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, NPCompleto.
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
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
[editar | editar código-fonte]- Breve histórico.
- Linguagens e cadeias.
- Linguagens regulares.
- Autômatos finitos determinísticos;
- Definição formal;
- Exemplos;
- Linguagem de um autômato finito determinístico;
- Desenvolvendo autômatos finitos determinísticos;
- Autômatos finitos não determinísticos;
- Definição formal;
- Exemplos;
- Linguagem de um autômato finito não determinístico;
- Desenvolvendo autômatos finitos não determinísticos;
- Equivalência entre autômatos finitos determinísticos e não determinísticos;
- Expressões regulares;
- Definição;
- Exemplos;
- Equivalência com autômatos finitos;
- Lema do bombeamento para linguagens regulares;
- Autômatos finitos determinísticos;
- Linguagens livres de contexto.
- Gramáticas livres de contexto;
- Definição formal;
- Exemplos;
- Derivação;
- Ambiguidade;
- Forma normal de Chomsky;
- Autômatos de pilha;
- Definição formal;
- Exemplos;
- Equivalência com gramáticas livres de contexto;
- Lema do bombeamento para linguagens livres de contexto;
- Gramáticas livres de contexto;
- Máquinas de Turing.
- Definição formal e exemplos;
- Variantes da máquina de Turing (multifita e não determinística);
- Desenvolvendo máquinas de Turing;
- Indecidibilidade.
- Método de diagonalização;
- O problema da parada;
- Uma linguagem Turing-irreconhecível;
- Redução de problemas;
- Exemplos de problemas indecidíveis;
- Problema de correspondência de Post;
- Complexidade de tempo.
- Notação assintótica;
- A classe P;
- A classe NP;
- NP-completude;
- Reduções em tempo polinomial;
- Definição;
- Teorema de Cook Levin;
- Outros problemas NP-Completos;
Playlist sugerida para estudo.
Mais informação sobre conteúdos pode ser encontrado na antiga página de Teoria da Computação.
Bibliografia Básica
[editar | editar código-fonte]- SIPSER, Michael. Introdução à teoria da computação. 2. ed. São Paulo: Thomson, 2007.
- HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à teoria de autômatos, linguagens e computação. Rio de Janeiro: Campus, c2003.
- 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: 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, 1994.