- •Открытая адресация
- •Особености:
- •Поясніть принцип «розділяй і пануй», опишіть його застосування на прикладі задачі о «ханойській вежі».
- •Дайте поняття динамічного програмування і наведіть класифікацію, приклади.
- •Алгоритми швидкого сортування
- •Класифікація:
- •Класифікація
- •Дерево бінарного пошуку (binary search tree, bst)
Дайте поняття динамічного програмування і наведіть класифікацію, приклади.
Таким чином, в назві "Динамічне програмування" під "Програмування" розуміють "прийняття рішень", "планування", а слово "динамічне" вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.
Динамическое программирование обычно придерживается двух подходов к решению задач:
Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
Восходящее ДП: Все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего ДП в смысле размера необходимого стэка и количества вызова функций, но иногда бывает нелегко заранее выяснить решение каких подзадач нам потребуется в дальнейшем.
Методи динамічного програмування є складовою частиною методів, ЯКІ використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)
Дайте поняття терміну "сортування" і визначте групи алгоритмів сортування.
Сортування – це процес упорядкування інформації за певними правилами.
Случаи сортировки
1.Применительно к самим данным;
2.Применительно к ключам, ассоциируемых с данными;
Групи алгоритмів сортування:
Елементарні алгоритми сортування
Алгоритми швидкого сортування
Алгоритми злиття і сортування
Алгоритми пірамідального сортування
Алгоритми порозрядного сортування.
Опишіть сутність алгоритмів групи елементарного сортування (вибору, вставки, бульбашки, Шелла).
Метод вибору
1) В наборе данных отыскивается наименьший элемент
2) Найденный элемент меняется местами с первым
3) В оставшейся неупорядоченной части набора данных отыскивается следующий наименьший элемент
4) Найденный элемент меняется местами с крайним левым
5) П3 и п4 повторяется до тех пор, пока данные не будут упорядочены
Недостаток – на время выполнения степень упорядоченности не влияет.
Сортування методом вставки
1) Набор упорядоченных данных делится на две части: упорядоченную и неупорядоченную
2) Каждый элемент набора данных из неупорядоченной части анализируется и определяется место его размещения уже среди отсортированных данных
3) Все данные, которые должны стоять после него, смещаются вправо
4) Данный элемент помещается в освободившуюся позицию.
В отличии от сортировки выборкой время выполнения зависит от исходного порядка упорядоченных данных.
Сортування методом бульбашки
Суть – выполняется многократный циклический проход по набору данных с выполнением обмена соседних элементов, нарушающих требуемый порядок.
Метод Шелла – Суть - расширенный метод сортировки вставкой, в котором осуществляется обмен не только соседними данными, а и находящимися далеко друг от друга.
Набор данных разбивается на независимые поднаборы, которые являются пресекающимися, и в каждом поднаборе используется сортировка алгоритмом вставки.
На практике используется убывающая последовательность шагов близкая к геометрической прогрессии.
Кнут предложил следующую последовательность шагов:
1 4 13 40 121
Т.е. формула: (h = h * 3 + 1)
Опишіть сутність алгоритмів групи елементарного сортування (по покажчиках, по індексам, розподільного підрахунку).
Сортировка по индексам и указателям
Применяется для непростых типов данных.
Суть – сортировке подлежит не сам набор данных, а массив ссылок (указателей на элементы набора данных) или индексный массив (элементы – это индексы элементов набора данных).
Сортировка методом распределяющего подсчета
Применяется для наборов данных, элементы которых идентифицируются ключом описываемым целым значением из диапазона [0; M] (ключи можно использовать в качестве индексов элементов).
Суть – сначала подсчитывается количество ключей для каждого значения ключа в массиве индексов, потом вычисляются частичные суммы (для каждого значения ключа подсчитывается количество ключей с меньшими значениями), затем в дополнительный массив переписываются ключи в соответствии с вычисленными значениями, а затем упорядоченный дополнительный массив переписывается в массив индексов.
Опишіть сутність алгоритмів групи «швидкого» сортування, наведіть їхню класифікацію і відмінності.