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.

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.

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 .$\pi$$\pi$$\mathbb{R}$

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”:

A następnie w sekcji 9:

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.

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ń :

• Mark Braverman, Stephen Cook, Obliczenia ponad rzeczywistością: podstawy obliczeń naukowych , Notices of the AMS, marzec 2006.

• Mark Braverman, O złożoności rzeczywistych funkcji , arXiv: cs / 0502066.

• Lenore Blum, Obliczenia w realu: gdzie Turing spotyka Newtona , Notices of the AMS, październik 2004.

• Vasco Brattka, Realistyczne modele obliczalności na liczbach rzeczywistych , kwiecień 2000.

• Vasco Brattka, Peter Hertling, Możliwe rzeczywiste maszyny o swobodnym dostępie , grudzień 1998.

• Lenore Blum, Mike Shub, Steve Smale, O teorii obliczeń i złożoności w stosunku do liczb rzeczywistych: kompletność NP, funkcje rekurencyjne i maszyny uniwersalne , Biuletyn AMS, lipiec 1989 r.

a oto artykuł na temat obliczeń analogowych :

• Hava Siegelmann, Eduardo Sontag, Obliczenia analogowe za pośrednictwem sieci neuronowych , wrzesień 1994 r.

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.

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.

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: autor : Andrew Dressel  - Praca własna, CC BY-SA 3.0 , Link

$r$$q$$r$$q×r$$π$$q×π$

$\pi$

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.

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ą.

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