Алгоритми та структури даних

Алгоритми та структури даних

Що таке структура даних? За якими критеріями можна класифікувати структури даних? Приклади.

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

Структури даних діляться на:

- Лінійні. Структури в яких елементи ніяк між собою не зв’язані. такі структури зберігаються у

ü Масив (векторне представлення)

ü Список, черга, стек (зв’язане представлення)

ü Асоціативній масив, масив в якому елементи мають не індекс, а строкове значення (ключ, ім’я…)

- Не лінійні. Структури в яких елементи мають звязок один з одним. Такі структури сберігаються у кучі (heap)

ü Дерево (бінарне, N-арне)

ü Хеш-таблиця

 

Якими способами розміщуються елементи структур даних у пам’яті? Приклади.

Що таке рекурсивна функція? Які особливості її реалізації? Приклад.

Рекурсивна функція - це функція, що викликає саму себе.

Особливості реалізації:

1. Рекурсивна функція не може викликати себе до безкінечності.

2. Рекурсивна функція завжди повинна мати умову завершення.

3. Кожен наступний виклик виконується зі зменшенням значення параметрам функції.

Приклад:

Вираховування факторіала, рекурсивний алгоритм

int fucktorial(int n)

{

if (n == 0) //Условие выхода из рекурсии

return 1;

return n*fucktorial(n - 1);

}

Теж саме, тільки без рекурсії

int fact(int n)

{

if(n == 0)

return 1;

int temp = 1;

for(int i = 1; i <= n; i++)

temp = temp * i;

return temp;

}

 

 

4. Як визначається структура даних «множина». Що таке хеш-таблиця? За якими критеріями можна класифікувати хеш-таблиці?

Множиною - називається скінченний набір однотипних даних.

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

Їх можна класифікувати за методами хешування:

ü Метод ділення

ü Метод множення

ü Метод універсального хешування

 

Для чого призначено хешування? Які є методи хешування?

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

Є 3 алгоритми отримання хеш ключа.

1. Ділення.

int GetHash(int key)

{

return (int)Key % size;

}

2. Множення.

int GetHash(int key)

{

double temp = key * 0.6130; //золота середина

temp = temp – (int) temp;

return (int);

}

3. Подвійний хеш. Полягає в тому щоб використовувати суму двох хеш ключів одночасно.

 

За яких умов у хеш-таблиці виникають колізії? Якими способами вони вирішуються?

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

ü Лінійне зондування

ü Квадратичне зондування

ü Подвійне зондування

 

Як визначається структура даних «дерево»? Які є види дерев? Якими способами здійснюється обхід бінарного дерева?

Дерево - одна з найпоширеніших структур даних. Формально дерево визначається як скінченна множина Т з однієї або більше вершин (вузлів, nodes), яке задовольняє наступним вимогам:

1. існує один відокремлений вузол — корінь (root) дерева

2. інші вузли (за виключенням кореня) розподілені серед m ≥ 0 непересічних множин T1…Tm і кожна з цих множин в свою чергу є деревом. Дерева T1…Tm мають назву піддерев (subtrees) даного кореня.

Види дерев (їх набагато більше, але тут основні):

1. Бінарне дерево. Дерево, кожен вузол якого має лише 2 посилання на 2 вузла,

лівій і правий. Правило за яким елементи додаються до такого дерева: якщо ключ

нового елемента більше ніж вузол, то перехід до правої гілки, якщо менше то до

лівої, якщо рівні то додавання не здійсниться. Якщо права чи ліва гілка відсутня

(яка саме залежить від значень ключем вузла та нового елемента) то замість

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

2. AVL дерево. Схоже на бінарне, але, елементи мають по 3 посилання на 3 вузли. Правила майже теж саме, але у випадку коли ключ нового елемента збігається з ключем вузда, то буде перехід то центральної гілки.

3. N-арне дерево. Дерево, кожен вузол якого має безліч посилань на наступні елементи.

4. Окто дерево. Дуже схоже на бінарне, але на відміну від бінарного, окто дерево має рівно 8 посилань

Э 3 алгоритми базові обходу дерев

1. Послідовний (Лівий, Правий, Вузол) (ЛПВ), всі елементи будуть виведені як відсортований масив, за збільшенням ключа.

2. Паралельний (Лівий, Вузол, Правий) (ЛВП)

3. В ширину (Вузол, Лівий, Правий) (ВЛП) пояснення:

Лівий – перехід до лівого вузла та повтор формули для нього

Правий – перехід до правого вузла та повтор формули для нього

Вузол - вивід значення даного вузла

 

Яким чином видаляються вузли дерева залежно від їх розташування?

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

1. Якщо у вузла z немає дочірніх вузлів, то ми просто змінюємо його батьківський вузол р[z], замінюючи в ньому покажчик на z значенням NULL.

2. Якщо у вузла z лише один дочірній вузол, то ми видаляємо вузол z, створюючи новий зв'язок між батьківським і дочірнім вузлом вузла z.

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

 

У чому полягає принцип «розділяй і пануй»? Як він застосовується у задачі «ханойські вежі»?

Принцип "розділяй і пануй": задача розвивається на під задачі і рішення під задачі призводить до отримання вирішення всієї задачі.

Реалізація задачі “ханойська вежа”

void nahoi (int N, int d)

{

if(N == 0)

return;

hanoi(N-1, -d);

move(N, d);

hanoi(N-1, -d);

}

 

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

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

Види динамічного програмування:

1. Ввисхідне динамічне програмування

2. Низсхідне динамічне програмування

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

 

Як визначається поняття «алгоритм»? Які його властивості?

 

Алгоритм — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій. При написанні комп'ютерних програм алгоритм описує логічну послідовність операцій. Для візуального зображення алгоритмів часто використовують блок-схеми.

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

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

- Дискретність. Процес, що визначається алгоритмом, можна розчленувати (розділити) на окремі елементарні етапи (кроки), кожен з яких називається кроком алгоритмічного процесу чи алгоритму.

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

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

- Вихідні дані. Алгоритм має одне або декілька вихідних даних, тобто, величин, що мають досить визначений зв'язок із вхідними даними.

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

- Масовість. Властивість алгоритму, яка полягає в тому, що алгоритм повинен забезпечувати розв'язання будь-якої задачі з класу однотипних задач за будь-якими вхідними даними, що належать до області застосування алгоритму.

 

Алгоритм вибірки

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

2. Знайдений елемент міняються місцями з першим.

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

4. Знайдений елемент міняються місцями з крайнім лівим елементом.

5. П.3 і п. 4 повторюється до тих пір, поки дані не будуть впорядковані.

Недоліки - ступінь впорядкованості даних до сортування мало впливає на час виконання.

Алгоритм вставки

1. Набір даних ділиться на дві частини впорядкованості і не впорядковану;

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

3. Всі дані, які повинні стояти після нього зміщається вправо;

4. Даний елемент розміщуються в позиції, що звільнилася.

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

 

Алгоритм Шелла

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

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

 

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

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

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

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

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

 

Математичний аналіз

Застосовується якщо:

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

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

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

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

 

Алгоритми та структури даних