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

приближений, определяется, надо ли продолжать дальше вычис­ ления, или их надо прекратить.

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

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

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

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

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

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

12

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

б. Алгоритмическая неразрешимость некоторых массовых проблем

Интересен случай решения некоторым алгоритмом бесконеч­ ного класса однородных задач. При этом возникает массовая проб­ лема с определенной степенью трудности, решение которой состо­ ит в отыскании единого конструктивного метода, позволяющего решить любую из задач данного класса. Эту проблему можно рас­ сматривать как результат объединения многих единичных проблем. Алгоритмическая неразрешимость массовых проблем означает не­ возможность нахождения общего алгоритма для всех задач, при­ надлежащих к данному классу. Это, естественно, не означает, что для некоторой конкретной задачи из исследуемого класса нельзя найти частный алгоритм, дающий ее решение. В качестве конкрет­ ных примеров, имеющих отношение к построению электротехни­ ческих алгоритмов, можно указать на то, что общая проблема представимости матриц оказалась алгоритмически неразрешимой. Ее формулируют так: пусть некоторая матрица и представима че­ рез матрицы u l t u2 , u n , если для некоторой конечной последо­ вательности (вообще говоря, с повторениями) u n , u i 2 , u i n этих матриц их произведение совпадает с заданной исходной матрицей и. Проблема представимости состоит в том, чтобы найти общий конструктивный прием, с помощью которого за конечное число шагов для любой матрицы и и любой конечной системы S матриц можно было бы узнать, представима матрица и через матрицы сис­ темы S, или непредставима.

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

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

13

§ 2.1. Общие замечания о программировании

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

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

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

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

15

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

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

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

§2.2. Алгоритмические языки

итранслирующие системы

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

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

16