ПИТАННЯ

модуля 1

1. Дайте визначення структури даних і наведіть класифікацію, приклади.

Структура даних – це спосіб організації даних в комп’ютері. Розрізняють лінійні(список, стек, дек) та нелінійні (дерево, хеш- таблиці) структури даних.

2. Дайте визначення такої структури даних як «дерево», наведіть його класифікацію, приклади і способи переміщення по дереву.

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

Типи дерев :

1. Вільне дерево – неупорядковані дерева з багатьма зв’язуваннями

2. Дерево з корнем – певний вузол дерева наз. корнем і і він не має інших вузлів над собою

3. Упорядковане дерево – кожен вузол має довільну кількість вузлів.

4. Бінарне дерево – кожен вузол зв’язаний тільки з парою дерев , які називаються праве та ліве.

Способи переміщення по дереву: обхід в ширину, послідовний, паралельний.

3. Дайте визначення такої структури даних як «хеш-таблиця» і наведіть класифікацію, приклади.

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

В зависимости от способа использования ключей объектов различаю:

- таблицы с прямой адресацией

- хеш-таблицы (динамические)

- хеш-таблицы с открытой адресацией.

Для представления множества объектов идентифицируемых ключом, используется массив, в котором индекс соответствует значению ключа.

Хеш-таблицы (динамические)

Для вычисления индекса элемента в массиве используется хеш-функция.

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

Если объекты попадают под один индекс, то они связываются как лист

4. Опишіть способи реалізації хеш-функції (перетворення ключа в індекс).

Методы хеширования:

1) Метод деления.

а) значение ключа – целое положительное число (или ключ легко можно представить таким числом);

б) делитель – простое число далекое от степени двойки.

Индекс (хэш-код) вычисляется путем деления значения ключа на размерность хеш-таблицы, а остаток от деления и будет индексом расположения ключа в таблице.

2) Метод умножения.

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

Б) множитель – значение равное степени двойки.

Индекс вычисления по следующему алгоритму:

1. Ключ умножается на константу из диапазона от 0 до 1 для выделения дробной части (0,6180339887).

2. Полученное значение делится на размерность хэш-таблицы и округляется до меньшего целого.

3) Метод универсального хеширования. Индекс – вычисляется с использованием хэш-функции, случайно выбираемой из некоторого отобранного класса функций.

5. Опишіть способи вирішення колізії в хеш-таблицях з відкритою адресацією.

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

Коллизии осложняют использование хеш-таблиц, так как нарушают однозначность соответствия между хеш-кодами и данными.

Открытая адресация

А) идеальное хэширование

Б) линейное хэширование

В) двойное хэширование

В массиве H хранятся сами пары. В случае возникновения коллизии, алгоритм поиска (удаления, добавления) объекта просто перемещается на ячейку вправо до момента разрешения коллизии. Разрешение коллизии происходит при достижении пустой ячейки или ячейки, в котором хранится пара с заданным ключом.

Размер шага смещения вправо может зависеть от значения ключа и вычисляться с помощью второй хэш-функции. Данная техника называется двойным хэшированием с открытой адресацией.

Ниже представлен простой код её демонстрирующий.

Открытая адресация: В отличие от хеширования с цепочками, при открытой адресации никаких списков нет, а все записи хранятся в самой хеш-таблице. Каждая ячейка таблицы содержит либо элемент динамического множества, либо NULL.

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

Алгоритм - це послідовність дій, яка веде до кінцевого результату.

Властивості алгоритму:

- Дискретність; Детермінованість ; Зрозумілість ; Завершеність (кінцівку) ; Масовість ; Результативність ;

- Алгоритм не містить помилок, якщо він дає правильні результати для будь-яких допустимих вихідних даних.

7. Дайте поняття рекурсії, наведіть її особливості, приклад.

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

Рекурсивный алгоритм – это алгоритм, который решает задачу путем решения нескольких узких вариантов той же задачи.

Рекурсивная функция – это ф-ция, которая вызывает сама себя.

Особености:

РФ не может вызывать себя до бесконечности, т.е. должна иметь конечное количество вызовов.

РФ всегда должна иметь условие завершения.

Каждый последующий вызов осуществляется с уменьшением значения параметре ф-ции.

8. Поясніть принцип «розділяй і пануй», опишіть його застосування на прикладі задачі о «ханойській вежі».

Разделя́й и вла́ствуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче. Разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.

Рекурсивный вариант решения задачи можно описать так:

Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду.

Если число дисков равно одному, тогда:

Передвиньте диск из источника в задание

В противном случае:

Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас

Передвиньте оставшийся диск из источника в задание

Передвиньте все диски из запаса в задание используя источник как запас