Que signifie cette notation entre crochets et parenthèses [premier1, dernier1)?

137

J'ai vu des plages de nombres représentées par [first1,last1)et [first2,last2).

J'aimerais savoir ce que signifie une telle notation.

mathematical-notation Nav
la source
3
[first, last)est un intervalle semi-ouvert comme d'autres l'ont noté. Dans certains manuels, cela est également écrit comme [first, last>et a exactement la même signification, seule la syntaxe est différente.
darioo
8
Un meilleur endroit pour cette question serait math.stackexchange.com (IMHO). Mais tant pis! :)
xk0der
8
En tant que mnémonique, pensez que la parenthèse carrée saisit cette valeur, signifiant «jusqu'à et y compris». Et la parenthèse ronde est plus douce et moins restrictive: «jusqu'à mais non compris».
Eric Leschinski
En tant que programmeur, chaque fois que je vois des crochets, cela me rappelle toujours le formulaire Extended Backus-Naur - en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
RBT
2
Je recommande de migrer ceci vers math.SE
Ben Leggiero

Réponses:

227

Un crochet signifie que la fin de la plage est inclusive - elle inclut l'élément répertorié. Une parenthèse signifie que la fin est exclusive et ne contient pas l'élément répertorié. Donc pour [first1, last1), la plage commence par first1(et l'inclut), mais se termine juste avant last1.

En supposant des entiers:

  • (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
la source
3
Cela évolue depuis la pré-algèbre de l'école primaire, où vous en apprenez davantage sur les fonctions f (x) et le domaine et la plage de la fonction, où une fonction comme f (x) = x ^ 2, aurait une plage de 0 à l'infini positif, notée par [0, ∞).
JohnMerlino
1
@Timbo ∞ n'est pas un nombre.
JakeD
2
@pycoder votre définition du nombre semble inutilement limitative. en.wikipedia.org/wiki/Surreal_number
Timbo
2
@JakeD Concernant votre commentaire initial, vous avez raison en ce sens que l'infini n'est pas un nombre, d'où la raison pour laquelle l'ensemble [0, ∞) ne l'inclut pas.
wjandrea
1
∞ n'est pas un nombre ordinal , du type avec lequel vous pouvez faire de l'arithmétique. Mais c'est un nombre cardinal valide pour répondre à des questions telles que "Combien y a-t-il d'entiers?". C'est aussi, comme dans ce cas, parfaitement valable comme limite
Kevin Wright
37

C'est un intervalle semi-ouvert .

  • Un intervalle fermé [a,b] comprend les points d'extrémité.
  • Un intervalle ouvert les (a,b) exclut .

Dans votre cas, le point final au début de l'intervalle est inclus, mais la fin est exclue. Cela signifie donc l'intervalle "first1 <= x <last1".

Les intervalles semi-ouverts sont utiles en programmation car ils correspondent à l'idiome commun pour la boucle:

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

Ici, i est compris entre [0, n).

Mark Byers
la source
15

Le concept de notation par intervalles apparaît à la fois en mathématiques et en informatique. La notation mathématique [, ], (, )désigne le domaine (ou gamme ) d'un intervalle.

  • Les parenthèses [et ]signifie:

    1. Le numéro est inclus ,
    2. Ce côté de l'intervalle est fermé ,

  • La parenthèse (et )signifie:

    1. Le numéro est exclu ,
    2. Ce côté de l'intervalle est ouvert .

Un intervalle avec des états mixtes est appelé "semi-ouvert" .

Par exemple, la plage d'entiers consécutifs de 1 à 10 (inclus) serait notée comme telle:

  • [1,10]

Remarquez comment le mot a inclusiveété utilisé. Si nous voulons exclure le point final mais "couvrir" la même plage, nous devons déplacer le point final:

  • [1,11)

Pour les bords gauche et droit de l'intervalle, il y a en fait 4 permutations:

(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

Quel est le lien avec les mathématiques et l'informatique?

Les index de tableau ont tendance à utiliser un décalage différent en fonction du champ dans lequel vous vous trouvez:

  • Les mathématiques ont tendance à être un -Basé.
  • Certains langages de programmation ont tendance à être basés sur zéro , tels que C, C ++, Javascript, Python, tandis que d'autres langages tels que Mathematica, Fortran, Pascal sont basés sur un.

Ces différences peuvent conduire à de subtiles erreurs de poteaux de clôture , alias, des bogues ponctuels lors de la mise en œuvre d'algorithmes mathématiques tels que les boucles for.

Entiers

Si nous avons un ensemble ou un tableau, disons des quelques premiers nombres premiers [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], les mathématiciens appelleraient le premier élément l' élément 1st absolu . ie En utilisant la notation en indice pour désigner l'index:

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

Certains langages de programmation, par opposition, appelleraient le premier élément l' élément zero'th relatif .

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

Puisque les index de tableau sont dans la gamme [0, N-1], alors pour des raisons de clarté, il serait "bien" de conserver la même valeur numérique pour la gamme 0 .. N au lieu d'ajouter du bruit textuel tel qu'un-1 biais.

Par exemple, en C ou JavaScript, pour parcourir un tableau de N éléments, un programmeur écrirait l'idiome commun de i = 0, i < Navec l'intervalle [0, N) au lieu du légèrement plus verbeux [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>
Développer l'extrait

Les mathématiciens, puisqu'ils commencent à compter à 1, utiliseraient plutôt la i = 1, i <= Nnomenclature, mais nous devons maintenant corriger le décalage du tableau dans un langage basé sur zéro.

par exemple

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>
Développer l'extrait

À part :

Dans les langages de programmation basés sur 0, vous pourriez avoir besoin d'un kludge d'un zéro élément factice pour utiliser un algorithme mathématique 1. par exemple Début de l'index Python

Point flottant

La notation par intervalles est également importante pour les nombres à virgule flottante afin d'éviter des bogues subtils.

Lorsqu'il s'agit de nombres à virgule flottante, en particulier en infographie (conversion de couleur, géométrie de calcul, accélération / fusion d'animation, etc.), des nombres normalisés sont souvent utilisés. Autrement dit, des nombres compris entre 0,0 et 1,0.

Il est important de connaître les cas limites si les points de terminaison sont inclusifs ou exclusifs :

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

Où M est une machine epsilon . C'est pourquoi vous pouvez parfois voir des const float EPSILON = 1e-#expressions idiomatiques dans le code C (comme 1e-6) pour un nombre à virgule flottante 32 bits. Cette question SO EPSILON garantit-il quelque chose? a quelques détails préliminaires. Pour une réponse plus complète, voir FLT_EPSILONet David Goldberg's ce que tout informaticien devrait savoir sur l'arithmétique à virgule flottante de

Certaines implémentations d'un générateur de nombres aléatoires random()peuvent produire des valeurs comprises entre 0,0 et 0,999 ... au lieu de 0,0 à 1,0, plus pratique. Des commentaires appropriés dans le code documenteront ceci comme [0.0,1.0) ou [0.0,1.0] donc il n'y a aucune ambiguïté quant à l'utilisation.

Exemple:

  • Vous souhaitez générer des random()couleurs. Vous convertissez trois valeurs à virgule flottante en valeurs 8 bits non signées pour générer un pixel 24 bits avec des canaux rouge, vert et bleu respectivement. Selon l'intervalle de sortie, random()vous pouvez obtenir near-white(254,254,254) ou white(255,255,255).
     +--------+-----+
     |random()|Byte |
     |--------|-----|
     |0.999...| 254 | <-- error introduced
     |1.0     | 255 |
     +--------+-----+

Pour plus de détails sur la précision en virgule flottante et la robustesse avec des intervalles, voir Détection de collision en temps réel de Christer Ericson , Chapitre 11 Robustesse numérique , Section 11.3 Utilisation robuste de la virgule flottante .

Michaelangel007
la source
1

Il peut s'agir d'une convention mathématique dans la définition d'un intervalle où les crochets signifient "extrémal inclus" et les crochets ronds "extremal exclusif".

Tourbillon
la source