Главная Промышленная автоматика.

ГЛАВА 1

Построение и анализ алгоритмов

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

1.1. От задачи к программе

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

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

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



Алгоритмы

Когда построена (подобрана) подходящая модель исходной задачи, то естественно искать рещение в терминах этой модели. На этом этапе основная цель заключается в построении рещения в форме алгоритма, состоящего из конечной последовательности инструкций, каждая из которых имеет четкий смысл и может быть выполнена с конечными вычислительными затратами за конечное время. Целочисленный оператор присваивания х := у + г - пример инструкции, которая будет выполнена с конечными вычислительными затратами. Инструкции могут выполняться в алгоритме любое число раз, при этом они сами определяют число повторений. Однако мы требуем, чтобы при любых входных данных алгоритм завер-щился после выполнения конечного числа инструкций. Таким образом, программа, написанная на основе разработанного алгоритма, при любых начальных данных никогда не должна приводить к бесконечным циклическим вычислениям.

Есть еще один аспект определения алгоритмов, о котором необходимо сказать. Выще мы говорили, что алгоритмические инструкции должны иметь "четкий смысл" и выполняться с "конечными вычислительными затратами". Естественно, то, что понятно одному человеку и имеет для него "четкий смысл", может совершенно иначе представл.яться другому. То же самое можно сказать о понятии "конечных затрат": на йрактике часто трудно доказать, что при любых исходных данных выполнение последовательности инструкций заверщится, даже если мы четко понимаем смысл каждой инструкции. В этой ситуации, учитывая все аргументы за и против, было бы полезно попытаться достигнуть соглащения о "конечных затратах" в отнощении последовательности инструкций, составляющих алгоритм. Однако кажущаяся сложность подобных доказательств может быть обманчивой. В разделе 1.5 мы оценим время выполнения основных структур языков программирования, что докажет конечность времени их выполнения и соответственно конечность вычислительных затрат»

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

Следующие примеры иллюстрируют основные этапы создания компьютерной программы.

Пример 1.1. Рассмотрим математическую модель, используемую для управления светофорами на сложном перекрестке дорог. Мы должны создать программу, которая в качестве входных данных использует множество всех допустимых поворотов на перекрестке (продолжение прямой дороги, проходящей через перекресток, также будем считать "поворотом") и разбивает это множество на несколько групп так, чтобы все повороты в группе могли выполняться одновременно, не создавая проблем друг для друга. Затем мы сопоставим с каждой группой поворотов соответствующий редким работы светофоров на перекрестке. Желательно минимизировать число разбиений исходного множества поворотов, поскольку при этом минимизируется количество режимов работы светофоров на перекрестке.

Для примера на рис. 1.1 показан перекресток возле Принстонского университета, известный сложностью его преодоления. Обратите внимание, что дороги С и £ односторонние, остальные - двухсторонние. Всего на этом перекрестке возможно 13 поворотов. Некоторые из этих поворотов, такие как АВ (поворот с дороги А на дорогу В) и ЕС, могут выполняться одновременно. Трассы других поворотов, например AD и ЕВ, пересекаются, поэтому их нельзя выполнять одновременно. Режимы работы светофоров должны учитывать эти обстоятельства и не допускать одновременного выполнения таких поворотов, как AD и ЕВ, но могут разрещать совместное выполнение поворотов, подобных АВ и ЕС.




Рис. 1.1. Сложный перекресток

Для построения модели этой задачи можно применить математическую структуру, известную как граф. Граф состоит из множества точек, которые называются вершинами, и совокупности линий (ребер), соединяющих эти точки. Для рещения задачи управления движением по перекрестку можно нарисовать граф, где верщины будут представлять повороты, а ребра соединят ту часть верщин-поворотов, которые нельзя выполнить одновременно. Для нащего перекрестка (рис. 1.1) соответствующий граф показан на рис. 1.2, а в табл. 1.1 дано другое представление графа - в виде таблицы, где на пересечении строки i и столбца j стоит 1 тогда и только тогда, когда существует ребро между верщинами i и j.


Рис. 1.2. Граф, показывающий нес<у вместимые повороты

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

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





0 [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018