Funções Recursivas

460 palavras 2 páginas
Ciência da Computação

Teoria da Computação
(ENG10395)

Profa. Juliana Pinheiro Campos
E-mail: jupcampos@gmail.com

TEORIA DA COMPUTAÇÃO

Funções recursivas
 Os formalismos usados para especificar algoritmos podem ser classificados nos seguintes tipos:
• Operacional: define-se uma máquina abstrata baseada em estados, em instruções primitivas e na especificação de como cada instrução modifica cada estado. Ex: MT.
• Axiomático: Associam-se regras às componentes da linguagem. As regras permitem afirmar o que será verdadeiro após a ocorrência de cada cláusula, considerando-se o que era verdadeiro antes da ocorrência. Ex: gramática.

TEORIA DA COMPUTAÇÃO

Funções recursivas
• Denotacional ou funcional: Trata-se de uma função construída a partir de funções elementares de forma composicional, no sentido em que o algoritmo denotado pela função pode ser determinado em termos de suas funções componentes. Ex: funções recursivas parciais (de
Stephen C. Kleene) e cálculo lambda (de Alonzo
Church)

TEORIA DA COMPUTAÇÃO

Funções recursivas de Kleene (ou funções recursivas parciais)
 São funções construídas sobre 3 funções naturais básicas
(funções recursivas primitivas):
• natural zero visto como uma função
• sucessor (de um número natural)
• projeção (na realidade, uma família de funções, pois depende do n° de componentes, bem como de qual componente deseja-se projetar) juntamente com as seguintes operações:
• substituição composicional (generaliza o conceito usual de composição de funções)

TEORIA DA COMPUTAÇÃO

Funções recursivas de Kleene (ou funções recursivas parciais)
• recursão (definição de uma função em termos dela mesma)
• minimização (busca, em um tempo finito, o menor valor para o qual uma certa condição ocorre) constituindo uma forma compacta e natural para definir muitas funções e suficientemente poderosa para descrever toda função intuitivamente computável.

TEORIA DA COMPUTAÇÃO


Relacionados

  • funções recursivas
    574 palavras | 3 páginas
  • Funçoes recursivas
    276 palavras | 2 páginas
  • recursividade
    1230 palavras | 5 páginas
  • Recursividade
    2088 palavras | 9 páginas
  • nada nenhum
    4883 palavras | 20 páginas
  • Lista de exercícios de teoria da computação
    1192 palavras | 5 páginas
  • A2 TADS4 Estrutura De Dados Teleaula 2 Tema 2 Impressao
    1244 palavras | 5 páginas
  • Topico 01 Prog Estrut 2 Fun Es
    935 palavras | 4 páginas
  • estudante
    1211 palavras | 5 páginas
  • Estrutura
    1428 palavras | 6 páginas