1.4. Алгоритмы

Понятие алгоритма

Многие процессы в ИС реализуются через программы ЭВМ. Про­грамма - это некоторая инструкция. Она составляется на специальном языке, понятном для ЭВМ, и состоит из ряда типовых выражений - команд. Программа вводится в память ЭВМ. Если запустить программу, то ЭВМ начнет выполнять действия в соответствии с ее командами. Современные ЭВМ могут выполнять сотни разных типов команд. Каждая команда определяет некоторое действие машины. Например, с помощью соответствующей команды в некоторую ячей­ку памяти ЭВМ можно поместить число 100, другой командой можно вывести содержимое этой ячейки на экран монитора и т.п.

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

Алгоритм (от латинского algorithmi, algorismus - первоначально транслитерация имени узбекского математика аль-Хорезми) - способ (программа) решения вычислительных и других задач, точно предписывающий последова­тельность получения результата, однозначно определяемый исходными дан­ными [11].

В технической литературе можно найти другие, но близкие по сути опреде­ления этого понятия. Так, в международном стандарте ISO 2382/1-84 приводится следующее определение: «Алгоритм - конечный набор предписаний, опре­деляющий решение задачи посредством конечного количества операций».

Мухаммед ибн Муса аль-Хорезми, живший в 783-850 гг., предложил пра­вила четырех арифметических действий над числами в десятичной системе счисления, которые опубликовал в своей книге «Об индийском счете», пере­веденной в XII в. на латынь и получившей широкое распространение в Евро­пе. Совокупность введенных аль-Хорезми правил стали называть «алгоризм», а впоследствии - «алгоритм». Сегодня существует и широко изучается теория алгоритмов.

В Большой российской энциклопедии указывается, что содержательные явления, приведшие к образованию понятия «алгоритм», прослеживаются в математике в течение всего времени ее существования. Однако само это поня­тие сформировалось лишь в XX в. и стало предметом самостоятельного изуче­ния лишь в 20-х гг. XX в. представителями математического интуиционизма Л.Э.Я. Брауэром и Г. Вейлем. Началом разработки теории алгоритмов можно считать 1936 г., когда А. Черч опубликовал первое уточнение понятия вычисли­мой функции (предложил отождествлять понятие всюду определенной вычис­лимой функции, имеющей натуральные аргументы и значения, с понятием

47

общерекурсивной функции) и привел первый пример функции, не являющей­ся вычислимой, a A.M. Тьюринг и Э.Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин Тьюрин­га и Поста). В дальнейшем теория алгоритмов получила развитие в трудах С.К. Клини, Э.Л. Поста, А.А. Маркова и др. В частности, А.А. Марков предло­жил уточнить понятие алгоритма с помощью введенного им понятия нормаль­ного алгоритма. Наиболее общий подход к уточнению понятия алгоритма пред­ложил А.Н. Колмогоров.

При составлении алгоритма необходимо описать:

- набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;

- правило начала;

- правило непосредственной переработки информации (описание последовательности действий);

• правило окончания;

• правило (форму) вывода результата для потребителя информации.

Разработке алгоритма предшествуют постановка задачи и построение формальной модели задачи. Обычно модель представляет собой некоторую систему условий, уравнений, неравенств. Далее эта модель является основой для постро­ения алгоритма.

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

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

Например, алгоритм вычисления суммы таможенной пошлины Т_п = N х С_е х х К_с/К_вк при обложении товара по специфическим ставкам (N - количество товара, С_е - ставка таможенной пошлины в евро за единицу товара, К, - курс евро к рублю, К_пк - курс валюты контракта к рублю) в словесно-формульном виде можно описать следующим образом:

1) ввести значения N, С , К , К ;

/ ' е' с^т вк'

2. вычислить произведение а = N х С х К_е;

3. вычислить Т = а / К ;

4. вывести на печать значение Т .

' п

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

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

В системе Государственных стандартов (ГОСТ) имеется особая группа стан­дартов, которые оформлены в виде единой системы программной документа-

48

ции (ЕСПД). Комплекс стандартов ЕСПД устанавливает правила разработки, оформления программ и программной документации. Правила оформления схем алгоритмов, программ, данных и систем устанавливаются, в частности, ГОСТ 19.701-90, который был разработан методом прямого применения между­народного стандарта ISO 5807-85 [21].

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

В стандарте ГОСТ 19.701-90 определены символы (табл. 1.2), предназначен­ные для использования в блок-схемах, и приведено руководство по условным обозначениям для их применения в схемах:

• данных;

• программ;

• работы системы;

• взаимодействия программ;

• ресурсов системы.

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

Линии показывают направления потоков данных или потоков управления. Стандартными считаются направления слева направо либо сверху вниз. Если потоки имеют направления, отличные от стандартных, то для указания направ­ления используют линии-стрелки.

Две или более входящих линии могут объединяться в одну исходящую линию. Однако при этом место объединения должно быть смещено (рис. 1.14 а).

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

Возможно использование идентификатора символа, который проставляется слева над ним (рис. 1.14 б).

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

Каждый выход из символа «решение» должен сопровождаться соответству­ющими значениями условий (рис. 1.14 г).

49

50

51

Примечание: знак «+» указывает, что символ используют в данной схеме, «-» - не используют.

52

Символ «предопределенный процесс» применяется для отображения про­цесса из одной или нескольких операций или шагов программы, которые опре­делены в другом месте схемы.

Символ «параллельные действия» используется для указания необходимости синхронного исполнения нескольких операций. На рис. 1.15 этот символ использу- ется для того, чтобы показать, что операции С, D и Е начинают выполняться одно- временно, а операции В, С и D.

одновременно завершаются.

Схемы данных отображают путь данных при решении задач и определяют этапы обработки, а также различные применяе­мые носители этих данных.

Схема данных состоит из символов:

• данных (символы дан­ных могут также указывать вид носителя данных);

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

• линий, указывающих потоки данных между процессами и (или) носителя­ми данных;

- специальных, используемых для облегчения написания и чтения схемы. Символы данных предшествуют и следуют за символами процесса. Схема

данных начинается и заканчивается символами данных (за исключением специ­альных символов).

53

Схемы программ отображают последовательность операций в программе. Схема программы состоит из:

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

• символов линейных, указывающих поток управления;

• символов специальных, используемых для облегчения написания и чтения схемы.

Схемы работы системы отображают управление операциямии и поток дан­ных в системе.

Схема работы системы состоит из:

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

• символов процесса, указывающих операции, которые следует выпол­нить над данными, а также определяющих логический путь, которого следует придерживаться;

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

• специальных символов, используемых для облегчения написания и чтения блок-схемы.

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

Схема взаимодействия программ состоит из:

• символов данных, указывающих на наличие данных;

• символов процесса, указывающих на операции, которые следует выпол­нить над данными;

• линейных символов, отображающих поток между процессами и данными, а также инициации процессов;

• специальных символов, используемых для облегчения написания и чтения схемы.

Схемы ресурсов системы отображают конфигурацию блоков данных и обра­батывающих блоков, которая требуется для решения задачи или набора задач. Схема ресурсов системы состоит из:

• символов данных, отображающих входные, выходные и запоминающие устройства вычислительной машины;

• символов процесса, отображающих процессоры (центральные процессоры, каналы и т.д.);

• линейных символов, отображающих передачу данных между устройст­вами ввода-вывода и процессорами, а также передачу управления между процессорами;

• специальных символов, используемых для облегчения написания и чтения схемы.

54

Выделяют линейные, ветвящиеся и циклические блок-схемы:

• линейные описывают процессы, в которых операции выполняются после­довательно без разветвлений;

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

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

На рис. 1.16 приведена схема алгоритма расче­та таможенной пошлины по рассмотренной ранее формуле Т. Для этого примера блок-схема является линейной.

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

Блок-схема с вложенным циклом приведена на рис. 1.17. Она описывает алгоритм вычисления сум­мы элементов матрицы размером 4x3. После ввода значений элементов матрицы производится процеду­ра инициализации, в ходе которой устанавливаются начальные значения переменных и индексов циклов (R, i, j). Внешний цикл (индекс j) обеспечивает пос­ледовательный выбор строк матрицы. Внутренний цикл (индекс i) позволяет организовать суммирова­ние элементов очередной строки. Результат суммиро­вания накапливается в переменной R. Условие j > 4 является условием завершения алгоритма.

Некоторые особенности появляются при состав­лении блок-схем, реализующих параллельные вычисления. Обычная ЭВМ выполняет операции

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

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

55

неоднозначного толкования. Язык описания алгоритма для его последующего ввода в ЭВМ принято называть языком программирования или алгоритмичес­ким языком, а запись алгоритма на этом языке - программой для компьютера. «Программа для ЭВМ - упорядоченная последовательность команд, подле­жащая обработке» (стандарт ISO 2382/1-84).

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

В настоящее время в мире существует несколько сотен реально используе­мых языков программирования. Для каждого есть своя область применения.

56

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

• машинные;

• машинно-ориентированные (ассемблеры);

• машинно-независимые (языки высокого уровня).

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

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

Примем, что код 01 задает команду (действие) сложения двух чисел. Пусть слагаемые размещаются в ячейках с адресами 2048 и 4092, а результат надо занес­ти в ячейку с адресом 4096. Тогда команду сложения в машинном коде можно, например, представить в виде: 01 2048 4092 4096.

Типы команд, структура машинной команды и двоичные коды их обозначе­ний зависят от используемой ЭВМ. Программа, записанная на машинном языке, представляет собой последовательность описаний команд.

Язык Ассемблера - это машинно-зависимый язык низкого уровня, в кото­ром короткие мнемонические имена соответствуют отдельным машинным командам. Используется для представления в удобочитаемой форме программ, записанных в машинном коде [2].

Так, основной формат записи команд на языке Ассемблера для IBM PC име­ет вид (рис. 1.18):

[метка] команда [операнд (ы)] комментарий.

В примере на рис. 1.18 в качестве имени программы указано PRIMER; под переменную с именем РАМ1 отведено 2 байта (на это указывает операнд DW), в которые занесено шестнадцатеричное число 100 (Н - указатель 16-рич-ной системы счисления); BEGIN - метка, определяющая место начала описания процедуры FINE.

Языки высокого уровня имитируют естественные языки, используя некото­рые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека. Языки высокого уровня были разработаны для того, чтобы освободить программиста от учета технических особенностей конкретных компьютеров, их архитектуры. Однако программы на ассемблере, как правило, более быстрые и требуют меньшей памяти для работы.

57

Языки высокого уровня подразделяются на:

процедурные (алгоритмические) (Basic, Pascal, С и др.), которые предна­значены для однозначного описания алгоритмов, при этом для решения зада­чи процедурные языки требуют в той или иной форме записать процедуру ее решения;

логические (Prolog, Lisp и др.), которые ориентированы не на точное изло­жение алгоритма решения задачи, а на систематическое и формализованное опи­сание задачи с тем, чтобы решение следовало из составленного описания;

объектно-ориентированные (Object Pascal, С++, Java и др.), в основе кото­рых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действи­тельности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

На рисунке 1.19 приведено описание на алгоритмическом языке высоко­го уровня ПАСКАЛЬ алгоритма ввода двух чисел г и Ь, а также определения и печати максимального значения. Справа от текста даны комментарии, поясня­ющие действия ЭВМ при выполнении соответствующей строки программы.

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

а,х + Ь,у - с, а₂х + Ь₂у = с₂

58

всех задач данного типа (т.е. при любых коэффициентах а,, Ь,, с,, а₂, Ь₂, с₂).

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

Уже в рассмотренных примерах довольно отчетливо выступают следующие черты алгоритмов, присущие и любому другому алгоритму [29, 35, 67].

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

Иными словами, при наличии алгоритма в процессе решения некоторой задачи не надо думать и следует делать только то, что указано в алгоритме.

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

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

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

Оценка эффективности алгоритмов

Для решения одной и той же задачи можно разработать несколько разных алгоритмов. Поэтому возникает проблема выбора наиболее эффектив­ных алгоритмов. Заметим, что точная оценка эффективности алгоритмов -достаточно сложная задача и в каждом конкретном случае требует проведения специального исследования [4, 30].

Ту часть теории алгоритмов, которая занимается оценкой их характеристик, называют метрической, она, в свою очередь, делится на качественную и коли­чественную [78]. Первая исследует алгоритмы на степень соответствия между исходными данными и результатами. Вторая оценивает сложность как самих алгоритмов, так и задаваемых ими «вычислений», т.е. процессов последователь­ного преобразования конструктивных объектов. Важно подчеркнуть, что слож­ность алгоритмов и вычислений может определяться различными способами, причем может оказаться, что при одном способе алгоритм А будет сложнее В, а при другом способе - наоборот.

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

60

(пропорциональной log п), квадратичной (пропорциональной п²) и т.д. Сравни­вая асимптотические оценки алгоритмов, решающих одну и ту же задачу, мож­но выбрать наболее эффективный алгоритм. Считают, что значение некоторого параметра Т(п) имеет порядок п^х, если существуют такие положительные кон­станты к и п_о, что для всех п>п_о выполняется неравенство

Предположим, что п - количество числовых данных, поступающих на вход нескольких разных алгоритмов (А,, А₂, А₃, А₄, А.), которые производят вычис­ления с одинаковой скоростью - 1000 операций в секунду, но имеют разные асимптотические оценки. В таблице 1.3 показаны значения п, которые могут обработать эти алгоритмы за 1 секунду, 1 минуту и 1 час (значения округлены в меньшую сторону до целого числа). Данные этой таблицы наглядно показывают, что производительность алгоритма (число данных, обрабатываемых в единицу времени) существенно зависит от характера функции асимптотической оценки.

Тестирование разработанных алгоритмов обычно проводится при небольших значениях параметра п, что позволяет получить уверенность в работоспособнос­ти алгоритма, но вовсе не гарантирует выполнение задачи при больших значе­ниях п. Причиной этого может быть отсутствие необходимого объема памяти ЭВМ или времени для решения поставленной задачи. Асимптотические оценки важны в том смысле, что позволяют оценить достаточность ресурсов ЭВМ для практических вычислений при известных пределах изменения параметра п.

Пусть алгоритм осуществляет последовательное сложение п чисел. Очевид­но, для него асимптотическая оценка числа сложений будет линейной функци­ей. Теперь предположим, что программа осуществляет попарное перемножение из п чисел и затем их сложение. Поскольку число возможных пар произведений равно п(п-1)/2, то нужно выполнить п(п-1)/2 операций умножения и на одну меньше операций сложения. Тогда общее число операций сложения и умно­жения можно оценить выражением T(n)=n²/2+n/2+n²/2+n/2-l=n²+n-l<2n². Следовательно, в данном случае асимптотическая оценка числа сложений и умножений имеет порядок п².

Таблица 1.3

61

Число обрабатываемых данных при разных функциях асимптотической оценки

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

Оценка требуемой памяти. Обычно ее объем представляют в виде суммы четырех компонент:

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

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

Оценка времени решения. Прямой способ подсчета времени решения зада­чи вычисляется по формуле

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

Время выполнения существенно зависит от метода решения, заложенного в алгоритме; может зависеть от значений входных данных. Так, если алгоритм производит вычисление по формуле N - ac+ad+bc+bd, то требуется выполнить четыре операции умножения и три операции сложения. Однако вычисления можно проводить и по другой формуле: N - (a+b)(c+d). Тогда потребуется толь­ко две операции сложения и одна умножения.

62

Кроме того, нужно иметь в виду, что в многопроцессорных вычислительных системах и даже в обычных ЭВМ одновременно могут выполняться сразу несколь­ко операций, что также следует учитывать при оценке времени вычислений.

Асимптотические оценки очень часто применяют именно для оценки вре­менных характеристик алгоритмов.

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

При оценке точности вычислений обычно учитывают:

- погрешность преобразований аналоговых сигналов в цифровые (при вводе в ЭВМ данных, представленных в аналоговой форме);

• погрешности из-за выбранного метода решения задачи;

• ошибки, возникающие из-за округлений и переполнения.

Приведем несколько примеров, иллюстрирующих причины неточностей при вычислениях.

Пусть ЭВМ работает со словами длиной в один байт и целыми числами с фиксированной точкой со знаком. Вычислим сумму 64 + 65: число 64: 01000000, число 65: 01000001, сумма: 10000001.

Напомним, что левый крайний разряд отведен для задания знака числа (0 - положительное, 1 - отрицательное число). При суммировании заданных положительных чисел произошел перенос единицы в знаковый (старший) раз­ряд байта. В результате вместо правильного значения «+129» в байте оказалось отрицательное число «—127».

Вычислим сумму (128+129) в предположении, что байт хранит целые числа с фиксированной точкой без знака:

число 128: 10000000,

число 129: 10000001,

сумма: 00000001.

В данном примере правильный результат суммирования 257. Однако байт может хранить числа только в интервале 0-255. Поэтому за счет переполнения ячейки получено неправильное значение 1.

Если ЭВМ работает с числами с плавающей точкой, то ячейке памяти может не хватить места для хранения всех разрядов мантиссы или порядка. Напри­мер, результат деления 10:3 - бесконечная дробь, а мантисса всегда имеет огра­ниченное число разрядов. Фактически тогда в ячейку помещается округление действительного значения до количества знаков после запятой, определяемых выбранным форматом задания чисел с плавающей точкой.

63

Кроме того, надо иметь в виду, что при некоторых сочетаниях данных или возникновении сбоев в аппаратной части ЭВМ возможны прерывания работы ЭВМ, которые приводят к непредсказуемым последствиям. В частности, преры­вание может возникать при делении на «О».

Контрольные вопросы и задания

1. В каком федеральном законе дается определение понятия «информация»?

2. Какая статья Таможенного кодекса РФ разъясняет отношение к информа­ции, получаемой таможенными органами?

3. В чем различие аналоговой и дискретной форм сигнала?

4. К какой форме относятся цифровые сигналы?

5. Сколько бит необходимо для кодирования дискретного сигнала, имеющего шесть возможных уровней?

6. Что такое избыточность информации, в чем ее полезность?

7. В чем сущность тезаурусной оценки количества информации?

8. Формула Хартли для оценки количества информации.

9. Что такое энтропия по Шеннону?

10. Формула Шеннона для оценки количества информации с учетом вероятнос­тей сообщений.

11. Понятие информационной технологии. В чем ее отличие от технологий в материальном производстве?

12. Понятие системы. Основные свойства системы.

13. Понятие информационной системы, ее основные компоненты.

14. Подсистемы автоматизированной системы.

15. Как оценивается экономическая эффективность системы?

16. Понятие надежности. Показатели надежности.

17. Что такое информационная безопасность?

18. Основные элементы сети связи.

19. В чем различие режимов симплексной, дуплексной и полудуплексной связи?

64

20. Как устроена общегосударственная коммутируемая сеть связи?

21. Система нумерации в телефонной сети.

22. Принципы построения сотовой связи.

23. Каким образом в системе сотовой связи обеспечивается связь с движущимся абонентом?

24. Принцип построения и особенности транкинговой связи.

25. Что такое полоса пропускания линии связи?

26. Что такое затухание в линии связи? От чего оно зависит?

27. Если передаются двухсимвольные сообщения из букв алфавита, содержаще­го 12 букв, каков максимальный объем информации, передаваемой с одним сообщением при равновероятности всех сообщений?

28. Можно ли передать с одним сообщением 6 и более бит информации, если объект имеет 32 возможных состояния? Минимальное число состояний, при котором сообщение принесет 6 бит информации?

29. Допустим, что максимальная энтропия сообщения Н = 6 бит, а в секунду по линии связи передается 100 ООО сообщений. Чему равна пропускная спо­собность линии?

30. Для обеспечения хорошего качества телефонного разговора по линии связи должны передаваться сигналы в диапазоне 300-3400 Гц. Какую полосу про­пускания должна обеспечивать линия связи?

31. Пусть каждый сигнал модема несет 4 бита информации. Если полоса про­пускания линии связи 4 кГц, то чему равна пропускная способность линии?

32. Какой полосой пропускания должна обладать линия связи, чтобы модем, каждый сигнал которого несет 6 бит информации, мог вести передачу со ско­ростью 33,6 Кбит/сек.

33. Что такое алгоритм? Какая необходима информация для составления алгоритма?

34. Какими свойствами должен обладать алгоритм?

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

36. Разработайте алгоритм определения максимального числа в списке из деся­ти чисел и изобразите его в виде блок-схемы.

37. Какие виды схем при описании алгоритмов выделяет ГОСТ 19.701-90?

38. Основные критерии оценки алгоритмов.

39. В чем сущность асимптотической оценки алгоритмов?

65