+3 8(066) 185-39-18
fПредмет:
Тип работы:
Методичні вказівки
К-во страниц:
36
Язык:
Українська
кожної нової ланки вказати, направо чи наліво здійснено поворот.
Варіант 2. Точки належать ламаній. Потрібно для кожної нової ланки вказати, чи перетинає вона будь-яку з попередніх.
Варіант 3. Точки є координатами багатокутника в порядку обходу. Ви-вести площину багатокутника та повідомити, за годинниковою стрілкою чи проти годинникової стрілки здійснено обхід.
Варіант 4. Побудувати опуклу оболонку наданих точок алгоритмом Грехема.
Варіант 5. Побудувати опуклу оболонку наданих точок алгоритмом Джарвіса.
Лабораторна робота 8. МАТЕМАТИЧНІ ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ
Мета роботи: навчитися визначати складність алгоритмів.
8.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 8
Аналізуючи алгоритм, можна намагатися знайти точне число виконува-них ним дій. Але в більшості випадків достатньо оцінити асимптотику зрос-тання часу роботи алгоритму при прямуванні величини розмірності вхідних даних до нескінченності:
8.2. Завдання до лабораторної роботи 8
Для кожного реалізованого алгоритму з попередніх робіт визначити складність. Для цього для кожного рядка алгоритму потрібно вказати кількість разів, що він виконується, залежно від розмірності вхідних даних. Результат записати у вигляді -позначення.
Для алгоритмів робіт «Базові структури даних» та «Фундаментальні ал-горитми на графах і деревах» визначити, чи є обрані структури даних оптима-льними, а якщо ні – запропонувати такі, що призводять до зменшення часу ро-боти алгоритму.
Лабораторна робота 9. РЕКУРСІЯ
Мета роботи: навчитися оцінювати складність рекурсивних алгоритмів.
9.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 9
Методи, які потрібно використати, розглянуто в лекційному курсі, а та-кож у запропонованій літературі.
Наведемо базову теорему про рекурентні співвідношення.
Нехай та – константи, – функція та – рекурентно визначена для невід’ємних цілих чисел функція:
де ми інтерпретуємо як або .
Тоді має такі асимптотичні оцінки:
1) якщо для деякої константи , тоді функція має вигляд: ;
2) якщо , тоді ;
3) якщо для деякої константи та якщо для деякої константи і всіх достатньо великих , тоді .
9.2. Завдання до лабораторної роботи 9
Для алгоритму, складність якого описано виданою згідно з варіантом ре-курентною функцією вигляду , визначити складність йо-го виконання, використовуючи такі методи:
1) метод підстановки;
2) перетворення до суми;
3) базова теорема про рекурентні співвідношення;
4) моделювання за допомогою програми (отримати значення для різних та підібрати формулу).
Отримані результати порівняти.
9.3. Варіанти завдань до лабораторної роботи 9
Варіант 1: .
Варіант 2: .
Варіант 3: .
Варіант 4: .
Варіант 5: .
Варіант 6: .
Лабораторна робота 10. ДИНАМІЧНЕ ПРОГРАМУВАННЯ
Мета роботи: навчитися використовувати динамічне програмування та оцінювати його складність.
10.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 10
Структури даних та алгоритми, які потрібно використати, розглянуто в лекційному курсі, а також у запропонованій літературі.
10.2. Завдання до лабораторної роботи 10
Розробити програму, яка читає з клавіатури вхідні дані та розв’язує зада-чу методом динамічного програмування. Визначити складність алгоритму.
10.3. Варіанти завдань до лабораторної роботи 10
Варіант 1. Пошук маршруту на прямокутному полі таким чином, щоб сума чисел у клітинках, через які він проходить, була максимальною. Рух по-чинається із клітинки верхнього лівого кута та завершується у правому ниж-ньому. Кожний крок виконується на одну позицію праворуч або вниз.
Вхідні дані: натуральні числа та послідовність натуральних чисел – прямокутне поле рядок за рядком.
Вихідні дані: таблиця динамічного програмування ( = максимальна сума маршруту до клітинки ); прямокутне поле із маршрутом, що відміче-но зірочками, та сума чисел у клітинках маршруту.
Варіант 2. Пошук найбільшої спільної підпослідовності.
Вхідні дані: натуральні числа та дві послідовно-сті та натуральних чисел довжиною та відповідно.
Вихідні дані: динамічна таблиця ( = довжина НСП для префіксів та ) та НСП для та .
Варіант 3. Пошук оптимального способу множення матриць.
Вхідні дані: натуральне число – кількість матриць, натуральні числа – розмірності матриць (матриця має розмірність ).
Вихідні дані: таблиця динамічного програмування ( = найменша кількість множень для обчислення добутку матриць ) та оп-тимальна розстановка дужок у виразі .
Лабораторна робота 11. ЖАДІБНІ АЛГОРИТМИ
Мета роботи: навчитися використовувати жадібні алгоритми та оціню-вати їхню складність.
11.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 11
Структури даних та алгоритми, які потрібно використати, розглянуто в лекційному курсі, а також у запропонованій літературі.
11.2. Завдання до лабораторної роботи 10
Розробити програму, яка читає з клавіатури вхідні дані та розв’язує зада-чу жадібним алгоритмом. Визначити складність алгоритму.
11.3. Варіанти завдань до лабораторної роботи 10
Варіант 1. Розв’язати задачу про вибір найбільшої кількості заявок для аудиторії. Вхідні дані: кількість заявок , пар натуральних чисел – початок та кінець заявок . Вихідні дані: заявки, відсортовані за зростанням часу закінчення, та номери заявок, які потрібно обрати.
Варіант 2. Стиснути послідовність нулів та одиниць алгоритмом Хаф-фмана. Вхідні дані: натуральні числа та послідовність груп по нулів та одиниць. Вихідні дані: перелік кодів, які потрібно використати для кожної групи, та стиснута послідовність.
Варіант 3. Розв’язати неперервну задачу про рюкзак. Вхідні дані: нату-ральні числа – кількість видів товару та місткість рюкзака, послідовність пар – вартість та вага товару номер i. Вихідні дані: набір дійсних чисел, які вказують, скільки кожного това-ру потрібно покласти до рюкзака, щоб сумарна вартість була максимальною.
СПИСОК ЛІТЕРАТУРИ
- Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона / Н. Вирт. М. : ДМК Пресс, 2010. 272 с.
- Ахо А.В. Структуры данных и алгоритмы / А.В. Ахо, Д.Э. Хопкрофт, Д.Д. Ульман. – М. : Вильямс, 2003. 384 с.
- Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн; пер. с англ. под ред. А. Шеня. – 3-е изд. – М. : ООО «И. Д. Вильямс», 2013. – 1398 с.
- Игошин В.И. Математическая логика и теория алгоритмов : учеб. по-соб. для студ. высш. учеб. заведен. / В.И. Игошин. – 2-е изд., стер. – М. : Изда-тельский центр «Академия», 2008. – 448 с.
- Игошин В.И. Задачи и упражнения по математической логике и тео-рии алгоритмов / В.И. Игошин. – 3-е изд., стер. – М. : Издательский центр «Академия», 2007. – 304 с.
- Романовский И.В. Вычислительная математика и структура алгоритмов / И.В. Романовский. – М. : МГУ, 2006. – 112 с.
- Cormen T.H. Introduction to Algorithms / T.H. Cormen, C. E. Leiserson, R.L. Rivest, C. Stein. – 3rd ed. – Cambridge : MIT Press and McGraw-Hill, 2009 – 1292 p.
- Wirth. N. Algorithms + Data Structures = Programs / N. Wirth. – Prentice-Hall, 1976. – 183 p.
- Aho A.V. Data Structures and Algorithms / A.V. Aho, J.E. Hopcroft, J.D. Ullman. – Addison-Wesley, 1983. – 384 p.