Дискретные объекты

Универсальность дискретного (цифрового) представления информации

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

Аналоговый сигнал	Дискретный сигнал

Аналоговая информация характеризуется плавным изменением ее параметров. Основные параметры наиболее простых синусоидальных аналоговых сигналов могут непрерывно и плавно меняться.
Дискретная информация базируется на ряде фиксированных уровней представления заданных параметров, взятых в определенные промежутки времени. Если этих уровней много, можно говорить о цифровом представлении информации, то есть когда в определенные дискретные моменты они принимают конкретные дискретные значения. К счастью, аналоговую информацию легко преобразовать в цифровую. Это делают так называемые аналогоцифровые преобразователи (АЦП). Обратное преобразование обеспечивают цифроаналоговые преобразователи (ЦАП).

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

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

К дискретным устройствам относятся:

• монитор – яркость луча изменяется не плавно, а скачкообразно (дискретно). Луч либо есть, либо его нет. Если луч есть, то мы видим яркую точку (белую или цветную). Если луча нет, мы видим черную точку. Поэтому изображение на экране монитора получается более четким, чем на экране телевизора;
• проигрыватель аудиокомпакт-дисков – звуковая дорожка представлена участками с разной отражающей способностью;
• струйный принтер – изображение состоит из отдельных точек разного цвета.

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

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

В технике непрерывная информация называется аналоговой. Многие устройства, созданные человеком, работают с аналоговой информацией. Луч кинескопа телевизора перемещается по экрану, вызывая свечение точек. Чем сильнее луч, тем ярче свечение. Изменение свечения происходит плавно и непрерывно. Проигрыватель грампластинок, ртутный термометр, манометр - примеры аналоговых устройств. Некоторые бытовые приборы могут иметь как аналоговую, так и цифровую конструкцию. К примеру, тонометр - прибор для измерения кровяного давления. Существенным отличием является то, что аналоговый прибор может выдать абсолютно произвольную величину показаний (чуть больше или меньше деления), а набор показаний у цифрового прибора ограничен количеством цифр на индикаторе. Компьютер работает исключительно с дискретной (цифровой) информацией. Память компьютера состоит из отдельных битов, а значит, дискретна. Датчики, посредством которых воспринимается информация, измеряют в основном непрерывные характеристики - температуру, нагрузку, напряжение и т.д. Встает проблема преобразования аналоговой информации в дискретную форму.

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

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

Дискретизация – это преобразование непрерывных изображений и звука в набор дискретных значений в форме кодов.

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

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

Практически 80% информации человек получает через зрение, что означает доминирование зрительных рецепторов в жизнедеятельности человека. Вся информация в аппарате мышления человека сохраняется в виде образов, причем в этом образе сконцентрирована информация, полученная всеми рецепторами человека. Можно сделать вывод, что информация в памяти человека хранится в виде графических объектов. Развивая гипотезу о том, что любая информация, получаемая человеком извне, проходит стадию преобразования в изображения с последующей их целенаправленной обработкой, можно вывести последовательность процедур, пригодную для реализации в автоматизированных системах обработки данных различного рода, в том числе и в речи:

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

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

• существует узел, в который не входит ни одной дуги (корень);
• в каждую вершину, кроме корня, входит одна дуга.

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



Все вершины, в которые входят ветви, исходящие из одной общей вершины, называются потомками, а сама вершина – предком. Для каждого предка может быть выделено несколько. Уровень потомка на единицу превосходит уровень его предка. Корень дерева не имеет предка, а листья дерева не имеют потомков.

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

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

Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень нуль. По величине степени дерева различают два типа деревьев:

• двоичные – степень дерева не более двух;
• сильноветвящиеся – степень дерева произвольная.

Упорядоченное дерево – это дерево, у которого ветви, исходящие из каждой вершины, упорядочены по определенному критерию.
Деревья являются рекурсивными структурами, так как каждое поддерево также является деревом. Таким образом, дерево можно определить как рекурсивную структуру, в которой каждый элемент является:

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

Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.

При обходе все вершины дерева должны посещаться в определенном порядке. Существует несколько способов обхода всех вершин дерева. Выделим три наиболее часто используемых способа обхода дерева (см. рис. ниже) :

• прямой;
• симметричный;
• обратный.

Бинарные деревья

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



Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:

• информационное поле (ключ вершины);
• служебное поле (их может быть несколько или ни одного);
• указатель на левое поддерево;
• указатель на правое поддерево.

По степени вершин бинарные деревья делятся на ( рис. ниже):

• строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);
• нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).