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

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

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

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

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

4. Опис структур даних методу Хафмена.

5. Програмний код з реалізацією методу Хафмена.

Лабораторна робота 4

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

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

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

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

Література:

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

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

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

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

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

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

Хід роботи

Завдання 1

1. Реалізувати АТД Множина на основі двоїчного вектора.

2. Оцінити складність, переваги і недоліки реалізації множин двоїчними векторами.

Завдання 2.

1. Реалізувати АТД Множина на основі впорядкованих векторів.

2. Оцінити складність, переваги і недоліки реалізації множин двоїчними векторами.

Завдання 3.

3. Реалізувати задачу про базу даних з голосування депутатів.

4. Оцінити складність, переваги і недоліки реалізації словників методами .

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

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

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

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

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

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

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

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

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

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

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

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

4. Опис структур даних методу Хафмена.

5. Програмний код з реалізацією методу Хафмена.

Лабораторна робота 5

Тема: Реалізація алгоритму Лемпела-Зіва архівації

Ціль: Засвоїти ефективний алгоритм (алгоритм Лемпела-Зіва) архівації файлів.

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

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

Література:

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

2. Ф.А.Новиков. Дискретная математика для программистов. СПб.:Питер, 2004.-302 с.

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

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

Хід роботи

Завдання 1 Реалізувати АТД Навантажене дерево для реалізації процедури пошуку слідуючого слова для кодування.

Завдання 2. Реалізувати АТД Таблиця кодування - декодування

Завдання 3. На базі реалізованих АТД реалізувати алгоритм Лемпела-Зіва

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

1. Як формулюється задача стискання інформації для її архівації в термінах абстрактних типів даних?

2. Які дані є вхідними та вихідними для алгоритмів архівації?

3. Які структури даних треба реалізувати для реалізації алгоритму Лемпела-Зіва?

4. Опишіть АТД Навантажене дерево.

5. Опишіть АТД Таблиця кодування – декодування текстової інформації

6. Опишіть стуктуру даних Навантажене дерево

7. Опишіть структуру даних Таблиця кодування – декодування текстової інформації

8. Оцініть ефективність алгоритму Лемпела-Зіва за часом та пам’ятью.

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

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

1. Опис АТД та структури даних Навантажене дерево

2. Опис АТД та структури даних Таблиця кодування – декодування

3. Програмний код з реалізацією алгоритму Лемпела-Зіва.

Лабораторна робота 6

Тема: Реалізація представлень оргафа. Реалізація пошуку в глибину.

Ціль: Засвоїти ефективні методи реалізації представлень орієнтованого графу за допомогою матриці суміжності та за допомогою списків суміжних вершин. Засвоїти метод реалізації обходу графа у глибину.

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

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

Література: