Я понимаю, что «структура» данных полностью зависит от булевой алгебры, но:
Почему данные считаются дискретным математическим объектом, а не непрерывным?
С этим связано:
Какие недостатки или инварианты нарушаются при структурировании данных как непрерывного объекта в измерениях?
Я не эксперт в этой области, так как я учусь на старшекурснике по математике, поэтому я был бы очень признателен, если бы кто-то объяснил мне это, как будто мне пять лет.
data-structures
mathematical-foundations
evil_potato
источник
источник
Ответы:
Ответ
Это был не выбор; теоретически и практически невозможно представить непрерывные, конкретные значения в цифровом компьютере или фактически в любом виде расчета.
Обратите внимание, что «дискретный» не означает «целое число» или что-то в этом роде. «дискретный» является противоположностью «непрерывного». Это означает, что для того, чтобы иметь компьютер, который действительно может хранить недискретные вещи, вам необходимо иметь возможность хранить два числа
a
иb
гдеabs(a-b) < ε
угодно для любого сколь угодно малого значенияε
. Конечно, вы можете пойти как можно глубже (используя все больше и больше места для хранения), но у каждого (физического) компьютера всегда есть верхняя граница. Независимо от того, что вы делаете, вы никогда не сможете создать (физический) компьютер, который будет хранить произвольно точно разрешенные числа.Даже если вы способны представлять числа математическими конструкциями (например
π
), это ничего не меняет. Если вы храните график или что-то, что представляет математическую формулу, то это так же дискретно, как и все остальное.добавление
Остальное - лишь небольшая перспектива за пределами области компьютерных наук. Как показали комментарии, физическая тема не является бесспорным, и как вы можете видеть, я сформулировал свой следующий пункт таким образом, что скорее UNCOMMITTED к ли это правда или нет. Считайте больше мотивом того, что понятие «континуум» не является тривиальным. Ответ, приведенный выше, не зависит от того, является ли пространство дискретным или нет.
Обратите внимание, что все это не столько проблема компьютеров, сколько проблема со значением «непрерывный». Например, не все даже соглашались или соглашались в прошлом, что Вселенная непрерывна (например, подразумевает ли масштаб Планка, что пространство-время дискретно? ). Для некоторых вещей (например, энергетических состояний электронов и многих других особенностей в квантовой (sic) механике) мы даже знаем, что Вселенная не является непрерывной; для других (например, должность ...) жюри все еще отсутствует (по крайней мере, в отношении интерпретации результатов исследований ...). (Несмотря на проблему, что, даже если она непрерывна, мы не можем измерить с произвольной точностью => Гейзенберг и т. Д.).
В математике изучение континуума (т. Е. Вещественных чисел) открывает много захватывающих аспектов, таких как теория мер, что делает совершенно невозможным фактически хранить «непрерывный» тип числа / данных.
источник
Компьютеры представляют фрагмент данных в виде конечного числа битов (нулей и единиц), а набор всех конечных битовых строк является дискретным. Вы можете работать с, скажем, действительными числами, только если найдете для них какое-то конечное представление. Например, вы можете сказать «эти данные соответствуют числу », но вы не можете сохранить все цифры на компьютере. Следовательно, компьютерные программы, которые работают с действительными числами, на самом деле работают только с дискретным подмножеством .π Rπ π р
источник
Чтобы добавить ко всем этим замечательным ответам, стоит отметить, что Алан Тьюринг, определяя свои машины, утверждает, что количество символов должно быть конечным (даже если оно сколь угодно большим), поскольку компьютер (то есть человек) не может различить все символы в противном случае.
Вот некоторые выдержки из его статьи 1936 года «О вычислимых числах с приложением к проблеме Entscheidungs»:
А затем в разделе 9:
источник
Это все в реализации.
Если вы думаете об этом, компьютеры действительно являются непрерывными устройствами. Это легко подтверждается тем фактом, что все уравнения ЭМ, определяющие их работу, являются непрерывными. Дискретная вещь - это модели, которые мы используем, чтобы решить, как использовать эти вычислительные устройства. Абстрактные машины, которые мы используем для описания вычислений, являются дискретными.
Огромное практическое преимущество заключается в независимости от множества проблем контроля качества. Если бы наши модели компьютеров использовали полную непрерывную природу своих транзисторов и конденсаторов, то нам пришлось бы заботиться о том, насколько хорошо мы построили каждый транзистор в огромной степени. Мы можем видеть это в мире аудио. В мире, где живут меломаны, разумно потратить 2000 долларов на усилитель, который может иметь 10 очень тщательно подобранных и согласованных транзисторов, которые делают именно то, что им нужно. Сравните это с 1 400 000 000 транзисторов в процессоре Core i7 по огромной цене в 400 долларов .
Поскольку наши вычислительные модели являются дискретными, мы можем смоделировать все сигналы, которые мы видим в компьютере, как дискретный сигнал плюс некоторый непрерывный член ошибки. Затем мы можем отфильтровать ошибки, просто заметив, что они неправильной формы, чтобы быть частью дискретного сигнала.
Основная часть этого - удаление временных терминов в наших абстрактных моделях. Многие из наших моделей измеряют не время против какого-либо физического процесса, а против некоторого «логического» сигнала, известного как часы. Если вы прерываете часы, система перестает двигаться, но не выходит из строя. Он просто завершает очистку от любых аналоговых ошибок, которые могут иметь, и сидит в ожидании следующего дискретного импульса тактовой частоты. Удаление непрерывных сроков существенно упрощает вычисления и доказательства вычислений. Вместо этого наши понятия времени измеряются дискретно, как видно из P и NP категорий алгоритмов.
источник
Потому что:
Цифровые компьютеры не могут хранить произвольные действительные числа.
Аналоговые компьютеры страдают от теплового шума (если он электронный), трения (если он механический или гидравлический), помех, чувствительности к колебаниям температуры, неизбежных дефектов и старения. С такими трудностями сталкиваются (экспериментальные) физики и инженеры. Большинство компьютерных наук просто абстрагируют физику.
Вот несколько статей о реальных вычислениях :
Марк Браверман, Стивен Кук, Вычислительные решения: основы научных вычислений , Уведомления AMS, март 2006 г.
Марк Браверман, О сложности реальных функций , arXiv: cs / 0502066.
Ленор Блум, « Расчеты над реалами»: где Тьюринг встречает Ньютона , «Уведомления об AMS», октябрь 2004 г.
Васко Браттка, Реалистичные модели вычислимости на действительных числах , апрель 2000 г.
Васко Браттка, Питер Хертлинг, Реальные машины с произвольным доступом , декабрь 1998.
Ленор Блум, Майк Шуб, Стив Смейл, К теории вычисления и сложности действительных чисел: NP-полнота, рекурсивные функции и универсальные машины , Бюллетень AMS, июль 1989.
и вот статья об аналоговых вычислениях :
источник
Термин «компьютер» на современном языке означает «цифровой компьютер»; Суть цифрового компьютера состоит в том, что он имеет конечное число дискретных состояний. Можно было бы провести интересную дискуссию о том, были ли причины, по которым цифровые компьютеры получили преимущество перед аналоговыми компьютерами, были связаны главным образом с инженерной практичностью или главным образом из-за лучшей поддержки теоретической информатики. Но какими бы ни были причины, цифровые компьютеры - это то, к чему мы пришли, и любая полезная математическая модель цифрового компьютера (и, следовательно, его данных) будет дискретной, а не непрерывной.
источник
Слово
data
происходит от латинского словаdatum
, что означает то, что было дано. Со временем форма множественного числа изменилась, и теперь она широко используется как единственное и множественное число. Это также стало ассоциироваться именно с информацией.Обратите внимание, что существует разница между элементом информации (датумом) и его представлением.
Теория информации имеет дело с (среди прочего) дискретными частями информации, представленной переменными. Это исчисляемые сущности. Например, скорость, местоположение, масса и т. Д. Являются непрерывными величинами, но они не зависят друг от друга: между массой и местоположением нет преобразования. Когда эти величины представлены численно, их элементы данных, как бы они ни были представлены, также являются дискретными друг от друга.
С другой стороны, подавляющее большинство наших современных компьютеров используют некоторую форму электрического заряда для представления информации. Заряд либо присутствует, либо его нет; есть ток в цепи или нет. Это тоже дискретно, но не обязательно! Просто из-за того, как наша технология развивалась, мы используем двоичное представление. Вполне возможно, что развитие в области квантовых вычислений изменит это в ближайшем будущем. Также немыслимо, что аналоговые компьютеры возродятся, и наши представления о том, что числа должны быть представлены двоичными числами, будут размыты!
Подведем итог:
data
состоят из отдельных элементов информации, каждый из которых является датумом; тогда как каждый элемент данных не должен быть представлен с использованием дискретной математики, но в настоящее время это чисто современное совпадение.источник
Я хочу оспорить вашу фундаментальную предпосылку:
Это не так.
Например, изучение Алгоритмов является важной областью компьютерных наук, и есть много алгоритмов, которые работают с непрерывными данными. Вы, вероятно, знакомы с алгоритмом Евклида для вычисления наибольшего общего делителя двух натуральных чисел, но знаете ли вы, что у Евклида также была геометрическая версия того же алгоритма, который вычисляет самую длинную общую меру двух соизмеримых линий? Это пример алгоритма (и, следовательно, объекта изучения информатики) над действительными числами, то есть непрерывными данными, хотя Евклид и не думал об этом таким образом.
Существует много разных способов классификации алгоритмов, но один из используемых способов состоит в том, чтобы классифицировать их по их «непрерывности»:
В других ответах уже упоминалось о реальных вычислениях в теории вычислимости, другом важном подразделе информатики.
Единственный реальный (очень капризный) недостаток заключается в том, что такие данные нельзя представить с помощью обычных цифровых компьютеров. Вы можете думать об алгоритмах над непрерывными данными, но не можете запускать их на стандартных машинах, которые мы обычно используем для запуска алгоритмов.
Это основная причина, по которой непрерывные данные не так «видимы», как цифровые данные.
Тем не менее, реализация аналогового алгоритма на самом деле не должна быть сложной, чтобы представить или даже построить. Например, это реализация аналогового алгоритма: По Эндрю Dressel - собственная работа, CC BY-SA 3,0 , Link
источник
Теперь набор всех возможных конечных данных можно поместить в лексикографическом порядке, то есть набор является исчисляемым. Но множество непрерывных действительных чисел неисчислимо, поэтому в континууме всегда есть числа, которые не могут быть сохранены данной вычислительной системой. Из этого можно сделать вывод, что для хранения произвольного действительного числа требуются бесконечные ресурсы.
источник
Данные не всегда считаются дискретными. Научное программирование часто включает в себя арифметику с плавающей точкой. Программист обычно делает вид, что задействованные переменные являются непрерывными, имея в виду проблему числовой стабильности, которая проистекает из того факта, что данные хранятся только с конечной точностью.
источник
Данные в информатике считаются дискретными.
источник