Файл: Основы теории алгоритмов учеб. пособие.pdf

Ц и - Ш 5 ' д

С о с т а в и т е л и :

доктор технических наук, профессор БЕРЕЗШ Н,Т. кандидат технических наук ФУРМАНОВ К.К.

- J -

ВВЕДЕНИЕ

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

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

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

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

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

- 4 -

Первое направление связано о изучением свойств алгорит­ мов гак объектов математической теории. Эта теория в первую очередь обязана фундаментальным работам А.А.Маркова, П.С.Нови­ кова, А.Тьюринга, А.И.Мальцева, Р.Петер, А.Н.Колмогорова, В.А.Успенского, С.Клини, А,Черча, К.Геделя.

*>В работах АД.Маркова [ з ] вводится понятие нормаль­ ных алгоритмов, которые являются универсальной алгоритмической системой. Здесь попользуется один тип элементарных операторов, называемых операторами подстановки, и один тип элементарных распознавателей, называемых распознавателями вхождения. Распознаватель вхождения задается указанием некоторого фикси­

- 5 -

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

Алгоритмической оиотемой, получившей достаточно полное развитие, является система, основанная на использовании конст­ руктивно определяемых арифметических (целочисленных) функций, получивших специальное название рекурсивных функций. Существен ный вклад в теорию рекурсивных функций внесли А.И.Колмогоров и В.А.Успенский [4 ,5 ] , Р.Петер [б ], С.Клини [ 7 ] , АЛерч (8-1 и]

К.Тед ель [ I I I .

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

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

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

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

Арифметические функции,которые могут быть построены vu элементарных арифметических функций, носят название частично рекурсивных функцай* Боли такие функции оказываются к то >•/

- 6 -

же всщ у определенными, то они называются общерекурсивными функциями.

Два следующих подхода к теории алгоритмов принадлежат

Э.Пооту и А.Тьюрингу.

Валгоритмической системе, предложенной Э.Постом

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

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

Доказано, что класс всех алгоритмов, эквивалентных ал­ горитмам Э.Поста, совпадает с классом всех нормализуемых ал­ горитмов.

Валгоритмической системе, предложенной А.Тьюрингом

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

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

Каждая ячейка информационной ленты служит для записи одной буквы. Эта буква может обозреваться специальным чувстви­ тельным элементом так называемой головки машины Тьюринга, спо­ собной перемещаться вдоль информационной ленты в обе стороны* Головка машины Тьюринга может находиться в конечном числе раз­ личных состояний , . . . , , печатать в обозреваемую ячейку любую букву la , 3CJL»**»»3Cm11 осуществлять сдвиг влево

- 7 -

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

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

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

теории алгоритмов, которая изучает свойства их, связанные с реализацией техническими системами.

Большой вклад в развитие этой теории внесли советские ученые А.А.Ляпунов, Н.А.Криницкий, Ю.И.Янов, А.П.Ершов, В.М. Глушков, M.F.Щура-Бура, Н.П.Бусленко, Б.З.Гнеденко, Д.А.Поспелов, В.В.Липаев, К.К.Колин, К),С.Голубев -Новожилов и многи». другие.

А.А.Ляпунов £1б] впервые ввел аппарат описания и нося*, допания алгоритмов на уровне групп операций (операторов). Схему алгоритма, составленную из арифметических операторов и логических условий, А.А.Ляпунов называл логической схемой п...

горитма.

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

за ним.

- 8 -

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

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

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

Логические схемы алгоритмов нашли широкое применение при программировании сложных математических задач о целью ре­ шения их на ЭЦВМ.

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

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

В работах Ю.й.Яяова [17,18] уже раскрывается внутренняя структура логических операторов (условий), считая остальные one-

- 9 -

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

В работах Н.А.Кршшцкого [19] исследуются схемы, со­ стоящие из операторов 3-х видов - действующих, логических и варьирующих. Для описания внутренней структуры нелогических операторов не было готового математичеокого аппарата, поэто­ му Н.А.Криницкому пришлось такой аппарат разработать. Ему уда­ лось получить сиотему эквивалентных преобразований комплексов, полную в том смысле, что с помощью конечного числа таких пре­ образований каждый из двух эквивалентных между собой комплек­ сов можно свести к другому. Получена обширная система равно­ сильных преобразований схем, содержащая в качестве своей час­ ти преобразования, изученные Ю.И.Яновым. Доказана полнота этой сиотемы равносильных преобразований для так называемых прямых и спрямленных схем,

А.П.Ершов [20,2l] исследует вопросы связи операторных алгоритмов с частично-рекурсивными функциями и нормальными ал­ горитмами, вопроон совместимости величин в памяти при програм­ мировании.

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

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

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

б ) существует'оператор, ни один путь из которого не дет к выходу, следовательно, если их этот оператор достигнет, то выполнение алгоритма никогда не закончится. Метод анализа алгоритмов, предложенный Р.М.Карпом, позволяет проверить, яв­ ляется ли блок-схема приемлемой. Подобные результаты получил