9

Precisava representar e documentar um algoritmo aritmético em uma notação matemática, o problema é que não encontro a melhor maneira de representar um loop composto para isso.

Suponhamos que temos o simples algoritmo E:

public int E () {
    return n / (m + 200);
}

A representação matemática seria:

inserir a descrição da imagem aqui

E estou com dúvida em como representar uma função um pouco mais composta, como:

public int E () {
     int e = 0;
     for(int i = 0; i < 5; i++) {
        e += i;
        e *= i + 2;
     }
     return e;
}

E representando num somatório:

inserir a descrição da imagem aqui

Na fórmula acima, não há nenhuma implementação de até onde o loop, começa, pula e deve ir (sendo que no código, é definido que o loop percorrerá até que i < 5, sendo inicialmente i = 0 e por loop, i += 1).

Está certa esta representação científica? Ou existe outra maneira matemática de representar um loop do gênero?

3 Respostas 3

14

Da maneira que está:

public int E () {
     int e = 0;
     for(int i = 0; i < 5; i++) {
        e += i;
        e *= i + 2;
     }
     return e;
}

A função E sempre retornará o valor 714, então a representação matemática seria:

inserir a descrição da imagem aqui

Mas se generalizarmos considerando uma entrada n:

public int E (int n) {
     int e = 0;
     for(int i = 0; i < n; i++) {
        e += i;
        e *= i + 2;
     }
     return e;
}

Então teremos uma função recursiva disfarçada. Recursiva porque o valor de cada iteração dependerá do valor passado; a única diferença é que este valor é armazenado em uma variável local e é calculado iterativamente do 0 até n, enquanto que na versão recursiva a chamada é feita de n até 0, sendo n = 0 nossa condição de parada, uma vez que o laço não executaria e seria retornado o valor zero.

public int E (int n) {
    if (n == 0) {
        return 0;
    }

    return (n+2) * (E(n-1) + n)
}

Para efeitos de comparação com a versão original, ao calcular E(5) teremos o mesmo resultado, 714. Desta forma, podemos representar nossa função E(n) como:

inserir a descrição da imagem aqui

8
  • Isso não responde a pergunta. Onde foi aplicado o Loop na expressão? Commented 25/04/2019 às 19:04
  • 2
    @CypherPotato Na recursividade
    – Woss
    Commented 25/04/2019 às 19:05
  • Onde posso especificar o ínicio, passo e fim da recursividade no exemplo citado? Commented 25/04/2019 às 19:07
  • @CypherPotato O que você entende por passo e fim?
    – Woss
    Commented 25/04/2019 às 19:11
  • 5
    @CypherPotato, matematicamente não há distinção entre loop e recursão. É tanto que o paradigma funcional, aquele que deriva da matemática diretamente (cálculo lambda, sendo mais específico), não prevê iterações, apenas recursões. Commented 25/04/2019 às 19:31
11

Especificamente sobre operações de somatório e produtório, não de modo geral e não consegue representar o seu caso específico porque a ordem da operação é importante.

Existem operações que são feitas em coleções. Elas são funções unárias baseadas em operações binárias (vide operação binária), contanto que a operação binária em si defina, com a coleção dos elementos, um grupo abeliano (não confundir grupo e conjunto, são objetos matemáticos distintos). E somatório e produtório são exemplos dessas operações.

Não tenho a garantia da necessidade de que o grupo necessite ser abeliano, porém, como por si só um grupo não tem ordenação, me parece intuitivo que op(a,b) = op(b,a) precise ser verdadeiro

A definição de um operador de coleção é recursiva. Seja uma coleção S (vide bag) um elemento de C* (vide estrela de Kleene), e C um conjunto pertencente ao grupo G = {C, op, e}, onde op define uma operação comutativa em C e e é o elemento neutro de op. Podemos criar um operador de conjunto opX que recebe uma coleção e retorna um elmento de C. Sua assinatura é assim (em LaTeX fica mais elegante, mas fica para um próximo momento, foquemos em ASCII):

opX: C* -> C

Isso significa que opX recebe uma quantidade variável de elemento de C (portanto, uma coleção com repetições, vulgo bag) e devolve um elemento de C. Seu retorno é escalar em C.

Essa é a assinatura de opX, que identifica quais os tipos de entradas e qual a sua saída. A definição de opX, entretanto, é assim:

opX(S) = e, se S = {}
opX(S) = op(a, opX(S\{a})), a em S, S != {}

O somatório é definido desse jeito:

Σ(S) = 0, se S = {}
Σ(S) = +(a, Σ(S\{a})), se a em S, S != {}

E a de produtório:

Π(S) = 1, se S = {}
Π(S) = *(a, Π(S\{a})), se a em S, S != {}

Acontece que muitas vezes não interessa descrever todos os elementos em S para essas operações. Então se faz uma inferência de conjunto. Para fazer essa inferência, você deve passar uma função unária em X para mapeamento (se o domínio passado for distinto do domínio da operação básica). Ou seja, você precisa descrever uma função da seguinte assinatura:

map: X -> C

Então você define uma coleção S' baseada em S aplicando a função de maepamento map:

S' = {map(s), s em S}

Então, por convenção, foi definido o seguinte:

Σ(S, map) = Σ(S'), S' = {map(s), s em S}

Porém, como na maior parte das vezes o intervalo de inteiros consiste de números consecutivos, bastaria informar o início e o fim desse intervalo. Também se convencionou que é elegante mostrar qual a variável de iteração, por isso que se coloca i = 0 debaixo do símbolo do sigma (ou do pi, no produtório) e apenas um número arbitrário acima. Exemplo dessa notação: aqui.

Em notação ASCII, seria equivalente a isso:

Σ(ini, fim, map) = Σ(S, map) = Σ(S')
S = [ini, fim], S' = {map(s), s em S}

Onde [ini, fim] é o intervalo fechado dos números inteiros entre ini e fim.

Eu particularmente as vezes escrevo apenas que a variável de iteração está contida em um conjunto. Vide os produtórios.


O algoritmo definido no seu laço em pseudo-código, entretanto, não consigo fazer com que ele se torne uma operação em algum conjunto numérico relevante (naturais/inteiros/racionais/reais/complexos).

2

Isso aí me parece uma relação de recorrência.

A representação matemática poderia ser

E₀ = 0
Eₙ₊₁ = (Eₙ + n) * (n + 2) (para n > 0)

Na Wikipedia.

Obs. estou colocando a Wikipedia como referência porque faz muito tempo já que estudei matemática.

2
  • 1
    Isso não é a resposta do @AndersonCarlosWoss de maneira bem sumarizada? Commented 25/04/2019 às 20:55
  • acho que esta notação mais resumida é a mais usada quando me trabalha com relações de recorrência...a notação que ele utilizou me parece ser uma notação mais genérica para denotar funções, não só funções definidas de maneira recursiva, mas também, por exemplo, funções descontínuas que a gente vê quando aprende cálculo diferencial
    – zentrunix
    Commented 25/04/2019 às 21:01

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .