Содержание

18) В чем заключается принцип “Разделяй и властвуй”. Приведите пример его применения

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

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

Выдержка из текста

Вопросы и задачи к контрольной работе

по дисциплине

«Теория алгоритмов»

Контрольная работа состоит из двух частей:

– теоретической;

– практической.

Варианты заданий

вар №№ теоретических вопросов №№

задач

17 17 11 18 3 21

Теоретическая часть

17. Какие алгоритмы называют алгоритмами с возвратом? В чем их особенность?

11. Структурная алгоритмизация (основные требования и принципы).

18. В чем заключается принцип “Разделяй и властвуй”. Приведите пример его использования.

Практическая часть

3. Построить Систему Алгоритмов определения факториала (n!). Привести фрагмент программы (С, Pascal, Basic).

21. Определите сложность алгоритма вычисления суммы элементов матрицы размерностью mхn (m<n).

Список использованной литературы

Список литературы:

1. Аляев Ю.Н., Козлов О.А. Алгоритмизация и языки программирования Pascal, C++, Visual Basic: Учебно-справочное пособие. — М.: Финансы и статистика, 2002. — 320 с.

2. Паулин О.Н. Основы теории алгоритмов: Учеб. пособие: — Одесса: Автограф, 2002. — 188 с.

3. А. Ахо, Дж. Хопкрофт, Дж. Ульман. Построение и анализ вычислитель¬ных алгоритмов. — М.: Мир, 1979. — 536 с.

4. Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика — М.: Мир, 1980. — 480 с.

Похожие записи