yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы и структуры данных

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

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

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

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

 

Алгоритмы

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

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

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

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

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

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

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

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

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

 

 

 

АВ

 

АС

 

AD

 

ВА

 

ВС

 

BD

 

DA

 

DB

 

DC

 

ЕА

 

ЕВ

 

ЕС

 

 

ED

 

 

АВ АС AD ВА ВС BD DA DB DC ЕА ЕВ ЕС ED

 

 

 

 

 

1

1

1

 

 

1

 

 

 

 

 

 

1

1

1

 

1

1

 

 

 

 

 

 

 

 

 

 

1

1

1

 

 

 

1

 

 

 

 

 

 

1

 

 

1

 

1

1

 

 

 

 

1

 

 

 

1

1

 

1

1

 

 

 

1

 

 

 

 

1

1

 

 

1

 

 

1

 

 

 

 

 

 

1

 

 

 

1

1

1

 

 

1

1

 

1

1

1

 

 

 

1

 

 

1

1

1

 

 

 

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

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

1.    Выбираем произвольную незакрашенную вершину и назначаем ей новый цвет.

2.    Просматриваем список незакрашенных вершин и для каждой из них определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если не соединена, то к этой вершине также применяется новый цвет.

Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных. Возможны ситуации, когда, будь алгоритм менее "жадным" и пропустил бы некоторые вершины при закраске новым цветом, мы получили бы раскраску графа меньшим количеством цветов. Например, для раскраски графа на рис. 1.3 можно было бы применить два цвета, закрасив вершину 1 в красный цвет, а затем, пропустив вершину 2, закрасить в красный цвет вершины 3 и 4. Но "жадный" алгоритм, основываясь на порядковой очередности вершин, закрасит в красный цвет вершины 1и 2, для закраски остальных вершин потребуются еще два цвета.

Применим описанный алгоритм для закраски вершин графа нашей задачи (рис.1.2), при этом первой закрасим вершину АВ в синий цвет. Также можно закрасить в синий цвет вершины AC, AD и ВА, поскольку никакие из этих четырех вершин не имеют общих ребер. Вершину ВС нельзя закрасить в этот цвет, так как существует ребро между вершинами АВ и ВС. По этой же причине мы не можем закрасить в синий цвет вершины BD, DA и DB — все они имеют хотя бы по одному ребру, связывающему их с уже закрашенными в синий цвет вершинами. Продолжая перебор вершин, закрашиваем вершины DC и ED в синий цвет, а вершины ЕА, ЕВ и ЕС оставляем незакрашенными.

Теперь применим второй цвет, например красный. Закраску этим цветом начнем с вершины ВС. Вершину BD можно закрасить красным цветом, вершину DA — нельзя, так как есть ребро между вершинами BD и DA. Продолжаем перебор вершин: вершину DB нельзя закрасить красным цветом, вершина DC уже закрашена синим цветом, а вершину ЕА можно закрасить красным. Остальные незакрашенные вершины имеют общие ребра с вершинами, окрашенными в красный цвет, поэтому к ним нельзя применить этот цвет.

Рассмотрим незакрашенные вершины DA, DB, ЕВ и ЕС. Если вершину DA мы закрасим в зеленый цвет, то в этот цвет также можно закрасить и вершину DB, но вершины ЕВ и ЕС в зеленый цвет закрасить нельзя. К последним двум вершинам применим четвертый цвет, скажем, желтый. Назначенные вершинам цвета приведены в табл. 1.2. В этой таблице "дополнительные" повороты совместимы с соответствующими поворотами из столбца "Повороты", хотя алгоритмом они окрашены в разные цвета. При задании режимов работы светофоров, основанных на одном из цветов раскраски, вполне безопасно включить в эти режимы и дополнительные повороты. Данный алгоритм не всегда использует минимально возможное число цветов. Можно использовать результаты из общей теории графов для оценки качества полученного решения. В теории графов k-кликой называется множество из k вершин, в котором каждая пара вершин соединена ребром. Очевидно, что для закраски k-клики необходимо k цветов, поскольку в клике никакие две вершины не могут иметь одинаковый цвет.

 

Таблица 1.2. Раскраска графа, представленного на рис. 1.2

 

Цвет

Повороты

 

Дополнительные повороты

 

Синий

Красный

Зеленый

Желтый

АВ, AC, AD, BA, DC, ED

ВС, BD, ЕА

DA, DB

ЕВ, ЕС

-

BA, DC, ED

AD, BA, DC, ED

BA, DC, EA, ED

В графе рис. 1.2 множество из четырех вершин AC, DA, BD и ЕВ является 4-кликой. Поэтому не существует раскраски этого графа тремя и менее цветами, и, следовательно, решение, представленное в табл. 1.2, является оптимальным в том смысле, что использует минимально возможное количество цветов для раскраски графа. В терминах исходной задачи это означает, что для управления перекрестком, показанным на рис. 1.1, необходимо не менее четырех режимов работы светофоров.

Итак, для управления перекрестком построены четыре режима работы светофорами, которые соответствуют четырем цветам раскраски графа (табл. 1.2).

 

Псевдоязык и пошаговая „кристаллизация" алгоритмов

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

Пример 1.2. Рассмотрим процесс преобразования "жадного" алгоритма раскраски графа в программу на языке Pascal. Мы предполагаем, что есть граф G, вершины которого необходимо раскрасить. Программа greedy (жадный) определяет множество вершин, названное newclr (новый цвет), все вершины которого можно окрасить в новый цвет. Эта программа будет вызываться на повторное выполнение столько раз, сколько необходимо для закраски всех вершин исходного графа. В самом первом грубом приближении программа greedy на псевдоязыке показана в следующем листинге.

Листинг 1.1. Первое приближение программы greedy

procedure greedy ( var G: GRAPH; var newclr: SET );P

{ greedy присваивает переменной newclr множество вершин

графа G, которые можно окрасить в один цвет)

begin

(1)         newclr:= ø1;

(2)         for для каждой незакрашенной вершины v из G do

(3)            if v не соединена с вершинами из newclr then begin

(4)                 пометить v цветом;

(5)                 добавить v в newclr

               end

end; { greedy }

1 Символ ø  — стандартное обозначение пустого множества.

В листинге 1.1 вы легко выделите средства нашего псевдоязыка. Мы применяем полужирное начертание для зарезервированных ключевых слов языка Pascal, которые имеют тот же смысл, что и в стандартном языке Pascal. Написание строчными буквами таких слов, как GRAPH (Граф) и SET1 (Множество), указывает на имена абстрактных типов данных. Их можно определить с помощью объявления типов языка Pascal и операторов, соответствующих абстрактным типам данных, которые задаются посредством процедур языка Pascal (эти процедуры должны входить в окончательный вариант программы). Более детально абстрактные типы данных мы рассмотрим в следующих двух разделах этой темы.

Управляющие конструкции языка Pascal, такие как if, for и while, могут применяться в операторах псевдоязыка, но условные выражения в них (как в строке (3)) могут быть неформальными, в отличие от строгих логических выражений Pascal. Также и в строке (1) в правой части оператора присваивания применяется неформальный символ. Еще отметим, что оператор цикла for в строке (2) проводит повторные вычисления по элементам множества.

Чтобы стать исполняемой, программа на псевдоязыке должна быть преобразована в программу на языке Pascal. В данном случае мы не будем приводить все этапы такого преобразования, а покажем только пример преобразования оператора if (строка (3)) в более традиционный код.

Чтобы определить, имеет ли вершина v соединение с какой-либо вершиной из newclr, мы рассмотрим каждый элемент w из newclr и по графу G проверим, существует ли ребро между вершинами v и w. Для этого используем новую булеву переменную found (поиск), которая будет принимать значение true (истина), если такое ребро существует. Листинг 1.2 показывает частично преобразованную программу листинга 1.1.

Листинг 1. 2.

   procedure greedy (var G: GRAPH; var newclr: SET );

        begin

(1)         newclr:= ø;

(2)         for для каждой незакрашенной вершины v из G do begin

(3.1)            found:= false;

(3.2)      for для каждой вершины w из newclr do

(3.3)            if существует ребро между v и w then

(3.4)                   found:= true;        

(3.5)                      if  found =  false then begin

                                      {   v не соединена ни с одной вершиной из newclr }

(4)                                  пометить  v цветом;

(5)                                  добавить  v в newclr

                              end

                     end

            end;   {   greedy }.

Обратите внимание, что наш алгоритм работает с двумя множествами вершин. Внешний цикл (строки (2) - (5)) выполняется над множеством незакрашенных вершин графа G. Внутренний цикл (строки (3.2) - (3.4)) работает с текущим множеством вершин newclr. Оператор строки (5) добавляет новые вершины в это множество.

Существуют различные способы представления множеств в языках программирования. В темах 4 и 5 мы изучим несколько таких представлений. В этом примере мы можем представить каждое множество вершин посредством абстрактного типа LIST (Список), который можно выполнить в, виде обычного списка целых чисел, ограниченного специальным значением null (для обозначения которого мы будем использовать число 0). Эти целые числа могут храниться, например, в массиве, но есть и другие способы представления данных типа LIST, которые мы рассмотрим в теме 2.

Мы отличаем абстрактный тип данных SET от встроенного типа данных set языка Pascal.Теперь можно записать оператор for в строке (3.2) в виде стандартного цикла по условию, где переменная w инициализируется как первый элемент списка newclr и затем при каждом выполнении цикла принимает значение следующего элемента из newclr. Мы также преобразуем оператор for строки (2) листинга 1.1. Измененная процедура greedy представлена в листинге 1.3. В этом листинге есть еще операторы, которые необходимо преобразовать в стандартный код языка Pascal, но мы пока ограничимся сделанным.

 

Листинг 1. 3.Измененная программа greedy

procedure greedy ( var G: GRAPH; var newclr : LIST );

     { greedy присваивает переменной newclr множество вершин

              графа G, которые можно окрасить в один цвет }

var

found: boolean;

v, w: integer;

begin

newclr := Ø;

v: = первая незакрашенная вершина из G;

while v <> null do begin

      found: = false;

      w:= первая вершина из newclr

      while w <> null do begin

           if существует ребро между v и w then

                 found: = true;

           w: = следующая вершина из newclr;

end;

if found = false then begin

      пометить v цветом;

      добавить v в newclr

end

 v:= следующая незакрашенная вершина из G;

end;

end; { greedy }

Резюме

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

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

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

 

4