Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 31
Текст из файла (страница 31)
152 С помощью блок-схем можно, наоборот, несколько алгоритмов, рассматриваемых как блоки, связать в один большой алгоритм. В частности, если алгоритм Аь вычисляющий функцию Г1(х), соединен с алгоритмом Аз, вычисляющим функцию )~(х) (рис. 5.2), и при этом исходными конец данными для А, служит результат А„то полученная блоксхема задает алгоритм, вычисляющий )~()~(х)), т. е. композицию 1, и ~~ (см. э 1,2).
Такое соединение алгоритмов называется композицией алгоритмов. На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации. Описание — это граф; процесс реализации — это путь в графе. Различные пути в одном и том же графе возникают при различных данных, которые создают разные логические условия в точках разветвления. Отсутствие сходимости означает, что в процессе вычисления не появляется условий, ведущих к концу, н процесс идет по бесконечному пути (зацикливается).
При всей наглядности языка блок-схем не следует, однако, переоценивать его возможности. Он достаточно груб и отражает связи лишь по управлению (что делать в следующий момент, т. е. какому блоку передать управление), а не по информации (где этому блоку брать исходные данные). Например, рис. 5.2 при сделанной оговорке относительно данных изображает вычисление (з((1(х) ), однако он же мог изображать последовательное вычисление двух независимых функций )1(5) и (,(!00), порядок которых несуществен. Блок-схемы не содержат сведений ни о данных, ни о памяти, нн об используемом наборе элементарных шагов.
В частности, надо иметь в виду, что если в блок-схеме иет циклов, это еще не значит, что нет циклов в алгоритме (они могут быть в каком-нибудь неэлементарном блоке). По существу блок-схемы — это не язык, а средство, правда, очень удобное, для одной цели — описания детерминизма алгоритма. Оно будет неоднократно использоваться в дальнейшем с одним видоизменением: условия, т.
е. точки разветвления, могут быть не только двоичными, но и многозначными; важно лишь, чтобы верным был ровно один из возможных ответов. Примеры таких условий: а) х~0, х=0, х)0; б) х.С5, 5«-'х<20, х= =20, х<20. О подходах к уточнению понятия калгоритм», Ранее были сформулированы основные требования к алгоритмам. Однако понятия, использованные в этих формулировках (такпе, как ясность, четкость, элементарность), сами нуждаются в уточнении.
Очевидно, что их словесные определения будут содержать новые понятия, которые снова потребуют уточнения, и т, д. Поэтому в теории алгоритмов принимается другой подход: выбирается конечный набор исходных объектов, которые объявляются элементарными, и конечный набор способов построения из них новых объектов. Этот подход был уже использован при обсуждении вопроса о данных: уточнеяием понятия «данные» в дальнейшем будем считать множества слов в конечных алфавитах. Для уточнения детерминизма будут использоваться либо блок-схемы и эквивалентные им словесные описания (типа того, который приведен в примере 5.1), либо описание механизма реализации алгоритма.
Кроме того, нужно зафиксировать набор элементарных шагов и договориться об организации памяти. После того как это будет сделано, получится конкретная алгоритмическая модель. Алгоритмические модели, рассматриваемые в этой главе, претендуют на право считаться формализацией понятия «алгоритм». Это значит, что они должны быть универсальными, т. е. допускать описание любых алгоритмов. Поэтому может возникнуть естественное возражение против предлагаемого подхода: не приведет ли выбор конкретных средств к потере общности формализациий Если иметь в виду основные цели, стоявшие при создании теории алгоритмов,— универсальность и связанную с ней возможность говорить в рамках какой-либо модели о свойствах алгоритмов вообще, то это возражение снимается следующим образом.
Во-первых, доказывается своднмость одних моделей к другим, т. е. показывается, что всякий алгоритм, описанный средством одной модели, может быть описан средствами другой. Во-вторых, благодаря взаимной сводимости моделей в теории алгоритмов удалось выработать инвариантнук~ по отношению к моделям систему понятий, позволяющую говорить о свойствах алгоритмов независимо от того, какая формализация алгоритма выбрана. Эта система поня- 164 тий основана на понятии вычислимой функции, т.е.
функции, для вычисления которой сушествует алгоритм. Общее понятие вычислимости и его свойства будут более подробно рассмотрены в 5 5.4. Тем не менее, хотя общность формализации в конкретной модели не теряется, различный выбор исходных средств приводит к моделям разного вида. Можно выделить три основных типа универсальных алгорнтмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм. Первый тип связывает понятие алгоритма с наиболее традиционными понятиямн математики — вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа— рекурсивные функции — является исторически первой формализацией понятия алгоритма.
Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивныс операции. Такое представление не оставляет сомнений в однозначности алгоритма и элементарности его шагов. Кроме того, эври. стика этих моделей близка к ЭВМ н, следовательно, к инженерной интуиции. Основной теоретической моделью этого типа (созданной в ЗО-х годах — раньше ЗВМ1) является машина Тьюринга. Наконец, третий тип алгоритмических моделей — это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т. е. замены куска слова (подслова) другим словом. Преимущества этого типа — в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (не обязательно число. вой) природы, Впрочем, как будет ясно из дальнейшего, модели второго и третьего типа довольно близки (их взаимная сводимость доказывается просто) и отличаются в основном эвристическими акцентами.
Примеры моделей этого типа — канонические системы Поста и нормальные алгоритмы Маркова. Взи МАШИНЫ ТЬЮРИНГА Основные определения. Машина Тьюринга состоит из: 1) управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество Я=(дь ..., д ); 2) ленты, разбитой на ячейки, в каждой нз которых может быть записан один из символов конеч- 16$ ного алфавита А=(аь ..., а ); 3) устройства обращения к ленте, т. е. считывающей и пишущей головки, которая в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (быть может, совпадающий с прежним или пустой, т.
е. стирает символ), сдвигается на ячейку влево или вправо или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом). Среди состояний управляющего устройства выделены начальное состояние д~ и заключительное состояние, которое будем обозначать д, (г здесь понимается не как числовая переменная, а как мнемонический знак конца). В начальном состоянии машина находится перед началом работы; попав в заключительное состояние, машина останавливается. Таким образом, память машины Тьюринга — это конечное множество состояний (внутренняя память) и лента (внешняя память), Лента бесконечна в обе стороны, однако в начальный момент времени только конечное число ячеек ленты заполнено непустыми символами, остальные ячейки пусты, т.
е, содержат пустой символ Х .(пробел), Из характера работы машины следует, что и в любой по. следующий момент времени лишь конечный отрезок ленты будет заполнен символами. Поэтому важна не фактическая (как говорят в математике, актуальная) бесконечность ленты, а ее неограниченность, т. е. возможность писать на ней сколь угодно длинные, но конечные слова. Данные машины Тьюринга — это слова в алфавите ленты; на ленте записываются и исходные данные, и окончательные результаты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
