Entiendo que la "estructura" de los datos depende totalmente del álgebra booleana, pero:
¿Por qué se considera que los datos son una entidad matemática discreta en lugar de una entidad continua?
Relacionado con esto:
¿Cuáles son los inconvenientes, o invariantes, que se violan al estructurar los datos como una entidad continua en dimensiones?
No soy un experto en el campo ya que soy un estudiante de matemáticas de pregrado, así que realmente agradecería que alguien me explicara esto como si tuviera cinco años.
data-structures
mathematical-foundations
malvada patata
fuente
fuente
Respuestas:
Responder
Esto no fue una elección; Es teórica y prácticamente imposible representar valores continuos y concretos en una computadora digital, o en realidad en cualquier tipo de cálculo.
Tenga en cuenta que "discreto" no significa "entero" o algo así. "discreto" es lo contrario de "continuo". Esto significa que, para tener una computadora que sea realmente capaz de almacenar cosas no discretas, necesitaría poder almacenar dos números
a
yb
dóndeabs(a-b) < ε
para cualquier valor arbitrariamente pequeño deε
. Claro, puedes ir tan profundo como quieras (usando más y más espacio de almacenamiento), pero cada computadora (física) siempre tiene un límite superior. No importa lo que haga, nunca puede hacer una computadora (física) que almacene números resueltos arbitrariamente.Incluso si puede representar números mediante construcciones matemáticas (por ejemplo
π
), esto no cambia nada. Si almacena un gráfico o lo que sea que represente una fórmula matemática, entonces esto es tan discreto como cualquier otra cosa.Apéndice
El resto es solo una pequeña perspectiva más allá del campo de la informática. Como han mostrado los comentarios, el tema físico no es indiscutible, y como puede ver, he formulado mi próximo párrafo de una manera que no está comprometida con si es cierto o no. Tómelo más como una motivación que el concepto de "continuo" no es trivial. La respuesta dada anteriormente no depende de si el espacio es discreto o no.
Tenga en cuenta que todo esto no es tanto un problema de las computadoras, sino un problema con el significado de "continuo". Por ejemplo, no todos están de acuerdo, o estuvieron de acuerdo en el pasado, que el Universo es continuo (por ejemplo, ¿la escala de Planck implica que el espacio-tiempo es discreto? ). Para algunas cosas (por ejemplo, estados de energía de electrones y muchas otras características en la Mecánica Cuántica (sic)) incluso sabemos que el Universo no es continuo; para otros (por ejemplo, posición ...) el jurado aún está fuera (al menos con respecto a la interpretación de los resultados de la investigación ...). (A pesar del problema de que incluso si es continuo, no podríamos medir con precisión arbitraria => Heisenberg, etc.).
En matemáticas, estudiar el continuo (es decir, los reales) abre muchos aspectos fascinantes, como la teoría de la medida, lo que hace que sea completamente imposible almacenar un tipo de datos / datos "continuos".
fuente
Las computadoras representan un dato como un número finito de bits (ceros y unos) y el conjunto de todas las cadenas de bits finitos es discreto. Solo puede trabajar con, digamos, números reales si encuentra alguna representación finita para ellos. Por ejemplo, puede decir "estos datos corresponden al número ", pero no puede almacenar todos los dígitos de en una computadora. Por lo tanto, los programas de computadora que funcionan con números reales en realidad solo funcionan en un subconjunto discreto de .π Rπ π R
fuente
Para agregar a todas estas excelentes respuestas, vale la pena señalar que Alan Turing, al definir sus máquinas, argumenta que la cantidad de símbolos debe ser finita (incluso si es arbitrariamente grande) ya que una computadora (es decir, un humano) no puede distinguir todos los símbolos de lo contrario.
Aquí hay algunos extractos de su artículo de 1936 "Sobre números computables, con una aplicación al problema Entscheidungs":
Y luego en la sección 9:
fuente
Todo está en la implementación.
Si lo piensas, las computadoras realmente son dispositivos continuos. Esto se muestra fácilmente por el hecho de que todas las ecuaciones EM que gobiernan cómo funcionan son continuas. Lo que es discreto son los modelos que usamos para decidir cómo usar estos dispositivos informáticos. Las máquinas abstractas que utilizamos para describir la computación son todas discretas.
La gran ventaja práctica de esto es tener independencia de muchos desafíos de control de calidad. Si nuestros modelos de computadoras aprovecharan la naturaleza continua y completa de sus transistores y condensadores, entonces tendríamos que preocuparnos por cuán bien construimos cada transistor en un grado tremendo. Podemos ver esto en el mundo del audio. En el mundo en que habitan los audiófilos, es razonable gastar $ 2000 en un amplificador que podría tener 10 transistores cuidadosamente seleccionados y combinados que hacen exactamente lo continuo que desean. Compare esto con 1,400,000,000 de transistores en una CPU Core i7 al costo de $ 400.
Debido a que nuestros modelos computacionales son discretos, podemos modelar todas las señales que vemos en una computadora como una señal discreta más algún término de error continuo. Luego podemos filtrar los errores simplemente observando que no son la forma correcta de ser parte de la señal discreta.
Una parte importante de esto es la eliminación de los términos de tiempo en nuestros modelos abstractos. Muchos de nuestros modelos no miden el tiempo contra algún proceso físico, sino contra alguna señal "lógica" conocida como reloj. Si interrumpe un reloj, el sistema deja de moverse, pero no se descompone. Simplemente termina de eliminar cualquier error analógico que pueda tener, y espera el próximo pulso discreto del reloj. Eliminar los términos de tiempo continuo simplifica drásticamente el cómputo y las pruebas sobre el cómputo. En cambio, nuestros conceptos de tiempo se miden discretamente, como se ve en las categorizaciones de algoritmos P y NP.
fuente
Porque:
Las computadoras digitales no pueden almacenar números reales arbitrarios.
Las computadoras analógicas están plagadas de ruido térmico (si es electrónico), fricción (si es mecánico o hidráulico), perturbaciones, sensibilidad a las variaciones de temperatura, imperfecciones inevitables y envejecimiento. Hacer frente a tales dificultades es lo que hacen los físicos e ingenieros (experimentales). La mayoría de la informática simplemente abstrae la física.
Aquí hay algunos documentos sobre computación real :
Mark Braverman, Stephen Cook, Informática sobre los reales: fundamentos de la informática científica , Avisos de la AMS, marzo de 2006.
Mark Braverman, Sobre la complejidad de las funciones reales , arXiv: cs / 0502066.
Lenore Blum, Computación sobre los reales: donde Turing se encuentra con Newton , Avisos de la AMS, octubre de 2004.
Vasco Brattka, Modelos realistas de computabilidad en números reales , abril de 2000.
Vasco Brattka, Peter Hertling, máquinas acceso aleatorio real , diciembre de 1998.
Lenore Blum, Mike Shub, Steve Smale, Sobre una teoría de la computación y la complejidad sobre los números reales: NP-completitud, funciones recursivas y máquinas universales , Boletín de la AMS, julio de 1989.
y aquí hay un artículo sobre computación analógica :
fuente
El término "computadora" en el lenguaje moderno significa "computadora digital"; La esencia de una computadora digital es que tiene un número finito de estados discretos. Uno podría tener un debate interesante sobre si las razones por las cuales las computadoras digitales se ganaron el favor de las computadoras analógicas se debieron principalmente a la practicidad de la ingeniería, o se debieron principalmente a una mejor base de la informática teórica. Pero cualesquiera que sean las razones, terminamos con las computadoras digitales, y cualquier modelo matemático útil de una computadora digital (y, por lo tanto, sus datos) será discreto en lugar de continuo.
fuente
La palabra
data
deriva de la palabra latina.datum
, que significa algo que se le dio. Con el tiempo, la forma plural ha cambiado de uso y ahora se usa comúnmente como singular y plural. También se ha asociado con información específicamente.Tenga en cuenta que existe una diferencia entre un elemento de información (un dato) y su representación.
Teoría de la información ocupa (entre otras cosas) de datos discretos representados por variables. Estas son entidades contables. Por ejemplo, la velocidad, la ubicación, la masa, etc. son cantidades continuas, pero discretas entre sí: no hay transformación entre la masa y la ubicación. Cuando estas cantidades se representan numéricamente, sus elementos de datos, aunque estén representados, también son discretos entre sí.
Por otro lado, la gran mayoría de nuestras computadoras actuales usan alguna forma de carga eléctrica para representar la información. El cargo está presente o no lo está; hay corriente en el circuito o no la hay. Esto también es discreto, ¡pero no tiene por qué serlo! Es simplemente por la forma en que nuestra tecnología se ha desarrollado que usamos la representación binaria. Es posible que los desarrollos en Quantum Computing cambien esto en un futuro cercano. Tampoco es inconcebible que las computadoras analógicas resurjan y nuestras nociones de que los números tienen que ser representados por binarios desaparecerán!
Para resumir:
data
están compuestos de elementos discretos de información, cada uno de los cuales es un dato; mientras que cada dato no necesita ser representado usando matemáticas discretas, pero actualmente es puramente por coincidencia contemporánea.fuente
Quiero desafiar tu premisa fundamental:
No lo es
Por ejemplo, el estudio de los algoritmos es un subcampo importante de la informática, y hay muchos algoritmos que funcionan con datos continuos. Probablemente esté familiarizado con el Algoritmo de Euclides para calcular el máximo divisor común de dos números naturales, pero ¿sabía que Euclides también tenía una versión geométrica de ese mismo algoritmo que calcula la medida común más larga de dos líneas conmensurables? Ese es un ejemplo de un algoritmo (y, por lo tanto, un objeto de estudio de la informática) sobre números reales, es decir, datos continuos, a pesar de que Euclides no lo pensó de esta manera.
Hay muchas formas diferentes de clasificar los algoritmos, pero una forma de usarlos es clasificarlos por su "continuidad":
Otras respuestas ya han mencionado la computación real en la teoría de la computabilidad, otro subcampo importante de la informática.
El único inconveniente real (juego de palabras muy intencionado) es que dichos datos no pueden representarse con computadoras digitales comunes. Puede pensar en algoritmos sobre datos continuos, pero no puede ejecutarlos en las máquinas estándar que usualmente usamos para ejecutar algoritmos.
Esa es la razón principal por la cual los datos continuos no son tan "visibles" como los datos digitales.
Sin embargo, la implementación de un algoritmo analógico en realidad no necesita ser complicada de imaginar o incluso de construir. Por ejemplo, esta es una implementación de un algoritmo analógico: por Andrew Dressel - Trabajo propio, CC BY-SA 3.0 , Enlace
fuente
Ahora, el conjunto de todos los datos finitos posibles se puede poner en orden lexicográfico, lo que significa que el conjunto es contable. Pero, el conjunto de números reales continuos es incontable, por lo que siempre hay números en el continuo que no pueden ser almacenados por un sistema de cálculo dado. A partir de esto, podemos concluir que el almacenamiento de un número real arbitrario requiere recursos infinitos.
fuente
Los datos no siempre se consideran discretos. La programación científica a menudo implica aritmética de punto flotante. El programador generalmente finge que las variables involucradas son continuas, sin dejar de tener en cuenta el problema de la estabilidad numérica, que se deriva del hecho de que los datos se almacenan con una precisión finita.
fuente
Los datos en informática se consideran discretos.
fuente