Ich verstehe, dass die "Struktur" von Daten vollständig von der Booleschen Algebra abhängt, aber:
Warum werden Daten nicht als kontinuierliche, sondern als diskrete mathematische Einheit betrachtet?
Im Zusammenhang damit:
Was sind die Nachteile oder Invarianten, die bei der Strukturierung von Daten als kontinuierliche Einheit in Dimensionen verletzt werden ?
Ich bin kein Experte auf diesem Gebiet, da ich ein Mathematikstudent im Grundstudium bin. Ich würde es wirklich begrüßen, wenn mir jemand dies erklären würde, als wäre ich fünf.
data-structures
mathematical-foundations
evil_potato
quelle
quelle
Antworten:
Antworten
Dies war keine Wahl; es ist theoretisch und praktisch unmöglich, kontinuierliche, konkrete Werte in einem digitalen Computer oder tatsächlich in irgendeiner Art von Berechnung darzustellen.
Beachten Sie, dass "diskret" nicht "ganzzahlig" oder so ähnlich bedeutet. "diskret" ist das Gegenteil von "kontinuierlich". Dieses Mittel, einen Computer haben , die wirklich in der Lage zu speichern nicht diskrete Dinge ist, würden Sie in der Lage sein müssen , um zwei Zahlen zu speichern ,
a
undb
woabs(a-b) < ε
für jeden beliebig kleinen Wertε
. Natürlich können Sie so tief gehen, wie Sie möchten (indem Sie immer mehr Speicherplatz verwenden), aber jeder (physische) Computer hat immer eine Obergrenze. Egal was Sie tun, Sie können niemals einen (physischen) Computer herstellen, der willkürlich fein aufgelöste Zahlen speichert.Auch wenn Sie Zahlen beispielsweise durch mathematische Konstrukte darstellen können
π
, ändert dies nichts. Wenn Sie ein Diagramm oder was auch immer speichern, das eine mathematische Formel darstellt, ist dies genauso diskret wie alles andere.Nachtrag
Der Rest ist nur eine kleine Perspektive jenseits der Informatik. Wie die Kommentare gezeigt haben, ist das physikalische Thema nicht unbestritten, und wie Sie sehen können, habe ich meinen nächsten Absatz so formuliert, dass es eher unverbindlich ist, ob es wahr ist oder nicht. Nehmen Sie es eher als Motivation, dass das Konzept des "Kontinuums" nicht trivial ist. Die obige Antwort hängt nicht davon ab, ob der Raum diskret ist oder nicht.
Beachten Sie, dass all dies nicht so sehr ein Problem von Computern ist, sondern ein Problem mit der Bedeutung von "kontinuierlich". Zum Beispiel waren sich nicht alle einig oder waren sich in der Vergangenheit einig, dass das Universum stetig ist (z. B. impliziert die Planck-Skala, dass die Raumzeit diskret ist? ). Für einige Dinge (zB Energiezustände von Elektronen und viele andere Merkmale in der Quantenmechanik) wissen wir sogar , dass das Universum nicht kontinuierlich ist; Für andere (z. B. Position ...) ist die Jury noch nicht besetzt (zumindest in Bezug auf die Interpretation der Forschungsergebnisse ...). (Ungeachtet des Problems, dass wir, selbst wenn es kontinuierlich ist, nicht mit willkürlicher Genauigkeit messen können => Heisenberg usw.).
In der Mathematik eröffnet das Studium des Kontinuums (dh der Realzahlen) viele faszinierende Aspekte, wie die Maßtheorie, die es unmöglich machen, tatsächlich eine "kontinuierliche" Art von Zahl / Daten zu speichern.
quelle
Computer stellen ein Datenelement als endliche Anzahl von Bits (Nullen und Einsen) dar, und die Menge aller endlichen Bitfolgen ist diskret. Sie können beispielsweise nur mit reellen Zahlen arbeiten, wenn Sie eine endliche Repräsentation für sie finden. Sie können beispielsweise sagen, dass diese Daten der Zahl , aber Sie können nicht alle Stellen von auf einem Computer speichern . Daher arbeiten Computerprogramme, die mit reellen Zahlen arbeiten, nur mit einer diskreten Teilmenge von .π Rπ π R
quelle
Um all diese großartigen Antworten zu ergänzen, ist anzumerken, dass Alan Turing bei der Definition seiner Maschinen argumentiert, dass die Menge der Symbole endlich sein muss (auch wenn sie willkürlich groß ist), da ein Computer (dh ein Mensch) sie nicht unterscheiden kann alle Symbole anders.
Hier einige Auszüge aus seiner Arbeit "Über berechenbare Zahlen mit einer Anwendung auf das Entscheidungsproblem" von 1936:
Und dann zu Abschnitt 9:
quelle
Es ist alles in der Umsetzung.
Wenn Sie darüber nachdenken, sind Computer wirklich kontinuierliche Geräte. Dies lässt sich leicht daran erkennen, dass alle EM-Gleichungen, die ihre Funktionsweise bestimmen, stetig sind. Die Sache, die diskret ist, sind die Modelle, die wir verwenden, um zu entscheiden, wie diese Computergeräte verwendet werden. Die abstrakten Maschinen, mit denen wir die Berechnung beschreiben, sind alle diskret.
Der enorme praktische Vorteil davon ist die Unabhängigkeit von vielen Qualitätskontrollherausforderungen. Wenn unsere Computermodelle die volle Kontinuität ihrer Transistoren und Kondensatoren nutzen würden, müssten wir uns darum kümmern, wie gut wir jeden Transistor in einem enormen Maße gebaut haben. Wir können das in der Audiowelt sehen. In der Welt, in der Audiophile leben, ist es vernünftig, 2000 US-Dollar für einen Verstärker auszugeben , der 10 sehr sorgfältig ausgewählte und abgestimmte Transistoren hat, die genau das tun, was sie wollen. Vergleichen Sie dies mit 1.400.000.000 Transistoren in einer Core i7-CPU zu den gewaltigen Kosten von 400 US-Dollar .
Da unsere Rechenmodelle diskret sind, können wir alle Signale, die wir in einem Computer sehen, als diskretes Signal plus einem kontinuierlichen Fehlerterm modellieren. Wir können dann die Fehler herausfiltern, indem wir einfach feststellen, dass sie nicht die richtige Form haben, um Teil des diskreten Signals zu sein.
Ein wesentlicher Teil davon ist das Entfernen von Zeitbegriffen in unseren abstrakten Modellen. Viele unserer Modelle messen die Zeit nicht an einem physikalischen Prozess, sondern an einem "logischen" Signal, das als Uhr bezeichnet wird. Wenn Sie eine Uhr unterbrechen, bleibt das System stehen, fällt aber nicht aus. Es löscht gerade alle analogen Fehler und wartet auf den nächsten diskreten Takt. Durch das Entfernen von fortlaufenden Zeitangaben werden die Berechnung und die Berechnungsnachweise erheblich vereinfacht. Stattdessen werden unsere Zeitkonzepte diskret gemessen, wie in P- und NP-Kategorisierungen von Algorithmen zu sehen ist.
quelle
Weil:
Digitale Computer können keine willkürlichen reellen Zahlen speichern.
Analoge Computer leiden unter thermischem Rauschen (wenn elektronisch), Reibung (wenn mechanisch oder hydraulisch), Störungen, Empfindlichkeit gegenüber Temperaturschwankungen, unvermeidlichen Fehlern und Alterung. Der Umgang mit solchen Schwierigkeiten ist das, was (experimentelle) Physiker und Ingenieure tun. Die meiste Informatik abstrahiert einfach die Physik.
Hier sind einige Artikel zur realen Berechnung :
Mark Braverman, Stephen Cook, Computing over the reals: Grundlagen für wissenschaftliches Rechnen , Mitteilungen des AMS, März 2006.
Mark Braverman, Zur Komplexität realer Funktionen , arXiv: cs / 0502066.
Lenore Blum, Computing over the reals: wo Turing auf Newton trifft , Mitteilungen des AMS, Oktober 2004.
Vasco Brattka, Realistische Modelle der Berechenbarkeit von reellen Zahlen , April 2000.
Vasco Brattka, Peter Hertling, Machbare reale Direktzugriffsmaschinen , Dezember 1998.
Lenore Blum, Mike Shub, Steve Smale, Über eine Theorie der Berechnung und Komplexität über die reellen Zahlen: NP-Vollständigkeit, rekursive Funktionen und universelle Maschinen , Bulletin des AMS, Juli 1989.
und hier ist ein Artikel über analoge Berechnungen :
quelle
Der Ausdruck "Computer" im modernen Sprachgebrauch bedeutet "digitaler Computer"; Das Wesen eines digitalen Computers ist, dass er eine endliche Anzahl von diskreten Zuständen hat. Man könnte eine interessante Debatte darüber führen, ob die Gründe, aus denen digitale Computer gegenüber analogen Computern bevorzugt wurden, in erster Linie in der technischen Anwendbarkeit lagen oder in erster Linie auf einer besseren Grundlage der theoretischen Informatik beruhten. Was auch immer die Gründe sein mögen, wir haben digitale Computer gefunden, und jedes nützliche mathematische Modell eines digitalen Computers (und damit seiner Daten) wird eher diskret als kontinuierlich sein.
quelle
Das Wort
data
leitet sich vom lateinischen Wort abdatum
, was etwas bedeutet, was gegeben wurde. Im Laufe der Zeit hat sich die Verwendung der Pluralform geändert und wird heute häufig sowohl als Singular als auch als Plural verwendet. Es wurde auch speziell mit Informationen in Verbindung gebracht.Beachten Sie, dass es einen Unterschied zwischen einer Information (einem Datum) und ihrer Darstellung gibt.
Die Informationstheorie befasst sich unter anderem mit diskreten Informationen, die durch Variablen dargestellt werden. Dies sind zählbare Einheiten. Zum Beispiel sind Geschwindigkeit, Ort, Masse usw. alle kontinuierliche Größen, aber voneinander getrennt: Es gibt keine Transformation zwischen Masse und Ort. Wenn diese Größen numerisch dargestellt werden, sind ihre Datenelemente, obwohl sie dargestellt werden, auch voneinander diskret.
Andererseits verwendet die überwiegende Mehrheit unserer heutigen Computer irgendeine Form elektrischer Ladung, um Informationen darzustellen. Die Ladung ist entweder vorhanden oder nicht vorhanden; Es gibt Strom im Stromkreis oder nicht. Dies ist auch diskret, muss aber nicht sein! Es liegt einfach an der Art und Weise, wie sich unsere Technologie entwickelt hat, dass wir die binäre Darstellung verwenden. Es ist möglich, dass Entwicklungen im Bereich Quantum Computing dies in naher Zukunft ändern werden. Es ist auch nicht unvorstellbar, dass analoge Computer wieder aufleben und unsere Vorstellung, dass Zahlen durch Binärzahlen dargestellt werden müssen, verwischt wird!
Zusammenfassend: Sie
data
setzen sich aus einzelnen Informationen zusammen, von denen jedes ein Datum ist. Während jedes Datum nicht mit diskreter Mathematik dargestellt werden muss, ist es derzeit nur ein zeitgemäßer Zufall.quelle
Ich möchte Ihre grundlegende Prämisse in Frage stellen:
Ist es nicht.
Zum Beispiel ist das Studium von Algorithmen ein wichtiges Teilgebiet der Informatik, und es gibt viele Algorithmen, die mit kontinuierlichen Daten arbeiten. Sie kennen wahrscheinlich den Algorithmus von Euclid zur Berechnung des größten gemeinsamen Divisors zweier natürlicher Zahlen, aber wussten Sie, dass Euclid auch eine geometrische Version desselben Algorithmus besitzt, mit der das längste gemeinsame Maß zweier korrespondierender Linien berechnet wird? Das ist ein Beispiel für einen Algorithmus (und damit Gegenstand eines Informatikstudiums) über reelle Zahlen, also kontinuierliche Daten, auch wenn Euklid nicht so darüber nachdachte.
Es gibt viele verschiedene Möglichkeiten, Algorithmen zu klassifizieren, aber eine Möglichkeit, die verwendet wird, besteht darin, sie nach ihrer "Kontinuität" zu klassifizieren:
Andere Antworten erwähnten bereits Real Computation in Computability Theory, einem weiteren wichtigen Teilgebiet der Informatik.
Der einzige wirkliche (sehr beabsichtigte) Nachteil ist, dass solche Daten nicht mit herkömmlichen digitalen Computern dargestellt werden können. Sie können Algorithmen über kontinuierliche Daten nachdenken , aber Sie können sie nicht auf den Standardmaschinen ausführen , die wir normalerweise zum Ausführen von Algorithmen verwenden.
Dies ist der Hauptgrund, warum kontinuierliche Daten nicht so "sichtbar" sind wie digitale Daten.
Die Implementierung eines analogen Algorithmus muss jedoch nicht unbedingt kompliziert vorstellbar oder gar zu erstellen sein. Dies ist beispielsweise eine Implementierung eines analogen Algorithmus: Von Andrew Dressel - Eigene Arbeit, CC BY-SA 3.0 , Link
quelle
Um abstrakter zu sein, kann jede mögliche Berechnung, die irgendwann zu einem Ergebnis führt, sei es auf einem Computer oder in Ihrem Kopf, nur eine begrenzte Datenmenge verarbeiten. Dies bedeutet, dass die Daten durch eine Zeichenfolge dargestellt werden können. Diese Zeichenfolge kann die Ziffern einer Zahl ("42") oder der Text eines Programms sein, das die Daten erstellt ("4 * atan (1)" für ). Die Zeichenfolge muss endlich sein, sonst könnte das Ganze nie gelesen werden, um das Programm auszuführen.π
Jetzt kann die Menge aller möglichen endlichen Daten in lexikografische Reihenfolge gebracht werden, was bedeutet, dass die Menge zählbar ist. Die Menge der fortlaufenden reellen Zahlen ist jedoch unzählig, sodass das Kontinuum immer Zahlen enthält, die von einem bestimmten Rechensystem nicht gespeichert werden können. Daraus können wir schließen, dass die Speicherung einer beliebigen reellen Zahl unendliche Ressourcen erfordert.
quelle
Daten werden nicht immer als diskret betrachtet. Wissenschaftliches Programmieren beinhaltet oft Fließkomma-Arithmetik. Der Programmierer gibt normalerweise vor, dass die beteiligten Variablen kontinuierlich sind, wobei er das Problem der numerischen Stabilität berücksichtigt, das sich aus der Tatsache ergibt, dass Daten nur mit einer endlichen Genauigkeit gespeichert werden.
quelle
Daten in der Informatik gelten als diskret.
quelle