O que significam essa notação entre colchetes e colchetes entre parênteses [primeiro1, último1)?

136

Vi intervalos de números representados como [first1,last1)e [first2,last2).

Eu gostaria de saber o que significa essa notação.

Nav
fonte
3
[first, last)é um intervalo semiaberto, como outros observaram. Em alguns livros didáticos, isso também é escrito [first, last>e tem exatamente o mesmo significado, apenas a sintaxe é diferente.
darioo 9/12/10
8
Um lugar melhor para esta pergunta seria math.stackexchange.com (IMHO). Mas não importa! :)
xk0der
8
Como um mnemônico, pense que o colchete se apega a esse valor, significando "até e incluindo". E o parêntese redondo é um significado mais suave e menos restritivo: "até, mas não incluindo".
Eric Leschinski
Como programador sempre que vejo colchetes, ele sempre me lembra a forma Extended Backus-Naur - pt.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
RBT
2
Eu recomendo migrar isso para math.SE
Ben leggiero

Respostas:

226

Um colchete significa que o final do intervalo é inclusivo - inclui o elemento listado. Um parêntese significa que final é exclusivo e não contém o elemento listado. Portanto [first1, last1), o intervalo começa com first1(e inclui), mas termina logo antes last1.

Assumindo números inteiros:

  • (0, 5) = 1, 2, 3, 4
  • (0, 5] = 1, 2, 3, 4, 5
  • [0, 5) = 0, 1, 2, 3, 4
  • [0, 5] = 0, 1, 2, 3, 4, 5
Michael Mrozek
fonte
3
Isso evolui da pré-álgebra da escola primária, onde você aprende sobre as funções f (x) e o domínio e o intervalo da função, onde uma função como f (x) = x ^ 2 teria um intervalo de 0 a infinito positivo, indicado com [0, ∞).
31413 JohnMerlino
1
@Timbo ∞ não é um número.
precisa saber é
2
@pycoder, sua definição de número parece desnecessariamente limitadora. en.wikipedia.org/wiki/Surreal_number
Timbo 20/01
2
@JakeD Em relação ao seu comentário inicial, você está certo de que o infinito não é um número, por isso o conjunto [0, ∞) não o inclui.
Wjandrea
1
∞ não é um número ordinal , do tipo que você pode fazer aritmética. Mas é um número cardinal válido ao responder a perguntas como "Quantos números inteiros existem?". É também, como neste caso, perfeitamente válido como um limite
Kevin Wright
37

É um intervalo semi-aberto .

  • Um intervalo fechado [a,b] inclui os pontos finais.
  • Um intervalo aberto os (a,b) exclui .

No seu caso, o ponto final no início do intervalo está incluído, mas o fim é excluído. Então isso significa o intervalo "first1 <= x <last1".

Intervalos semi-abertos são úteis na programação porque correspondem ao idioma comum para loop:

for (int i = 0; i < n; ++i) { ... } 

Aqui eu estou no intervalo [0, n).

Mark Byers
fonte
15

O conceito de notação intervalo surge em ambos Matemática e Ciência da Computação. A notação matemática [, ], (, )indica o domínio (ou gama ) de um intervalo.

  • Os suportes [e ]meios:

    1. O número está incluído ,
    2. Este lado do intervalo está fechado ,
  • Os parênteses (e os )meios:

    1. O número é excluído ,
    2. Este lado do intervalo está aberto .

Um intervalo com estados mistos é chamado "semi-aberto" .

Por exemplo, o intervalo de números inteiros consecutivos de 1 a 10 (inclusive) seria anotado da seguinte forma:

  • [1,10]

Observe como a palavra inclusivefoi usada. Se queremos excluir o ponto final, mas "cobrir" o mesmo intervalo, precisamos mover o ponto final:

  • [1,11)

Para as bordas esquerda e direita do intervalo, existem na verdade 4 permutações:

(1,10) =   2,3,4,5,6,7,8,9       Set has  8 elements
(1,10] =   2,3,4,5,6,7,8,9,10    Set has  9 elements
[1,10) = 1,2,3,4,5,6,7,8,9       Set has  9 elements
[1,10] = 1,2,3,4,5,6,7,8,9,10    Set has 10 elements

Como isso se relaciona com a matemática e a ciência da computação?

Os índices de matriz tendem a usar um deslocamento diferente, dependendo do campo em que você está:

  • Matemática tende a ser um baseados.
  • Certas linguagens de programação tendem a ser baseadas em zero , como C, C ++, Javascript, Python, enquanto outras linguagens como Mathematica, Fortran, Pascal são baseadas em uma.

Essas diferenças podem levar a erros sutis de postes de cerca , também conhecidos como erros isolados por um ao implementar algoritmos matemáticos, como for-loops.

Inteiros

Se tivermos um conjunto ou matriz, digamos dos primeiros primos [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], os matemáticos se refeririam ao primeiro elemento como o elemento 1st absoluto . Por exemplo, usando notação subscrita para indicar o índice:

  • a 1 = 2
  • a 2 = 3
  • :
  • a 10 = 29

Algumas linguagens de programação, em contraste, se refeririam ao primeiro elemento como o elemento zero'th relativo .

  • a [0] = 2
  • a [1] = 3
  • :
  • a [9] = 29

Como os índices da matriz estão no intervalo [0, N-1], para fins de clareza, seria "bom" manter o mesmo valor numérico para o intervalo 0 .. N em vez de adicionar ruído textual , como um -1viés.

Por exemplo, em C ou JavaScript, para iterar sobre uma matriz de N elementos, um programador escreveria o idioma comum i = 0, i < Ncom o intervalo [0, N) em vez do ligeiramente mais detalhado [0, N-1]:

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 0; i < 10; i++ ) // [0,10)
       output += "[" + i + "]: " + a[i] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById('output1').innerHTML = output;
}
 <html>
     <body onload="main();">
         <pre id="output1"></pre>
     </body>
 </html>

Os matemáticos, como começam a contar com 1, usariam a i = 1, i <= Nnomenclatura, mas agora precisamos corrigir o deslocamento da matriz em uma linguagem baseada em zero.

por exemplo

function main() {
    var output = "";
    var a = [ 2, 3, 5, 7,  11, 13, 17, 19, 23, 29 ];
    for( var i = 1; i <= 10; i++ ) // [1,10]
       output += "[" + i + "]: " + a[i-1] + "\n";

    if (typeof window === 'undefined') // Node command line
        console.log( output )
    else
        document.getElementById( "output2" ).innerHTML = output;
}
<html>
    <body onload="main()";>
        <pre id="output2"></pre>
    </body>
</html>

Fora :

Nas linguagens de programação baseadas em 0, você pode precisar de um kludge de um elemento zero zero para usar um algoritmo matemático 1. por exemplo, Python Index Start

Ponto flutuante

A notação de intervalo também é importante para números de ponto flutuante para evitar erros sutis.

Ao lidar com números de ponto flutuante, especialmente em computação gráfica (conversão de cores, geometria computacional, facilitação / mistura de animações, etc.), muitas vezes são usados ​​números normalizados. Ou seja, números entre 0,0 e 1,0.

É importante conhecer os casos extremos se os pontos de extremidade são inclusivos ou exclusivos :

  • (0,1) = 1e-M .. 0,999 ...
  • (0,1] = 1e-M .. 1,0
  • [0,1) = 0,0 .. 0,999 ...
  • [0,1] = 0,0 1,0

Onde M é alguma máquina epsilon . É por isso que às vezes você pode ver o const float EPSILON = 1e-#idioma no código C (como 1e-6) para um número de ponto flutuante de 32 bits. Esta pergunta do SO EPSILON garante alguma coisa? tem alguns detalhes preliminares. Para obter uma resposta mais abrangente, consulte o artigo de FLT_EPSILONDavid Goldberg, O que todo cientista da computação deve saber sobre aritmética de ponto flutuante

Algumas implementações de um gerador de números aleatórios random()podem produzir valores no intervalo 0,0 .. 0,999 ... em vez do mais conveniente 0,0 .. 1,0. Comentários adequados no código documentarão isso como [0.0,1.0) ou [0.0,1.0], portanto, não há ambiguidade quanto ao uso.

Exemplo:

  • Você deseja gerar random()cores. Você converte três valores de ponto flutuante em valores de 8 bits não assinados para gerar um pixel de 24 bits com canais vermelho, verde e azul, respectivamente. Dependendo do intervalo de saída, random()você pode terminar com near-white(254.254.254) ou white( 255.255.255 ).
     +--------+-----+
     |random()|Byte |
     |--------|-----|
     |0.999...| 254 | <-- error introduced
     |1.0     | 255 |
     +--------+-----+

Para obter mais detalhes sobre precisão e robustez de ponto flutuante com intervalos, consulte Detecção de colisão em tempo real da Christer Ericson , capítulo 11 Robustez numérica , Seção 11.3 Uso robusto de ponto flutuante .

Michaelangel007
fonte
1

Pode ser uma convenção matemática na definição de um intervalo em que colchetes signifique "extremal inclusivo" e colchetes "extremal exclusivo".

Eddy
fonte