Easd_Laboratornye_Raboty_1-7

Лабораторна робота 1
Тема:
Побудова і аналіз алгоритмів. Аналіз алгоритмів сортування і пошуку
Ціль:
Засвоїти метод покрокового уточнення алгоритму під час розробки програми. Засвоїти методику оцінки складності алгоритму і програми за часом.
Опорні знання:
Мови програмування Паскаль, С. Поняття ефективності алгоритму за часом. Прості і ефективні алгоритми сортування масивів.
Завданння:
Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.
Література:
1. М.С. Львов, А.В.Спиваковский, С.В.Белоусова. Основы программирования на языке Паскаль. Херсон: МИБ, 1997.- 153 с.
2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
3. Конспект лекций.

Тема 1. Побудова і аналіз алгоритмів
Змістовні постановки задач та їх математичні моделі. Метод покрокового уточнення алгоритму. Псевдо-алгоритмічна мова. Абстрактні типи ланих. Час виконання алгоритму. О-символіка. Методи аналізу складності алгоритму за часом.

Хід роботи
Экспортувати з тексту роботи в програмний файл программу bublsort.pas.
Доповнити програму процедурой генерації випадкового масиву.
Доповнити програму засобами підрахунку часу виконання сортування.
Виконати експеримент з сортування масиву. Заповнити клітинки таблиці експерименту.
Экспортувати з тексту роботи в програмний файл программу insort.pas.
Доповнити програму процедурой генерації випадкового масиву.
Доповнити програму засобами підрахунку часу виконання сортування.
Виконати експеримент з сортування масиву. Заповнити клітинки таблиці експерименту.
Экспортувати з тексту роботи в програмний файл программу bublsort.pas.
Доповнити програму процедурой генерації випадкового масиву.
Доповнити програму засобами підрахунку часу виконання сортування.
Виконати експеримент з сортування масиву. Заповнити клітинки таблиці експерименту.
На одному полі графіку побудувати графіки складності програм за часом.
Обчислити коєфіцієнти порівнянь I/B та H/B
Перевірити гіпотези про квадратичність алгоритмів В, І та ефективність Н.

N
Алгоритми сортування

Порівняння


Обмінами В
Вставками І
Хоара Н
І/B
H/B








1000






2000






3000






4000






5000






6000






Програма сортування обмінами

Program BublSort;
Const
n = 20;
Var
a : array[1..n] of Data;
i, j : Integer;
b : Data;
Begin
For i := n - 1 downto 1 do
For j := 1 to i do
If a[j] > a[j+1]
then begin
b := a[j+1];
a[j+1] := a[j];
a[j] := b
end;
End.

Програма сортування вставками

Program InsSort;
Const
n = 20;
Var
A : array[1..n] of Data;
k, l, r, i, j : Integer;
b : Data;

Begin
For k := 1 to n-1 do begin
b := A[k+1];
If b < A[k]
then
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Програма швидкого сортування.

Program QuickSort;
Const
n = 21;
Var
A : array[1..n] of Data;

Procedure Swap(i, j : Integer);
Var
b : Data;
Begin
b := a[i];
a[i] := a[j];
a[j] := b
End;

Procedure Hoare(L, R : Integer);
Var
left, right : Int
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Контрольні запитання
Як застосувати метод покрокової деталізації для розробки алгоритмів сортування
Як оцінюється алгоритм сортування обмінами?
Як оцінюється алгоритм сортування вставками?
Як оцінюється алгоритм сортування Ноара?
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити:
Порівняльну таблицю 1, заповнену результатами експерименту.
Графік ефективності алгоритмів за часом
Висновки про ефективності досліджуваних алгоритмів.

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

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

Ціль:
Засвоїти метод реалізації лінійних зв’язних динамічних структур: стеків, черг та списків.
Опорні знання:
Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Стек, Список та Черга.
Завданння:
Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.
Література:
1. М.С. Львов, А.В.Спиваковский, С.В.Белоусова. Основы программирования на языке Паскаль. Херсон: МИБ, 1997.- 153 с.
2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
3. Конспект лекций.

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

Хід роботы
Завдання 1
Реалізувати АТД Черга на основі циклічного масиву.
Реалізувати додатково метод пошуку та видалення мінімального елементу з черги.
Оцінити складність методу пошуку та видалення мінімального елементу.
Завдання 2.
Реалізувати АТД Двозв’язаний список на основи пари стеків. АТД Стек реалізувати довільним чином.
Реалізувати додатково метод пошуку мінімального елементу списку.
Оцінити складність методу пошуку елементу
Завдання 3.
Реалізувати АТД Двозв’язаний список на основи вказівців Next, Pred.
Реалізувати додатково метод пошуку мінімального елементу списку.
Оцінити складність методу пошуку мінімального елементу

Контрольні запитання
Перелічити основні операції АТД Стек.
Перелічити методи реалізації АТД Стек та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.
Перелічити основні операції АТД Черга.
Перелічити методи реалізації АТД Черга та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.
Перелічити основні операції АТД Список.
Перелічити методи реалізації АТД Список та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-3 відомості:
Перелік операцій відповідного АТД зі спеціфікаціями.
Опис структур даних відповідного АТД.
Програмний код з реалізацією АТД.
Лабораторна робота 3

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

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

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

Література:
М.С. Львов, А.В.Спиваковский, С.В.Белоусова. Основы программирования на языке Паскаль. Херсон: МИБ, 1997.- 153 с.
А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
Конспект лекций.

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

Хід роботи:
Завдання 1
Реалізувати АТД Дерево на основі масиву .
Реалізувати методи пошуку даного елементу обходами зліва направо, зверху вниз, знизу вверх.
Оцінити складність методів пошуку даного елементу
Завдання 2
Реалізувати АТД Бінарне дерево.
Реалізувати алгоритм Хафмена методом побудови бінарного дерева.
Оцінити складність методу Хафмена.
Контрольні запитання
Перелічити основні операції АТД Дерево
Перелічити методи реалізації АТД Дерево на основі різних структур даних
Перелічити основні методи обходів дерева.
Перелічити методи реалізації АТД Дерево та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.
Описати постановку задачі кодування та метод Хафмена.
Описати структури даних необхідні для реалізації методу Хафмена.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-2 відомості:
Перелік операцій відповідного АТД зі спеціфікаціями.
Опис структур даних відповідного АТД.
Програмний код з реалізацією АТД.
Опис структур даних методу Хафмена.
Програмний код з реалізацією методу Хафмена.
Лабораторна робота 4
·

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

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

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

Література:
М.С. Львов, А.В.Спиваковский, С.В.Белоусова. Основы программирования на языке Паскаль. Херсон: МИБ, 1997.- 153 с.
А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
Конспект лекций.
Тема 2. АТД Множина. Ефективні алгоритми реалізації множин.
Змістовні визначення АТД Множина. Методи реалізації множин на основі двоїчного вектора, впорядкованого списку. АТД Словник. Задача про базу даних з голосування депутатів.

Хід роботи
Завдання 1.
Реалізувати АТД Множина на основі двоїчного вектора.
Оцінити складність, переваги і недоліки реалізації множин двоїчними векторами.
Завдання 2.
Реалізувати АТД Множина на основі впорядкованих векторів.
Оцінити складність, переваги і недоліки реалізації множин двоїчними векторами.
Завдання 3.
Реалізувати задачу про базу даних з голосування депутатів.
Оцінити складність, переваги і недоліки реалізації словників методами .
Контрольні запитання
Перелічити основні операції АТД Дерево
Перелічити методи реалізації АТД Дерево на основі різних структур даних
Перелічити основні методи обходів дерева.
Перелічити методи реалізації АТД Дерево та порівняти їх такими критеріями: ефективність, простота реалізації, універсальність.
Описати постановку задачі кодування та метод Хафмена.
Описати структури даних необхідні для реалізації методу Хафмена.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-2 відомості:
Перелік операцій відповідного АТД зі спеціфікаціями.
Опис структур даних відповідного АТД.
Програмний код з реалізацією АТД.
Опис структур даних методу Хафмена.
Програмний код з реалізацією методу Хафмена.
Лабораторна робота 5
Тема: Реалізація алгоритму Лемпела-Зіва архівації
Ціль:
Засвоїти ефективний алгоритм (алгоритм Лемпела-Зіва) архівації файлів.
Опорні знання:
Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Навантажене дерево. АТД Словник.

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

Література:
1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
2. Ф.А.Новиков. Дискретная математика для программистов. СПб.:Питер, 2004.-302 с.
3. Конспект лекций.

Хід роботи
Завдання 1.
Реалізувати АТД Навантажене дерево для реалізації процедури пошуку слідуючого слова для кодування.
Завдання 2.
Реалізувати АТД Таблиця кодування - декодування
Завдання 3.
На базі реалізованих АТД реалізувати алгоритм Лемпела-Зіва
Контрольні запитання
Як формулюється задача стискання інформації для її архівації в термінах абстрактних типів даних?
Які дані є вхідними та вихідними для алгоритмів архівації?
Які структури даних треба реалізувати для реалізації алгоритму Лемпела-Зіва?
Опишіть АТД Навантажене дерево.
Опишіть АТД Таблиця кодування – декодування текстової інформації
Опишіть стуктуру даних Навантажене дерево
Опишіть структуру даних Таблиця кодування – декодування текстової інформації
Оцініть ефективність алгоритму Лемпела-Зіва за часом та пам’ятью.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-3 відомості:
Опис АТД та структури даних Навантажене дерево
Опис АТД та структури даних Таблиця кодування – декодування
Програмний код з реалізацією алгоритму Лемпела-Зіва.
Лабораторна робота 6
Тема: Реалізація представлень оргафа. Реалізація пошуку в глибину.
Ціль:
Засвоїти ефективні методи реалізації представлень орієнтованого графу за допомогою матриці суміжності та за допомогою списків суміжних вершин. Засвоїти метод реалізації обходу графа у глибину.
Опорні знання:
Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Орієнтований граф. Алгоритм обходу орієнтованого груфу.
Завданння:
Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.
Література:
1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
2. Ф.А.Новиков. Дискретная математика для программистов. СПб.:Питер, 2004.-302 с.
3. Конспект лекций.
Хід роботи
Завдання 1.
Реалізувати представлення орієнтованого графу матрицею суміжності.
Завдання 2.
Реалізувати представлення орієнтованого графу списками суміжних вершин.
Завдання 3.
На базі представлення графу списками суміжних рершин реалізувати алгоритм обходу графа у глибину.
Контрольні запитання
Дайте означення орієнтованого графа.
Як формулюється задача обходу графа? Які методи обходів графу є найбільш розповсюдженими?
Які дані є вхідними та вихідними для представлення графу матрицею суміжності?
Які дані є вхідними та вихідними для представлення списками суміжних вершин?
Які структури даних треба реалізувати для реалізації алгоритму обходу графа у глибину?
Опишіть АТД Орієнтований граф.
Опишіть алгоритм обходу орієнтованого графа у глибину.
Опишіть алгоритм обходу орієнтованого графа у ширину.
Оцініть ефективність алгоритму обходу графа у глибину за часом та пам’ятью.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-2 відомості:
Опис АТД та структури даних Орієнтований граф
Програмний код з реалізацією алгоритму обходу графа у глибину.
Лабораторна робота 7
Тема: Реалізація алгоритма Краскала
Ціль:
Засвоїти ефективні методи реалізації представлень неорієнтованого графу за допомогою матриці суміжності та за допомогою списків суміжних вершин. Засвоїти метод реалізації алгоритму Краскала розв’язання задачі пошуку остовного дерева найменшої вартості.
Опорні знання:
Мови програмування Паскаль, С. Поняття АТД та реалізації АТД. АТД Орієнтований граф. Алгоритм обходу орієнтованого груфу.
Завданння:
Ознайомитися з теоретичним матеріалом та виконати завдання, визначені в розділі Хід роботы, підготувати відповіді на конетрольні запитання, оформити протокол виконання роботи.
Література:
1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
2. Ф.А.Новиков. Дискретная математика для программистов. СПб.:Питер, 2004.-302 с.
3. Конспект лекций.
Хід роботи
Завдання 1
Реалізувати представлення позначеного неорієнтованого графу матрицею суміжності.
Завдання 2.
Описати АТД для алгоритму Краскала.
Завдання 3.
Реалізувати алгоритму Краскала розв’язання задачі пошуку остовного дерева найменшої вартості.
Контрольні запитання
Дайте означення неорієнтованого графа.
Дайте означення позначеного графа.
Як формулюється задача пошуку остовного дерева найменшої вартості Які методи розв’язання цієї задачі є найбільш відомими?
Які дані є вхідними та вихідними для представлення неорієнтованого позначеного графу матрицею суміжності?
Які структури даних треба реалізувати для реалізації алгоритму Краскала?
Опишіть АТД Неорієнтований позначений граф.
Опишіть АТД для алгоритму Краскала.
Оцініть ефективність алгоритму Краскала за часом та пам’ятью.
Зміст і вимоги до оформлення протоколу роботи
Протокол роботи повинен містити для кожного з завдань 1-3 відомості:
Формулювання задачі пошуку остовного дедева найменшої вартості
Опис АТД та структури даних Неорієнтований граф позначений граф.
Програмний код з реалізацією алгоритму Краскала.
Їђ Заголовок 1Їђ Заголовок 2Їђ Заголовок 3Їђ Заголовок 4Їђ Заголовок 5Їђ Заголовок 6Їђ Заголовок 7Їђ Заголовок 8Їђ Заголовок 915

Приложенные файлы

  • doc 17920233
    Размер файла: 113 kB Загрузок: 0

Добавить комментарий