Dlaczego dane w informatyce są uważane za dyskretne?

35

Rozumiem, że „struktura” danych jest całkowicie zależna od Algebry Boolean, ale:

Dlaczego dane są uważane za dyskretny byt matematyczny, a nie ciągły?

Powiązane z tym:

Jakie wady lub niezmienniki są naruszane w strukturze danych jako ciągłej jednostki w wymiarach ?r

Nie jestem ekspertem w tej dziedzinie, ponieważ jestem studentem matematyki na studiach licencjackich, więc naprawdę byłbym wdzięczny, gdyby ktoś wytłumaczył mi to tak, jakbym miał pięć lat.

evil_potato
źródło
12
Prawdziwe obliczenia byłyby nadmiernie potężne
Harold
1
Przejrzyj ten rozdział, jeśli czas na to pozwala. Autor wyjaśnia to w bardzo łatwy sposób na podstawie sygnałów analogowych a binarnych
Muhammad Sayef

Odpowiedzi:

44

Odpowiedź

dlaczego dane uważano za dyskretny byt matematyczny, a nie ciągły

To nie był wybór; teoretycznie i praktycznie niemożliwe jest przedstawienie ciągłych, konkretnych wartości w komputerze cyfrowym lub w rzeczywistości w jakichkolwiek obliczeniach.

Zauważ, że „dyskretny” nie oznacza „liczby całkowitej” lub czegoś podobnego. „dyskretny” jest przeciwieństwem „ciągłego”. Oznacza to, że aby mieć komputer, który naprawdę jest w stanie przechowywać niedyskretne rzeczy, musisz mieć możliwość przechowywania dwóch liczb ai bgdzie abs(a-b) < εdla dowolnej arbitralnie małej wartości ε. Oczywiście możesz wchodzić tak głęboko, jak chcesz (wykorzystując coraz więcej miejsca), ale każdy (fizyczny) komputer zawsze ma górną granicę. Bez względu na to, co robisz, nigdy nie możesz stworzyć (fizycznego) komputera, który przechowuje arbitralnie dokładnie rozwiązane liczby.

Nawet jeśli potrafisz reprezentować liczby za pomocą konstrukcji matematycznych (na przykład π), nic to nie zmienia. Jeśli przechowujesz wykres lub cokolwiek, co reprezentuje wzór matematyczny, jest to tak samo dyskretne jak wszystko inne.

Uzupełnienie

Reszta to tylko niewielka perspektywa poza dziedziną informatyki. Jak pokazały komentarze, temat fizyczny nie jest bezdyskusyjny, a jak widzicie, sformułowałem swój następny akapit w sposób, który jest raczej niezobowiązany do tego, czy to prawda, czy nie. Potraktuj to raczej jako motywację, że pojęcie „kontinuum” nie jest banalne. Powyższa odpowiedź nie zależy od tego, czy przestrzeń jest dyskretna, czy nie.

Zauważ, że wszystko to nie jest tak bardzo problemem komputerów, ale problemem w znaczeniu „ciągłego”. Na przykład, nie wszyscy nawet zgadzają się lub nie zgadzali się w przeszłości, że Wszechświat jest ciągły (np. Czy skala Plancka sugeruje, że czasoprzestrzeń jest dyskretna? ). W przypadku niektórych rzeczy (np. Stanów energetycznych elektronów i wielu innych cech mechaniki kwantowej (sic)) wiemy nawet , że Wszechświat nie jest ciągły; dla innych (np. pozycja ...) jury jest nadal nieobecne (przynajmniej jeśli chodzi o interpretację wyników badań ...). (Niezależnie od problemu, że nawet jeśli jest ciągły, nie możemy zmierzyć z dowolną dokładnością => Heisenberga itp.).

W matematyce badanie kontinuum (tj. Reali) otwiera wiele fascynujących aspektów, takich jak teoria miar, co sprawia, że ​​całkowicie niemożliwe jest przechowywanie „ciągłego” rodzaju liczby / danych.

AnoE
źródło
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
29

Komputery reprezentują kawałek danych jako skończoną liczbę bitów (zer i jedynek), a zestaw wszystkich skończonych ciągów bitów jest dyskretny. Możesz pracować z, powiedzmy, liczbami rzeczywistymi, tylko jeśli znajdziesz dla nich skończoną reprezentację. Na przykład możesz powiedzieć „te dane odpowiadają liczbie ”, ale nie możesz zapisać wszystkich cyfr π na komputerze. Stąd, programy komputerowe, że praca z liczb rzeczywistych faktycznie pracują tylko na dyskretne podzbiór R .ππR

Christian Matt
źródło
Robią to komputery cyfrowe, ale nie komputery analogowe.
Drew
Komentarze nie są przeznaczone do rozszerzonej dyskusji; ta rozmowa została przeniesiona do czatu .
DW
8

Aby dodać do wszystkich tych wspaniałych odpowiedzi, warto zauważyć, że Alan Turing, definiując swoje maszyny, twierdzi, że ilość symboli musi być skończona (nawet jeśli dowolnie duża), ponieważ komputer (czyli człowiek) nie mógł odróżnić w przeciwnym razie wszystkie symbole.

Oto kilka fragmentów jego artykułu z 1936 r. „O liczbach obliczalnych z zastosowaniem do Entscheidungsproblem”:

wprowadź opis zdjęcia tutaj

A następnie w sekcji 9:

wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Guido
źródło
1
Transkrybuj obrazy, aby mogły być indeksowane przez wyszukiwania.
Raphael
7

Wszystko zależy od implementacji.

Jeśli się nad tym zastanowić, komputery naprawdę są urządzeniami ciągłymi. Łatwo to pokazuje fakt, że wszystkie równania EM rządzące ich działaniem są ciągłe. Dyskretne są modele, których używamy do decydowania o sposobie korzystania z tych urządzeń komputerowych. Wszystkie abstrakcyjne maszyny, których używamy do opisywania obliczeń, są dyskretne.

Ogromną praktyczną zaletą tego jest niezależność od wielu wyzwań związanych z kontrolą jakości. Jeśli nasze modele komputerów wykorzystałyby w pełni ciągły charakter swoich tranzystorów i kondensatorów, wówczas musielibyśmy dbać o to, jak dobrze zbudowaliśmy każdy tranzystor w ogromnym stopniu. Widzimy to w świecie audio. Na świecie mieszkają audiofile, rozsądnie jest wydać 2000 $ na wzmacniacz, który może mieć 10 bardzo starannie dobranych i dopasowanych tranzystorów, które robią dokładnie to, czego chcą. Porównaj to z 1 400 000 000 tranzystorów w procesorze Core i7 za ogromną cenę 400 USD .

Ponieważ nasze modele obliczeniowe są dyskretne, możemy modelować wszystkie sygnały, które widzimy w komputerze, jako sygnał dyskretny plus pewien ciągły błąd. Następnie możemy odfiltrować błędy, po prostu obserwując, że nie mają one odpowiedniego kształtu, aby być częścią sygnału dyskretnego.

Główną częścią tego jest usunięcie terminów w naszych abstrakcyjnych modelach. Wiele naszych modeli nie mierzy czasu w stosunku do jakiegoś fizycznego procesu, ale w stosunku do jakiegoś „logicznego” sygnału zwanego zegarem. Jeśli przerwiesz zegar, system przestanie się poruszać, ale nie ulegnie awarii. Po prostu kończy usuwanie ewentualnych błędów analogowych i czeka na następny dyskretny puls zegara. Usunięcie ciągłych terminów czasowych drastycznie upraszcza obliczenia i dowody na ich obliczanie. Zamiast tego nasze pojęcia czasu są mierzone dyskretnie, jak widać w kategoryzacjach algorytmów P i NP.

Cort Ammon
źródło
7

Dlatego:

  • Komputery cyfrowe nie mogą przechowywać dowolnych liczb rzeczywistych.

  • Komputery analogowe są nękane hałasem termicznym (jeśli elektroniczny), tarciem (mechaniczne lub hydrauliczne), zakłóceniami, wrażliwością na zmiany temperatury, nieuniknionymi niedoskonałościami i starzeniem się. Radzenie sobie z takimi trudnościami to, co robią (eksperymentalni) fizycy i inżynierowie. Większość informatyki po prostu odciąga fizykę.

Oto kilka artykułów na temat prawdziwych obliczeń :

a oto artykuł na temat obliczeń analogowych :

Rodrigo de Azevedo
źródło
4

Termin „komputer” w nowoczesnym języku oznacza „komputer cyfrowy”; istotą komputera cyfrowego jest to, że ma on skończoną liczbę stanów dyskretnych. Można by przeprowadzić interesującą debatę na temat tego, czy powody, dla których komputery cyfrowe zyskały przewagę nad komputerami analogowymi, dotyczyły przede wszystkim praktyczności inżynierii, czy też przede wszystkim ze względu na lepsze podstawy informatyki teoretycznej. Ale bez względu na powód, komputery cyfrowe są tym, z czym skończyliśmy, a każdy użyteczny model matematyczny komputera cyfrowego (a zatem i jego danych) będzie raczej dyskretny niż ciągły.

Michael Kay
źródło
2

Słowo datapochodzi od słowa łacińskiego datum, co oznacza coś, co zostało dane. Z biegiem czasu liczba mnoga zmieniła użycie i jest obecnie powszechnie stosowana jako liczba pojedyncza i mnoga. Stało się również związane z konkretnymi informacjami.

Zauważ, że istnieje różnica między elementem informacji (punktem odniesienia) a jego reprezentacją.

Teoria informacji dotyczy (między innymi) odrębnych informacji reprezentowanych przez zmienne. Są to istoty policzalne. Na przykład, prędkość, lokalizacja, masa itd. Są wielkościami ciągłymi, ale dyskretnymi względem siebie: nie ma transformacji między masą a lokalizacją. Gdy wielkości te są reprezentowane numerycznie, ich elementy danych, niezależnie od tego, jak są reprezentowane, są również od siebie dyskretne.

Z drugiej strony ogromna większość naszych obecnych komputerów wykorzystuje jakąś formę ładunku elektrycznego do reprezentowania informacji. Opłata jest albo obecna, albo nie; w obwodzie jest prąd lub nie ma go. Jest to również dyskretne, ale nie musi tak być! Po prostu z powodu rozwoju naszej technologii używamy reprezentacji binarnej. Możliwe, że rozwój technologii kwantowej zmieni to w najbliższej przyszłości. Nie jest również wykluczone, że komputery analogowe odrodzą się, a nasze wyobrażenia, że ​​liczby muszą być reprezentowane przez binarne, zostaną zmyte!

Podsumowując: dataskładają się z dyskretnych elementów informacji, z których każdy jest układem odniesienia; podczas gdy każdy układ odniesienia nie musi być reprezentowany za pomocą dyskretnej matematyki, ale obecnie jest to wyłącznie współczesny przypadek.

Evil Dog Pie
źródło
1
Teoria informacji może również obsługiwać zmienne ciągłe.
Yuval Filmus
1
Patrz na przykład entropia różnicowa .
Yuval Filmus
2

Chcę podważyć twoją podstawową przesłankę:

Dlaczego dane są uważane za dyskretny byt matematyczny, a nie ciągły?

To nie jest

Na przykład badanie algorytmów jest ważnym polem informatyki i istnieje wiele algorytmów, które działają z ciągłymi danymi. Prawdopodobnie znasz algorytm Euclida do obliczania największego wspólnego dzielnika dwóch liczb naturalnych, ale czy wiesz, że Euclid miał również geometryczną wersję tego samego algorytmu, który oblicza najdłuższą wspólną miarę dwóch współmiernych linii? Jest to przykład algorytmu (a zatem przedmiotu badań informatyki) nad liczbami rzeczywistymi, tj. Ciągłymi danymi, mimo że Euclid nie myślał o tym w ten sposób.

Istnieje wiele różnych sposobów klasyfikowania algorytmów, ale jednym ze stosowanych sposobów jest klasyfikowanie ich według „ciągłości”:

  • Algorytmy cyfrowe (algorytmy zdarzeń dyskretnych na danych cyfrowych):
    • wariant numeryczny algorytmu Euclida
    • podział na długie ręce, mnożenie itp., jak uczy się w szkole
    • dowolny program komputerowy, program do obliczania λ, maszyna Turinga
  • Dane niecyfrowe, algorytmy zdarzeń dyskretnych (algorytmy na danych ciągłych, które jednak nadal mają pojęcie „kroku”, tj. Dane ciągłe, ale czas dyskretny):
    • wariant geometryczny algorytmu Euclida
    • algorytmy na liczbach rzeczywistych (np. Procedura eliminacji Gaussa)
    • algorytmy funkcji ciągłych (np. algorytm bisekcji)
  • Algorytmy analogowe (czas ciągły, dane ciągłe):
    • obwody elektryczne
    • żyroskopy mechaniczne
  • Algorytmy hybrydowe (dowolna kombinacja powyższych)
    • roboty

Inne odpowiedzi wspominały już o Real Computation in The Computability Theory, innym ważnym obszarze informatyki.

r

Jedyną prawdziwą wadą (bardzo zamierzoną pun) jest to, że takich danych nie można przedstawić za pomocą zwykłych komputerów cyfrowych. Możesz myśleć o algorytmach zamiast ciągłych danych, ale nie możesz ich uruchamiać na standardowych maszynach, których zwykle używamy do uruchamiania algorytmów.

To główny powód, dla którego ciągłe dane nie są tak „widoczne” jak dane cyfrowe.

Jednak implementacja algorytmu analogowego wcale nie musi być skomplikowana, aby ją sobie wyobrazić, a nawet zbudować. Na przykład jest to implementacja algorytmu analogowego: Rower Triumphautor : Andrew Dressel  - Praca własna, CC BY-SA 3.0 , Link

rqrq×rπq×π

Jörg W Mittag
źródło
„istnieje wiele algorytmów, które działają z ciągłymi danymi” - moglibyśmy długo dyskutować, czy takie rzeczy powinny być nazywane „algorytmami”, ale byłoby to flamewar na temat semantyki, więc nie. Chodzi o to, że nie są to „algorytmy” działające na komputerach, ale na teoretycznych, formalnie zdefiniowanych urządzeniach super-Turinga.
Raphael
1
Metafora rowerowa jest myląca. Coś, co oblicza jedną funkcję, nie jest komputerem, który domyślnie zakładamy, że jest dziś uniwersalny .
Raphael
1

π

Teraz zestaw wszystkich możliwych danych skończonych można uporządkować w porządku leksykograficznym, co oznacza, że ​​zestaw można policzyć. Ale zbiór ciągłych liczb rzeczywistych jest niepoliczalny, więc w kontinuum zawsze znajdują się liczby, których dany system obliczeniowy nie może zapisać. Z tego możemy wywnioskować, że przechowywanie dowolnej liczby rzeczywistej wymaga nieskończonych zasobów.

Mark H.
źródło
1
Myślę, że to nasuwa pytanie . Rozważ komputer, który pobiera dane wejściowe z kawałka papieru, który bada, i który podaje dane wyjściowe na kawałku papieru, z którego czerpie. Gdyby dane były ciągłe, jak sugeruje PO, wówczas taki komputer mógłby być nieskończenie precyzyjny z jedynie skończoną ilością danych.
ruakh
@ruakh Czy mówisz o czymś w rodzaju analogowej maszyny Turinga, w której mógłby na przykład odczytać dokładną długość narysowanej linii?
Mark H
Tak, dokładnie. Jak rozumiem, o to pyta OP.
ruakh
0

Dane nie zawsze są uważane za dyskretne. Programowanie naukowe często obejmuje arytmetykę zmiennoprzecinkową. Programista zwykle udaje, że zaangażowane zmienne są ciągłe, pamiętając przy tym o stabilności numerycznej, która wynika z faktu, że dane są przechowywane tylko z skończoną precyzją.

Yuval Filmus
źródło
12
Punkt zmiennoprzecinkowy jest dyskretny ... jeśli programista udaje, że jest ciągły, oznacza to po prostu, że albo wyniki nie mają znaczenia, albo że programista nie zrozumiał, co robi.
AnoE
2
Z szacunkiem się nie zgadzam.
Yuval Filmus
6
@YuvalFilmus niestety, ponieważ zmiennoprzecinkowa jest dyskretna, nie ma nic więcej do powiedzenia. Za każdym razem, gdy coś jest wkładane do zwykłego komputera, jest to dyskrecjonalne.
Jean-Baptiste Yunès
5
@AnoE oznacza, że ​​wyniki można ufać z pewną precyzją, co Yuval rozumie przez „udawanie”. Możesz uzyskać użyteczne wyniki, ale musisz zatrzeć precyzję. W przypadku dużych zestawów ma to sens. Porównaj to z klasycznymi problemami z mechaniką: wiesz, że twoje pomiary nie są precyzyjne. obiekt 3 cm nie ma faktycznie 3,000000000 ~ cm długości. Wystarczy wyciąć precyzję pomiaru w rozsądnym punkcie.
Mindwin
6
Nie sądzę, że pytanie dotyczy tego, jak działają nasze umysły. Myślę, że chodzi o to, jak rzeczy naprawdę działają. Powodem, dla którego liczby zmiennoprzecinkowe są przybliżone, jest to, że są dyskretne. To, że myślisz o nich jako ciągłych, nawet jeśli tak naprawdę nie jest, nie pomaga odpowiedzieć na pytanie, dlaczego wartości są dyskretne w komputerach. Na marginesie, twój sposób myślenia może być niebezpieczny. Wiele błędów wynika z tego, że programiści uważają zmiennoprzecinkowe za ciągłe. Nawet zwykłe liczby, które uważamy za tak dokładne, jak 1 dziesiąta lub setna, są przybliżone w liczbach zmiennoprzecinkowych.
JimmyJames,
-2
  • Aby komputer mógł pracować z danymi, dane muszą istnieć w dostępnej pamięci komputera
  • Dostępna pamięć komputera jest skończona
  • W pamięci dostępnej na komputerze mogą istnieć tylko dane skończone
  • Wartości niedyskretne są nieskończone

Dane w informatyce są uważane za dyskretne.

Repomeister
źródło
elimt(1+1/t)t
Podana formuła jest krótsza - nie można jej użyć w żadnych obliczeniach, których rzeczywista „odpowiedź” jest potrzebna, a zatem komputer nie może wykonać żadnej znaczącej „pracy”. Mógłbyś napisać mały program do analizowania tekstu, aby przyjmował i wypluwał reprezentacje tekstowe liczb niewymiernych, ale rzeczywista reprezentacja liczbowa „wartości” tych liczb nie może być przechowywana w pamięci - więcej niż ja mogę napisać „to jest nieskończoność” na kartce papier i powiedz, że trzymam wszystko w ręku.
Repomeister
1
Wydaje się, że zakładasz, że jedynym sposobem obliczenia na liczbach rzeczywistych jest uzyskanie rozszerzenia dziesiętnego. Po prostu tak nie jest.
David Richerby
2
eiπ=116π
1
<,,>,,=,+,,×,÷x1,x2,,xnx1,,xn