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

 

 

ВСТУП 

Загальні рекомендації щодо виконання лабораторних робіт 

Лабораторна робота 1. Базові структури даних 

1.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 1 

1.2. Завдання до лабораторної роботи 1

1.3. Варіанти завдань до лабораторної роботи 1 

Лабораторна робота 2. Базові структури даних. Хеш-таблиці

2.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 2 

2.2. Завдання до лабораторної роботи 2

2.3. Варіанти завдань до лабораторної роботи 2 

Лабораторна робота 3. Базові структури даних: червоно-чорні дерева 

3.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 3 

3.2. Завдання до лабораторної роботи 3 

3.3. Варіанти завдань до лабораторної роботи 3

Лабораторна робота 4. Алгоритми сортування

4.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 4 

4.2. Завдання до лабораторної роботи 4 

4.3. Варіанти завдань до лабораторної роботи 4

Лабораторна робота 5. Комбінаторні алгоритми 

5.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 5 

5.2. Завдання до лабораторної роботи 5

5.3. Варіанти завдань до лабораторної роботи 5 

Лабораторна робота 6. Фундаментальні алгоритми на графах і деревах 

6.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 6 

6.2. Завдання до лабораторної роботи 6

6.3 Варіанти завдань до лабораторної роботи 6 

Лабораторна робота 7. Геометричні алгоритми

7.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 7 

7.2. Завдання до лабораторної роботи 7 

7.3. Варіанти завдань до лабораторної роботи 7

Лабораторна робота 8. Математичні основи теорії алгоритмів 

8.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 8 

8.2. Завдання до лабораторної роботи 8

Лабораторна робота 9. Рекурсія 

9.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 9 

9.2. Завдання до лабораторної роботи 9

9.3. Варіанти завдань до лабораторної роботи 9

Лабораторна робота 10. Динамічне програмування

10.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 10 

10.2. Завдання до лабораторної роботи 10 

10.3. Варіанти завдань до лабораторної роботи 10

Лабораторна робота 11. Жадібні алгоритми

11.1. Теоретичний матеріал, необхідний для виконання лабораторної роботи 11 

11.2. Завдання до лабораторної роботи 10

11.3. Варіанти завдань до лабораторної роботи 10

Список літератури 

 

 

Методичні вказівки до виконання лабораторних робіт з курсу «Алгорит-ми та структури даних» є частиною загального методичного забезпечення кур-су «Алгоритми та структури даних», який викладається для студентів спе-ціальності 121 «Інженерія програмного забезпечення» в 2-му семестрі.

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

Методичні вказівки містять завдання для 11-ти лабораторних робіт та необхідний для їх виконання теоретичний матеріал, а також варіанти завдань до кожної роботи.

ЗАГАЛЬНІ РЕКОМЕНДАЦІЇ ЩОДО ВИКОНАННЯ ЛАБОРАТОРНИХ РОБІТ

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

За результатом виконання кожної лабораторної роботи студент формує звіт відповідно до вимог НТУ «ХПІ» щодо оформлення навчальної докумен-тації.

Здача лабораторних робіт відбувається протягом усього навчального се-местру відповідно до графіка їх проведення. Строк здачі комплексу лаборато-рних робіт – до останнього тижня семестру.

План проведення лабораторних робіт подано в таблиці 1.1.

 

 

 

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

 

 

Стеки і черги – це динамічні множини, в яких елемент видаляється з множини операцією Delete, яка не задається довільно, а визначається структу-рою множини. Саме зі стеку (stack) можна видалити тільки той елемент, який був у нього доданий останнім: стек працює за принципом «останнім прий-шов – першим пішов» (last-in, first-out – LIFO). З черги (queue), навпаки, мож-на видалити тільки той елемент, який знаходився в черзі довше за всіх: працює принцип «першим прийшов – першим пішов» (first-in, first-out – FIFO).

У зв’язаному списку (або просто списку; linked list) елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а вказівни-ками, що входять до складу елементів списку. Списки є зручним способом ре-алізації динамічних множин.

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

Іншими словами, елемент двобічно зв’язаного списку (doubly linked list) – це запис, що містить три поля: key (ключ) і два вказівники next (наступ-ний)