Aps 6 periodo Ipesu

Aspectos Teóricos da Computação
© Todos os direitos reservados. Nenhuma parte desta obra pode ser reproduzida ou transmitida por qualquer forma e/ou quaisquer meios (eletrônico, incluindo fotocópia e gravação) ou arquivada em qualquer sistema ou banco de dados sem permissão escrita da Universidade Paulista.
3
APRESENTAÇÃO
Aspectos Teóricos da Computação
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;
— Explicar como alguns problemas não apresentam solução algorítmica;
— 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 – 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
4
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.1Problemas Não Solucionáveis sobre as Máquinas de Turing e sobre as Gramáticas.
6.2 Propriedades das