Технологии проектирования алгоритмов

Технологии проектирования алгоритмов

Этапы решения задач на ЭВМ. Нисходящее и восходящее проектирование алгоритмов. Пошаговая детализация. Размерность задачи. Временная и емкостная сложность алгоритмов. Последовательный поиск. Двоичный поиск. Алгоритмы сортировки.

Процесс решения задачи на ЭВМ можно разбить на ряд этапов:

1 - постановка задачи;

2 - математическое описание задачи - создание математической модели задачи;

3 - составление алгоритма решения задачи;

4 - составление программы;

5 - разработка тестовой задачи;

6 - отладка программы;

7 - расчет на ЭВМ, получение и анализ результатов.

Разберем подробнее эти этапы:

1. Задача должна быть четко сформулирована (т.е. должны быть высказаны те предположения, которые позволят из информации о рассматриваемом предмете выудить исходные данные, определить, что требуется получить). Если коротко, должны быть определены аргументы и результаты.

2. На этом этапе решения задачи уточняется, чем в постановке задачи можно, а чем нельзя пренебречь. Выбор той или иной модели зависит от точности, с какой необходимо получить результат. Для повышения точности модель приходится усложнять, уточняя особенности объекта.

Далее определяются связи между исходными данными и результатами.

Все это: связи, предположения, исходные данные и результаты - называют моделью задачи.

Если задача решается на компьютере, то надо позаботиться о том, чтобы исходные данные и результаты были указаны в виде, понятном для ЭВМ, (например, числами), а связи между ними - математическими соотношениями.

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

1. Составляем для ЭВМ четкую инструкцию с указанием последовательности действий - алгоритм - для получения плана решения (словесный, в виде блок-схемы, с использованием псевдокода) .

2. Записываем алгоритм на каком-либо языке программирования (фортран, алгол, бейсик, си, Паскаль, лого, лисп, пролог и т.п.). Алгоритм, записанный на языке программирования, называется программой.

3. Готовим тесты, т.е. такие исходные данные, которые позволят проверить правильность работы программы. Тесты должны учитывать все варианты работы программы

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

5. Производим расчеты на ЭВМ, сопоставляем результаты расчетов с экспериментальными данными, теоретическими воззрениями и другой информацией об объекте. Зачем это нужно? Так как в основе расчетов лежит модель, основанная на некоторых упрощениях, то нужно быть уверенным в том, что модель соответствует реальной задаче. При этом может возникнуть необходимость уточнить математическую модель, поскольку выяснится, что при ее разработке не было учтено что-либо существенное. Уточняют модель, исправляют алгоритм, переписывают программу, проводят расчеты на ЭВМ, анализируют результаты... И так до тех пор, пока анализ результатов не покажет их соответствие знаниям об объекте.

Существенным шагом на пути снижения трудоемкости этапов 3 и 4 стал структурный подход к проектированию алгоритмов. Его основным принципами являются нисходящее проектирование и модульное программирование. Нисходящее проектирование заключается в последовательном разбиении задачи на всё более мелкие и мелкие участки, т.е. процесс программирования идёт "сверху вниз". Модульное программирование предполагает создание для каждого такого участка отдельной автономной программы - модуля. Специально созданная программа объединяет все модули в единое целое и управляет их работой.

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

Такой подход к проектированию алгоритмов позволяет повысить качество и надёжность разрабатываемых программ. Кроме того, появляется возможность использовать отдельные модули программы при решении других задач.

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

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

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

Сложность алгоритма - количественная характеристика, которая говорит либо о том, сколько времени он работает, либо о том, какой объем памяти он занимает. Сложность рассматривается в основном для алгоритмических моделей, поскольку в них время и память присутствуют в явном виде.

Физическое время выполнения алгоритма - это величина t*n ,где t-число действий (элементарных шагов, команд), а n - среднее время выполнения одного действия. Число шагов n определяется способом описания алгоритма данной модели и не зависит от физической реализации модели; t - величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ. Поэтому объективной математической характеристикой трудоемкости алгоритма в данной модели является число действий.

Емкостная сложность алгоритма определяется числом ячеек памяти, используемых в процессе его вычисления. Эта величина не может превосходить числа действий n, умноженного на небольшую константу (число ячеек, используемых в данной модели на одном шаге); в свою очередь, число шагов может сколь угодно сильно превосходить объем памяти (за счет циклов по одним и тем же ячейкам).

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

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

Наиболее употребительны два способа определения функции сложности: а) ее значением является сложность худшего случая ( минимальное число действий, достаточное для обработки алгоритмом А любых данных размерности n); б) - значением является средняя сложность А, взятая по всем данным размерности n.

Рассмотрим примеры

1 Задачи поиска.

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

Если о расположении данных в таблице нет никаких сведений, тогда проверка одного элемента не дает никакой информации об остальных. Способ поиска в этом случае - последовательный перебор.

Алг поиск (арг цел N, арг вещ таб а[1: N], арг вещ х, рез цел k)

нач

k:=1

нц пока kx

k:=k+1

кц

если kN

то k:=0

все

кон

Алгоритм поиска объекта во множестве, состоящем из n объектов, последовательно перебирает объекты множества. Сложность худшего случая равна n ( искомый объект может оказаться последним); средняя продолжительность поиска равна сумме всех номеров от 1 до n, деленной на 2, что составляет (n+1)/2. В обоих случаях функция сложности имеет вид a*n+b, т.е. является линейной.

2 Дано n чисел. Требуется найти в этой последовательности максимальное число.

Метод решения: в некоторой памяти М запоминаем первое число.

Следующие числа последовательности сравниваем с числом, лежащим в М. Записываем в M большее из этих чисел (т.е. сохраняем в M прежнее число - если оно больше, - либо записываем вместо него следующее) .

Повторяем операцию сравнения до тех пор, пока не дойдем до конца данной последовательности.

Сложность данного алгоритма также линейна ( каждое из n чисел просматривается только один раз , и при просмотре каждого числа совершается не более 5 операций) .

3. С помощью этого алгоритма (п. 2) можно построить алгоритм упорядочения последовательности из n чисел : находим наибольшее число в исходной последовательности из n чисел, выписываем его и вычеркиваем из исходной последовательности ; находим наибольшее число в оставшейся последовательности из n-1 чисел, приписываем его справа к найденному ранее числу и вычеркиваем из исходной последовательности и т. д. Трудоемкость этого алгоритма равна многочлену второй степени. (В программировании под сортировкой понимают процесс размещения заданного множества объектов в некотором определенном порядке).

4. Обычно для решения некоторой задачи существуют различные алгоритмы, поэтому естественно искать для нее алгоритм с наименьшей сложностью и определять сложность задачи как минимум среди всех сложностей алгоритмов, решающих эту задачу. С этой точки зрения некоторые из приведенных выше алгоритмов не являются оптимальными. Например, в упорядоченном множестве поиск можно осуществить гораздо быстрее, чем за n шагов. Этот быстрый алгоритм, называемый алгоритмом двоичного ( бинарного) поиска, работает так. Задаем границы поиска места элемента, первоначально 1 и n+1), обращаемся к среднему элементу множества объектов. Если искомый элемент меньше среднего, берем меньшую часть множества и обращаемся к ее середине; если он больше среднего, обращаемся к середине большей части - и так до тех пор, пока очередная середина не совпадет с искомым элементом (пока границы не совпадут).

Ниже приведен фрагмент реализации бинарного поиска в таблице а[1:N] элемента Х:

Нач

L:=1 {На первом шаге рассматривается весь массив}

R:=N

F:= 0 {признак результативности поиска : F=1, если Х найден, и 0 - в противном случае}

нц пока LR и F=0 {условия продолжения поиска}

M:= div (L+R,2) {выбор среднего элемента}

если A[M]=X {}

то F:=1 {элемент найден, поиск надо прекратить}

иначе если A[M]X

то L:=M+1 {отбрасывается левая часть}

иначе R:=M-1 {отбрасывается правая часть}

все

все

кц

кон

На каждом шаге длина последовательности, в которой происходит поиск, уменьшается вдвое и общая трудоемкость этого алгоритма имеет порядок log2*n. Высокая скорость этого алгоритма возможна только для упорядоченных множеств и говорит о том, как важен порядок в расположении некоторых объектов. Используя упорядоченность, мы ищем слова в словарях, книги в каталогах, телефоны в справочниках и т.д.

5. Из этих общих рассуждений вытекает, что необходимо иметь хорошие алгоритмы для задачи упорядочения, которая в программировании называется задачей сортировки. Описанный выше алгоритм сортировки (см. п. 3) не является оптимальным. Известны алгоритмы сортировки со сложностью в худшем случае порядка n log n. К ним относится обменная сортировка с разделением (сортировка Хоара ). Его идея:

1. В исходном неотсортированном массиве выбрать некоторый элемент x=a[k].

2. Переставить элементы массива таким образом, чтобы слева от х оказались элементы массива, меньшие или равные х, а справа - элементы массива, большие х. Пусть при этом элемент х попадает в позицию с номером k, тогда массив будет иметь вид:

(а[1], a[2], ... , a[k-1], a[k], a[k+1], ..., a[n]).

Каждый из элементов а[1], a[2], ... , a[k-1] меньше либо равен a[k], каждый из элементов a[k+1], ... a[n]) больше a[k]. Отсюда можно сделать вывод, что элемент a[k] стоит на своем месте. А исходный массив при этом разделился на две неотсортированные части, барьером между которыми является элемент a[k].

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

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

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

Сортировать элементы можно по неубыванию (a₁a₂a_n) и по невозрастанию(a₁=a₂ =...=a_n); если числа .попарно различны , то можно говорить об убывании и о возрастании.

Методы сортировки "на том же месте" можно разбить на 3 основные категории:

1. Сортировки с помощью выбора. Его алгоритм: найти элемент массива, имеющий наименьшее значение, переставить его с первым элементом, затем проделать то же самое, начав со второго элемента и т.д.

2. Сортировки с помощью включения. Алгоритм: просматривать последовательно a₂ ,..., a_n и каждый новый элемент a_i вставлять на подходящее место в уже упорядоченную совокупность a_1, ... , a_{i -1}. Это место определяется последовательным сравнением a_i с упорядоченными элементами a_1, ... , a_{i -1.}

3. Сортировки с помощью обменов. Алгоритм: последовательным просмотром

a₁ ,...a_n найти наименьшее i такое, что a _i a_i+1. Поменять a_i и a_i+1 местами, возобновить просмотр с a_i+1 элемента и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на 1 количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.

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

Эти методы еще называют прямыми. В них требуется порядка n*n сравнений.

На алгоритмическом языке Кумир один из алгоритмов упорядочения по неубыванию будет выглядеть следующим образом:

алг упорядочение (цел n , вещ таб A [1:n])

арг A, n,

рез A

нач цел.i,l, вещ R

нц для i от 1 до n-1

нц для k от i+1 до n

если a[i]a[k]

то R:=a[i]

a[i]:=a[k]

a[k]:=R

все

кц

кц

кон.

Вообще говоря , алгоритмов сортировки придумано достаточно много. Рассмотрим следующий

Алгоритм упорядочения простыми вставками можно улучшить. Место, на которое надо вставить а_i в уже упорядоченную совокупность а_i , ...,а _i-1 , определяется алгоритмом деления пополам (см. п. 4). Этот алгоритм сортировки называется алгоритмом сортировки бинарными вставками. Алгоритм требует около n*log₂n сравнений элементов.

Сортировка слиянием:

Задача Даны два упорядоченных массива размерности m и n. Образовать из элементов этих массивов упорядоченный массив С[1:m+n]. Число сравнений при этом не должно превышать m+n.

Идея: Рассмотрим первые элементы массивов, сравним их и меньший занесем в массив С. В массиве, где находится меньший элемент, увеличим на 1 порядковый номер очередного просматриваемого элемента, и сравниваем очередную пару элементов из обоих массивов. Повторяем подобные действия до исчерпания одного из массивов. Оставшиеся элементы другого массива переносим в массив С напрямую без дополнительных сравнений.

Упражнения

1. Возьмем список из букв. «Пометим» первую и следующую за ней буквы. Если порядок букв правильный, то так их и оставим и передвинем метку вправо на одну позицию. Если порядок букв неверный, то поменяем их местами и также передвинем метку вправо. Закончим процесс, не доходя одной строчки до конца списка, чтобы предотвратить сравнение с элементами за пределами списка. Поясняющий пример:

1 2 3 4 5

b z d c a

b z d c a

b d z c a

b d c z a

b d c a z

1. Утопили самую тяжелую букву. Осталось отсортировать список букв, лежащих слева от самой тяжелой. С этим списком поступим так же, как и с полным списком.

1. Можно попробовать написать алгоритм решения этой задачи

Какой метод здесь применен?

1. 2 На тарелке один на другой в произвольном порядке положены 15 блинов разных размеров. В любом месте стопки можно засунуть лопатку и перевернуть верхнюю часть стопки. Составить алгоритм упорядочения блинов в порядке увеличения их размеров.

1. Ваш приятель живет в 100- этажном доме, где на каждом этаже разное число квартир. Он позвал Вас в гости, номер квартиры сказал, а этаж назвать забыл. Составить алгоритмы поиска номера нужного этажа. Какой из них самый эффективный?

1. Великан - людоед поймал 7 братьев - малышей, но будучи в добром настроении, пообещал отпустить самого легкого из них, если они найдут способ поиска его за 6 взвешиваний на весах с коромыслом и двумя чашками. Поможете малышам?

1. Великан обещал отпустить всех братьев, если они составят 6 способов поиска самого легкого из 7 братьев, шесть раз сравнивая их попарно на весах (можно сравнивать братьев, объединяя их в группы по двое, по трое).

1. Даны 5 попарно различных целых чисел a, b, c, d, e. Упорядочить их по возрастанию, используя для этого не более семи сравнений.