Ementa de Aspectos Teoricos da Computação

PLANO DE ENSINO

CURSO: Ciência da Computação

SÉRIE: 6º semestre

DISCIPLINA: Aspectos Teóricos da Computação

CARGA HORÁRIA SEMANAL: 1,5 horas/aula

CARGA HORÁRIA SEMESTRAL: 30 horas/aula

I – EMENTA

Máquinas de Turing e a tese de Turing-Church; Problemas Solucionáveis e Não-Solucionáveis; Complexidade Computacional e Problemas NP-Completos. Problemas NP-Difíceis. Teorema da Incompletude de Gödel.

II - OBJETIVOS GERAIS

Permitir que os alunos travem contato com resultados teóricos da Ciência da Computação e avaliem adequadamente a importância dos mesmos.        

III - OBJETIVOS ESPECÍFICOS

•  Explicar a tese de Turing-Church e seu significado;
• Apresentar exemplos de problemas que não são computáveis;
•  Definir as classes de problemas P e NP;
•  Explicar o que são problemas NP-completos e NP-difíceis;
•  Apresentar o Teorema da Incompletude de Gödel.

IV - COMPETÊNCIAS

Compreender o conceito da máquina de Turing. Entender por que alguns problemas não apresentam solução algorítmica. Apropriar-se dos resultados teóricos que embasam a Ciência da Computação.

V - CONTEÚDO PROGRAMÁTICO

1.        Introdução

1.1        Hierarquia de Chomsky

1.2        Máquina de Estados Finitos

1.3        Máquina de Turing: modelo que simula procedimentos computacionais mais gerais que a máquina de estados finitos

2.        Máquinas de Turing – Parte I

2.1        A definição formal da Máquina de Turing

2.2        A computação na Máquina de Turing: funções recursivas e linguagens recursivamente enumeráveis

3.        Máquinas de Turing – Parte II

3.1        Extensões da Máquina de Turing

3.2        Máquinas de Turing com Acesso Aleatório

3.3        Máquinas de Turing Não-Determinísticas

4.        Máquinas de Turing como Calculadora de Funções Numéricas

5        Problemas Indecidíveis – Parte I

5.1      A Tese de Turing Church

5.2        Máquinas de Turing Universais

5.3        O Problema da Parada

6.         Problemas Indecidíveis – Parte II.

6.1    Problemas Não Solucionáveis sobre as Máquinas de Turing e sobre as Gramáticas

6.2      Propriedades das Linguagens Recursivas

7.         Tempo de Execução de um Programa.

7.1      Comportamento Assintótico de Funções

7.2  Classes de Comportamento Assintótico: complexidade logarítmica, complexidade polinomial (complexidade linear, complexidade quadrática, etc.); complexidade exponencial

8.        Complexidade Computacional – Parte I

8.1        A Classe P: definição

8.2        Grafos Eulerianos e Hamiltonianos

9.        Complexidade Computacional - Parte II

9.1        Problema do Caixeiro Viajante

9.2        Clique (Máximo e Mínimo)

9.3        Problema da Cobertura dos Nós

9.4        Problema do Particionamento

10.        Complexidade Computacional – Parte III

10.1        Satisfabilidade e Satisfabilidade Booleana

10.2        Problema da Mochila

11.        Completude NP e Problemas NP-Difíceis

11.1        Definição

11.2        Teorema de Cook

11.3        Problemas NP-Difíceis

12. O Teorema de Gödel

VI – ESTRATÉGIA DE TRABALHO

As aulas serão ministradas utilizando recursos tecnológicos digitais.

VII – AVALIAÇÃO

• Duas provas bimestrais.
• Trabalhos (individuais e/ou em grupos) e /ou listas de exercícios.

VIII – BIBLIOGRAFIA

Básica

LEWIS, Harry R. & PAPADIMITRION, Christos H.  - Elementos de Teoria da Computação. 2.ed. – Ed. Bookman, 2000.

MENEZES, Paulo Blauth. - Linguagens formais e autômatos. 2.ed. – Ed. Sagra Luzzatto, 1998.

DIVERIO, T. A. E Menezes, P.B. - Teoria da Computação Máquinas Universais e Computabilidade, Série Livros Didáticos Número 5, Instituto de Informática, da UFRGS, Editora Sagra Luzzatto, 1a edição, 1999.