9. Дайте поняття динамічного програмування і наведіть класифікацію, приклади.

Таким чином, в назві "Динамічне програмування" під "Програмування" розуміють "прийняття рішень", "планування", а слово "динамічне" вказує на суттєве значення часу та порядку виконання операцій в процесах і методах, що розглядаються.

Динамическое программирование обычно придерживается двух подходов к решению задач:

Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.

Восходящее ДП: Все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего ДП в смысле размера необходимого стэка и количества вызова функций, но иногда бывает нелегко заранее выяснить решение каких подзадач нам потребуется в дальнейшем.

Методи динамічного програмування є складовою частиною методів, ЯКІ використовуються при дослідженні операцій, і використовуються як у задачах оптимального планування, так і при розв'язанні різних технічних проблем (наприклад, у задачах визначення оптимальних розмірів ступенів багатоступеневих ракет, у задачах оптимального проектування прокладення доріг та ін.)

10. Дайте поняття терміну "сортування" і визначте групи алгоритмів сортування.

Сортування – це процес упорядкування інформації за певними правилами.

Случаи сортировки

1.Применительно к самим данным;

2.Применительно к ключам, ассоциируемых с данными;

Групи алгоритмів сортування:

1. Елементарні алгоритми сортування

2. Алгоритми швидкого сортування

3. Алгоритми злиття і сортування

4. Алгоритми пірамідального сортування

5. Алгоритми порозрядного сортування.

11. Опишіть сутність алгоритмів групи елементарного сортування (вибору, вставки, бульбашки, Шелла).

Метод вибору

1) В наборе данных отыскивается наименьший элемент

2) Найденный элемент меняется местами с первым

3) В оставшейся неупорядоченной части набора данных отыскивается следующий наименьший элемент

4) Найденный элемент меняется местами с крайним левым

5) П3 и п4 повторяется до тех пор, пока данные не будут упорядочены

Недостаток – на время выполнения степень упорядоченности не влияет.

Сортування методом вставки

1) Набор упорядоченных данных делится на две части: упорядоченную и неупорядоченную

2) Каждый элемент набора данных из неупорядоченной части анализируется и определяется место его размещения уже среди отсортированных данных

3) Все данные, которые должны стоять после него, смещаются вправо

4) Данный элемент помещается в освободившуюся позицию.

В отличии от сортировки выборкой время выполнения зависит от исходного порядка упорядоченных данных.

Сортування методом бульбашки

Суть – выполняется многократный циклический проход по набору данных с выполнением обмена соседних элементов, нарушающих требуемый порядок.

Метод Шелла – Суть - расширенный метод сортировки вставкой, в котором осуществляется обмен не только соседними данными, а и находящимися далеко друг от друга.

Набор данных разбивается на независимые поднаборы, которые являются пресекающимися, и в каждом поднаборе используется сортировка алгоритмом вставки.

На практике используется убывающая последовательность шагов близкая к геометрической прогрессии.

Кнут предложил следующую последовательность шагов:

1 4 13 40  121

Т.е. формула: (h = h * 3 + 1)

12. Опишіть сутність алгоритмів групи елементарного сортування (по покажчиках, по індексам, розподільного підрахунку).

Сортировка по индексам и указателям

Применяется для непростых типов данных.

Суть – сортировке подлежит не сам набор данных, а массив ссылок (указателей на элементы набора данных) или индексный массив (элементы – это индексы элементов набора данных).

Сортировка методом распределяющего подсчета

Применяется для наборов данных, элементы которых идентифицируются ключом описываемым целым значением из диапазона [0; M] (ключи можно использовать в качестве индексов элементов).

Суть – сначала подсчитывается количество ключей для каждого значения ключа в массиве индексов, потом вычисляются частичные суммы (для каждого значения ключа подсчитывается количество ключей с меньшими значениями), затем в дополнительный массив переписываются ключи в соответствии с вычисленными значениями, а затем упорядоченный дополнительный массив переписывается в массив индексов.

13. Опишіть сутність алгоритмів групи «швидкого» сортування, наведіть їхню класифікацію і відмінності.