8. Теорія алгоритмів (2017 р.)

ТЕОРІЯ АЛГОРИТМІВ

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторної роботи № 8

з дисципліни “Алгоритмізація та програмування, частина 2”

для студентів спеціальності 122 «Комп’ютерні науки та інформаційні технології»

 

Теорія алгоритмів: Методичні вказівки до лабораторної роботи № 8 / Укл.: В.А. Висоцька, Л.В. Чирун. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2017. – 10 с.

Укладачі

                                      Висоцька В.А., канд. техн. наук, доц.

                                      Чирун Л.В., канд. техн. наук, доц.

                           

 

Відповідальний за випуск Литвин В.В., доктор техн. наук., проф.

Рецензенти     Верес О.М., канд. техн. наук, доц.

                          Берко А.Ю., доктор техн. наук., проф.

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

            В результаті виконання лабораторних робіт студенти  повинні:

• знати поняття алгоритму, способи подання алгоритму, основні алгоритмічні конструкції, принципу проектування алгоритму "зверху-вниз" та покрокового уточнення алгоритму, типи даних, операції, визначені над даними різних типів.;
• вміти застосовувати різні форми опису алгоритмів, описувати розв’язки типових навчальних задач мовами програмування, реалізовувати програми на комп’ютері, аналізувати вхідні дані і отримані результати, використовувати навчальні програми для вивчення інформатики та інших предметів.

1. Вимоги до лабораторної роботи
   1. Кожен студент отримує набір завдань відповідно до свого порядкового номеру у списку групи або відповідно до номеру залікової книжки.
   2. ЗВІТ ПОВИНЕН БУТИ НАДРУКОВАНИЙ.
   3. Звіт про виконання роботи оформляється у вигляді завдань та розв’язку до них.
   4. Звіт акуратно оформляється на аркушах А4 та скріпляється скріпкою або вставляється у файлик.
   5. Звіт про виконання лабораторної роботи необхідно захистити у строго визначені терміни.
   6. Загальний принцип оформлення титульного листа лабораторної роботи:

1. Порядок роботи
   1. Ознайомитися iз структурою, командами та функціональними можливостями інтегрованого середовища Python чи С/C++.
   2. Використовуючи літературні джерела, конспект лекцій, методичні розробки з дисципліни, засвоїти теоретичний матеріал, пов’язаний з тематикою лабораторної роботи.
   3. Отримати індивідуальне завдання, розробити схему алгоритму для його розв’язування та написати відповідну програму на мові Python чи С/C++;
   4. Використовуючи вбудований редактор текстів, набрати програму на мові Python чи С/C++.
   5. Використовуючи засоби інтегрованого середовища мови Python чи С/C++, набрати, відредагувати та відкомпілювати текст програми;
   6. Вiдкомпiлювати, вiдлагодити та виконати програму.
   7. Ознайомитися з теоретичним матеріалом по визначенню та застосуванню директив препроцесора.
   8. При підготовці до лабораторної роботи згідно з індивідуальним завданням скласти програму на мові Python чи С/C++.
   9. Завантажити інтегроване середовище Python чи С/C++.
   10. Підготувати текст програми згідно завдання.
   11. По виданому завданню розробити програму iз застосуванням директив замiни iдентифiкатора, макросів та умовної компiляцiї програм.
   12. Використовуючи вбудовані засоби інтегрованого середовища ввести та вiдлагодити програму на мові Python чи С/C++.
   13. Виконати програму. Якщо будуть виявлені помилки в програмі, вияснити причину помилки (використовуючи допомогу) та виправити.
   14. Ввести вхiднi дані та отримати результат виконання програми.
   15. Протестувати задачу.
   16. Підготувати вхідні дані для перевірки правильності виконання програми;
   17. Виконати програму та зафіксувати отримані результати;

Примітка. Для зменшення часу введення великих об’ємів вхідних даних при відлагодженні програми рекомендується виконати перенаправлення вводу даних з клавіатури на ввід даних з попередньо створеного текстового файлу. Перенаправлення потоків здійснюється у режимі командного рядка, наприклад: C:\Students\KH-215\Lab07.exe < MyData.txt.  В результаті дані з файлу MyData.txt будуть прочитані функціями вводу програми Lab07.exe .

1. Перевірити правильність роботи програми; при необхідності внести зміни у програму та виконати її повторний запуск.
2. Записати текст програми на диск.
3. Оформити та захистити звіт по лабораторній роботі згідно вимог. Відповісти керівнику лабораторних занять на поставлені запитання за темою  лабораторної роботи;
4. Проаналiзувати отриманий результат та оформити звiт по роботi, дотримуючись наступного змiсту:

¨     назва роботи;

¨     мета роботи;

¨     технологiя вводу, компiляцiї, вiдлагодження та виконання програми;

¨     завдання для роботи;

¨     блок-схема програми;

¨     програма та результати її роботи;

¨     висновки.

1. Вимоги до оформлення звіту

Звіт по роботі має включати в себе наступні розділи:

• Номер та назва роботи;
• Мета виконання лабораторної роботи;
• Індивідуальне завдання для виконання роботи згідно варіанту з детальним формулюванням розв’язуваної задачі;
• Алгоритми розв’язування задачі;
• Графічна схема алгоритму розв’язування задачі з поясненням (блок-схеми програми, підпрограми та їх опис);
• Текст програми на мові Python чи С/C++. Програма повинна контролювати правильність вводу вхідних даних та мати коментарі до її основних структурних конструкцій.
• Результати комп’ютерної реалізації програми. Вказується формат і значення вхідних даних та отриманих для них результатів;
• Висновки. Вказується призначення програми, обмеження на її застосування, можливі варіанти вдосконалення та які знання отримано в ході виконання  роботи.

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

1. Завдання

Розв’язати завдання, подані у додатку, відповідно до свого порядкового номеру у списку групи. При оформленні лабораторної роботи дотримуватись вимог, які наведені в методичних вказівках. Оцінювання виконаної лабораторної роботи проводиться згідно кількості правильно розв’язаних завдань з відповідного варіанту. Завдання лабораторної роботи мають три рівня складності. Оцінювання виконання завдань першого рівня в п’ятибальній системі відповідає оцінці “задовільно”, другий рівень – “добре”, третій – “відмінно”. Наприклад, якщо на лабораторну виділено 5 балів, тоді 1 бал за виконання першого рівня, 1.5 балів – другого рівня, та 2.5 балів – третього рівня.

Перший рівень

Розробити програмy згідно алгоритму з використанням рекурсивної функції та без використання рекурсивної функції. Оцінити час виконання та складність алгоритму.

Другий рівень

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

Варіанти індивідуальних завдань.

№	Завдання
	Перевірити, чи двійкове дерево є збалансованим.
	Знайти вершину в дереві.
	Розробити програму для роботи з червоно-чорним деревом та процедуру пошуку в ньому.
	Розробити програму побудови бінарного дерева за арифметичним виразом (наприклад, 2+3-5+7)
	Знищити заданий елемент в бінароному дереві.
	Додати вершину у впорядковане бінарне дерево.
	Додати вершину у невпорядковане дерево.
	Здійснити заміну значення заданої вершини.
	Вивести на друк листи дерева.
	Вивести на друк ліві вершини дерева.
	Вивести на друк всі вершини, значення яких більше за корінь на одиницю.
	Вивести на друк праві вершини дерева.
	Вивести на друк всі вершини, значення яких більше за корінь на задану величину.
	Перевірити зи допомогою дерева, чи стрічка є паліндромом
	Побудувати дерево синтаксичного розрору речення
	Вивести на друк всі ліві вершини збалансованого дерева
	Вивести на друк всі червоні вершини червоно-чорного дерева
	Вивести на друк всі чорні вершини червоно-чорного дерева
	Знайти в бінарному дереві вершину, сума значень прямих нащдків якої є максимальна
	Знайти в бінарному дереві вершину, сума значень прямих нащдків якої є максимальна

2. Забезпечити зберігання графа у вигляді матриці суміжності.

Варіанти індивідуальних завдань.

№	Завдання
	Розробити алгоритм знаходження зв’язних підграфів заданого графа.
	Розробити програму обходу графа вшир, поданого матрицею суміжності.
	Розробити програму обходу графа вглиб, поданого матрицею суміжності.
	Розробити програму пошуку вершини в графі.
	Розробити програму пошуку вершини в графі за її значенням.
	Розробити програму, результатом якої є стек, сформований на основі послідовності вершин, отриманих при обході вглиб.
	Розробити програму, результатом якої є черга, сформований на основі послідовності вершин, отриманих при обході вшир.
	Дерево — це зв'язний ациклічний (що не має циклів) граф. Кожен граф, що не містить циклів, називається лісом. Представити алгоритм, що визначає, чи є граф деревом.
	Розробити програму, яка за матрицею суміжності формує множину ребер.
	Знайти у графі двонаправлені ребра.
	Сформувати множину вершин, з яких виходять ребра заданої вартості.
	Сформувати множину ребер, які є ациклічними.
	Знайти у графі петлі
	Знайти вартість шляху між заданими вершинами. Якщо прямого шляху нема, то вивести повідомлення

Третій рівень

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

Варіанти індивідуальних завдань.

Розробити процедури та функції для пошуку в одновимірних масивах посортованих та непосортованих та для їх сортування. В контрольному прикладі забезпечити пошук потрібних елементів в непосортованих масивах. Здійснити їх сортування.  Здійснити пошук в посортованих масивах. Оцінити час виконання операцій.

№	Завдання
1	Елементи, які присутні в обох масивах А і В
2	Елементи, які є тільки в масиві А або тільки в масиві В
3	Елементи, котрі присутні в масиві А, але  відсутні в масиві В
4	Елементи, котрі присутні в обох масивах А і В в декількох екземплярах
5	Елементи, котрі присутні в декількох екземплярах в масиві А, але відсутні в масиві В
6	Елементи, котрі присутні в декількох екземплярах або тільки в масиві A, або тільки в масиві В
7	Елементи, котрі присутні в декількох екземплярах або в масиві А, або в масиві В (або в обох масивах)
8	Елементи масиву А, які повторюються в масиві В декілька раз
9	Елементи присутні в обох масивах А і В в одному екземплярі
10	Елементи, присутні в одному екземплярі або тільки в масиві А, або тільки в масиві В
11	Елементи масиву А, які повторюються  і одночасно є в масиві В
12	Елементи масиву А, які повторюються  і одночасно є в масиві В в одному екземплярі
13	Елементи масиву А, які не повторюються і одночасно є в масиві В в декількох екземплярах
14	Елементи масиву А, які повторюються  і одночасно відсутні в масиві В
15	Елементи масиву А в одному екземплярі, котрі є в масиві В тільки в одному екземплярі
16	Елементи масиву А в одному екземплярі, котрі є в масиві В тільки в декількох екземплярах
17	Елементи, які присутні в декількох екземплярах або тільки в масиві А, або тільки в масиві В
18	непарні елементи масиву А, котрі парні в масиві В
19	елементи, присутні в обох масивах А і В і більші числа К
20	елементи, котрі є тільки в масиві А або в масиві В
21	парні елементи масиву А, присутні в масиві В
22	неповторювані елементи масиву А, котрих нема масиві В
23	елементи масиву А в одному екземплярі, котрі присутні в масиві B
№	Завдання
24	елементи масиву A, присутні в одному екземплярі в масиві B
25	елементи масиву В, які повторюються в масиві А декілька раз
26	елементи масивів, котрі присутні в масиві В, але відсутні в масиві А
27	елементи масивів, котрі присутні непарну кількість раз в обох масивах А і В
28	елементи масивів, котрі присутні в декількох екземплярах в масиві В, але  відсутні в масиві А
29	елементи масивів, котрі присутні в декількох екземплярах або тільки в масиві A, або тільки в масиві В
30	знайти медіани масивів А і В

Алгоритми пошуку:

• Лінійний пошук;
• Лінійний пошук з бар’єром;
• Бінарний пошук;
• Пошук Фібоначі;
• Пошук з перестановкою в початок;
• Пошук с транспозицією;

Алгоритми сортування:

• Сортування обміном

• Сортування вибором
• Бульбашкове сортування 
• Сортування включениями
• Бульбашкове сортування  вставками.
• Швидке сортування
• Сортування Шелла
• Пірамідальне сортування
• Сортування Хоара.