книги из ГПНТБ / Голембо, З. Б. Алгоритмизация и программирование электротехнических задач на электронных цифровых вычислительных машинах учеб. пособие

АЛ Г О Р И Т М И З А Ц И Я

ИП Р О Г Р А М М И Р О В А Н И Е S Э Л Е К Т Р О Т Е Х Н И Ч Е С К И Х

^З А Д А Ч

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

М О С К В А « В Ы С Ш А Я Ш К О Л А » 1 9 7 4

шинах. Учеб. пособие для вузов. М., «Высш. школа», 1974.

176с. с ил.

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

Ре ц е н з е н т ы :

1.Проф. Веников В. А.

2.Кафедра вычислительной техники Московского инженерноэкономического института.

3.Кафедра инженерной кибернетики Московского института ста­ ли и сплавов.

© Издательство «Высшая школа» 1974

П Р Е Д И С Л О В ИЕ

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

Настоящая книга является первой попыткой создания такого учебного пособия, которое в пепвую очередь предназначается для студентов специальностей «Кибернетика электрических систем», «Автоматика и телемеханика», «Автоматизированныесистемы управ­ ления», «Электронные вычислительные машины» и «Автоматиза­ ция, производство и распределение электрической энергии».

Формирование курса алгоритмизации и программирования элек­ тротехнических задач применительно к указанным специальностям связано с рядом особенностей, обусловленных высокими темпами развития ЭЦВМ, алгоритмических языков и самой алгоритмизацией возникающих здесь задач. Указанная специфика учитывалась авто­ ром при написании настоящей книги.

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

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

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

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

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

Автор

° § 1.1. Информация в кибернетике

а. Понятие информации

Спонятием информация ранее связывалось свойство челове­

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

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

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

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

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

4

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

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

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

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

Следовательно, применение теории информации к системам и процессам управления в том виде, в котором она используется в

го математически основные свойства передаваемых и принимаемых сообщений.

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

5

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

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

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

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

ции равно л. С учетом соотношения между Р и п выбираются лога­ рифмы с основанием 2, что дает / = log2 P.

Таким образом, при измерении информации возникает бинар­ ная система счета. Получающаяся единица количества информа­ ции, согласно английскому наименованию «Ыпагу digit», кратко обозначается словом «бит».

Принятая логарифмическая форма соотношения между величи­ нами I и Р должна удовлетворять условию

/ = / ( Р 1 Р 2 ) = / 1 + / 2 >

где I t = f(Pi) и / 2 = f2{P2) — информации, относящиеся к двум независимым задачам, имеющим соответственно Pi и Р2 возможных

6

ответа. Природа этих задач может быть или одинакова или различ­ на. Так, например, количество получаемой информации в случае бросания игрального кубика / = log2 6 = 2,6 бит; полная инфор­ мация, получаемая при трех последовательных бросаниях одного кубика (или при бросании трех кубиков), будет 3-2,6 = 7,8 бит, тогда как полная информация, получаемая при подбрасывании мо­ неты и извлечении одной карты из колоды в 32 карты, / 4 = log22 = = 1 бит; I 2 = log232 = 5 бит; Ii + / 2 = 6 бит.

§1.2. Кодирование цифровой информации

а.Передача кодированной информации

в Э Ц В М по каналам связи

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

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

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

В системах передачи информации в ЭЦВМ непосредственно по каналам связи используется простейший бинарный или двухбуквенный алфавит.

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

Информация для ЭЦВМ является преимущественно цифровым материалом, поэтому определение неправильно принятой информа­ ции не может быть осуществлено по смысловому признаку. Напри­ мер, для телеграфных систем связей высокого качества на 100 ООО

переданных знаков допускается не более трех ошибок. При этом до­ пускается не более одной ошибки, вносимой каждой из основных частей системы связи (передатчик, канал связи, приемник). При передаче цифровой информации ее достоверность должна быть по­ рядка 10"5 — 10~7 (одна ошибка на 100 ООО — 10 000 000 передан-

7

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

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

б. Представление цифровой информации в ЭЦВМ

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

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

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

Форма представления чисел с фиксированной запятой. При такой форме записи место запятой фиксировано постоянно для всех чисел — перед старшим разрядом. Это обеспечивает довольно огра­ ниченный диапазон (—1, +1). Числа же, используемые в научных вычислениях, не укладываются в единичный интервал (0, 1). По­ этому необходим выбор масштаба представления чисел. Задачу сна-

8

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

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

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

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

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

9