Методы программирования и прикладные алгоритмы. Учебное пособие СанктПетербург 2007
 Скачать 2.32 Mb.
|
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования Санкт-Петербургский государственный университет аэрокосмического приборостроения Е. А. Крук, А. А. Овчинников МЕТОДЫ ПРОГРАММИРОВАНИЯ И ПРИКЛАДНЫЕ АЛГОРИТМЫ Учебное пособие Санкт-Петербург 2007 УДК 519.68 ББК 22.18 К84 Рецензенты: кафедра распределенных вычислений и компьютерных сетей Санкт-Петербургского государственного политехнического университета; профессор кафедры автоматизированных систем обработки информации и управления Санкт-Петербургского государственного электротехнического университета «ЛЭТИ», заслуженный работник высшей школы РФ, доктор технических наук С. А. Яковлев Утверждено редакционно-издательским советом университета в качестве учебного пособия Крук Е. А., Овчинников А. А. K84 Методы программирования и прикладные алгоритмы: Учебное пособие/ Е. А. Крук, А. А. Овчинников; ГУАП. – СПб., 2007. – 166 с.:ил. ISBN 5-8088-0237-7 Учебное пособие представляет собой курс лекций, многие годы чи- тающийся студентам, обучающимся по направлениям «Информацион- ная безопасность», «Информационные системы», «Информатика и вы- числительная техника» в Санкт-Петербургском государственном уни- верситете аэрокосмического приборостроения и в Санкт-Петербургском государственном политехническом университете. Предназначено для студентов специальности 090104, а также мо- жет быть использовано для самостоятельной работы при выполнении заданий по НИР. УДК 519.68 ББК 22.18 ISBN 5-8088-0237-7 c ГУАП, 2007 c Е. А. Крук, А. А. Овчинников, 2007 СОДЕРЖАНИЕ Предиcловие 4 1. Введение в разработку и анализ алгоритмов 6 1.1. Вычисление веса двоичного вектора . . . . . . . . . 6 1.2. Коды, сохраняющие разность . . . . . . . . . . . . . 12 2. Методы построения алгоритмов 18 2.1. Этапы построения алгоритмов . . . . . . . . . . . . . 18 2.2. Методы частных целей, подъема вверх и отрабаты- вания назад . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3. Рекурсия . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4. Методы декомпозиции и композиции . . . . . . . . . 51 2.5. Эвристические алгоритмы . . . . . . . . . . . . . . . 57 2.6. Контрольные задачи . . . . . . . . . . . . . . . . . . 62 3. Методы анализа алгоритмов 68 3.1. Классы алгоритмов . . . . . . . . . . . . . . . . . . . 68 3.2. Решение рекуррентных уравнений . . . . . . . . . . 79 3.3. Контрольные задачи . . . . . . . . . . . . . . . . . . 110 4. Методы исчерпывающего поиска 115 4.1. Исчерпывающий поиск . . . . . . . . . . . . . . . . . 115 4.2. Динамическое программирование . . . . . . . . . . . 121 4.3. Метод ветвей и границ . . . . . . . . . . . . . . . . . 139 4.4. Методы решета . . . . . . . . . . . . . . . . . . . . . 152 4.5. Приближение исчерпывающего поиска . . . . . . . . 158 Библиографический список 165 3 Предисловие Развитие вычислительной техники не только дало в руки лю- дей мощный инструмент для проведения вычислений, но измени- ло и само представление о том, что значит решить задачу. По сути дела, решением задачи в «докомпьютерную» эпоху была форму- ла, вычисление которой при конкретных значениях входящих в нее величин и было предметом исследования или расчета. Вы- числительная техника дала возможность получать решение с по- мощью последовательности действий — алгоритма. Может быть с общематематических позиций разница вышеизложенных решений не так и велика (формула тоже задает вычисление), но их прак- тический смысл очень различен. Решая задачу с помощью неко- торого алгоритма, как бы говорим «я не могу указать формулу для решения задачи, но я утверждаю, что, проделав указанную алгоритмически последовательность действий, это решение полу- чим». Конечно, формула является эстетически более красивым решением, и она допускает символьный анализ решения, но зато алгоритмические решения удается получить для многих задач, где аналитическое решение неизвестно или даже вовсе не может быть получено. Однако поиск алгоритмического решения задачи так же сло- жен для исследователя, как и поиск решения аналитического — расширился набор используемых инструментов (в качестве ин- струмента теперь могут использоваться алгоритмы), но расши- рился и круг решаемых задач. Требуются специальные методы, позволяющие строить эффективные алгоритмы. Учебное пособие предназначено для изучения этих методов. Оно представляет собой первую часть учебника по изучению ба- зовых алгоритмов обработки информации и состоит из четырех глав. В первой главе формулируются общие принципы и критерии оценки алгоритмов. Вторая глава посвящена систематизации ос- новных приемов построения алгоритмов. Эти приемы соответ- ствуют обычному здравому смыслу и достаточно просты в фор- 4 мулировках, но оказываются весьма действенными при решении алгоритмических задач. И поскольку авторы не знают других спо- собов научить решать задачи, кроме как их решать, то основное внимание в разделе уделено именно решению многочисленных за- дач и примеров, соответствующих тем или иным приемам постро- ения алгоритмов. Таким образом, первые три главы можно интер- претировать, как введение в анализ и разработку алгоритмов. В четвертой главе введенные приемы и понятия используются при рассмотрении важного класса прикладных алгоритмов — алго- ритмов исчерпывающего поиска. Авторы хотели бы выразить свою глубокую признательность В. А. Чернышеву и Е. М. Линскому за помощь при подготовке пособия. 5 1 . введение в разработку и анализ алгоритмов 1.1. Вычисление веса двоичного вектора Рассмотрим последовательность элементов x = (x 1 , . . . , x n ), где каждый элемент x i может принимать значения 0 и 1, x i ∈ {0, 1}. Назовем последовательность x n-мерным двоичным век- тором с элементами (координатами) x i , а весом W (x) вектора x — число его ненулевых элементов. Тогда сформулируем задачу. Задача 1.1 . Найти вес двоичного вектора x = (x 1 , . . . , x n ). На первый взгляд, задача нахождения веса вектора может быть решена тривиально, простым последовательным рассмотре- нием элементов вектора и сравнением их с нулем. То же самое может быть также записано как вычисление W (x) = n i=1 x i (1.1) Вычисления в (1.1) — пример решения задачи методом пе- ребора, т.е. имея конечное множество объектов, рассматриваем их один за другим (перебираем), возможно выполняя при этом какие-то действия или вычисления для нахождения искомого от- вета. Таким образом, найдено хотя бы одно решение задачи. Однако существует еще целый ряд вопросов, которые возникают в связи с предложенным решением. Можно ли решить эту задачу проще? Если да, то насколько проще, и что такое «простота» той или иной задачи? Прежде чем попытаться ответить на эти вопросы, введем ряд обозначений и дадим несколько определений. Определение 1.1 Для двух функций f (n) и g(n) запишем f (n) = O(g(n)), если lim n→∞ f (n) g(n) = C > 0, (1.2) для некоторой константы C. 6 Определение 1.2 Для двух функций f (n) и g(n) запишем f (n) = o(g(n)), если lim n→∞ f (n) g(n) = 0. (1.3) Обозначения O(·) и o(·), введенные определениями 1.1 и 1.2 , позволяют оценивать скорость роста функции f (n) относительно скорости роста функции g(n). Часто с помощью этих обозначе- ний оценивают сложность того или иного алгоритма, где n — раз- мерность задачи (параметр, непосредственно влияющий на слож- ность); g(n) — некоторая известная функция (линейная, степен- ная, логарифмическая, экспоненциальная и т.д.), а f (n) — слож- ность алгоритма. В случае выполнения (1.2) говорят, что функ- ция f (n) «растет, как» функция g(n) или «имеет порядок» g(n). В случае выполнения (1.3) говорят, что функция f (n) «растет мед- леннее, чем» функция g(n) или «имеет порядок, меньший, чем» g(n). Например, функция f (n) = 2n + 1 имеет порядок O(n), а функция f (n) = 3n 3 + 5n 2 + 2 имеет порядок O(n 3 ). В качестве f (n) может рассматриваться как число некоторых элементарных действий, операций (или, проще говоря, требуемое «время» выполнения), так и объем данных, которые необходи- мо хранить (требуемая «память»). Критерии время/память часто могут обмениваться одно на другое, но в общем случае при оценке сложности того или иного алгоритма необходимо оценивать оба этих параметра. Анализ сложности с точки зрения O(·) позволяет лишь оце- нить скорость роста функции f (n), т.е. оценить сложность алго- ритма в асимптотике, и с его помощью нельзя получить точное значение числа требуемых шагов или ячеек памяти — явное вы- ражение для f (n). Такой асимптотический анализ может быть ис- пользован при сравнении различных алгоритмов, при оценке их реализуемости. Для нахождения f (n) в явном виде часто требу- ется более тонкий и глубокий анализ, и в этом случае речь мо- жет идти уже не об алгоритмах, а о конкретных их реализациях. В дальнейшем, как правило, будем ограничиваться асимптоти- 7 ческой оценкой роста f (n), что будет достаточно для вывода об эффективности того или иного решения задачи. Теперь рассмотрим предложенное ранее решение задачи о весе двоичного вектора методом перебора по элементам вектора (1.1). Размерностью данной задачи является число элементов n в век- торе x. Вычисление (1.1) состоит в выполнении n − 1 «базовых действий» — сложений, при этом размер необходимой памяти не меняется с изменением n и фактически память требуется только для хранения промежуточного результата суммы, т.е. сложность данного алгоритма составляет O(n) по времени и O(1) по памяти. Таким образом, вопрос о том, существует ли более эффектив- ный способ вычисления веса двоичного вектора, теперь может быть сформулирован как вопрос существования алгоритма, да- ющего сложность по времени меньшую, чем O(n). Константная сложность по памяти уменьшена быть уже не может, если прини- мать во внимание только порядок роста, а не значение самой кон- станты. Простейшим способом уменьшения сложности по времени при решении данной задачи может служить предвычисление веса для всех возможных наборов двоичных векторов длины n. Вы- численные веса могут храниться в таблице, где адресом ячейки является сам вектор, а значением — вес данного вектора. Напри- мер, для n = 3 Адрес x = (x 1 x 2 x 3 ) W (x) 0 (000) −→ 0 1 (001) −→ 1 2 (010) −→ 1 3 (011) −→ 2 4 (100) −→ 1 5 (101) −→ 2 6 (110) −→ 2 7 (111) −→ 3 В общем случае объем такой таблицы составит 2 n ячеек памя- ти, а для вычисления веса вектора потребуется одна операция — одно обращение к таблице. Таким образом, выиграв по времени и 8 снизив временную сложность до O(1), увеличиваем сложность по памяти до O(2 n ), т.е. меняем время на память, причем неравно- ценно. Данный подход табличного предвычисления, полного или частичного, часто используется при решении задач и является предпочтительным в случаях, когда отсутствуют ограничения по объему используемой памяти или эти ограничения незначитель- ны, а время работы алгоритма является критическим парамет- ром. Более тонкий способ решения задачи можно получить, если заметить, что операция (x − 1) ∧ x, где x — десятичное представ- ление двоичного набора (x 1 , . . . , x n ), «−» обозначает десятичное вычитание, а «∧» — побитовое умножение, приводит к тому, что во множестве (x 1 , . . . , x n ) обнуляется самая правая единица, т.е. общее число единиц в результате становится на одну меньше. На- пример − 1 0 0 1 0 1 0 0 1 ∧ 1 0 0 1 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 (1.4) Тогда решение задачи для вектора x можно сделать за W (x) шагов, каждый раз сравнивая результат вычисления (x − 1) ∧ x с нулем. Каждый такой шаг можно разбить на четыре операции: вычитание единицы, побитовое умножение, увеличение счетчика числа единиц и сравнение с нулем. Таким образом, можно оценить сложность такого алгоритма как O(W (x)) по времени и O(1) по памяти. Если вес вектора x мал, то получим выигрыш по срав- нению с O(n), если же вес вектора сравним с n, сложность полу- чится большей, так как каждый шаг представляет собой не одну, а четыре операции. В заключение рассмотрим простую модификацию вычисления выражения (1.1), позволяющую увидеть способ упрощения реше- ния задачи. Наш переборный «по времени» алгоритм в (1.1) осу- ществлял суммирование по всем позициям вектора x, затрачивая n−1 сложение. Ту же самую операцию можно выполнить, поменяв 9 1 0 tt £ ¢ ¡ 1 0 1 tt £ ¢ ¡ 1 5 5 £ ¢ ¡ 2 0 1 tt £ ¢ ¡ 1 0 0 tt £ ¢ ¡ 0 5 5 £ ¢ ¡ 1 3 3 3 3 £ ¢ ¡ 3 Рис. 1.1. Подсчет числа единиц в векторе порядок cуммирования, как показано на рис. 1.1, для рассматри- ваемого примера (1.4). Листьями дерева являются элементы век- тора, корнем — сумма всех элементов. Изменение порядка сумми- рования конечно не приводит к уменьшению числа сложений (оно, как и прежде, составляет n − 1), однако вид рис. 1.1 позволяет увидеть оригинальную идею уменьшения сложности вычислений. Поясним эту идею на примере. Пусть x = 10010100 — исходный вектор. В соответствии с рис. 1.1 вначале нужно сложить элементы на соседних позици- ях. Выделим из x позиции, имеющие четные и нечетные номера, следующим образом. Умножим побитово вектор x на двоичную маску m (нч) 1 = 01|01|01|01. В результате получим вектор x (нч) 1 = 00|01|01|00. Для выделения четных позиций x применим маску m (ч) 1 = 10|10|10|10 и сдвинем результат на один бит вправо x (ч) 1 = 01|00|00|00. Тогда сумма десятичных представлений x (нч) 1 и x (ч) 1 даст век- тор x 1 = 01|01|01|00, и если сгруппированные разряды записать в десятичном виде, то получим последовательность (1|1|1|0) 10 , т.е. в точности результат сложений всего нижнего уровня на рис. 1.1. Итак, выполнили за одно десятичное сложение n-битных чисел 10 сразу n/2 сложений однобитных чисел. Выигрыш при этом будет достигаться только в предположении, что сложность суммирова- ния чисел разной размерности одинакова, хотя это и неверно с алгоритмической точки зрения, но часто имеет место на практике в силу фиксированной разрядности вычислительного устройства, если только n не превышает этой разрядности. Аналогичным образом, за одно сложение можно вычислить и результат второго уровня, применив маски m (нч) 2 = 0011|0011 и m (ч) 2 = 1100|1100 и сдвинув четную часть на 2 позиции вправо x (нч) 2 = 0001|0000, x (ч) 2 = 0001|0001, x 2 = 0010|0001 = (2|1) 10 , т.е. вычислили веса левой и правой частей x. Заключительный шаг осуществляется с помощью масок m (нч) 3 = 00001111 и m (ч) 3 = 11110000 и сдвига на 4 позиции x (нч) 3 = 00000001, x (ч) 3 = 00000010, x 3 = 00000011 = 3 10 , что и дает ответ W (x) = 3. Описанный алгоритм требует столь- ко сложений, сколько уровней содержит дерево на рис. 1.1 и это дает временную сложность O(log n). Таким образом, удалось по- строить решение задачи, гораздо более эффективное, чем пере- борные методы — получить логарифмическую сложность вместо линейной и экспоненциальной. Может сложиться впечатление, что в данном случае реше- ние было некоторым образом «угадано», однако на самом деле в его основе лежит один из часто используемых общих методов построения алгоритмов: разбиение задачи на подзадачи меньшей размерности, или декомпозиция. Действительно, структура дере- ва на рис. 1.1 иллюстрирует простое соотношение: если разобъем вектор на любое число частей, то вес вектора будет равен сумме 11 весов этих частей. Уровни дерева — это разбиения вектора x на 2, 4, 8 и т.д. частей (заметим, что сумма (1.1) представляет со- бой просто другой способ разбиения вектора x). Такое разбиение можно проводить до тех пор, пока веса полученных подвекторов не смогут быть вычислены с помощью чрезвычайно простой про- цедуры, т.е. нужно найти подзадачу такой размерности, которая имеет простое решение. Очевидно, что в нашей задаче такой про- стейшей подзадачей является нахождение веса вектора длины 1: вес в этом случае просто равен значению вектора. Рассмотренные алгоритмы перебора по элементам вектора и использования масок представляют собой разные способы даль- нейшего объединения полученных решений в общее решение зада- чи. При этом могут и должны учитываться не только количество шагов алгоритма или требуемая память, но и особенности строе- ния и функционирования тех вычислительных машин, в которых предполагается использование того или иного алгоритма. 1.2. Коды, сохраняющие разность В этом подразделе рассмотрим задачу, связанную с представ- лением данных. При построении алгоритма и дальнейшей его ре- ализации с помощью языка программирования можно использо- вать данные того или иного типа — целые числа, множества, де- ревья, списки и т.д. Тип данных может быть встроен в язык про- граммирования или реализован средствами этого языка. Как пра- вило, реализация типа данных, т.е. то внутреннее, «машинное» представление, которое дается используемой информации, может быть выполнена некоторым очевидным для данного языка про- граммирования способом. Выбор способа представления данных может напрямую влиять на эффективность работы алгоритма, ис- пользующего эти данные. Такое представление должно быть ори- ентировано не только на возможности используемого языка про- граммирования, но и на наиболее типичные операции, которые должны производиться с данными в процессе работы алгоритма. Например, пусть у нас есть объект x, описываемый набором своих свойств (признаков) {x 1 , . . . , x g }, и пусть каждый признак 12 может принимать неотрицательное целое значение, x i ∈ {0, 1, 2, . . ., N −1}. В дальнейшем будем считать x вектором с g координа- тами, x = (x 1 , . . . , x g ). Для простоты будем полагать, что N явля- ется степенью двойки, N = 2 k . Пусть доступная машинная память состоит из ячеек некоторого фиксированного размера m (бит), и следовательно, все операции также являются m-разрядными. Это значит, что даже если ячейка хранит число, представимое менее чем m битами, при операциях с этим числом будут задействованы все m бит. Будем предполагать, что k ≤ m. Тогда наиболее очевидным способом хранения вектора x является запись значения каждо- го элемента x i в отдельную ячейку памяти (рис. 1.2, а). Тогда хранение вектора x потребует g ячеек, или gm бит. Так как x i принимает значения от 0 до 2 k − 1, для его представления до- статочно k бит, и если k меньше m, то на хранение x расходуется (m−k)g лишних бит. Оптимизация объема используемой памяти в этом случае также очевидна: для этого потребуется записать биты значений x i не в каждую отдельную ячейку, а подряд (рис. 1.2, б ). В этом случае отводим для хранения x почти ровно столько бит памяти, сколько требуется (точнее, kg/m ячеек, где · означа- ет округление вверх), однако для работы с элементами x i теперь недостаточно просто работать с ячейками памяти: вначале нужно извлечь из них нужные биты с помощью операций сдвига, логи- ческого умножения и т.п., т.е. возрастает сложность совершения операций с элементами вектора x, и увеличивается время работы программы. x 1 x 2 x 3 x g k k k k m m m m |