Лабораторные работы

по предмету : ” Анализ и построение алгоритмов ”

Лабораторная работа № 1

	Тема: Сравнение времени работы алгоритмов

Цель:  Временной  анализ  функций

Задание:
	1. Пусть имеется алгоритм, решающий задачу размера n за f(n) микросекунд. Каков максимальный размер задачи, которую он сможет решить за время t ? Найти его для функций и времён, перечисленных в таблице.

№ варианта	f(n)	1 сек	1 мин	1 час	1 день	1 месяц	1 год	1 век	
1	log n								
2	ln n								
3	√n								
4	n								
5	1/n								
6	n log n								
7	n2								
8	n3								
9	2n								
10	n!								
11	n/ log n								
12	log log n								
13	log (n!)								

	2. Сравнение алгоритмов

Для всех клеток следующей таблицы ответьте «да» или «нет» на вопрос о том, можно ли записать А как Ơ, ơ, Ω, ω или Θ от В (k≥1, ε>0, c, m>1 – некоторые константы).

A	B	Ơ	ơ	Ω	ω	Θ	
Logk n	nε						
nk	cn						
√n	nsin n						
2n	2n/2						
nlog m	mlog n						
log (n!)	log (nn)						
	3. Сравнение скорости роста

	Расположите следующие функции в порядке увеличения скорости роста и отметьте, какие из этих функций на самом деле имеют одинаковую скорость роста (каждая функция есть Ơ (следующая)) и отметьте, какие из этих функций  на самом деле имеют одинаковую скорость роста ( одна есть Θ от другой):

1.	2log m  	 	(√2) log m

2.	22**n		22**n+1	

3.	n!		( n+1)!	

4	log (n!)	(log n)!

5.	(3/2)n		en 		n*2n	

6.	n		2n		n3		n2

7.	n1/ log n  	n log log n	(log n) (log n)	

8.	ln n		ln ln n

9.	4 log n	log2 n		n log n

10.	`√ (log n)	2√ (2log n)

Содержание отчета:

1.	Привести алгоритм реализации функции и построения графической зависимости времени от размерности массива.
2.	Привести временной анализ функции в зависимости от размерности массива в виде таблицы.
3.	Построить график заданной функции
4.	Листинг программ

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

	Тема:  Методы быстрой сортировки и их сравнительный анализ

Цель:  Реализация и анализ алгоритмов сортировки

Содержание отчета:

1.	Для трех любых алгоритмов сортировки записать алгоритм с помощью псевдокода.
2.	Продемонстрировать работу алгоритмов для массива, указанном в разделе «задание к лабораторным работам» п.2.
3.	Провести временной анализ алгоритмов сортировки, времена нужно измерять без учета операций чтения/записи (см. п.1 в разделе «задание к лабораторным работам». Построить графическую зависимость времени от размерности массива для каждого из алгоритмов.
4.	Результаты работы программ.
5.	Листинги программ.

Теоретическая часть

Перечень эффективных методов сортировки

1.	Сортировка методом  вставок.
2.	Сортировка методом Шелла
3.	Быстрая сортировка 
4.	Сортировка методом Синглтона.
5.	Сортировка подсчетом.
6.	Восходящая поразрядная сортировка.
7.	Нисходящая поразрядная сортировка.

Методы сортировки слиянием

1.	Сортировка двоичным слиянием.
2.	Сортировка слиянием с делением на секции.
3.	Сортировка слиянием по принципу « нарезание  печенья » 

Задания к лабораторной работе:

1. Испытать программу на заданных файлах разной длины и степени упорядоченности. Имена файлов в наборе исходных данных сформированы из трех чисел. Первые два числа составляют имя файла: 4 - значное, задающее длину N файла в байтах и идущее за ним через символ подчеркивания "_" 3-значное, задающее процент I инверсий. Процент инверсий вычисляется от максимально возможного числа инверсий (число пар i < j  для которых A[i] > A[j]) N*(N-1)/2 и принимает значения от 0 до 100. Расширение файла может принимать значения 1 и 2 и определяет случайный вариант файла с одними и теми же параметрами N и I. Например, файл 0256_050.2 соответствует последовательности из N=256 чисел с количеством инверсий I = 50% от максимального, вариант 2. Таким образом, программу нужно испытать на примерно 30 различных файлах, что приводит к необходимости сводить времена работы программы в таблицы, соответствующие разным процентам инверсий I = 0%, 50%, 100%. Для значений I = 0% и I = 100% очевидно существует только по одному варианту файла данных.

	Пример таблицы для I=50%

№	128	256	512	1024	4096	8192	16384	
Вар.1								
Вар 2								

2. 
№ варианта	Массив	
1	21, 31, 24, 10, 31, 41, 8, 2	
2	15, 25, 10, 16, 5, 30, 57, 15	
3	3, 42, 31, 84, 89, 5, 73, 42	
4	1, 99, 33, 5, 3, 37, 44, 32	
5	7, 5, 2, 96, 37, 54, 49, 8	
6	56, 83, 55, 9, 55, 1, 10, 90	
7	11, 35, 56, 41, 24, 88, 6, 11	
8	67, 82, 36, 34, 55, 82, 4, 18	
9	17, 3, 7, 80, 3, 11, 64, 32	
10	49, 28, 74, 56, 81, 14, 76, 44	
11	87, 22, 57, 13, 9, 11, 31, 89	
12	16, 54, 33, 54, 17, 19, 90, 2	
13	53, 50, 60, 78, 5, 77, 86, 12	
14	3, 5, 16, 9, 31, 15, 32, 87	
15	4, 1, 21, 15, 5, 1, 18, 30	

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

	Тема:  Организация очереди с приоритетом  с помощью кучи

Цель: Изучение основного свойства кучи, ее построение и сортировка. Организация очереди с приоритетом с помощью кучи.

Задание:
1.	Реализовать алгоритм построения кучи
2.	Реализовать алгоритм сортировки с помощью кучи.
3.	Организовать очередь с приоритетами и показать работу процедур:
-	HEAP-INSERT (A,key) для кучи А;
-	HEAP-EXTRACT-MAX   для этой кучи. 

Содержание отчета 

1.	Привести, используя псевдокоды, алгоритмы основных операций над кучей 
-	поддержание основного свойства кучи,
-	построение кучи,
-	сортировка массива, не используя дополнительной памяти,
-	взятие наибольшего элемента массива,
-	добавление элемента.
2.	Продемонстрировать эти алгоритмы на примере (см. задание к лабораторной работе)
3.	Провести сравнение с алгоритмами, рассмотренными в лабораторной работе № 2. Сформулировать выводы.
4.	Результаты работы программ.
5.	Листинги программ

Задания к лабораторной работе: 

№ варианта	Массив A	Элемент добавления, key	
1	21, 31, 24, 10, 31, 41, 8, 2, 57, 15	26	
2	15, 25, 10, 16, 5, 30, 57, 15, 8, 2	20	
3	3, 42, 31, 84, 89, 5, 73, 40, 44, 32	40	
4	1, 99, 33, 5, 3, 37, 44, 32, 57, 15	30	
5	7, 5, 2, 96, 37, 54, 49, 8, 44, 32	50	
6	56, 83, 25, 9, 55, 1, 10, 90, 8, 2	60	
7	21, 35, 56, 41, 24, 88, 6, 11, 57, 15	40	
8	67, 82, 36, 34, 55, 89, 4, 18, 44, 32	50	
9	17, 3, 7, 80, 23, 11, 64, 32, 8, 2	20	
10	49, 28, 74, 56, 81, 14, 76, 44, 57, 15	60	
11	87, 22, 57, 13, 9, 11, 31, 89, 8, 2	30	
12	16, 54, 33, 34, 17, 19, 90, 2, 44, 32	20	
13	53, 50, 60, 78, 5, 77, 86, 12, 57, 15	65	
14	3, 5, 16, 9, 31, 15, 32, 87, 8, 2, 44	20	
15	15, 25, 10, 16, 3, 5, 30, 57, 1, 44, 32	27	
16	1, 99, 33, 5, 3, 37, 7, 44, 32, 57, 15	40	
17	56, 83, 55, 9, 55, 1, 10, 12, 90, 44, 32	60	
18	67, 3, 82, 36, 34, 55, 83, 4, 18, 8, 2	50	
19	49, 28, 74, 56, 81, 19, 14, 76, 4, 57, 15	50	
20	16, 54, 33,5, 58, 17, 19, 90, 2, 44, 32	40	
21	3, 5, 16, 9, 31, 15, 32, 35, 87, 8, 2	34	
22	21, 30, 7, 24, 10, 31, 41, 8, 2, 57, 15	25	
23	83, 3, 42, 31, 84, 89, 5, 73, 46, 8, 2	50	
24	7, 5, 2, 17, 96, 37, 54, 49, 8, 44, 32	40	
25	11, 35, 56, 53, 41, 24, 88, 6, 21, 57, 15	55	
26	17, 38, 7, 80, 3, 11, 64, 32, 36, 8, 2	60	
27	87, 22, 57, 63, 13, 9, 11, 31, 89, 44, 32	60	
28	53, 50, 60, 78, 5, 77, 11, 86, 12, 57, 15	70	
29	9, 6, 93, 84, 67, 33, 52 ,99, 81, 8, 2	70	
30	3, 5, 16, 9, 31, 15, 32, 87, 8, 2, 44	20	

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

Тема: Хеш-таблицы

Цель: Изучить работу  алгоритмов: прямой адресации, хеш-таблицы и открытой адресации. Реализовать перечисленные выше алгоритмы и провести их сравнительный анализ.

Задание

1.	Написать алгоритмы основных операций (добавление, поиск и удаление) в псевдокодах для прямой адресации, хеш-таблицы и открытой адресации.
2.	Реализовать основные операции на ЭВМ.
3.	Провести анализ этих алгоритмов и сделать вывод по их применимости.

Содержание отчета

1.	Привести все используемые алгоритмы в псевдокодах.
2.	Продемонстрировать работу алгоритмов на примере (см. раздел «задание к лабораторной работе»).
3.	Привести сравнительный анализ алгоритмов в соответствии с заданием (п.1).
4.	Результаты работы программ.
5.	Листинги программ.

 Задания к лабораторной работе 

1. Пусть размер хеш-таблицы равен m = 20, а хеш-функция имеет вид
h(k) = [m(kA mod 1)], где А = (- l)/2.
В какие позиции попадут ключи (см. таблицу, столбец 3)?
2. Как будет выглядеть хеш-таблица с цепочками  после того, как  в неё последовательно поместили элементы с  ключами (см. таблицу, столбец 2) (в указанном порядке)? Число позиций в таблице равно 9, хеш-функция имеет вид h(k)=k mod 9.
3. Выполните добавление ключей (в указанном порядке, см. таблицу. столбец 2) в хеш-таблицу с открытой адресацией размера m = 11. Для вычисления последовательности проб используется линейный метод с h'(k) = k mod m. Выполните то же задание, если используется квадратичный метод с той же h', c1 = 1, c2 = 3, а также для двойного хеширования с h1 = h' и h2(k) = 1 + (k mod (m - 1)).
Таблица
№ варианта	Массив	Ключи	
1	2	3	
1	10, 22, 31, 4, 15, 28, 17, 88, 59	61, 62, 63, 64 и 65	
2	21, 31, 24, 10, 40, 41, 9, 2, 20	51, 52, 53, 54 и 55	
3	15, 25, 10, 16, 5, 30, 57, 18, 19	41, 42, 43, 44 и 45	
4	3, 42, 31, 84,9, 5, 73, 4, 13	31, 32, 33, 34 и 35	
5	1, 99, 33, 5, 3, 37, 44, 32, 12	21, 22, 23, 24 и 25	
6	7, 5, 2, 19, 37, 54, 49, 8, 10	46, 47, 48, 49 и 50	
7	56, 18, 55, 9, 50, 1, 10, 88, 27	36, 37, 38, 39 и 40	
8	11, 35, 56, 41, 24, 88, 6, 2, 26	44, 45, 46, 47 и 48	
9	67, 76, 37, 34, 57, 13, 4, 1, 10	56, 57, 58, 59 и 60	
10	17, 3, 9, 73, 6, 10, 64, 32, 21	66, 67, 68, 69 и 70	
11	49, 32, 75, 53, 85, 19, 76, 44, 5	81, 82, 83, 84 и 85	
12	80, 22, 57, 13, 9, 18, 31, 86, 42	43, 44, 45, 46 и 47	
13	16, 5, 33, 34, 17, 29, 35, 6, 38	33, 34, 35, 36 и 37	
14	59, 50, 4, 28, 5, 77, 86, 12, 22	53, 54, 55, 56 и 57	
15	3, 5, 16, 9, 21, 14, 36, 44, 17	87, 86, 88, 89 и 90	
16	3, 42, 31, 12, 33, 24, 13, 40, 10	63, 64, 65, 66 и 67	
17	19, 37, 54, 49, 10, 1, 45,  18, 13	83, 84, 85, 86 и 87	
18	17, 88, 59, 4, 15, 28, 10, 22, 31	65,63, 64, 62 и 61	
19	9, 2, 20, 10, 40, 41, 21, 31, 24	55, 54, 53, 52 и 51	
20	57, 18, 19, 16, 5, 30, 15, 25, 10	45, 44, 43, 42 и 41	
21	73, 4, 13, 84,9, 5, 3, 42, 31	35, 34, 33, 32 и 31	
22	44, 32, 12, 5, 3, 37, 1, 99, 33	25, 24, 23, 22 и 21	
23	49, 8, 10, 19, 37, 54, 7, 5, 2	50, 49, 48, 47 и 46	
24	10, 88, 27, 9, 50, 1, 56, 18, 55	40, 39, 38, 37 и 36	
25	88, 6, 2, 26, 56, 41, 24, 56, 18	48, 47, 46, 45 и 44	
26	6, 2, 26, 41, 24, 88, 11, 35, 56	60, 59, 58, 57 и 56	
27	64, 32, 21, 73, 6, 10, 17, 3, 9	70, 69, 68, 67 и 66	
28	76, 44, 5, 53, 85, 19, 80, 22, 57	85, 84, 83, 82 и 81	
29	31, 86, 42, 13, 9, 18, 80, 22, 57	47, 46, 45, 44 и 43	
30	35, 6, 38, 34, 17, 29, 16, 5, 33	37, 36, 35, 34 и 33	

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

Тема:  Динамическое программирование. Задача об умножении последовательности матриц

Цель: Найти такую (полную) расстановку скобок  в произведении матриц, чтобы вычисление произведения требовало наименьшего числа умножений

Задание:
1.	Реализовать алгоритм перемножения двух матриц MATRIX- MULTIPLY(A, B).
2.	Реализовать алгоритм вычисления оптимальной стоимости MATRIX-CHAIN-ORDER(p).
3.	Реализовать алгоритм построения оптимального решения MATRIX-CHAIN-MULTIPLY(A, s, i, j).
4.	Разработайте алгоритм MATRIX-CHAIN-PARENS , печатающий оптимальную расстановку скобок.

Содержание отчета 

1.	Привести, используя псевдокоды, перечисленные ниже алгоритмы: 
a.	перемножение двух матриц,
b.	вычисление оптимальной стоимости,
c.	построение оптимального решения.
2.	Продемонстрировать эти алгоритмы на примере (см. задание к лабораторной работе)
3.	Результаты работы программ.
4.	Листинги программ

Задания к лабораторной работе: 

Найдите оптимальную расстановку в задаче о перемножении матриц, если 

№ варианта	Массив P	
1	< 5, 10, 3, 12, 6>	
2	< 12, 5, 50, 6, 3 >	
3	< 10, 3, 5, 12, 4 >	
4	< 12,  30, 5, 6, 10 >	
5	< 3, 10,  5, 50, 5 >	
6	< 50, 5, 10, 6, 4 >	
7	< 4, 8, 3, 20, 5 >	
8	< 20, 4, 8, 5, 10 >	
9	< 10, 5, 20, 15, 10 >	
10	< 10, 3, 5, 12, 4 >	
11	< 2, 10, 5, 15, 10 >	
12	< 10, 15, 5, 12, 4 >	
13	< 10, 4, 5, 15, 8 >	
14	< 6, 8, 4, 10, 15 >	
15	< 10, 8, 5, 12, 5 >	
16	< 4, 10, 6, 8, 5 >	
17	< 4, 8, 6, 10, 20 >	
18	< 10, 4, 10, 12, 5 >	
19	< 6, 4, 15, 8,  5 >	
20	< 4, 6, 8, 10, 5 >	
21	< 4, 10, 8, 5, 10 >	
22	< 5, 8, 6, 10, 5 >	
23	< 6, 10, 15, 10, 5 >	
24	< 4, 10, 15, 10, 4>	
25	<15, 4, 8, 10, 15>	
26	< 4, 15, 20, 10, 5 >	
27	<10, 6, 15, 10, 5 >	
28	< 10, 5, 20, 15, 10 >	
29	< 4, 8, 3, 20, 5 >	
30	< 20, 4, 8, 5, 10 >