- •Тема 1. Побудова і аналіз алгоритмів
- •Зміст і вимоги до оформлення протоколу роботи
- •1. М.С. Львов, а.В.Спиваковский, с.В.Белоусова. Основы программирования на языке Паскаль. Херсон: миб, 1997.- 153 с.
- •2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
- •Тема 2. Ефективні алгоритми реалізації списків, черг і стеків.
- •Зміст і вимоги до оформлення протоколу роботи
- •1. М.С. Львов, а.В.Спиваковский, с.В.Белоусова. Основы программирования на языке Паскаль. Херсон: миб, 1997.- 153 с.
- •2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
- •Тема 3. Ефективні алгоритми реалізації дерев та бінарних дерев.
- •Зміст і вимоги до оформлення протоколу роботи
- •1. М.С. Львов, а.В.Спиваковский, с.В.Белоусова. Основы программирования на языке Паскаль. Херсон: миб, 1997.- 153 с.
- •2. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
- •Тема 2. Атд Множина. Ефективні алгоритми реалізації множин .
- •Зміст і вимоги до оформлення протоколу роботи
- •1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
- •1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
- •1. А.Ахо, Дж.Хопкрофт, Дж. Ульман. Структуры данных и алгоритмы.: пер. С англ. Изд. Дом Вильямс, 2001. 384 с.
- •3. Конспект лекций.
Лабораторна робота 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 begin
l := 1;
r := k;
Repeat
j := (l + r) div 2;
If b < A[j]
then r := j
else l := j + 1;
Until (l = j);
For i := k downto j do
A[i+1] := A[i];
A[j] := b ;
end
end;
End.
Програма швидкого сортування.
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 : Integer;
x : Data;
Begin
If L < R
then begin
x := A[(L + R) div 2];
left := L;
right := R ;
Repeat
While A[left] < x do
left := left + 1;
While A[right] > x do
right:=right - 1;
If left <= right
then begin
Swap(left, right);
left := left + 1;
right := right - 1;
end
until left > right;
Hoare(L, right);
Hoare(left, R)
end
End;
Begin
Hoare(1, n);
End.
Контрольні запитання
-
Як застосувати метод покрокової деталізації для розробки алгоритмів сортування
-
Як оцінюється алгоритм сортування обмінами?
-
Як оцінюється алгоритм сортування вставками?
-
Як оцінюється алгоритм сортування Ноара?