¿Qué significan esta notación de corchetes y paréntesis [first1, last1)?

136

He visto rangos de números representados como [first1,last1)y [first2,last2).

Me gustaría saber qué significa tal notación.

mathematical-notation Nav
fuente
3
[first, last)es un intervalo medio abierto como otros han notado. En algunos libros de texto, esto también se escribe [first, last>y tiene exactamente el mismo significado, solo que la sintaxis es diferente.
darioo
8
Un mejor lugar para esta pregunta sería math.stackexchange.com (en mi humilde opinión). ¡Pero no importa! :)
xk0der
8
Como mnemónico, piensa que el corchete se agarra a ese valor, que significa "hasta e incluyendo". Y el paréntesis redondo tiene un significado más suave y menos restrictivo: "hasta pero no incluido".
Eric Leschinski
Como programador cada vez que veo corchetes, siempre me recuerda el formato extendido Backus-Naur - en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
RBT
2
Recomiendo migrar esto a las matemáticas
Ben Leggiero

Respuestas:

226

Un paréntesis significa que el final del rango es inclusivo : incluye el elemento listado. Un paréntesis significa que el final es exclusivo y no contiene el elemento listado. Entonces [first1, last1), el rango comienza con first1(y lo incluye), pero termina justo antes last1.

Suponiendo enteros:

  • (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
fuente
3
Esto evoluciona del pre-álgebra de la escuela primaria, donde aprende sobre las funciones f (x) y el dominio y el rango de la función, donde una función como f (x) = x ^ 2, tendría un rango de 0 a infinito positivo, denotado con [0, ∞).
JohnMerlino
1
@Timbo ∞ no es un número.
JakeD
2
@pycoder tu definición de número parece innecesariamente limitante. en.wikipedia.org/wiki/Surreal_number
Timbo
2
@JakeD Con respecto a su comentario inicial, tiene razón en que el infinito no es un número, de ahí que el conjunto [0, ∞) no lo incluya.
wjandrea
1
∞ no es un número ordinal , del tipo con el que puedes hacer aritmética. Pero es un número cardinal válido al responder preguntas como "¿Cuántos enteros hay?". También es, como en este caso, perfectamente válido como límite
Kevin Wright, el
37

Eso es un intervalo medio abierto .

  • Un intervalo cerrado [a,b] incluye los puntos finales.
  • Un intervalo abierto los (a,b) excluye .

En su caso, se incluye el punto final al comienzo del intervalo, pero se excluye el final. Entonces significa el intervalo "first1 <= x <last1".

Los intervalos medio abiertos son útiles en la programación porque corresponden al idioma común para el bucle:

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

Aquí estoy en el rango [0, n).

Mark Byers
fuente
15

El concepto de notación de intervalos surge tanto en Matemáticas como en Ciencias de la Computación. La notación matemática [, ], (, )denota el dominio (o rango ) de un intervalo.

  • Los corchetes [y los ]medios:

    1. El número está incluido ,
    2. Este lado del intervalo está cerrado ,

  • El paréntesis (y los )medios:

    1. El número está excluido ,
    2. Este lado del intervalo está abierto .

Un intervalo con estados mixtos se llama "medio abierto" .

Por ejemplo, el rango de enteros consecutivos de 1 .. 10 (inclusive) se anotaría como tal:

  • [1,10]

Observe cómo inclusivese usó la palabra . Si queremos excluir el punto final pero "cubrir" el mismo rango, necesitamos mover el punto final:

  • [1,11)

Para los bordes izquierdo y derecho del intervalo, en realidad hay 4 permutaciones:

(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

¿Cómo se relaciona esto con las matemáticas y la informática?

Los índices de matriz tienden a usar un desplazamiento diferente según el campo en el que se encuentre:

  • Las matemáticas tienden a ser de una sola base.
  • Ciertos lenguajes de programación tienden a ser de base cero , como C, C ++, Javascript, Python, mientras que otros lenguajes como Mathematica, Fortran, Pascal están basados ​​en uno.

Estas diferencias pueden dar lugar a sutiles errores poste de la cerca , también conocido como off-by-one errores en la aplicación de algoritmos matemáticos, tales como para-bucles.

Enteros

Si tenemos un conjunto o matriz, digamos de los primeros números primos [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], los matemáticos se referirían al primer elemento como el elemento 1st absoluto . es decir, usar la notación de subíndice para denotar el índice:

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

Algunos lenguajes de programación, en contraste, se referirían al primer elemento como el elemento zero'th relativo .

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

Dado que los índices de la matriz están en el rango [0, N-1], entonces, por razones de claridad, sería "bueno" mantener el mismo valor numérico para el rango 0 .. N en lugar de agregar ruido textual como un-1 sesgo.

Por ejemplo, en C o JavaScript, para iterar sobre una matriz de N elementos, un programador escribiría el idioma común i = 0, i < Ncon el intervalo [0, N) en lugar del ligeramente más detallado [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>
Expandir fragmento

Los matemáticos, dado que comienzan a contar en 1, en su lugar usarían la i = 1, i <= Nnomenclatura, pero ahora necesitamos corregir el desplazamiento de la matriz en un lenguaje basado en cero.

p.ej

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>
Expandir fragmento

Aparte :

En los lenguajes de programación basados ​​en 0, es posible que necesite un kludge de un elemento ficticio cero para usar un algoritmo matemático basado en 1. por ejemplo , inicio de índice de Python

Punto flotante

La notación de intervalo también es importante para los números de punto flotante para evitar errores sutiles.

Cuando se trata de números de punto flotante, especialmente en Gráficos por computadora (conversión de color, geometría computacional, suavizado / fusión de animación, etc.) a menudo se usan números normalizados. Es decir, números entre 0.0 y 1.0.

Es importante conocer los casos límite si los puntos finales son inclusivos o 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

Donde M es alguna máquina épsilon . Es por eso que a veces puede ver const float EPSILON = 1e-#modismos en el código C (como 1e-6) para un número de coma flotante de 32 bits. Esta pregunta SO ¿EPSILON garantiza algo? Tiene algunos detalles preliminares. Para obtener una respuesta más completa, consulte el artículo de FLT_EPSILONDavid Goldberg Lo que todo informático debe saber sobre la aritmética de coma flotante.

Algunas implementaciones de un generador de números aleatorios random()pueden producir valores en el rango 0.0 .. 0.999 ... en lugar del más conveniente 0.0 .. 1.0. Los comentarios correctos en el código documentarán esto como [0.0,1.0) o [0.0,1.0] para que no haya ambigüedad en cuanto al uso.

Ejemplo:

  • Quieres generar random()colores. Convierte tres valores de coma flotante en valores de 8 bits sin signo para generar un píxel de 24 bits con canales rojo, verde y azul, respectivamente. Dependiendo del intervalo de salida por el random()que puede terminar con near-white(254,254,254) o white(255,255,255).
     +--------+-----+
     |random()|Byte |
     |--------|-----|
     |0.999...| 254 | <-- error introduced
     |1.0     | 255 |
     +--------+-----+

Para obtener más detalles sobre la precisión de punto flotante y la robustez con intervalos, consulte Detección de colisión en tiempo real de Christer Ericson , Capítulo 11 Robustez numérica , Sección 11.3 Uso robusto de punto flotante .

Michaelangel007
fuente
1

Puede ser una convención matemática en la definición de un intervalo donde los corchetes significan "extremal inclusivo" y los corchetes "extremal exclusivo".

Remolino
fuente