Почему данные в информатике считаются дискретными?

35

Я понимаю, что «структура» данных полностью зависит от булевой алгебры, но:

Почему данные считаются дискретным математическим объектом, а не непрерывным?

С этим связано:

Какие недостатки или инварианты нарушаются при структурировании данных как непрерывного объекта в измерениях?р

Я не эксперт в этой области, так как я учусь на старшекурснике по математике, поэтому я был бы очень признателен, если бы кто-то объяснил мне это, как будто мне пять лет.

evil_potato
источник
12
Реальный расчет будет неоправданно мощным
Harold
1
Перейдите к этой главе, если позволит время. Автор объясняет это очень легко учиться из аналоговых против двоичных сигналов
Мухаммед Сайеф

Ответы:

44

Ответ

почему данные считались дискретным математическим объектом, а не непрерывным

Это был не выбор; теоретически и практически невозможно представить непрерывные, конкретные значения в цифровом компьютере или фактически в любом виде расчета.

Обратите внимание, что «дискретный» не означает «целое число» или что-то в этом роде. «дискретный» является противоположностью «непрерывного». Это означает, что для того, чтобы иметь компьютер, который действительно может хранить недискретные вещи, вам необходимо иметь возможность хранить два числа aи bгде abs(a-b) < εугодно для любого сколь угодно малого значения ε. Конечно, вы можете пойти как можно глубже (используя все больше и больше места для хранения), но у каждого (физического) компьютера всегда есть верхняя граница. Независимо от того, что вы делаете, вы никогда не сможете создать (физический) компьютер, который будет хранить произвольно точно разрешенные числа.

Даже если вы способны представлять числа математическими конструкциями (например π), это ничего не меняет. Если вы храните график или что-то, что представляет математическую формулу, то это так же дискретно, как и все остальное.

добавление

Остальное - лишь небольшая перспектива за пределами области компьютерных наук. Как показали комментарии, физическая тема не является бесспорным, и как вы можете видеть, я сформулировал свой следующий пункт таким образом, что скорее UNCOMMITTED к ли это правда или нет. Считайте больше мотивом того, что понятие «континуум» не является тривиальным. Ответ, приведенный выше, не зависит от того, является ли пространство дискретным или нет.

Обратите внимание, что все это не столько проблема компьютеров, сколько проблема со значением «непрерывный». Например, не все даже соглашались или соглашались в прошлом, что Вселенная непрерывна (например, подразумевает ли масштаб Планка, что пространство-время дискретно? ). Для некоторых вещей (например, энергетических состояний электронов и многих других особенностей в квантовой (sic) механике) мы даже знаем, что Вселенная не является непрерывной; для других (например, должность ...) жюри все еще отсутствует (по крайней мере, в отношении интерпретации результатов исследований ...). (Несмотря на проблему, что, даже если она непрерывна, мы не можем измерить с произвольной точностью => Гейзенберг и т. Д.).

В математике изучение континуума (т. Е. Вещественных чисел) открывает много захватывающих аспектов, таких как теория мер, что делает совершенно невозможным фактически хранить «непрерывный» тип числа / данных.

Anoe
источник
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
DW
29

Компьютеры представляют фрагмент данных в виде конечного числа битов (нулей и единиц), а набор всех конечных битовых строк является дискретным. Вы можете работать с, скажем, действительными числами, только если найдете для них какое-то конечное представление. Например, вы можете сказать «эти данные соответствуют числу », но вы не можете сохранить все цифры на компьютере. Следовательно, компьютерные программы, которые работают с действительными числами, на самом деле работают только с дискретным подмножеством .π Rππр

Кристиан Мэтт
источник
Это делают цифровые компьютеры, но не аналоговые.
Дрю
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
DW
8

Чтобы добавить ко всем этим замечательным ответам, стоит отметить, что Алан Тьюринг, определяя свои машины, утверждает, что количество символов должно быть конечным (даже если оно сколь угодно большим), поскольку компьютер (то есть человек) не может различить все символы в противном случае.

Вот некоторые выдержки из его статьи 1936 года «О вычислимых числах с приложением к проблеме Entscheidungs»:

введите описание изображения здесь

А затем в разделе 9:

введите описание изображения здесь введите описание изображения здесь

Guido
источник
1
Пожалуйста, расшифруйте изображения, чтобы они могли быть проиндексированы поиском.
Рафаэль
7

Это все в реализации.

Если вы думаете об этом, компьютеры действительно являются непрерывными устройствами. Это легко подтверждается тем фактом, что все уравнения ЭМ, определяющие их работу, являются непрерывными. Дискретная вещь - это модели, которые мы используем, чтобы решить, как использовать эти вычислительные устройства. Абстрактные машины, которые мы используем для описания вычислений, являются дискретными.

Огромное практическое преимущество заключается в независимости от множества проблем контроля качества. Если бы наши модели компьютеров использовали полную непрерывную природу своих транзисторов и конденсаторов, то нам пришлось бы заботиться о том, насколько хорошо мы построили каждый транзистор в огромной степени. Мы можем видеть это в мире аудио. В мире, где живут меломаны, разумно потратить 2000 долларов на усилитель, который может иметь 10 очень тщательно подобранных и согласованных транзисторов, которые делают именно то, что им нужно. Сравните это с 1 400 000 000 транзисторов в процессоре Core i7 по огромной цене в 400 долларов .

Поскольку наши вычислительные модели являются дискретными, мы можем смоделировать все сигналы, которые мы видим в компьютере, как дискретный сигнал плюс некоторый непрерывный член ошибки. Затем мы можем отфильтровать ошибки, просто заметив, что они неправильной формы, чтобы быть частью дискретного сигнала.

Основная часть этого - удаление временных терминов в наших абстрактных моделях. Многие из наших моделей измеряют не время против какого-либо физического процесса, а против некоторого «логического» сигнала, известного как часы. Если вы прерываете часы, система перестает двигаться, но не выходит из строя. Он просто завершает очистку от любых аналоговых ошибок, которые могут иметь, и сидит в ожидании следующего дискретного импульса тактовой частоты. Удаление непрерывных сроков существенно упрощает вычисления и доказательства вычислений. Вместо этого наши понятия времени измеряются дискретно, как видно из P и NP категорий алгоритмов.

Корт Аммон - Восстановить Монику
источник
7

Потому что:

  • Цифровые компьютеры не могут хранить произвольные действительные числа.

  • Аналоговые компьютеры страдают от теплового шума (если он электронный), трения (если он механический или гидравлический), помех, чувствительности к колебаниям температуры, неизбежных дефектов и старения. С такими трудностями сталкиваются (экспериментальные) физики и инженеры. Большинство компьютерных наук просто абстрагируют физику.

Вот несколько статей о реальных вычислениях :

и вот статья об аналоговых вычислениях :

Родриго де Азеведо
источник
4

Термин «компьютер» на современном языке означает «цифровой компьютер»; Суть цифрового компьютера состоит в том, что он имеет конечное число дискретных состояний. Можно было бы провести интересную дискуссию о том, были ли причины, по которым цифровые компьютеры получили преимущество перед аналоговыми компьютерами, были связаны главным образом с инженерной практичностью или главным образом из-за лучшей поддержки теоретической информатики. Но какими бы ни были причины, цифровые компьютеры - это то, к чему мы пришли, и любая полезная математическая модель цифрового компьютера (и, следовательно, его данных) будет дискретной, а не непрерывной.

Майкл Кей
источник
2

Слово dataпроисходит от латинского слова datum, что означает то, что было дано. Со временем форма множественного числа изменилась, и теперь она широко используется как единственное и множественное число. Это также стало ассоциироваться именно с информацией.

Обратите внимание, что существует разница между элементом информации (датумом) и его представлением.

Теория информации имеет дело с (среди прочего) дискретными частями информации, представленной переменными. Это исчисляемые сущности. Например, скорость, местоположение, масса и т. Д. Являются непрерывными величинами, но они не зависят друг от друга: между массой и местоположением нет преобразования. Когда эти величины представлены численно, их элементы данных, как бы они ни были представлены, также являются дискретными друг от друга.

С другой стороны, подавляющее большинство наших современных компьютеров используют некоторую форму электрического заряда для представления информации. Заряд либо присутствует, либо его нет; есть ток в цепи или нет. Это тоже дискретно, но не обязательно! Просто из-за того, как наша технология развивалась, мы используем двоичное представление. Вполне возможно, что развитие в области квантовых вычислений изменит это в ближайшем будущем. Также немыслимо, что аналоговые компьютеры возродятся, и наши представления о том, что числа должны быть представлены двоичными числами, будут размыты!

Подведем итог: dataсостоят из отдельных элементов информации, каждый из которых является датумом; тогда как каждый элемент данных не должен быть представлен с использованием дискретной математики, но в настоящее время это чисто современное совпадение.

Пирог злой собаки
источник
1
Теория информации также может обрабатывать непрерывные переменные.
Ювал
1
Смотрите, например, дифференциальную энтропию .
Ювал
2

Я хочу оспорить вашу фундаментальную предпосылку:

Почему данные считаются дискретным математическим объектом, а не непрерывным?

Это не так.

Например, изучение Алгоритмов является важной областью компьютерных наук, и есть много алгоритмов, которые работают с непрерывными данными. Вы, вероятно, знакомы с алгоритмом Евклида для вычисления наибольшего общего делителя двух натуральных чисел, но знаете ли вы, что у Евклида также была геометрическая версия того же алгоритма, который вычисляет самую длинную общую меру двух соизмеримых линий? Это пример алгоритма (и, следовательно, объекта изучения информатики) над действительными числами, то есть непрерывными данными, хотя Евклид и не думал об этом таким образом.

Существует много разных способов классификации алгоритмов, но один из используемых способов состоит в том, чтобы классифицировать их по их «непрерывности»:

  • Цифровые алгоритмы (алгоритмы дискретных событий над цифровыми данными):
    • численный вариант алгоритма Евклида
    • деление на длинные руки, умножение и т. д. в школе
    • любая компьютерная программа, программа λ-исчисления, машина Тьюринга
  • Нецифровые данные, алгоритмы дискретных событий (алгоритмы над непрерывными данными, которые, однако, все еще имеют понятие «шаг», то есть непрерывные данные, но дискретное время):
    • геометрический вариант алгоритма Евклида
    • алгоритмы на действительные числа (например, процедура исключения Гаусса)
    • алгоритмы на непрерывных функциях (например, алгоритм деления пополам)
  • Аналоговые алгоритмы (непрерывное время, непрерывные данные):
    • электрические цепи
    • механические гироскопы
  • Гибридные алгоритмы (любая комбинация вышеперечисленного)
    • роботы

В других ответах уже упоминалось о реальных вычислениях в теории вычислимости, другом важном подразделе информатики.

р

Единственный реальный (очень капризный) недостаток заключается в том, что такие данные нельзя представить с помощью обычных цифровых компьютеров. Вы можете думать об алгоритмах над непрерывными данными, но не можете запускать их на стандартных машинах, которые мы обычно используем для запуска алгоритмов.

Это основная причина, по которой непрерывные данные не так «видимы», как цифровые данные.

Тем не менее, реализация аналогового алгоритма на самом деле не должна быть сложной, чтобы представить или даже построить. Например, это реализация аналогового алгоритма: Велосипед Triumph CycleПо Эндрю Dressel  - собственная работа, CC BY-SA 3,0 , Link

рQрQ×рπQ×π

Йорг Миттаг
источник
«Есть много алгоритмов, которые работают с непрерывными данными» - мы могли бы долго обсуждать, следует ли называть такие вещи «алгоритмами», но это было бы огненной войной в отношении семантики, поэтому давайте не будем. Дело в том, что это не «алгоритмы», которые работают на компьютерах, а на теоретических, формально определенных, супер-тьюринговых устройствах.
Рафаэль
1
Я нахожу велосипедную метафору вводящей в заблуждение. Нечто, вычисляющее одну функцию, не является компьютером, который мы сегодня неявно предполагаем универсальным .
Рафаэль
1

π

Теперь набор всех возможных конечных данных можно поместить в лексикографическом порядке, то есть набор является исчисляемым. Но множество непрерывных действительных чисел неисчислимо, поэтому в континууме всегда есть числа, которые не могут быть сохранены данной вычислительной системой. Из этого можно сделать вывод, что для хранения произвольного действительного числа требуются бесконечные ресурсы.

Марк Н
источник
1
Я думаю, что это напрашивается на вопрос . Рассмотрим компьютер, который берет свои данные с листа бумаги, который он рассматривает, и который выдает свои данные на листе бумаги, на котором он рисует. Если бы данные были непрерывными, как предполагает ОП, то такой компьютер мог бы быть бесконечно точным, имея лишь конечный объем данных.
Руах
@ruakh Вы говорите о чем-то похожем на аналоговую машину Тьюринга, где она могла бы, например, прочитать точную длину нарисованной линии?
Марк Х
Да, точно. Насколько я понимаю, именно об этом спрашивает ОП.
Руах
0

Данные не всегда считаются дискретными. Научное программирование часто включает в себя арифметику с плавающей точкой. Программист обычно делает вид, что задействованные переменные являются непрерывными, имея в виду проблему числовой стабильности, которая проистекает из того факта, что данные хранятся только с конечной точностью.

Юваль Фильмус
источник
12
С плавающей точкой является дискретным ... если программист делает вид , что является непрерывным, что просто означает , что либо результаты не имеют значения, или что программист не понял , что он делает.
AnoE
2
Я с уважением не согласен.
Юваль
6
@YuvalFilmus, увы, поскольку плавающая точка дискретна, больше нечего сказать. Каждый раз, когда что-то помещается в обычный компьютер, оно подвергается дискретизации.
Жан-Батист Юнес
5
@ AnoE это означает, что результатам нужно доверять с определенной точностью, то есть то, что Ювал имеет в виду под "притворством". Вы можете получить некоторые полезные результаты, но вы должны размыть о точности. Для больших наборов это имеет смысл. Сравните это с проблемами классической механики: вы знаете, что ваши измерения не точны. 3 см объект не имеет фактически 3,000000000 ~ см длины. Вы просто снижаете точность измерения в какой-то разумной точке.
Mindwin
6
Я не думаю, что вопрос в том, как работает наш разум. Я думаю, что это о том, как все работает на самом деле. Причина того, что числа с плавающей точкой являются приблизительными, заключается в том, что они являются дискретными. То, что вы думаете о них как о непрерывных, даже если они на самом деле не таковые, не помогает ответить на вопрос, почему ценности в компьютерах дискретны. Кстати, ваш образ мышления может быть опасным. Многие ошибки возникли из-за того, что программисты думали о плавающей точке как о непрерывной. Даже обычные числа, которые мы склонны считать точными, например, одна десятая или одна сотая, являются приблизительными с плавающей запятой.
JimmyJames
-2
  • Для работы компьютера с данными эти данные должны существовать в доступной памяти компьютера.
  • Доступная память компьютера конечна
  • Только доступные данные могут существовать в доступной памяти компьютера
  • Недискретные значения бесконечны

Данные в информатике считаются дискретными.

Repomeister
источник
еИтT(1+1/T)T
Указанная вами формула является сокращенной - вы не можете использовать ее в любых вычислениях, для которых нужен реальный «ответ», и, следовательно, компьютер не может выполнить значимую «работу». Вы могли бы написать небольшую программу анализа текста, чтобы принимать и выплевывать текстовые представления иррациональных чисел, но фактическое числовое представление «значений» этих чисел не может быть сохранено в памяти - больше, чем я могу написать «это бесконечность» на бланке бумаги и скажи, что я все держу в руке.
Repomeister
1
Похоже, вы предполагаете, что единственный способ вычислить действительное число - это произвести его десятичное расширение. Это просто не тот случай.
Дэвид Ричерби
2
еяπзнак равно-116π
1
<,,>,,знак равно,+,-,×,÷Икс1,Икс2,...,ИксNИкс1,...,ИксN