Введение_в_специальность

Любая реальная материальная система, входящая в источник со- общений, может иметь непрерывный ряд состояний. Однако сведе- ния, передаваемые о ней, никогда не исчерпывают всех особенно-

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

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

Разумеется, с ростом Т увеличивается и число различных сооб- щений АТ, которое может создать дискретный источник, причем это число для любых источников возрастает приблизительно по экспо- ненциальному закону. Поэтому если не ограничивать интервал вре- мени Т, то множество АT окажется всегда бесконечным. Однако для дискретного источника сообщений оно всегда будет счетным. Это значит, что все мыслимые сообщения можно расположить по неко- торому закону в ряд и перенумеровать. Так, например, для источни- ка, создающего сообщения в виде текста, записанного русским ал- фавитом, можно разделить все возможные сообщения на группы, отличающиеся количеством букв в сообщении, расположить эти группы в порядке возрастания числа букв, а внутри каждой группы расположить сообщения в алфавитном порядке и полученную по- следовательность сообщений пронумеровать. Следовательно, такой источник сообщений является дискретным. Любые два сообщения этого источника, если они не тождественны, отличаются, по край- ней мере, одной буквой.

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

61

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

должен округлять измеренные значения с определенной точностью (например, до 0,01 мм рт. ст.). Легко убедиться, что такой видоиз- мененный источник оказывается дискретным. В то же время, если указанные моменты времени расположены достаточно часто, а точ- ность приближенного представления достаточно велика, то с точки

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

В настоящей работе рассматриваются только сообщения, созда- ваемые дискретными источниками, которые для краткости называ- ются дискретными сообщениями.

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

общения хранятся в записанном виде и выдаются по требованиям передающего (кодирующего) устройства. В источниках второго типа сообщения выдаются в некоторые моменты времени, опреде-

ляемые самим источником и не зависящие от работы передающего устройства.

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

мерами источника с фиксированной скоростью являются многие датчики в телеметрических системах, электронные вычислительные машины, человек, говорящий перед микрофоном, сцена, передавае- мая по телевидению, и т. д.

Часто между источником с фиксированной скоростью и переда- ющим устройством включается элемент буферной памяти. Если ем- кость буферной памяти беспредельно увеличивать, то условия пе- редачи сообщений приближаются к тем, которые имеют место при источниках с управляемой скоростью.

62

6.2. Преобразование сообщения в сигнал

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

В электрических каналах связи сигнал представляет собой ток в проводе либо напряженность электрического поля, в акустических каналах – звуковое давление и т. д. Отвлекаясь от физической сущ- ности сигнала, будем рассматривать множество сигналов как мно- жество Z некоторых функций z(t). Аргументом t обычно является время, и только этот случай будет здесь рассматриваться, хотя в бо- лее общей теории t может иметь и другой смысл (например, коор- динаты точки при записи сообщения на бумаге). Каждый сигнал этого множества определен на ограниченном отрезке аргумента t.

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

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

Таким образом, система преобразования сообщения в сигнал и

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

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

63

число элементов множества А очень невелико, такой словарный ме- тод преобразования оказывается пригодным.

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

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

Пример 1 . Пусть источник сообщения осуществляет измере- ния некоторой скалярной величины с точностью до ε. Приняв ε за единицу, можно изобразить каждый результат измерения целым числом. Это число может быть записано цифрами в десятичной или любой иной системе счисления. Тогда всякое сообщение, являюще- еся результатом одного измерения или последовательностью ре- зультатов нескольких измерений, можно расчленить на цифры вы- бранной системы счисления. Каждая цифра представляет при этом элементарное сообщение (или «букву»), так что множество X (при десятичной системе) может в этом примере содержать 10 элемен- тов. В некоторых случаях целесообразно включить в состав Х еще одно элементарное сообщение (разделительное), означающее, что данный результат измерения закончен, и начинается сообщение о другом результате.

Пример 2 . Пусть сообщения источника могут быть выражены словами и записаны на каком-либо языке. Тогда за элементарное сообщение можно принять букву алфавита данного языка (включив в него разделы между словами и знаки препинания). Можно было бы также принять за элементарное сообщение слово или фразу. Все эти методы расчленения приводят к конечному множеству X, одна- ко расчленение по словам или фразам практически неудобно, так как при этом X будет содержать очень большое число элементов.

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

64

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

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

Таким образом, каждое сообщение а из множества А может быть представлено в виде последовательности элементов х множества X:

a = (x (1), x (2),..., x (L) ).

(6.1)

Здесь L будем называть длиной данного сообщения а в алфавите X. Верхние индексы при обозначениях элементов сообщения указы- вают на порядковый номер данного элемента, а нижние – на его ме- сто в алфавите. Любой элемент х(k) в (6.1) может иметь значения x1,

x2, …,xl.

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

элементарных сообщений (6.1), в канал связи поочередно посыла- ются сигналы: z(1)(t), z(2)(t) … z(L)(t), где z(k)(t) – сигнал, соответству-

ющий элементу сообщения х(k).

Однако при большом объеме алфавита обычно прибегают еще к одному дополнительному преобразованию – кодированию, которое заключается в переходе от алфавита X, имеющего объем l, к ново- му алфавиту, представляющему множество символов Y = {y1, у2,

..., ..., уm}, имеющему объем m < 1. Правило преобразования эле- ментарных сообщений алфавита X в символы алфавита Y и наобо- рот называется кодом. Объем кодового алфавита обычно называют основанием кода.

65

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

ния на элементы каждое из элементарных сообщений представляет неделимый отрезок, несущий некоторую «смысловую нагрузку».

Метод расчленения обычно задается самим источником сообщения и, как уже отмечалось, осуществляется в самом источнике.

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

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

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

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

Контрольные вопросы

1.Сообщения, сигналы, каналы связи.

2.Преобразование сообщения в сигнал.

66

ГЛАВА 7 ОБЩИЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

7.1. Понятие алгоритма и его свойства

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

алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использо- вать для обозначения любой последовательности действий, приводя- щей к решению поставленной задачи [9, 10].

Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т. д.). Свойством, характеризующим любого исполнителя, является то, что он умеет выполнять некоторые ко- манды. Совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя. Алгоритм описывается в командах исполнителя, который будет его реализо- вывать. Объекты, над которыми исполнитель может совершать дей- ствия, образуют так называемую среду исполнителя. Исходные

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

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако в отличие от рецепта или процесса алгоритм характеризуется следующими свойствами: дис- кретностью, массовостью, определенностью, результативностью, формальностью.

67

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

Массовость – применимость алгоритма ко всем задачам рассмат- риваемого типа при любых исходных данных. Например, алгоритм

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

Определенность (детерминированность, точность) – свойство алго- ритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не должен допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку об Иване-царевиче? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, нале- во пойдешь – разбогатеешь». Стоит Иван и думает, что дальше де- лать». Таких инструкций алгоритм содержать не может.

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

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

7.2. Способы описания алгоритмов

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

Словесное описание представляет структуру алгоритма на есте- ственном языке. Например, любой прибор бытовой техники (утюг,

68

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

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

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

Строгих синтаксических правил для записи псевдокода не суще- ствует. Это облегчает запись алгоритма при проектировании и поз- воляет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, прису- щие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или фор- мального определения псевдокода не существует, поэтому возмож- ны различные псевдокоды, отличающиеся набором используемых слов и конструкций [9, 10].

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

Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем алгоритмов программ, регламентирован-

ные ГОСТ 19.701-90 (рис. 7.1).

Блок, характеризующий начало/конец алгоритма (для подпро- грамм – вызов/возврат).

Блок-процесс, предназначенный для описания отдельных действий.

69

Начало

Конец

<Действие>

Рис. 7.1. Основные конструкции, использующиеся для построения блок-схем

Блок – предопределенный процесс, предназначенный для обра- щения к вспомогательным алгоритмам (подпрограммам).

Блок ввода/вывода с неопределенного носителя или описания исходных данных.

Блок-решение (проверка условия или условный блок), представ- ленный на рис. 7.2.

Нет

Да

Рис. 7.2. Блок-решение

Блок – границы цикла, описывающий циклические процессы ти- па цикл с предусловием, цикл с постусловием (рис. 7.3).

<тело цикла>

Рис. 7.3. Блок – границы цикла

70