Правила выполнения лабораторных работ

Перед выполнением заданий лабораторной работы рекомендуется изучить теоретический материал по теме практической работы работы и описание методов обработки данных на псевдокоде, используя конспекты лекционных занятий и литературу из списка.

Задания лабораторных  работ выполняются только на языке программирования С/С++, среда программирования по выбору студента.
Изучаемые методы обработки данных рекомендуется программно реализовывать в виде отдельных функций (подпрограмм), массивы (последовательности) данных должны передаваться в подпрограммы в качестве параметров. Заполнение массивов данными, вывод их на экран, вычисление вспомогательных величин и пр. необходимо оформлять в виде отдельных подпрограмм.
При выполнении заданий следует обеспечить вывод на экран данных на всех шагах алгоритма. Программа должна иметь дружественный, интуитивно понятный интерфейс (меню пользователя, вывод подсказок, комментарии при вводе/выводе данных и т.д.).
В программе в ходе выполнения алгоритма необходимо предусмотреть подсчет количества сравнений С и количества пересылок М и вывести их экран.
Тестирование разработанной программы необходимо проводить для различных типов входных данных (случайный массив, упорядоченный массив в прямом и обратном порядке). После тестирования необходимо проанализировать полученные результаты, т.е. проверить соответствие полученных экспериментальным путем величин М и С теоретическим оценкам трудоемкости реализованных методов.

Для зачета по лабораторной работе студенту необходимо представить в отдельной папке

• Исходные тексты программ с подробными комментариями;
• Исполняемые файлы;
• Отчет по лабораторной работе.

Отчет должен включать в себя следующие разделы

• Формулировку задания
• Описание основных методов, используемых в  работе;
• Результаты работы программы (в виде файла или в виде скриншота);
• Анализ результатов.

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

Методы сортировки массивов

Цель работы: Освоить методы сортировки массивов.

Порядок выполнения работы:

1. Разработать подпрограммы сортировки массива целых чисел методами прямого выбора, методом Шелла и методом пирамидальной сортировки (или методом Хоара на выбор).
2. Отладить правильность работы соритровок на массивах малой длины. Кроме того,

 контролировать правильность сортировки путем подсчета контрольной суммы и числа серий в массиве (оформить в виде подпрограммы).

Серией называется неубывающая последовательность элементов массива максимальной длины.

Пример: в массиве 23145314  (23  145   3  14) содержится  4 серии

3. Составить таблицу следующего вида (данные получить экспериментально) для n=100, 200, 300, 400, 500. (n – количество элементов в массиве)

Размер массива	Мф+Сф метод пр. выбора			Мф+Сф м. Шелла			Мф+Сф пирам. (м. Хоара)
	Убыв.	Случ.	Возр.	Убыв.	Случ.	Возр.	Убыв.	Случ.	Возр.
100
200
300
400
500

4. Проанализировать полученные результаты, сравнить их с теоретическими оценками трудоемкости.

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

Быстрые методы сортировки последовательностей.

Цель работы: Освоить быстрые методы сортировки последовательностей

Порядок выполнения работы:

1. Разработать подпрограммы сортировки последовательности целых чисел методом прямого слияния (или методом цифровой сортировки).
2. Разработать сервисные функции для работы со списками:

• заполнение списка (стека) возрастающими числами;
• заполнение списка (стека) убывающими числами;
• заполнение списка (стека) случайными числами;
• печать элементов списка;
• подсчет контрольной суммы элементов списка;
• подсчет количества серий в списке.

3. Составить таблицу следующего вида (данные получить экспериментально) для n= 100, 200, 300, 400, 500. (n – количество элементов в массиве)

Длина списка	(Мф+Сф ) метод прямого слияния (цифровая сорт.)
	Возрастающие числа	Убывающие числа	Случайные числа
100
200
300
400
500

4. Проанализировать полученные результаты, сравнить их с теоретическими оценками трудоемкости. Сравнить полученные результаты с трудоемкостью метода прямого выбора и метода пирамидальной сортировки (использовать результаты предыдущих лабораторных работ).

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

Хэширование и поиск

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

Порядок выполнения работы:

1. Разработать подпрограмму хеширования массива целых чисел методом прямого связывания и подпрограмму поиска в хэш-таблице элемента по заданному ключу. Вывести на экран построенную хэш-таблицу.
2. Реализовать подпрограмму хеширования массива целых чисел методом открытой адресации. Для разрешения коллизий использовать линейные и квадратичные пробы. Вывести на экран заполненные хеш-таблицы для m=11 в виде

Номер ячейки	0	1	2	3	…			…	m-1
Число

3. Подсчитать и сравнить количество коллизий при линейных и квадратичных пробах. Построить таблицу и проанализировать полученные результаты:

Размер хеш-таблицы	Количество исходных чисел	Количество коллизий
		Линейные пробы	Квадратичные пробы
13	15
29	30
43	45
67	70
83	85

4. Организовать поиск элемента с заданным ключом для метода открытой адресации (линейные и квадратичные пробы).