Пример готовой контрольной работы по предмету: Информатика
Содержание
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 с.
