Постановка задачи. Этапы построения алгоритма

Этапы построения алгоритма

Структуры данных

Конспект лекций

Лекция 16

Теория сложности алгоритмов. Библиотека алгоритмов

Научный редактор доц., д-р техн. наук Л.Г. Доросинский

Екатеринбург

Содержание

1. Этапы построения алгоритма. 4

1.1 Постановка задачи. 4

1.2. Построение алгоритма. 5

1.3. Проверка правильности алгоритма. 5

1.4. Анализ алгоритма. 5

1.5. Программная реализация алгоритма. 8

1.5. Основные правила анализа алгоритмов. 9

1.6. Анализ базовых алгоритмических конструкций. 10

2. Теория алгоритмов. 12

2.2.Возникновение теории алгоритмов. 12

2.3. Тезис Чёрча — Тьюринга и алгоритмически неразрешимые массовые проблемы 12

3. Современное состояние теории алгоритмов. 14

3.1. Анализ трудоёмкости алгоритмов. 14

3.2. Классы сложности. 16

Дополнительная литература. 18

Любая человеческая деятельность, направленная на получение, обработку, накопление информации непосредственно связана с реализацией (зачастую неосознанно) соответствующего алгоритма и требует рассмотрения общих стадий построения алгоритма решения прикладных задач. На основе работ А. Ахо, C. Гудмана], Д. Кнута, А.Р. Есаяна, Т. Кормена, Ч. Лейзерсона, Р. Ривеста, А.Г. Кушниренко, Г.В. Лебедева, М.П. Лапчика, и других авторов в процессе полного построения алгоритма можно выделить следующие основные этапы:

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

2) разработка модели;

3) построение алгоритма;

4) проверка правильности алгоритма;

5) анализ алгоритма;

6) программная реализация алгоритма.

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

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

- Все ли термины, используемые в предварительной формулировке, понятны и адекватно используются?

- Является ли система входных данных полной?

- Что требуется найти?

- Какие существуют подходы к определению решения данной задачи?

- Какие сделаны допущения в предварительной формулировке и насколько они обоснованы?

В зависимости от конкретной задачи приведенная система вопросов может расширятся. После получения частичных или полных ответов на поставленные вопросы следует провести повторный анализ и, возможно, некоторые вопросы придется поставить заново.

Дата добавления: 2014-01-07