Главная Обратная связь

Дисциплины:






Тема 3-4. Алгоритми сортування



Охарактеризуйте алгоритми класу NP.

К классу NP относятся задачи, которые могут быть решены за полиномиально выраженное время с помощью недетерминированной вычислительной машины, то есть машины, следующее состояние которой не всегда однозначно определяется предыдущими. Работу такой машины можно представить как разветвляющийся на каждой неоднозначности процесс: задача считается решённой, если хотя бы одна ветвь процесса пришла к ответу.

Примітка:

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

2. Назвіть варіанти розв‘язку NP-повних задач.

Методом проб і помилок, повторів або випадкового вибору.

3. Опишіть покроково рекурсивний алгоритм.

4. Охарактеризуйте зв‘язок та NP-повних задач та наближених алгоритмів.

Тема 3-4. Алгоритми сортування

Рівень ІІІ

http://vns.lp.edu.ua/moodle/mod/page/view.php?id=56494

http://vns.lp.edu.ua/moodle/mod/page/view.php?id=56494

1. Метод простої вибірки. Записати складність алгоритму.

O(n2)

2. Метод бульбашки. Записати складність алгоритму.

O(n2)

3. Швидкий метод сортування. Записати складність алгоритму.

O(n*log2n)

4. Метод сортування включенням. Записати складність алгоритму.

При сортуванні включенням до відсортованої множини R кожний раз приєднується один елемент, а саме: із невідсортованої вхідної множини М вибирається довільний елемент і розміщується у вихідну множину R.

Вихідну множину R при кожному включенні можна відсортовувати відомим методом сортування, наприклад, методом простої вибірки. Майже всі методи сортування включенням у найгіршому випадку вимагають порядку n2 порівнянь, тому їх застосування пов‘язане з деяким ризиком. Є багато варіантів цього методу сортування.

5. Метод Шелла. Записати складність алгоритму.

O(n1.2)

6. Метод сортування розподілом. Записати складність алгоритму.

Виходячи із лекцій Коротєєвої, сортування розподілом – це і є цифровий алгоритм сортування (див. п.8).

7. Метод сортування злиттям. Записати складність алгоритму.

Вся процедура злиття разом вимагає не більше ніж n порівнянь для n елементів i потрібно буде виконати log2 n переходів із однієї множини у другу. Тобто алгоритм С вимагає пlog2 n порівнянь.

Час роботи алгоритму злиття T(n) для n елементів задовольняє рекурентному співвідношенню: T(n) = 2∙T(∙n/2) + O(n), де T(∙n/2) - час на впорядкування половини масиву, O(n) - час на злиття цих половинок. Враховуючи, що T(1) = O(1), розв’язком співвідношення є: T(n) = O(n∙log(n)).



8. Цифровий алгоритм сортування. Записати складність алгоритму.

O(m*n), де m – кількість цифр, а n – к-сть елементів.

Тема 5-6. Дерева. Основні визначення та поняття. Бінарні дерева. Зображення в пам‘яті ЕОМ графоподібних структур. Алгоритми обходу дерев.Висхідні, нисхідні, змішані алгоритми обходу дерев.

РівеньІ

1. Що називають степеню вершини?

 

2. Яке дерево називається кореневим?

Кореневим деревом називають орієнтований граф, у якого:

· є одна особлива вершина, в яку не заходить жодне ребро і яку називають коренем дерева;

· у всі інші вершини заходить рівно одне ребро, а виходить скільки завгодно;

· немає циклів.

3. Чому дорівнює степінь листка?

0 (не має синів)

4. Що таке довжина шляху?

Довжина шляху - це кількість дуг, які треба пройти від кореня для досягнення даної вершини.

5. Що таке рівень, aбo ранг, вершини дерева?

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

6. Що таке висота дерева?

Висота дерева дорівнює кількості рівнів у дереві.

РівеньІІ

7. Як описується вершина-"син"у позиційному дереві?

8. Які існують алгоритми обходу дерев?

а) бінарне дерево; б) низхідний обхід: зверху вниз;

в) змішаний обхід: зліва направо; г) висхідний обхід: знизу – вверх.

9. Що таке бінарне дерево?

Бінарним називають таке 2-арне дерево, в якого один потомок є лівим, а другий - правим.

10. Яке дерево називають збалансованим?

Бінарне дерево з m вершинами називають збалансованим, якщо різниця між рівнями будь-яких двох вершин не більша від одиниці.

РівеньІІІ

11. Способи зображення графів в пам‘яті комп‘ютера.

Отже, для зображення в пам‘яті графів існує декілька способів:

1) використовується матриця (або матриця суміжності, або матриця інцедентності), яка зберігається стандартним способом у векторній пам‘яті;

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

3) використовується спискова динамічна структура, де для кожної нової підмножини пам‘ять виділяється в процесі побудови фрагмента графа.

12. Які способи зображення дерев в пам‘яті комп‘ютера є оптимальними?

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

13. В якому випадку не потрібно зберігати інформацію про ребра?

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

14. Метод сортування на деревах - метод вибірки з дерева. Записати складність алгоритму.

Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 6.1 видно, що задана послідовність буде впорядкована у низхід­ному порядку за 10-1=9 кроків.

Сумарний час виконання такого сортування приблизно пропорційний величині п log2 n . Існує декілька модифікацій цього алгоритму, які скорочують цей час .

15. Алгоритм побудови бінарного дерева згортання. Записати складність алгоритму

Дуже довго і муторно все описано. У парі картинок:

Послідовність ключів K1 , К2... К n називають "пірамідою", якщо Kj < Ki при 2<j<n. i =[ j /2] - ціла частина від j/2 .

Бінарне дерево розміщується послідовно таким чином, що індекси лівого і правого "синів" запису будуть мати відповідно значення і 2і+1. Навпаки, індекс "батька" запису буде мати значення [j/2]. Якщо знайдено пірамідальне зображення таблиці, то запис з найбільшим ключем знаходиться в корені дерева.

 

Тема 8. Лінійні структури даних. Стеки, черги, деки. Організація стеків, черг і деків. Види черг. Представлення лінійнихї структур в комп‘ютері. Операції додавання та видалення елементів з лінійних структур.

Рівень І

16. Стек – це…

Стек - це впорядкована лінійна динамічно змінювана послідовність елементів, в якій виконуються наступні умови:

1) новий елемент приєднуєть­ся завжди до одного і того ж боку послідовності;

2) доступ до елемента здійснюється завжди з того боку послідовності, до якого приєднується елемент;

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

17. Деки – це…

Деки - це впорядкована лінійна динамічно змінювана послідовність елементів, в якій виконуються такі умови:

1) новий елемент може приєднуватися з обох боків послідовності;

2) вибірка елементів можлива також з обох боків послідовності.

18. Черга – це…

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

1) новий елемент приєднується завжди з одного і того ж боку послідовності;

2) доступ до елементів aбo їх виключення завжди здійснюється з другого боку послідовності.

19. Лінійна черга це…

Звичайна лінійна черга може бути зображена масивом, з двома вказівниками: перший вказує на елемент для вибірки з черги, другий - на останній елемент, записаний у чергу.

20. Пріоритетна черга це…

Чергу, для якої є можливість включати або виключати елементи з певної позиції в залежності від деяких її характеристик називають пріоритетною чергою. Прикладом пріоритетної черги може служити порядок розв'язування потоку задач на комп‘ютері у деяких операційних системах . Така черга зводиться до послідовності лінійних черг, якщо відомі пріоритети її елементів. Кожна черга з послідовності обслуговується за дисципліною FIFO , але елементи з другої черги обслуговуються тільки тоді, коли порожня попередня черга, а з третьої тоді, коли порожні перша і друга черги. При включенні елементи приєднуються до боку однієї з черг згідно з їх пріоритетом.Циклічна черга це …

Рівень ІІ

1. Перевагою стека перед іншими організаціями даних є…

Основною перевагою стека перед іншими організаціями даних є те, що у ньому не потрібна адресація елементів. Для обслуговування стека потрібно лише дві команди: PUSH -"проштовхнути" iPOP - "виштовхнути". Зі стеком пов'язаний завжди один вказівник, який вказує на верхній елемент у стеку.

Рівень ІІІ

1. Галузі застосування стеків.

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

2. Операції над лінійними структурами даних. Їх реалізація.

а) створення нової структури даних;

б) запис або включення елемента у вже існуючу структуру даних;

в) виключення елемента зі структури;

г) перевірка умови існування структури.

 

 





sdamzavas.net - 2017 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...