Класифікація

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

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

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

4. Пошук ідентифікуванням по ключу

5. Дерево бінарного пошуку (Binary search tree BST)

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

19. Опишіть сутність послідовного, бінарного та інтерполяційного пошуку.

Послідовний пошук – використовується для набору даних організованого в виді масиву або списку (упорядкованого або неупорядкованого)

Бінарний пошук – набір ділиться на дві частини, далі представляється частина до якої належить деякий елемент, далі пошук здійснюється в відповідній частині.

Якщо до універсального набору даних використати принцип «Розділяй та пануй», то отримаємо бінарний пошук.

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

20. Дайте визначення BST-дерева і наведіть особливості реалізації пошуку на основі таких дерев.

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

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

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

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

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

Реализация:

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

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

3. Ротация…

21. Опишіть операції "ротація-вліво" і "ротація-вправо", наведіть їх призначення та приклад.

Ротація – це перетворення дерева, яке основане на обміні кореня з його дочірнім вузлом при збереженні порядку послідовності ключів в вузлах BST – дерева.

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

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

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

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

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

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

22. Наведіть методи балансування BST-дерева, приклади.

Поиск на БСТ- деревьях работает с гарантированной производительностью только при условии сбалансированности дерева, т.е. когда все внешние узлы находятся на одном уровне (высоте) или последнем и предпоследнем уровнях.

Є кілька способів балансування BST дерева:

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

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

3. Оптимізація – використання вузлів з деякими ключами і зв’язками, нисхідні дерева 2-3-4

23. Опишіть сутність алгоритмів порозрядного пошуку, визначите DST-дерева та TST-дерева.

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

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

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

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

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

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

24. Розкрийте необхідність аналізу алгоритмів, наведіть методи аналізу.

Аналіз алг – це спосіб передбачення необхідних ресурсів (час виконання і об’єм памяті) для його виконання (оцінка його ефективності). Використовується як на етапі розробки так і на етапі реалізації. Розглядувані методи аналізу використовуються для алгоритмів, вирішующих 1 і туж задачу.

Бла-бла… Математичний аналіз, емпіричний аналіз.

25. Поясните сутність емпіричного аналізу алгоритмів, його особливості й причини застосування.

Емпіричний аналіз(експериментальний ) – вичислення часу виконання шляхом запуску на виконання реалізованих алгоритмів.

Припущвення при емпіричному аналізі:

(реалізація)

• Алгоритми реалізовані на одній і тій же мові програмування

• Реалізація алгоритмів відбувається з однаковою ретельністю.

• Виконуваний код (програма) алгоритмів був отриманий з використанням одного і тогож середовища програмування.

• Виконання алгоритмів відбувається на тій самій машині.

(вихідні дані)

• Використання реальних даних (точне вимірювання часу виконання)

• Використання випадкових значень (для виміру середнього часу виконання)

• Використання незвичайних даних (виміювання найгіршого випадку)

26. Поясните сутність математичного аналізу, його особливості й причини застосування.

Математичний аналіз – вирахування відносного часу виконання шляхом побудови математичного виразу.

Математичний аналіз використовується якщо:

• Відсутня реалізація алгоритму

• Необхідно передбачити час виконання алгоритму в новому середовищі

• Зрівнюються різні алгоритми, призначені для вирішення одної задачі.

27. Дайте поняття "рост-функція", призначення. Наведіть типи рост-функцій.

Рост-функція – прості математичні формули , за допомогою яких визначається залежність часу виконання алгоритму від головного параметра.

Типи рост-функцій:

1 – постоянное время выполнения (почти все операции выполняются один раз или несколько).

Например, поиск индексированием по ключу.

N –линейное время выполнения (если каждый элемент подвергается обработке).

Например, последовательный поиск.

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

Например, бинарный поиск.

NlogN – время выполнения, пропорциональное NlogN (задача разбивается на подзадачи, решения которых затем объединяются).

Например, нисходящая сортировка слиянием.

N^2- квадратичное время выполнения (когда обрабатываются все пары элементов – двойные циклы).

Например, сортировка алгоритмом вставки в наихудшем случае.

N^3- кубическое время выполнения (тройные циклы). Например, сортировка двумерного массива по значениям одной строки алгоритмом пузырька.

2^N- экспоненциальное время выполнения (прямое решения задачи).

28. Поясніть "q-нотацію", "О-нотацію", "W-нотацію".

-нотацію –«тета нотація» - математичний запис асимптотичної оцінки

Т(n) = (g(n)), де (g(n)) множина ф-цій, для яких справедливий вираз f(n) є (g(n)), якщо існують константи с₁, с₂, n_0….

Визначення асимптотичної верхньої границі називається О-нотацією. Через О-нотацию описывается наихудший случай. Например, сортировка по возрастанию алгоритмом вставки массива, если исходно он упорядочен по убыванию.

Визначення асимптотичної нижньої границі називається -нотацією. Через омега-нотацию описывается наилучший случай. Например, массив данных уже упорядочен.