Учебник_Информатика. Стандарт третьего поколениян. В. Макарова, В. Б. Волков
 Скачать 14.49 Mb.
|
|
Описание инструкции Условное обозначение инструкции 1 Пометить ячейку, если она пуста, и перейти к инструкции j 1 Mj 2 Стереть метку, если она есть, и перейти к инструкции j 1 С) 3 Переместиться влево на 1 ячейку и перейти к инструкции j 1 <-j 4 Переместиться вправо на 1 ячейку и перейти к инструкции j 1 -+j 5 Определить, помечена ячейка или нет. Если ячейка пуста, перейти на инструкцию j u если помечена — на инструкцию j2 / г. - и 6 Остановиться i. стоп Программа представляет собой нумерованную последовательность инструкций, причем в инструкции 5 переходы производятся на указанные в ней номера других инструкций. Программа, или набор инструкций, в терминах Э. Поста, является од ной и той же для всех конкретных задач, поэтому соотнесена с общей постановкой задачи. Таким образом, Пост формулирует требование универсальности алгоритма. Далее Э. Пост вводит следующие понятия: □ набор инструкций применим к общей проблеме, если для каждой конкретной проблемы не возникает коллизий в инструкциях 1 и 2, то есть программа никогда не стирает метку в пустой ячейке и не устанавливает метку в помеченной ячейке; □ набор инструкций заканчивается, если после конечного количества инструкций выполняется инструкция 6. 14.1. Представление об алгоритмах 395 Начальное состояние машины Поста полностью определяется двумя факторами: положением каретки (на какой из ячеек она находится) и состоянием ленты (на личием на ленте помеченных ячеек). В зависимости от начального состояния машины Поста могут быть три варианта выполнения одной и той же программы: 1. В ходе выполнения программы машина доходит до невыполнимой инструкции (печатания метки в непустой ячейке или стирания метки в пустой ячейке). Про исходит безрезультатная остановка машины. 2. В ходе выполнения программы машина доходит до инструкции Стоп. Проис ходит результативная остановка. 3. Работа машины продолжается бесконечно. Машина Поста оперирует натуральными числами, которые представляются в непозиционной системе счисления (то есть 0 обозначается одной помеченной ячейкой, 1 — двумя идущими подряд помеченными ячейками, и т. д.). В общей фор ме натуральное число п представляется п + 1 смежными помеченными ячейками. Пример. Рассмотрим следующую программу для машины Поста: / - > 4 2.СЗ 3. стоп 4. -> 2 Зададим такое начальное состояние машины, которое показано на рис. 14.2. V Рис. 14.2. Начальное состояние машины Поста Поскольку каретка находится на пустой ячейке, первая команда программы вы зывает переход на команду с номером 4. При этом каретка не меняет своего по ложения, и состояние ленты также не меняется (метка не ставится и не стирается). Команда с номером 4 вызывает перемещение каретки на одну позицию вправо (те перь каретка находится на помеченной ячейке) и передачу управления команде 2. Команда 2 стирает метку в текущей ячейке и передает управление команде 3. Команда 3 останавливает работу машины. 14.1.3. Формализация понятия алгоритма посредством машины Тьюринга Алан Тьюринг в 1936 г. опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешения», 396 Глава 14. Основы теории алгоритмов которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов. Предыстория появления этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 г. нерешенных математических проблем. Одной из них была задача дока зательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как «проблему разрешимости» — нахождение общего метода для определения выполнимости данного высказывания на языке формальной логики. Статья Тьюринга как раз и давала ответ на эту задачу, но значение статьи Тью ринга выходило далеко за ее рамки. Вот как охарактеризовал эту работу Джон Хопкрофт (известный американский ученый в области теории вычислительных систем): «Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представ ления о методе как о некоем алгоритме, то есть процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последователь ность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга». Машина Тьюринга является расширением модели конечного автомата, вклю чающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу. То есть «конструктивно» машина Тьюринга, так же как и машина Поста, состоит из двух основных узлов: ленты с ячейками и каретки. Решаемая проблема задается путем записи на ленту конечного количества сим волов 5,-, образующих слово в алфавите S, где е — это специальный пустой символ, показывающий отсутствие любого символа алфавита S в ячейке (рис. 14.3). е S1 S2 S3 S4 Sn е Рис. 14.3. Машина Тьюринга В отличие от машины Поста, в машине Тьюринга каретка неподвижна, а лента проматывается лентопротяжным механизмом на одну ячейку вправо или влево. Состояния машины Тьюринга обозначаются как q{ и принадлежат множеству состо яний Q. Управляется машина при помощи функции переходов, которая называется программой машины Тьюринга и может быть задана в виде таблицы или ориен тированного графа. При этом при задании функции переходов используются как команды лентопротяжному механизму (смещение ленты на одну ячейку вправо, смещение ленты на одну ячейку влево, перемотка в начало, останов), так и команды каретки (запись нового символа, чтение символа, запись пустого символа). После задания проблемы машина переводится в начальное состояние (обозначаемое как #о), и лента проматывается так, чтобы каретка находилась у самого левого непу стого символа, после чего в соответствии с указанной функцией переходов машина начинает заменять обозреваемые символы, передвигать каретку вправо или влево 14.1. Представление об алгоритмах 397 и переходить в другйе состояния (путем стирания текущего символа и замены его новым). Останов машины происходит в том случае, если для пары «состояние машины — символ в текущей ячейке» (qb Sj) функция перехода не определена или получена команда останова. Тьюринг высказал предположение, что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной в предложенной им модели вычислений. Это предположение известно как тезис Черча—Тьюринга. Каждый компьютер может моделировать машину Тьюринга, для этого достаточно моделировать операции перезаписи ячеек, сравнения и перехода к другой соседней ячейке с учетом изменения состояния машины. Значит, он может моделировать алгоритмы в машине Тьюринга, и из этого тезиса следует, что все компьютеры, независимо от мощности, архитектуры и других особенностей, с точки зрения принципиальной возможности решения алгоритмически разрешимых задач эк вивалентны. 14.1.4. Современная теория алгоритмов Начальной точкой отсчета современной теории алгоритмов можно считать теорему о неполноте символических логик, доказанную немецким математиком Куртом Геделем в 1931 г. В этой работе было показано, что некоторые математиче ские проблемы не могут быть решены алгоритмами определенного класса. Общность результата Геделя связана с вопросом о том, совпадает ли использо ванный им класс алгоритмов с классом всех алгоритмов в интуитивном понимании этого термина. Эта работа дала толчок к поиску и анализу различных формализа ций понятия «алгоритм». Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930-х гг. Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс рекурсивно-вы- числимых функций Черча были первыми формальными описаниями алгоритма, опирающимися на строго определенные модели вычислений. Сформулированные гипотезы Поста и Черча—Тьюринга постулировали эквивалентность предложен ных ими моделей вычислений, как формальных систем, и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство существования алгоритмически неразрешимых проблем. В 1950-х гг. существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и основанный на теории формальных грамматик алгоритмический формализм Маркова — так называемые нормальные алгоритмы Маркова. Формаль ные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой. Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели в 1960—1970-х гг. к практически значимым исследованиям алгоритмов и вычислительных задач. На этой основе впоследствии выделилось несколько разделов теории алгоритмов (рис. 14.4). 398 Глава 14. Основы теории алгоритмов Рис. 14.4. Разделы современной теории алгоритмов Классическая теория алгоритмов: формулировка задач в терминах формальных языков; понятие задачи разрешения; описание сложностных классов задач; фор мулировка в 1965 г. Эдмондсом проблемы Р = NP; открытие класса TV P-полных задач и его исследование; введение новых моделей вычислений — алгебраического дерева вычислений (Бен-Op), машины с произвольным доступом к памяти, схем алгоритмов Янова, стандартных схем программ Котова и др. Теория асимптотического анализа алгоритмов: понятие сложности и трудоем кости алгоритма; критерии оценки алгоритмов; методы получения асимптотиче ских оценок, в частности, для рекурсивных алгоритмов; асимптотический анализ трудоемкости или времени выполнения; получение теоретических нижних оценок сложности задач. В развитие этой теории внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп, Мошков, Кудрявцев и др. Теория практического анализа вычислительных алгоритмов: получение явных функций трудоемкости; интервальный анализ функций; практически значимые критерии качества алгоритмов; методики выбора рациональных алгоритмов. Ос новополагающей работой в этом направлении, очевидно, следует считать фунда ментальный труд Д. Кнута «Искусство программирования для ЭВМ». Методы создания эффективных алгоритмов включают в себя множество алго ритмов, среди которых динамическое программирование, метод ветвей и границ, метод декомпозиции, «жадные» алгоритмы, специальные структуры данных и пр. Обобщая исследования в различных разделах теории алгоритмов, можно вы делить следующие основные задачи и направления развития, характерные для современной теории алгоритмов: □ формализация понятия «алгоритм» и исследование формальных алгоритмиче ских систем (моделей вычислений); □ доказательство алгоритмической неразрешимости задач; □ формальное доказательство правильности и эквивалентности алгоритмов; □ классификации задач, определение и исследование сложностных классов; □ доказательство теоретических нижних оценок сложности задач; □ получение методов разработки эффективных алгоритмов; □ асимптотический анализ сложности итерационных алгоритмов; □ исследование и анализ рекурсивных алгоритмов; 14.2. Способы записи алгоритмов 399 □ получение явных функций трудоемкости алгоритмов; □ разработка классификаций алгоритмов; □ исследование емкостной (по ресурсу памяти) сложности задач и алгоритмов; □ разработка критериев сравнительной оценки ресурсной эффективности алго ритмов и методов их сравнительного анализа. 14.2. Способы записи алгоритмов Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно. Соответ ствующие системы правил называют языками описаний. К средствам описания алгоритмов относятся следующие основные способы их представления: словесный, графический (блок-схема), псевдокоды, программный, диаграмма Несси—Ш ней дермана (рис. 14.5). Рис. 14.5. Способы представления алгоритмов 14.2.1. Словесный способ представления алгоритма Словесный способ записи алгоритмов представляет собой последовательное описание основных этапов обработки данных, заданное в произвольном изложении на естественном языке. Этот способ записи основан на общепринятых средствах общения между людьми. Его удобно использовать на начальном этапе алгоритми зации задачи. Рассмотрим понятие словесного представления алгоритма на примере нахож дения произведения п натуральных чисел — факториала числа п (с = гг!), то есть вычисления по формуле с = 1 х 2 х 3 х ... х п. Этот процесс может быть записан в виде следующей последовательности шагов (инструкций, пунктов, указаний): 1. Присваиваем переменной с значение, равное единице, и переходим к следую щему шагу. 2. Присваиваем переменной i значение, равное единице, и переходим к следующему шагу. 400 Глава 14. Основы теории алгоритмов 3. Вычисляем выражение г х с, полученное значение присваиваем переменной с и переходим к следующему шагу. 4. Проверяем, равно ли значение переменной i значению переменной п. Если i = и, то вычисления прекращаем. Если i < п, то увеличиваем i на единицу и переходим к шагу 3. Неудобства словесных определений связаны с проблемой однозначной трактов ки терминов. В таких определениях должен быть, хотя бы неявно, указан исполни тель действий (предписаний). Например, алгоритм вычисления производной для полинома фиксированной степени вполне ясен тем, кто знаком с основами мате матического анализа, но для прочих он может оказаться совершенно непонятным. Это рассуждение заставляет указывать также вычислительные возможности испол нителя, а именно, уточнять какие операции для него являются «элементарными». Другие трудности связаны с тем, что алгоритм заведомо существует, но его очень трудно описать в некоторой заранее заданной форме. Классический пример такой ситуации — алгоритм завязывания шнурков на ботинках или узла на галсту ке. Практически невозможно дать только словесное описание этого алгоритма без использования иллюстраций. К недостаткам словесного способа записи можно отнести следующее: □ полное подробное словесное описание алгоритма получается очень громоздким; □ естественный язык допускает неоднозначность толкования инструкций; □ при переходе к этапу программирования требуется дополнительная работа по формализации алгоритма, так как словесное описание может быть понятно человеку, но «непонятно» компьютеру. По этим причинам словесный способ записи алгоритмов не получил широкого распространения. 14.2.2. Графический способ записи алгоритма Запись алгоритма с помощью графических объектов в виде блок-схемы (ГОСТ 19.701-90, ИСО 5807-85) применяется довольно широко для представления про стых алгоритмов небольшого размера. Однако по мере роста сложности отобража емого фрагмента алгоритма (программы) его логическая структура перегружается деталями и связями («спагетти») и схема становится нечитабельной. По этой причине в настоящее время блок-схемы алгоритмов используются в основном для иллюстрации программ1. При графическом представлении алгоритма с помощью схемы каждый пункт алгоритма отображается на схеме некоторой геометрической фигурой (блоком) и дополняется элементом словесного описания. Блоки на схемах соединяются 1 Кроме блок-схем алгоритмов, для тех же целей представления алгоритмов, программ или иных видов деятельности, в том числе и на этапе проектирования систем, могут использоваться и дру гие виды графической нотации. Среди них заметное место в современных методиках разработки заним ает диаграмма деятельности (A ctivity diagram ), являю щ аяся частью унифицированного язы ка моделирования UM L. 14.2. Способы записи алгоритмов 401 линиями потоков информации. Основное направление потока информации идет сверху вниз и слева направо (стрелки могут не указываться), снизу вверх и спра ва налево (стрелки обязательны). Количество входящих линий для блока не ограничено. Выходящая линия должна быть одна (исключение составляет блок решения). Основные элементы блок-схемы алгоритма приведены в табл. 14.2. Таблица 14.2. Основные элементы схемы алгоритма (по ГОСТ 19.701-90) № Символическое обозначение Наименование Описание 1 Процесс Блок функции обработки данных любого вида: выполнение определенной операции или группы операций, приводящее к изменению значения, формы, размещения информации или к опреде лению направления дальнейшего движения 2 Решение Блок решения или функции переключательного типа. Внутри блока записывается условие. Блок имеет один вход и два альтернативных выхода: «да» — условие выполнено, «нет» — условие не выполнено 3 ZZ7 Данные Блок отображает данные, носитель данных не определен 4 С ) Терминатор Блок отображает выход во внешнюю среду и вход из внешней среды (начало или конец схемы) 5 О Соединитель Символ отображает выход в часть схемы и вход из другой части этой схемы и используется для обрыва линии и продолжения ее в другом месте. Соответствующие символы-соединители долж ны быть одинаковыми 6 Предопределен ный процесс Блок для отображения подпрограммы или модуля 7 <г> Подготовка Блок отражает модификацию команды или груп пы команд с целью воздействия на некоторую последующую функцию (установка переклю чателя, модификация индексного регистра или инициализация программы) 8 |