Зміст і вимоги до оформлення протоколу роботи

Протокол роботи повинен містити:

1. Порівняльну таблицю 1, заповнену результатами експерименту.

2. Графік ефективності алгоритмів за часом

3. Висновки про ефективності досліджуваних алгоритмів.

Лабораторна робота 2

Тема: Ефективні алгоритми реалізації списків, черг і стеків.

Ціль: Засвоїти метод реалізації лінійних зв’язних динамічних структур: стеків, черг та списків.

Опорні знання: Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Стек, Список та Черга.

Завданння: Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.

Література:

1. М.С. Львов, а.В.Спиваковский, с.В.Белоусова. Основы программирования на языке Паскаль. Херсон: миб, 1997.- 153 с.

2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.

3. Конспект лекций.

Стислі теоретичні відомості

Тема 2. Ефективні алгоритми реалізації списків, черг і стеків.

Змістовні визначення АТД Стек, черга, список. Методи реалізації АТД на основі масиву. Методи реалізації АТД вказівцями.

Хід роботы

Завдання 1

1. Реалізувати АТД Черга на основі циклічного масиву.

2. Реалізувати додатково метод пошуку та видалення мінімального елементу з черги.

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

Завдання 2.

4. Реалізувати АТД Двозв’язаний список на основи пари стеків. АТД Стек реалізувати довільним чином.

5. Реалізувати додатково метод пошуку мінімального елементу списку.

6. Оцінити складність методу пошуку елементу

Завдання 3.

7. Реалізувати АТД Двозв’язаний список на основи вказівців Next, Pred.

8. Реалізувати додатково метод пошуку мінімального елементу списку.

9. Оцінити складність методу пошуку мінімального елементу

Контрольні запитання

1. Перелічити основні операції АТД Стек.

2. Перелічити методи реалізації АТД Стек та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.

3. Перелічити основні операції АТД Черга.

4. Перелічити методи реалізації АТД Черга та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.

5. Перелічити основні операції АТД Список.

6. Перелічити методи реалізації АТД Список та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.

Зміст і вимоги до оформлення протоколу роботи

Протокол роботи повинен містити для кожного з завдань 1-3 відомості:

1. Перелік операцій відповідного АТД зі спеціфікаціями.

2. Опис структур даних відповідного АТД.

3. Програмний код з реалізацією АТД.

Лабораторна робота 3

Тема: Ефективні алгоритми реалізації дерев.

Ціль: Засвоїти метод реалізації дерев на різноманітних структурах даних. Реалізація обходів дерева.

Опорні знання: Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Дерево.

Завданння: Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.

Література:

1. М.С. Львов, а.В.Спиваковский, с.В.Белоусова. Основы программирования на языке Паскаль. Херсон: миб, 1997.- 153 с.

2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.

3. Конспект лекций.

Стислі теоретичні відомості

Тема 3. Ефективні алгоритми реалізації дерев та бінарних дерев.

Змістовні визначення АТД Дерево. Методи обходів дерева зліва направо, зверху вниз, знизу вверх.Реалізація АТД Дерево на основі масиву. Бінарні дерева та коди Хафмена.

Хід роботи

Завдання 1

1. Реалізувати АТД Дерево на основі масиву .

2. Реалізувати методи пошуку даного елементу обходами зліва направо, зверху вниз, знизу вверх.

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

Завдання 2.

1. Реалізувати АТД Бінарне дерево.

2. Реалізувати алгоритм Хафмена методом побудови бінарного дерева.

3. Оцінити складність методу Хафмена.

Контрольні запитання

1. Перелічити основні операції АТД Дерево

2. Перелічити методи реалізації АТД Дерево на основі різних структур даних

3. Перелічити основні методи обходів дерева.

4. Перелічити методи реалізації АТД Дерево та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.

5. Описати постановку задачі кодування та метод Хафмена.

6. Описати структури даних необхідні для реалізації методу Хафмена.