Warum werden Daten in der Informatik als diskret betrachtet?

35

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 ?r

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.

evil_potato
quelle
12
Eine echte Berechnung wäre unangemessen leistungsfähig
harold
1
Gehen Sie dieses Kapitel durch, wenn es die Zeit erlaubt. Der Autor erklärt es sehr einfach, von analogen vs binären Signalen
Muhammad Sayef

Antworten:

44

Antworten

Warum wurden die Daten nicht als kontinuierliche, sondern als diskrete mathematische Einheit betrachtet?

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 , aund bwo abs(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.

AnoE
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
29

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

Christian Matt
quelle
Das machen digitale Computer, aber keine analogen Computer.
Drew
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
DW
8

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:

Bildbeschreibung hier eingeben

Und dann zu Abschnitt 9:

Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

Guido
quelle
1
Bitte transkribieren Sie die Bilder, um sie durch Suchen zu indizieren.
Raphael
7

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.

Cort Ammon
quelle
7

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 :

und hier ist ein Artikel über analoge Berechnungen :

Rodrigo de Azevedo
quelle
4

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.

Michael Kay
quelle
2

Das Wort dataleitet sich vom lateinischen Wort ab datum, 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 datasetzen 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.

Schlechter Hundekuchen
quelle
1
Die Informationstheorie kann auch mit kontinuierlichen Variablen umgehen.
Yuval Filmus
1
Siehe zum Beispiel Differentialentropie .
Yuval Filmus
2

Ich möchte Ihre grundlegende Prämisse in Frage stellen:

Warum werden Daten nicht als kontinuierliche, sondern als diskrete mathematische Einheit betrachtet?

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:

  • Digitale Algorithmen (Ereignisdiskrete Algorithmen für digitale Daten):
    • die numerische Variante des Euklid-Algorithmus
    • Langzeitteilung, Multiplikation etc. wie in der Schule gelehrt
    • ein beliebiges Computerprogramm, λ-Kalkülprogramm, Turing Machine
  • Nicht digitale Daten, diskrete Ereignisalgorithmen (Algorithmen über kontinuierliche Daten, die jedoch immer noch den Begriff "Schritt" haben, dh kontinuierliche Daten, aber diskrete Zeit):
    • die geometrische Variante von Euklids Algorithmus
    • Algorithmen für reelle Zahlen (z. B. Gauß-Eliminierungsverfahren)
    • Algorithmen für stetige Funktionen (zB der Bisektionsalgorithmus)
  • Analoge Algorithmen (kontinuierliche Zeit, kontinuierliche Daten):
    • Stromkreise
    • mechanische Gyroskope
  • Hybridalgorithmen (beliebige Kombination der oben genannten)
    • Roboter

Andere Antworten erwähnten bereits Real Computation in Computability Theory, einem weiteren wichtigen Teilgebiet der Informatik.

r

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: Triumph Fahrrad fahrenVon Andrew Dressel  - Eigene Arbeit, CC BY-SA 3.0 , Link

rqrq×r q × ππq×π

Jörg W. Mittag
quelle
"Es gibt viele Algorithmen, die mit kontinuierlichen Daten arbeiten" - Wir könnten lange darüber diskutieren, ob solche Dinge "Algorithmen" genannt werden sollten, aber das wäre eine Flamme über Semantik, also lasst uns nicht. Der Punkt ist, dass dies keine "Algorithmen" sind, die auf Computern ausgeführt werden, sondern auf theoretischen, formal definierten Super-Turing-Geräten.
Raphael
1
Ich finde die Fahrradmetapher irreführend. Etwas, das eine Funktion berechnet , ist kein Computer, von dem wir heutzutage implizit annehmen, dass es universell ist .
Raphael
1

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.

Mark H
quelle
1
Ich denke, das wirft die Frage auf . Stellen Sie sich einen Computer vor, dessen Eingabe von einem Blatt Papier stammt, das er untersucht, und dessen Ausgabe auf einem Blatt Papier erfolgt, auf das er zeichnet. Wenn die Daten kontinuierlich wären, wie es das OP nahelegt, könnte ein solcher Computer mit nur einer begrenzten Datenmenge unendlich genau sein.
Ruakh
@ruakh Sprechen Sie von so etwas wie einer analogen Turing-Maschine, bei der beispielsweise die genaue Länge einer gezogenen Linie abgelesen werden kann?
Mark H
Ja genau. Soweit ich weiß, fragt das OP danach.
Ruakh
0

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.

Yuval Filmus
quelle
12
Gleitkomma ist diskret ... wenn ein Programmierer vorgibt, es sei stetig, bedeutet dies nur, dass entweder die Ergebnisse keine Rolle spielen oder dass der Programmierer nicht verstanden hat, was er tut.
AnoE
2
Ich bin mit Respekt anderer Meinung.
Yuval Filmus
6
@YuvalFilmus leider als Gleitkomma ist diskret gibt es nichts mehr zu sagen. Jedes Mal, wenn etwas in einen normalen Computer gesteckt wird, wurde es für diskretisiert.
Jean-Baptiste Yunès
5
@AnoE bedeutet, dass den Ergebnissen bis zu einer gewissen Genauigkeit vertraut werden muss, was Yuval unter "vorgeben" versteht. Sie können einige brauchbare Ergebnisse erzielen, aber Sie müssen die Präzision verwischen. Bei großen Sets macht es Sinn. Vergleichen Sie dies mit klassischen mechanischen Problemen: Sie wissen, dass Ihre Messungen nicht präzise sind. Ein 3-cm-Objekt hat nicht wirklich eine Länge von 3.000000000 ~ cm. Sie schneiden einfach die Genauigkeit Ihrer Messung an einem vernünftigen Punkt ab.
Mindwin
6
Ich glaube nicht, dass es um die Funktionsweise unseres Geistes geht. Ich denke, es geht darum, wie die Dinge tatsächlich funktionieren. Der Grund, warum Gleitkommazahlen ungefähr sind, ist, dass sie diskret sind. Die Frage, warum Werte in Computern diskret sind, lässt sich nicht beantworten, wenn Sie sie als kontinuierlich betrachten, obwohl sie es wirklich nicht sind. Nebenbei bemerkt, Ihre Denkweise kann gefährlich sein. Viele Fehler sind darauf zurückzuführen, dass Programmierer Fließkommazahlen als fortlaufend betrachten. Selbst gebräuchliche Zahlen, die wir eher für genau halten, wie z. B. 1 Zehntel oder 1 Hundertstel, sind ungefähre Gleitkommazahlen.
JimmyJames
-2
  • Damit ein Computer mit Daten arbeiten kann, müssen sich die Daten im zugänglichen Speicher des Computers befinden
  • Der verfügbare Speicher eines Computers ist endlich
  • Im zugänglichen Speicher eines Computers können nur endliche Daten vorhanden sein
  • Nicht diskrete Werte sind unendlich

Daten in der Informatik gelten als diskret.

Repomeister
quelle
elimt(1+1/t)t
Die von Ihnen angegebene Formel ist eine Kurzformel - Sie können sie nicht in Berechnungen verwenden, deren tatsächliche "Antwort" benötigt wird, und daher kann der Computer keine sinnvolle "Arbeit" ausführen. Sie könnten ein kleines Textanalyseprogramm schreiben, um Textdarstellungen irrationaler Zahlen aufzunehmen und auszuspucken, aber die tatsächliche numerische Darstellung der "Werte" dieser Zahl kann nicht gespeichert werden - genauso wenig wie ich "das ist unendlich" auf einen Zettel schreiben kann Papier und sagen, ich halte alles in meiner Hand.
Repomeister
1
Sie scheinen anzunehmen, dass die einzige Möglichkeit, eine reelle Zahl zu berechnen, darin besteht, ihre Dezimalerweiterung zu erzeugen. Das ist einfach nicht der Fall.
David Richerby
2
Wenn Sie keinen tatsächlichen Wert haben, "rechnen" Sie dann wirklich? Absolut. Jedes Computer-Algebra-Paket tut dies die ganze Zeit. Indem Sie die tatsächlichen Werte in schriftliche Formeln zusammenfassen, können Sie höchstens die Beziehungen zwischen Entitäten und nicht ihre tatsächlichen Werte zeigen. sieht für mich wie ein tatsächlicher Wert aus. Wenn sich die Berechnungen nie zu einem tatsächlichen Wert auflösen, handelt es sich nur um eine Annäherung. Ähm, wenn ich Ihnen sage, dass die Fläche eines Kreises mit Radius 2 ist, dann ist das "eine Annäherung", aber wenn ich Ihnen sage, dass es 50,265 ist, dann ist das keine Annäherung? 16 πeiπ=116π
David Richerby
1
@Repomeister Die Anzahl der Murmeln wäre vermutlich eine ganze Zahl, daher ist es ein weniger interessantes Beispiel - Sie benötigen keine reellen Zahlen, um sie auszudrücken. Aber Computer tun können , genau auf reellen Zahlen Mathe, ein berühmtes Ergebnis von Tarski (verbessert durch Ben-Or, Kozen & Reif in den 80er Jahren). Insbesondere wenn Sie einen Ausdruck mit Ganzzahlen schreiben, Vergleichsoperatoren , die Feldoperatoren und die Variablen Ein Computer kann entscheiden, ob es reelle Zahlen , die den Ausdruck wahr machen. + , - , × , ÷ x 1 , x 2 , , x n x 1 , , x n<,,>,,=,+,,×,÷x1,x2,,xnx1,,xn
Charles