Методы разработки алгоритмов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное  бюджетное образовательное учреждение

Высшего профессионального  образования

<<РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ  СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ>>

 

 

 

 

 

Реферат на тему:

«Методы разработки алгоритмов»

 

 

 

 

 

Работу выполнил:

Студент группы ПГ-201

Коваленко М.С.

Проверил:

Асс. Нестерова А.В 

 

 

 

 

 

Ростов - на - Дону

2013 г.

 

 

 

 

 Методы  разработки алгоритмов

Составление алгоритмов решения  задач - это работа творческая. Нет  универсального способа, позволяющего без особого труда составлять любые алгоритмы. К сожалению, такого способа не существует, ведь жизненные  ситуации и задачи так разнообразны и непредсказуемы! Если бы дело обстояло иначе, появилась бы реальная возможность  автоматизировать сам процесс алгоритмизации, поручив его некоторому исполнителю - вероятно, очень высокоинтеллектуальному  компьютеру.

Тем не менее, некоторые рекомендации, касающиеся методики разработки алгоритмов, можно дать.

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

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

При дальнейшей постановке задачи на ПК отыскивается наиболее рациональный способ решения задачи.

Однако, алгоритмы становятся все более и более сложными, соответственно растет трудность понимания  того, как они работают. А еще  труднее обнаружить и исправить  в них ошибки или внести какие-то изменения. От 50 до 100% времени программист  тратит на исправление и модификацию  программ. В связи с этим индустрия  программирования предлагает более  систематичные подходы к программированию (а тем самым и к алгоритмизации задач в общем), т.е. предлагает методики, использование которых уменьшает  вероятность ошибок в программах, упрощает их понимание и облегчает  модификацию.

Структурное программирование - одна из популярных методик. Фундаментом структурного программирования является доказанная Бемом и Джекопини теорема о структурировании [15]. Эта теорема устанавливает, что как бы сложна ни была задача, блок-схема соответствующей программы (читай - "соответствующего алгоритма") всегда может быть представлена с использованием весьма ограниченного числа элементарных управляющих структур (последовательность, ветвление, цикл).

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

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

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

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

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

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

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

Метод декомпозиции.

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

Возможно, самым важным и наиболее широко применимым методом проектирования эффективных алгоритмов является метод, называемый методом декомпозиции (или  метод "разделяй и властвуй", или  метод разбиения). Этот метод предполагает такую декомпозицию (разбиение) задачи размера n на более мелкие задачи, что  на основе решений этих более мелких задач можно легко получить решение  исходной задачи. Мы уже знакомы  с рядом применений этого метода, например в сортировке слиянием или  в деревьях двоичного поиска. Чтобы  проиллюстрировать этот метод, рассмотрим хорошо известную головоломку "Ханойские  башни". Имеются три стержня  А, В и С. Вначале на стержень А  нанизаны несколько дисков: диск наибольшего  диаметра находится внизу, а выше — диски последовательно уменьшающегося диаметра, как показано на рис.. Цель головоломки — перемещать диски (по одному) со стержня на стержень так, чтобы диск большего диаметра никогда не размещался выше диска меньшего диаметра и чтобы в конце концов все диски оказались нанизанными на стержень В. Стержень С можно использовать для временного хранения дисков.

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

 

Задачу перемещения n наименьших дисков со стержня A на стержень B можно

 представить себе состоящей из двух подзадач размера n – 1.Сначала нужно

 переместить n – 1 наименьших дисков со стержня A на стержень C, оставив на

стержне A n-й наибольший диск. Затем этот диск нужно переместить с A на B.

 Потом следует переместить  n – 1 дисков со стержня C на  стержень B. Это

 перемещение n – 1 дисков выполняется путем рекурсивного применения указанного  
метода. Поменьше тех, которые в перемещении не участвуют, не нужно

задумываться над тем, что находится под перемещаемыми дисками на стержнях A,

B или C.

  Хотя фактическое перемещение  отдельных дисков не столь  очевидно, а

моделирование вручную выполнить непросто из-за образования стеков рекурсивных

вызовов, с концептуальной точки зрения этот алгоритм все же довольно прост

для понимания и доказательства его правильности (а если говорить о быстроте

разработки, то ему вообще нет равных). Именно легкость разработки алгоритмов

по методу декомпозиции обусловила огромную популярность этого метода; к тому

же во многих случаях эти алгоритмы оказываются более эффективными, чем

алгоритмы, разработанные традиционными методами.

 

Расписание проведения турнира, таким  образом, представляет собой таблицу, состоящую из л строк и п  — 1 столбцов; элементом на пересечении  строки i и столбца j является номер  игрока, с которым игрок i должен провести матч в у'-й день. Метод  декомпозиции позволяет составить  расписание для половины игроков. Это  расписание составляется на основе рекурсивного применения данного алгоритма для  половины этой половины игроков и  т.д. Когда количество игроков будет  сокращено до двух, возникнет "базовая  ситуация", в которой мы просто устанавливаем порядок проведения встреч между ними. Допустим, в турнире  участвуют восемь игроков. Расписание для игроков 1 - 4 заполняет верхний  левый угол (4 строки х З столбца) составляемого расписания. Нижний левый  угол (4 строки х З столбца) этого  расписания должен свести между собой  игроков с более высокими номерами (5 - 8). Эта часть расписания получается путем прибавления числа 4 к каждому  элементу в верхнем левом углу.

Итак, нам удалось упростить  задачу. Теперь остается свести между  собой игроков с низкими и  более высокими номерами. Сделать  это нетрудно: надо на 4-й день свести в пары игроков, имеющих номера 1 - 4, с игроками 5-8 соответственно, а  в последующие дни просто циклически переставлять номера 5 - 8. Этот процесс  показан на рис. 10.3. Надеемся, теперь читатель сможет обобщить описанный  алгоритм и составить расписание для 2* игроков при любом значении k.