- •Л.І. Маркова
- •1 Розв’язання задач з використанням методів пошуку
- •1.1 Мета роботи
- •1.2 Вказівки з підготовки до роботи
- •Лінійний пошук
- •З метою поліпшення можна прийти до питання, а чи потрібна перевірка
- •1.3 Варіанти індивідуальних завдань до лабораторної роботи 1
- •2.3 Варіанти індивідуальних завдань до лабораторної роботи 2
- •2.4 Контрольні запитання та завдання
- •3 Розв’язання задач з використанням алгоритмів сортування
- •3.1 Мета роботи
- •3.2 Підготовка до роботи
- •Бульбашкове сортування
- •4.3 Варіанти індивідуальних завдань до лабораторної роботи 4
- •6 Розв’язання задач у просторі станів
- •6.3 Варіанти індивідуальних завдань до лабораторної роботи 6
- •Початок // Begin
- •7.3 Варіанти індивідуальних завдань до лабораторної роботи 7
- •7.4 Контрольні запитання та завдання
- •"Теорія алгоритмів"
- •Віддруковано в учбово-виробничому видавничо-поліграфічному центрі хнуре
- •61166, , Харків, просп. Леніна, 14.
МІНІСТЕРСТВО ОСВІТИ І науки УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ
УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторних робіт з дисципліни
"ТЕОРІЯ АЛГОРиТМІВ"
для студентів спеціальності "Інформатика"
ХАРКІВ 2004
МІНІСТЕРСТВО ОСВІТИ І науки УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ
УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторних робіт з дисципліни
"ТЕОРІЯ АЛГОРИТМІВ"
для студентів спеціальності "Інформатика"
ЗАТВЕРДЖЕНО
кафедрою інформатики.
Протокол №18 від 7.03.03
ХАРКІВ 2004
Методичні вказівки до лабораторних робіт з курсу "Теорія алгоритмів" для студентів спеціальності "Інформатика" / Упоряд.: Бритік В.І., Свинар М.К., Маркова Л.І., – Харків: ХНУРЕ, 2004. – 40 с.
Упорядники: В.I. Бритiк,
М.К. Свинар,
Л.І. Маркова
ЗМІСТ
Загальні вказівки 5
1 Розв’язання задач з використанням методів пошуку 5
1.1 Мета роботи 5
1.2 Вказівки з підготовки до роботи 5
1.3 Варіанти індивідуальних завдань до лабораторної роботи 1 8
1.4 Контрольні запитання та завдання 9
2 Розв’язання задач з використанням рекурсії 9
2.1 Мета роботи 9
2.2 Підготовка до роботи 9
2.3 Варіанти індивідуальних завдань до лабораторної роботи 2 12
2.4 Контрольні запитання та завдання 14
3 Розв’язання задач з використанням алгоритмів сортування 14
3.1 Мета роботи 14
3.2 Підготовка до роботи 14
3.3 Варіанти індивідуальних завдань до лабораторної роботи 3 16
3.4 Контрольні запитання 17
4 Розв’язання задач з використанням графів та знаходження хроматичного числа 18
4.1 Мета роботи 18
4.2 Підготовка до роботи 18
4.3 Варіанти індивідуальних завдань до лабораторної роботи 4 19
4.4 Контрольні запитання та завдання 21
5 Розв’язання задач з використанням графів та знаходження найкоротшого шляху 21
5.1 Мета роботи 21
5.2 Підготовка до роботи 21
5.3 Варіанти індивідуальних завдань до лабораторної роботи 5 23
5.4 Контрольні запитання та завдання 23
6 Розв’язання задач у просторі станів 23
6.1 Мета роботи 23
6.2 Підготовка до роботи 24
6.3 Варіанти індивідуальних завдань до лабораторної роботи 6 26
6.4 Контрольні запитання та завдання 31
7 Розв’язання задач оптимізації потоків у мережах 31
7.1 Мета роботи 31
7.2 Підготовка до роботи 31
7.3 Варіанти індивідуальних завдань до лабораторної роботи 7 32
7.4 Контрольні запитання та завдання 37
Перелік посилань 38
ЗАГАЛЬНІ ВКАЗІВКИ
Розв’язання практично всіх сучасних задач неможливе без використання обчислювальної техніки. При цьому значно зростає потреба в грамотних інженерах, здатних ставити та вирішувати задачі на ЕОМ.
В основу курсу покладене вивчення таких тем:
Основи теорії алгоритмів із використанням теорії формальних граматик;
Основи рекурсивних функцій і побудова інтелектуальних алгоритмів;
Питання побудови й аналізу ефективних алгоритмів, а також розбираються класи швидких алгоритмів і прийоми їхньої побудови.
Виконання лабораторних робіт, наведених у даній методичній вказівці, дозволить придбати практичні навички розв’язання задач різного ступеня складності.
Звіт з лабораторної роботи має містити:
прізвище і ініціали студента з зазначенням групи та курсу;
номер варіанта і вихідні дані виконуваного завдання;
блок – схему алгоритму;
тверду копію тексту програми і результатів її виконання;
аналіз помилок і висновки.
1 Розв’язання задач з використанням методів пошуку
1.1 Мета роботи
Студенти повинні: ознайомитися з методами пошуку.
1.2 Вказівки з підготовки до роботи
Необхідно ознайомитися з основними методами пошуку елементів із заданими характеристиками.
Лінійний пошук
Об'єкт знайдений, якщо .
Об'єкт не знайдений, якщо .
З двох висловлень випливає: .
while (i<N && a[i]!=x) i++;
if(i==N) немає об'єкта.
Єдина можливість прискорити пошук об'єкта – спростити умову (предикат). Така можливість існує, якщо є апріорна впевненість, що елемент існує.
// N задається за межами масиву, тобто потрібно об'явити
тоді
a[N]=x; i=0;
while (a[i]!=x) i++;
предикат для цього випадку:
Пошук розподілу навпіл (двійковий пошук).
Вважаємо, що дані упорядковані.
L___________m______________R
L=0; R=N-1; i=0; m=0;
while(L<=R && a[i] !=x)
{m=(L+R)/2;
if(a[m]==x) i=m, break;
else if(a[m]<x) L=m+1;
else R=m-1;
}
Умова останова:
Спростивши, одержимо
На ефективність впливає вибір . Однак краще, коли береться ½ масиву, що забезпечує максимальне число порівнянь рівне log. Тоді як лінійний пошук забезпечує N/2 порівнянь.
Ефективність можна поліпшити, помінявши місцями, оператори перевірки
while( a[m] !=x && L<=R )
Умова L<=R не обчислюється, якщо a[m] !=x прагне до 0.