У чому полягає сутність базового алгоритму пірамідального сортування. Які відмінності його реалізації у разі використання черги за пріоритетом.

Приклад реалізації пірамідально го базового сортування з використанням черги за пріоритетом:

Створити посту чергу -> зі отримувати чергу, використовуючи ввисхідну вставки (встановку), з елементів вихідні го набору даних -> видалити елементи черги, використовуючи низсхідним вставкк (встановку), виконуючи по цьому впорядковане перегрупування початкового набору даних.

 

Пірамідальний алгоритм сортування даних – алгоритм сортування на основі порівнянь. Хоча, на практиці, він трохи повільніший на більшості машин, ніж швидке сортування, у нього є перевага – швидкодія у найгіршому випадку рівна (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];

 

У чому полягає сутність групи алгоритмів порозрядного сортування?

Сортування, построєне на обробку даних (значення ключа) по одній позиції (розряду) на крок, називається порозрядною.

Алгоритми, построєні на сортуванні об'єктів з ключами, де ключі розглядаються як числа, представлені в деякий системі числення та обробка чисел виконується поруіями (цифрами) за один крок.

Існує два базових підходи до порозрядногосортування сортування:

1. По старшій цифрі (порозрядне сортування most significant digit, MSD)

2. По молодшій цифрі (порозрядне сортування least significant digit, LSD)

В залежності від контексту ключем в порозрядному сортуванні може бути рядок, чи слово.

Рядок – це послідовність розрядів змінної довжини.

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

Передбачається, що нумерація розрядів починається зліва зі значення 0.

 

21. Як визначається поняття "пошук"? За якими критеріями класифікуються алгоритми пошуку?

Пошук - це процес отримання інформації (даних) із деякого інформаційного простору з ціллю її обробки.

Ефективність алгоритмів пошуку інформації залежить від впорядкованості і структурованості даних.

Вважається, що зберігаються у вигляді записів, що мають ключ, що використовується пр пошуку.

Пошук інформації основується на операції порівняння, результатом якої являється повідомлення про успішний (попаданя) та не успішний (промах) пошук.

Класифікації алгоритмів пошуку:

1. Послідовний пошук;

2. Біднарний пошук;

3. Інтерполяціонний пошук;

4. Пошук індексуванням по ключу;

5. Дерево бін арешт пошуку (binary search tree, BST);

6. Порозрядною пошук.

 

У чому полягає сутність послідовного, бінарного та інтерполяційного пошуку?

Бінарний пошук

Якщо до впорядкованості набору даних додати принцип "розділяй і владарюй", то отримаємо бін принц пошук.

Суть - набір даних розділяється на дві частини, далі визначається частина, до якої належать шукав дані, далі пошук виконується у відповідній частині.

Інтерполяційний пошук

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

 

Як визначається BST-дерево? Як організовано пошук на основі BST-дерев?

Дерево бінарного пошуку (binary search tree, BST)

Ключ кожного вузла дерева має значення більше чи рівному значенню ключів його лівого під дерева і менше чи рівно - правого під дерева.

BST-дерево - це вже від сортований набір даних.

Стандартна реалізація операції пошуку для додавання вузла в дерево робить новий елемент зовнішнім вузлом.

Існує інший метод вставки, при якому новий елемент стає коренем, тобто всі останні виставлені вузли знаходяться коло вершини.

Двійкове (або Бінарне) дерево пошуку — двійкове дерево, в якому кожній вершині x співставлене певне значення val[x]. При цьому такі значення повинні задовольняти умові впорядкованості

• Нехай x — довільна вершина двійкового дерева пошуку. Якщо вершина y знаходиться в лівому піддереві вершини x, то val[y] ≤ val[x].

• Якщо у знаходиться у правому піддереві x, то val[y] ≥ val[x].

Таке структурування дозволяє надрукувати усі значення у зростаючому порядку за допомогою простого алгоритму центрованого обходу дерева.

Представляється таке дерево вузлами наступного вигляду:

Бінарні дерева пошуку набагато ефективніші в операціях пошуку, аніж лінійні структури, в яких витрати часу на пошук пропорційні O(n), де n — розмір масиву даних, тоді як в повному бінарному дереві цей час пропорційний в середньому O(log2n) або O(h), де h — висота дерева (хоча гарантувати, що h не перевищує log2n можна лише для збалансованих дерев, які є ефективнішими на пошукових алгоритмах, аніж прості бінарні дерева пошуку).

Процедура пошуку починається з кореня дерева і проходить вниз по дереву. Для кожного вузла х на шляху вниз його ключ key[x] порівнюється з переданим в якості параметра ключем k. Якщо ключі однакові, пошук завершується. Якщо k менше key[х], пошук триває в лівому піддереві х; якщо більше - то пошук переходить в праве піддерево.

 

24. Для чого призначені операції "ротація-вліво" і "ротація-вправо"? Як вони виконуються?

Ротація вправо - місцями змінюються корінь і його лівий вузол:

ü Старий корінь стає правим піддеревом нового корня;

ü Праве піддерево нового кореня стає лівим піддеревом старого кореня.

Ротація вліво - місцями міняються корінь і його правий вузол:

ü Старий корінь стає лівим піддеревом нового кореня;

ü Ліве піддерево нового кореня стає правим піддеревом старого кореня.

 

 

Для чого призначене балансування BST-дерева? Чим розрізняються методи балансування?

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

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

Існує 3 основні алгоритми балансування.

1. Рандомізація. За таким алгоритмом балансування виконується шляхом випадкової ротації при додаванні нового елемента.

2. Амортизація. Кожен елемент спочатку додається до дерева по звичайним правилам, потім за допомогою ротації піднімається в корінь.

3. Оптимізація.

 

У чому полягає сутність алгоритмів порозрядного пошуку? Приклад.

При пошуку елемента значення ключа оцінюється порціями, а не повністю.

Простий порозрядний пошук основується на використанні дерев цифрового пошуку (digital search trees, DST).

Використання DST-дерев ефективно для дуже великого набору даних з невеликий значеннями ключів, по скільки час пошуку обмежується тільки довгого ключа.

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

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

Якщо значенням ключа є рядок символів, тоді для порозрядного сортування пошуку даних можна використовувати дерево тренер нього пошуку (ternary search tree, TST- дерево).

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