8. Охарактеризуйте теоретичні аспекти та практичні підходи до реалізації наступних алгоритмів сортування даних у нелінійних структурах: пірамідальне сортування.

Сортування даних (англ. Heapsort) – алгоритм сортування на основі порівнянь. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага – швидкодія у найгіршому випадку рівна (n log n). Є не стабільним алгоритмом.

Опис алгоритму

Нехай A[1 .. n] — деякий масив. Зіставимо йому дерево, використовуючи такі правила:

1. A[1] - корінь дерева.

2. Якщо A[i] - вузол дерева і 2i , то A[2*i] - вузол - “лівий син” вузла A[i].

3. Якщо A[i] - вузол дерева і 2i + 1 , то A[2*i+1] - вузол - “правий син” вузла A[i].

Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:

4. Якщо A[i] - вузол дерева та i > 1, то A[i mod 2] - вузол - «батько» вузла A[i];

Достоинства

• Имеет доказанную оценку худшего случая .

• Сортирует на месте, то есть требует всего O(1) дополнительной памяти (если дерево организовывать так, как показано выше).

Недостатки

• Сложен в реализации.

• Неустойчив — для обеспечения устойчивости нужно расширять ключ.

• На почти отсортированных массивах работает столь же долго, как и на хаотических данных.

• На одном шаге выборку приходится делать хаотично по всей длине массива — поэтому алгоритм плохо сочетается с кэшированием и подкачкой памяти.

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

Сортировка слиянием при расходе памяти O(n) быстрее ( с меньшей константой) и не подвержена деградации на неудачных данных.

Из-за сложности алгоритма выигрыш получается только на больших n. На небольших n (до нескольких тысяч) быстрее сортировка Шелла.

9. Охарактеризуйте теоретичні аспекти та практичні підходи до реалізації наступних алгоритмів пошуку даних: послідовний та бінарний пошук.

Лінійний (послідовний) пошук базується на прямому переборі елементів послідовності. Загальною властивістю алгоритмів послідовного пошуку є те, що час пошуку пропорційний кількості елементів послідовності. Проте якщо послідовність впорядкувати, то пошук можна здійснити більш раціонально.

Бінарний (двійковий) пошук застосовується лише до впорядкованої послідовності. Його суть: у послідовності   вибирається середній елемент  . З ним порівнюється шукане ім’я. Якщо вони співпадають, пошук завершено. Якщо ім’я у середині списку менше шуканого, продовжуємо пошук у правій частині списку, якщо більше – в лівій. Так продовжуємо до тих пір, доки або не знайдемо ім’я або ділити буде нічого. Цей метод значно швидший за лінійного методу. Проте він застосовується лише до впорядкованої за зростанням або спаданням послідовності.

10. Охарактеризуйте теоретичні аспекти та практичні підходи до реалізації наступних алгоритмів пошуку даних: метод інтерполяції та метод «золотого перерізу».

Інтерполяція – це спосіб побудови рядів динаміки за попередній пері­од, коли з якихось причин були відсутні відомості про розміри явища, або для знаходження невідомих проміжних рівнів ряду динаміки. Відсутність цих даних може бути обумовлена різними причинами: був відсутній облік цих явищ в попередній час, змінилася методика обчислення показника тощо. Для того щоб обчислити невідомі рівні ряду динаміки, провадять математичні розрахунки різної складності.

Невідомі рівні ряду динаміки знаходять або на базі сусідніх відомих зна­чень ряду динаміки шляхом обчислення їх середньої арифметичної простої, або на базі взаємозв`язку цього явища з іншими, кількісний вираз яких відо­мий. При застосуванні методу інтерполяції робиться припущення, що загаль­на тенденція, яку ми маємо зараз, мала місце і в попередній інтервал часу. Завжди при застосуванні цього методу проводяться математичні розрахунки різної складності.

Наприклад, таким чином можна обчислити населення країни протягом року, тому що офіційна статистика обов`язково наводить дані лише на поча­ток кожного року.

Інтерполяція дає змогу приблизно відобразити ті закономірності, які склалися протягом певного періоду.

Метод золотого перерізу - метод пошуку значень дійсно-значної функції на заданому відрізку. В основі методу лежить принцип поділу в пропорціях золотого перерізу. Найбільш широко відомий як метод пошуку екстремуму у вирішенні задач оптимізації.

На першій ітерації заданий відрізок ділиться двома симетричними відносно його центру точками і розраховуються значення в цих точках. Після чого той з кінців відрізка, до якого серед двох знову поставлених точок ближче виявилася та, значення в якій максимально (для випадку пошуку мінімуму), відкидають. На наступній ітерації в силу показаного вище властивості золотого перерізу вже треба шукати лише одну нову точку. Процедура триває до тих пір, поки не буде досягнута задана точність.