Of.: S-6 T:04 L:00 HS:04 SL:04 C:04

Pre-Req.: MC538

Ementa:

Famílias de algoritmos: universalidade, teorema SMN, teorema da recursão. Modelos computacionais. Funções recursivas: funções primitivas recursivas, funções recursivas. Computabilidade e decidibilidade: relativização, redução. Complexidade abstrata: "sdepped-up", "gap", teorema da compresão.

Programa:

1. Famílias de algorítmos
1. a noção do algoritmo
2. funções computáveis
3. decidibilidade
4. universalidade
5. teorema "S-M-N"
6. teorema da recursão
7. exemplos
2. Modelos computacionais concretos
1. Máquinas de Turing
2. RAMs
3. Algoritmos de Markov
4. Funções recursivas (sintaxe)
5. Exemplos
3. Funções recursivas
1. Parte semântica
2. Funções básicas
3. Funções primitivas recursivas
4. Exemplos
5. Funções totatis não primitivas recursivas
6. Recursão: variações
7. Funções recursivas
8. Exemplos
4. Computabilidade e Decidibilidade
1. Funções computáveis
2. Relativização
3. Conjuntos recursivos
4. Conjuntos recursivamente enumeráveis
5. Reduções
6. Exemplos
5. [opcional] Aplicações
1. lógica: exemplos
2. linguagens livre de contexto: exemplos
6. [opcional] Complexidade Abstrata
1. medidas de complexidade
2. teorema "sDepped-up"
3. teorema do "gap"
4. teorema da compressão
7. [opcional] Algoritmos e problemas intratáveis
1. complexidade exponencial
2. complexidade super-exponencial
3. complexidade elementar

Bibliografia:

F. Hennie. Introduction to Computability. Addison-Wesley, 1977

M. Machtey, P. Young. An Introduction to the General Theory of Algorithms. North-Holland, 1978

P. Odifreddi. Classical Recursion Theory. Elsevier, 1989

D. Harel. Algorithms: The Spirit of Computing. Addison-Wesley, 1993

M. Minsky. Computation: Finite and Infinite Machines. Prentice-Hall, 1967

H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967