Производительность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность порядка
O(f(N)) (произносится «О большое от F от N»),
если с увеличением размерности исходных данных N время выполнения алгоритма растет пропорционально функции f(N).
Билет №49
Сложность рекурсивных алгоритмов
Рекурсивными процедурами (recursive procedure) называются
процедуры, вызывающие сами себя
Sub CountDown(N As Integer)
If N <= 0 Then Exit Sub
CountDown N - 1
End Sub
вычислительная сложность фрагмента будет порядка
O(N)
Многократная рекурсия
Sub DoubleCountDown(N As Integer)
If N <= 0 Then Exit Sub
DoubleCountDown N - 1
DoubleCountDown N - 1
End Sub
2 * O(N) = O(N)
число раз, которое выполняется процедура DoubleCountDown с
параметром N
N=0
после первого шага закончит работу
Билет №50
Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Классификация алгоритмов сортировки
Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов.
Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат.
В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.
Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
Объём данных не позволяет им разместиться в ОЗУ.
Также алгоритмы классифицируются по:
потребности в дополнительной памяти или её отсутствии
потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой.
Билет №51
Модель - упрощенное представление о реальном объекте, процессе или явлении.
Модель - это, как правило, искусственно созданный объект в виде схемы, математических формул, физической конструкции, наборов данных и алгоритмов их обработки и т.п.
Модель воспроизводит в специально оговоренном виде строение и свойства исследуемого объекта. Исследуемый объект, по отношению к которому изготавливается модель, называется оригиналом, образцом, прототипом.
Модель - это объект, используемый вместо другого объекта с какой-то целью.
Вычислительные (численные) методы — методы решения математических задач в численном виде (см. Компьютерная алгебра)[1]
Представление как исходных данных в задаче, так и её решения — в виде числа или набора чисел
В системе подготовки инженеров технических специальностей является важной составляющей.
Основами для вычислительных методов являются:
решение систем линейных уравнений
интерполирование
численное интегрирование
численное решение системы нелинейных уравнений
численное решение обыкновенных дифференциальных уравнений
Билет №52
Физическая постановка задачи. На этом этапе определяются основные цели и задачи, рассматривается реальное явление.
Математическая постановка задачи. Реальная задача заменяется моделью. Модель должна быть достаточно простой и в то же время адекватно отражать основные функции реально го объекта. Этап заканчивается выводом некоторых математических соотношений (уравнения, системы уравнений).
Прямые методы используют конечные соотношения (формулы) для вычисления неизвестных. Они сравнительно просты и универсальны. Вместе с тем, эти методы требуют большого объема памяти ЭВМ, а при их реализации накапливается вычислительная погрешность.
Итерационные методы - это методы последовательных приближений. Они имеют более сложные алгоритмы, объем вычислений заранее определить сложно. Однако, их реализация требует меньшего объема памяти ЭВМ, а вычислительная погрешность почти не накапливается.
Билет №53
Алгоритм метода:
1. Установить интервал |а,Ь| на начало интервала поиска (а=х0).
2. Определить координату точки b (b=a+h), а также значе
ния функции в точках а и b: F(a) и F(b).
3. Проверить условие F(a)*F(b)<0. Если условие не выпол
нено - передвинуть интервал [а,Ь] на один шаг (а=Ь) и перейти к пункту 2.
• Если условие выполнено - закончить алгоритм.
Решением являются координаты точек а и Ь. Отрезок |а,Ь] содержит корень уравнения, поскольку функция F(x) на его концах имеет разные знаки.
