Co oznacza zapis w nawiasach kwadratowych i nawiasach kwadratowych [pierwszy1, ostatni1)?


142

Widziałem zakresy liczb reprezentowane jako [first1,last1)i [first2,last2).

Chciałbym wiedzieć, co oznacza taki zapis.


3
[first, last)jest półotwartym odstępem, jak zauważyli inni. W niektórych podręcznikach jest to również napisane [first, last>i ma dokładnie to samo znaczenie, tylko składnia jest inna.
darioo,

9
Lepszym miejscem na to pytanie byłaby witryna math.stackexchange.com (IMHO). Ale nieważne! :)
xk0der

8
Jako mnemonik pomyśl, że nawias kwadratowy łapie się za tę wartość, co oznacza „do i włącznie”. A okrągły nawias jest bardziej miękki i mniej restrykcyjny: „do, ale nie włącznie”.
Eric Leschinski

Jako programista, ilekroć widzę nawiasy kwadratowe, zawsze przypomina mi to rozszerzony formularz Backus-Naur - en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
RBT

2
Polecam migrację do matematyki SE
Ben Leggiero

Odpowiedzi:


240

Nawias - [lub ]- oznacza, że ​​koniec zakresu jest włącznie - obejmuje wymieniony element. Nawias oznacza, że ​​koniec jest wyłączny i nie zawiera wymienionego elementu. Tak więc [first1, last1)zakres zaczyna się od first1(i obejmuje go), ale kończy się tuż przed last1.

Zakładając liczby całkowite:

  • (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

4
To ewoluuje od podstaw algebry w szkole podstawowej, gdzie uczysz się o funkcjach f (x) oraz dziedzinie i zakresie funkcji, gdzie funkcja taka jak f (x) = x ^ 2, miałaby zakres od 0 do dodatniej nieskończoności, oznaczony [0, ∞).
JohnMerlino

1
@Timbo ∞ nie jest liczbą.
JakeD,

3
@pycoder Twoja definicja liczby wydaje się niepotrzebnie ograniczająca. pl.wikipedia.org/wiki/Surreal_number
Timbo,

4
@JakeD Odnośnie twojego początkowego komentarza, masz rację w tym sensie, że nieskończoność nie jest liczbą, stąd dlaczego zbiór [0, ∞) jej nie zawiera.
wjandrea

2
∞ nie jest liczbą porządkową , taką, którą można wykonywać arytmetycznie. Ale jest to poprawna liczba kardynalna w przypadku odpowiedzi na pytania typu „Ile jest liczb całkowitych?”. To również, jak w tym przypadku, doskonale sprawdza się jako limit
Kevin Wright,

38

To jest półotwarta przerwa .

  • Zamknięty przedział [a,b] obejmuje punkty końcowe.
  • Otwarta przerwa (a,b) wyklucza ich.

W twoim przypadku punkt końcowy na początku interwału jest uwzględniony, ale koniec jest wykluczony. Oznacza to więc przedział „first1 <= x <last1”.

Przedziały półotwarte są przydatne w programowaniu, ponieważ odpowiadają popularnemu idiomowi dla pętli:

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

Tutaj i jest w zakresie [0, n).


16

Pojęcie notacji interwałowej pojawia się zarówno w matematyce, jak i informatyce. Oznaczenie matematyczne [, ], (, )oznacza domenę (lub zakresu ) w odstępie.

  • Nawiasy [i ]oznaczają:

    1. Numer jest wliczony w cenę ,
    2. Ta strona przedziału jest zamknięta ,
  • Nawias (i )oznacza:

    1. Liczba jest wykluczona ,
    2. Ta strona przedziału jest otwarta .

Przedział ze stanami mieszanymi nazywany jest „półotwartym” .

Na przykład zakres kolejnych liczb całkowitych od 1 do 10 (włącznie) byłby zapisany jako taki:

  • [1,10]

Zwróć uwagę, jak inclusivezostało użyte to słowo . Jeśli chcemy wykluczyć punkt końcowy, ale „zakryć” ten sam zakres, musimy przesunąć punkt końcowy:

  • [1,11)

Zarówno dla lewej, jak i prawej krawędzi przedziału są w rzeczywistości 4 permutacje:

(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

Jak to się ma do matematyki i informatyki?

Indeksy tablic mają tendencję do używania różnych przesunięć w zależności od tego, w którym polu się znajdujesz:

  • Matematyka jest oparta na jednej zasadzie.
  • Niektóre języki programowania są zwykle oparte na zerach , na przykład C, C ++, Javascript, Python, podczas gdy inne języki, takie jak Mathematica, Fortran, Pascal, są oparte na jedynce.

Różnice te mogą prowadzić do subtelnych błędów słupków ogrodzenia , czyli błędów typu off-by-one podczas implementowania algorytmów matematycznych, takich jak pętle for.

Liczby całkowite

Jeśli mamy zbiór lub tablicę, powiedzmy kilku pierwszych liczb pierwszych [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ], matematycy określiliby pierwszy element jako element 1st absolutny . tj. Używanie notacji z indeksem dolnym do oznaczenia indeksu:

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

W przeciwieństwie do tego niektóre języki programowania odwoływałyby się do pierwszego elementu jako elementu zero'th względnego .

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

Ponieważ indeksy tablicy znajdują się w zakresie [0, N-1], wówczas dla przejrzystości byłoby „miło” zachować tę samą wartość liczbową dla zakresu 0 .. N zamiast dodawać szum tekstowy, taki jak -1odchylenie.

Na przykład w C lub JavaScript, aby iterować po tablicy N elementów, programista napisałby wspólny idiom i = 0, i < Nz interwałem [0, N) zamiast nieco bardziej rozwlekłego [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>

Matematycy, ponieważ zaczynają liczyć od 1, zamiast tego i = 1, i <= Nużywaliby nazewnictwa, ale teraz musimy poprawić przesunięcie tablicy w języku zerowym.

na przykład

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>

Poza :

W języków programowania, które są oparte na 0 może trzeba kludge manekina zero'th elementu do wykorzystania algorytmu matematycznego opartego 1. np. Python Index Start

Liczba zmiennoprzecinkowa

Notacja interwałowa jest również ważna w przypadku liczb zmiennoprzecinkowych, aby uniknąć drobnych błędów.

Gdy mamy do czynienia z liczbami zmiennoprzecinkowymi, szczególnie w grafice komputerowej (konwersja kolorów, geometria obliczeniowa, łagodzenie / mieszanie animacji itp.), Często używane są liczby znormalizowane. Oznacza to, że liczby od 0,0 do 1,0.

Ważne jest, aby znać przypadki skrajne, jeśli punkty końcowe są włączające lub wyłączające :

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

Gdzie M jest jakąś maszyną epsilon . Dlatego czasami możesz zobaczyć const float EPSILON = 1e-#idiom w kodzie C (na przykład 1e-6) dla 32-bitowej liczby zmiennoprzecinkowej. To TAK pytanie Czy firma EPSILON coś gwarantuje? zawiera wstępne szczegóły. Bardziej wyczerpująca odpowiedź znajduje się w FLT_EPSILONksiążce Co każdy informatyk powinien wiedzieć o arytmetyce zmiennoprzecinkowej oraz w książce Davida Goldberga

Niektóre implementacje generatora liczb losowych random()mogą generować wartości z zakresu 0,0… 0,999… zamiast wygodniejszego 0,0… 1,0. Odpowiednie komentarze w kodzie udokumentują to jako [0.0,1.0) lub [0.0,1.0], więc nie ma niejednoznaczności co do użycia.

Przykład:

  • Chcesz generować random()kolory. Konwertujesz trzy wartości zmiennoprzecinkowe na wartości 8-bitowe bez znaku, aby wygenerować 24-bitowy piksel odpowiednio z kanałami czerwonym, zielonym i niebieskim. W zależności od przedziału czasu wyjściowego random()może zakończyć się near-white(254,254,254) lub white(255,255,255).
     +--------+-----+
     |random()|Byte |
     |--------|-----|
     |0.999...| 254 | <-- error introduced
     |1.0     | 255 |
     +--------+-----+

Aby uzyskać więcej informacji na temat precyzji i niezawodności zmiennoprzecinkowej z interwałami, zobacz Wykrywanie kolizji w czasie rzeczywistym Christera Ericsona , Rozdział 11 Odporność numeryczna , Rozdział 11.3 Solidne użycie zmiennoprzecinkowe .


1

Może to być konwencją matematyczną w definicji przedziału, w którym nawiasy kwadratowe oznaczają „ekstremalne włącznie”, a okrągłe nawiasy „ekstremalnie wykluczające”.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.