Реферат: Методы разработки алгоритмов. Жадные алгоритмы

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

2. Жадные алгоритмы

3. Задача о выборе заявок

4. Правильность алгоритма

5. Когда применим жадный алгоритм?

6. Принцип жадного выбора

7. Оптимальность для подзадач

8. Жадный алгоритм или динамическое программирование?

9. Заключение.

10. Литература

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

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

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

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

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

обеспечение оптимального времени решения задачи;

обеспечение оптимального использования имеющихся ресурсов (памяти);

обеспечение требуемой точности вычислений;

минимальные стоимостные затраты;

возможность использования стандартных подпрограмм.

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

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

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

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

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

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

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

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

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--