Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 30
Текст из файла (страница 30)
Вместо того чтобы пытаться дать общее словесное определение четкой определенности объекта, в теории алгоритмов фиксируют конкретные конечные наборы исходных объектов (называемых элементарными) и конечный набор средств построения других объектов из элементарных. Набор элементарных объектов образует конечный алфавит исходных символов (цифр, букв и т.
д.), из которых стро- . ятся другие объекты; типичным средством построения являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Простейшее индуктивное определение в это определение некоторого множества слов, классическим примером которого служит определение идентификатора в АЛГОЛе; идентификатор — это либо буква, либо идентификатор, к которому приписана справа буква илн цифра. Слова конечной длины в конечных алфавитах (в частности, числа) — наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) — естественная единица измерения объема обрабатываемой информации.
Более сложный случай алгоритмических объектов — формулы. Они также определяются индуктнвно и также являются словами в конечном алфавите, однако не каждое слово в этом алфавите является формулой. В этом случае обычно основным алгоритмам предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям. Такая проверка называется синтаксическим анализом (см. гл. 7). 2. Данные для своего размещения требуют памяти.
Память обычно считается однородной и дискретной, т. е. состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ алфавита данных. Таким образом, 14з единицы измерения объема данных и памяти согласованы. При этом память может быть бесконечной. Вопрос о том, нужна лн одна память илн несколько и, в частности, нужна лн отдельная память для каждого из трех видов данных (входных, выходных и промежуточных), решается поразному. 3. Алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно.
Типичный пример множества элементарных действий — система команд ЭВМ. Обычно элементарный шаг имеет дело с фиксированным числом символов (это удобно, например, для измерения времени работы алгоритма числом проделанных шагов), однако это требование не всегда выполняется. Например, в ЭВМ третьего поколения есть команды типа «память память», работающие с полями памяти переменной длины. 4.
Последовательность шагов алгоритма детерминирована, т. е. после каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной. 5. Естественно от алгоритма потребовать результативности, т. е. остановки после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления функции 1(х), обязан показать, что алгоритм останавливается после конечного числа шагов (как говорят, сходится) для любого х из области задания г. Однако проверить результа.
тивность (сходнмость) гораздо труднее, чем требования, изложенные в пп. 1 — 4. В отличие от инх сходимость обычно не удается установить простым просмотром описания алгоритма; общего же метода проверки сходимости, пригодного для любого алгоритма А и любых данных х, как будет показано далее, вообще не существует. Обсуждение трудностей, связанных с' распознаванием сходимости, см.
в 9 5.4. 6. Следует различать: а) описание алгоритма (инструкцию или программу); б) механизм реализации алгоритма (например, ЭВМ), включающий средства пуска, остановки, реализации элементарных шагов, выдачи результатов и обеспечения детерминированности, т.е. управления ходом вычисления; в) процесс реализации алгоритма, т. е. последовательность шагов, которая будет порождена при применении алгоритма к конкретным данным. 149 Будем предполагать, что описание алгоритма и механизм его реализации конечны (память, как уже говорилось, может быть бесконечной,ноона не-включается в механизм).
Требования к конечности процссса реализации совпадают с требованиями результативности (см. п, 5). Пример 5.1. Рассмотрим следующую задачу: дана последовательность Р из п положительных чисел (п — конечное, ио произвольное число); требуется упорядочить их, т, е. построить последовательность 1?, в которой эти же числа расположены в порядке возрастания.
Почти сразу же приходит в голову следующий простой способ ее решения: просматриваем Р и находим в ней наименьшсечисло; вы. черкиваем его из Р и выписываем его в качестве первого числа 1?; снова обращаемся к Р н находим в ней наименьшее число; приписываем его справа к полученной части )? н так далее, до тех пор, пока в Р не будут вычеркнуты все числа. Возникает естественный вопрос: что значит «и так далее». Для большей ясности перепишем описание способа решения в более четкой форме, разбив его на шаги и указав переходы между шагами. Ш а г 1. Ищем в Р наименьшее число. Ш а г 2.
Найденное число приписываем справа к 1? (в начальный момент )? пуста) и вычеркиваем его из Р. Шаг 3. Если в Р нет чисел, то переходим к шагу 4. В противном случае переходим к шагу 1. Ш а г 4. Конец. Результатом считать последовательность Й, построенную к данному моменту. Большинство читателей сочтет такое описание достаточно ясным (и даже излишне формальным), чтобы, пользуясь им, однозначно получить нужный результат. Однако это впечатление ясности опирается на некоторые неявные предположения, к правильности которых мы привыкли, но которые нетрудно нарушить.
Например, что значит «дана последовательность чисел»? Является ли таковой последо- 7 — Б вательностьт З,у'2, (1,2)"? Очевидно, да, однако в нашем описании ничего не сказано, как найти наименьшее число среди таких чисел. В нем вообще не говорится о том, как искать наименьшие числа, по-видимому, предполагается, что речь идет о числах, представленных в виде десятичных дробей, и что известно, как их сравнивать. Итак, необходимо уточнить формы представления данных.
При этом нельзя просто заявить, что допустимо лю- бое представление чисел. Ведь для каждого представления существует свой алфавит (который, помимо цифр, может включать запятые, скобки, знаки операций и функций и т. д.) и свой способ сравнения чисел (напрнмер, способ перевода в десятичную дробь), тогда как конечность алфавита требует фиксировать его заранее, а конечность описания алгоритма позволяет включить в него лишь заранеефиксированное число способов сравнения. Фиксация представления чисел в виде десятичных дробей также ие решает всех проблем. Сравнение 10 — 20-разрядных чисел уже не может считаться элементарным действием: сразу нельзя сказать, какое из чисел больше: 90811557001,15 или 32899901467,0048.
В машинных алгоритмах само представление числа еще требует дальнейшего уточнения: нужно, во-первых, ограничить число разрядов (цифр) в числе, так как от этого зависит, сколько ячеек памяти будет занимать число, а во-вторых, договориться о способе размещения десятичной запятой в числе, т. е. выбрать представление в виде числа с фнкснровайной- или плавающей запятой, поскольку способы обработки этих двух представлений различны. Наконец, любой, кто имел дело с программированием, отметит, что на шаге 1 требуется узнать две вещи: само наименьшее число (чтобы записать его в Я) и его место в Р, т.
е. его адрес в той части памяти, где хранится Р (чтобы вычеркнуть его из Р), а следовательно нужно иметь средства указания этого адреса. Таким образом, даже в этом простом примере несложный анализ показывает, что описанию, которое выглядит вполне ясным, еше далеко до алгоритма. Мы столкнулись здесь с необходимостью уточнить почти все основные характеристики алгоритма, которые отмечались ранее: алфавит данных и форму их представления, память и размещение в ней элементов Р н Я, элементарные шаги (поскольку шаг 1 явно неэлементарен)., Кроме того, становится ясным, что выбор механизма реализации (скажем, человека или ЭВМ) будет влиять и на сам характер уточнения: у человека требования к памяти, представлению данных и к элементарности шагов гораздо более слабые и «укрупненные», отдельные незначительные детали он может уточнить сам.
Пожалуй, только два требования к алгоритмам в приведенном описании выполнены в достаточной мере (они-то н создают впечатление ясности). Довольно очевидна сходимасть алгоритма: после выполнения шагов 1 и 2 либо работа заканчивается, либо нз Р вычеркивается одно число; поэтому ровно после и выполнений шагов 1 и 2 из Р будут вычеркнуты все числа и алгоритм остановится, а )г будет результатом. Кроме того, не вызывает сомнения детерминированность: после каждого шага ясно, что делать дальше, если учесть, что здесь и в дальнейшем используется общепринятое соглашение — если шаг не содержит указаний о дальнейшем переходе, то выполняем шаг, следующий за ним в описании. Поскольку использованные в примере средства обеспечения детерминированности носят довольно общий характер, остановимся на них несколько под.
робнее, Блок-схемы алгоритмов, Связи между шагами можно изобразить в виде графа, Для примера 5.1 граф нзобрз. жен на рпс. 5.1. рис. 5.1 Такой граф, в котором вершинам соответствуют шаги, а ребрам — переходы между шагами, называется блоксхемой алгоритма. Его вершины могут быть двух видов: вершины, из которых выходит одно ребро (их называюг операторами), и вершины, из которых выходят два ребра (их называют логическими условиями, или предикатами). Кроме того, имеется единственный оператор конца, из которого не выходит ни одного ребра, и единственный оператор начала.
Важной особенностью блок-схемы является то, что связи, которые она описывает, не зависят от того, являются ли шаги элементарными или представляют собой самостоятельные алгоритмы,— как говорят в программировании, блоки (по существу шаг 1 таковым и является). Возможность «разблочивать» алгоритм хорошо известна в программировании и широко там используется: большой алгоритм разбивается на блоки, которые можно раздать для программирования разным лицам. Для данного блока неважно, как устроены другие блоки; для программирования блока достаточно знать, где лежит вся исходная информация, какова форма ее представления, что должен делать блок и куда записать результат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
