- •Лабораторный практикум по курсу « Структуры и алгоритмы обработки данных » Оглавление
- •20 Методика выполнения лабораторной работы 28
- •30 Лабораторное задание 45
- •47 Решение задач 72
- •1. Лабораторная работа - Методы сортировки
- •Теоретические сведения
- •Сортировка выбором
- •Сортировка вставкой
- •Сортировка обменом
- •Сортировка Шелла
- •Быстрая сортировка (сортировка Хоара)
- •Сортировка в нелинейных структурах
- •Турнирная сортировка
- •Пирамидальная сортировка
- •Функция сложности алгоритма
- •Лабораторное задание
- •Методика выполнения лабораторной работы
- •Пояснения к выполнению работы.
- •Лабораторная работа -Методы поиска
- •Теоретические сведения
- •Последовательный поиск.
- •Бинарный поиск.
- •Фибоначчиев поиск.
- •Интерполяционный поиск.
- •Поиск по бинарному дереву.
- •Поиск по сбалансированному дереву.
- •Поиск по бору
- •Поиск хешированием
- •Алгоритмы поиска словесной информации
- •Алгоритм Кнута - Морриса - Пратта
- •Алгоритм Бойера - Мура
- •Алгоритм Рабина
- •Лабораторное задание
- •Методика выполнения лабораторной работы
- •Лабораторная работа -Итеративные и рекурсивные алгоритмы
- •Теоретические сведения
- •Итеративный алгоритм.
- •Итеративное вычисление факториала
- •Рекурсивное вычисление факториала
- •Рекурсивные структуры данных
- •Формирование бинарного дерева
- •Рекурсивная процедура обхода узлов дерева сверху-вниз
- •Лабораторное задание
- •Требования к отчету
- •Контрольные вопросы
- •Литература
- •Лабораторная работа - Алгоритмы построения остовного дерева сети
- •Теоретические сведения
- •Алгоритмы Крускала и Прима
- •Пример со схемой микрорайона
- •Пример со схемой компьютерной сети
- •Лабораторное задание
- •Требования к отчёту
- •Литература
- •Задание к лабораторной работе 4
- •Решение задач
- •Лабораторная работа - Алгоритмы нахождения на графах кратчайших путей
- •Теоретические сведения
- •Метод динамического программирования.
- •Пример определения кратчайшего пути №1
- •Пример нахождения кратчайшего пути при условии, что граф неориентированный№2
- •Метод Дейкстры
- •Алгоритм Флойда
- •Алгоритм Йена
- •Алгоритм Беллмана- Форда
- •Литература
- •Лабораторное задание.
- •Требования к отчету
- •Варианты заданий
- •Задание 1: Найти кратчайший путь на графе между тремя парами вершин методом динамического программирования
- •Задание 2: Найти кратчайший путь между тремя парами вершин методом Дейкстры
- •Решение задач
- •Задание на разработку программы
- •Лабораторная работа -Эвристические алгоритмы
- •Теоретические сведения
- •Волновой алгоритм
- •Двухлучевой алгоритм.
- •Пример 2. Осуществить трассировку элементов а и в .
- •Четырехлучевой алгоритм
- •Маршрутный алгоритм.
- •Геометрическая модель задачи о лабиринте
- •Алгоритмы составления расписания.
- •Литература
- •Лабораторное задание.
- •Требования к отчету
- •Решение задач
-
Сортировка в нелинейных структурах
Сортировка в нелинейных структурах осуществляется только на бинарных деревьях (деревьях, из каждой вершины которого выходит по два ребра).
-
Турнирная сортировка
Свое название эта сортировка получила, потому что она используется при проведении соревнований, турниров и олимпиад. Элементы исходного множества представляются листьями дерева. Их по парное сравнение позволяет определить максимальный элемент.
Пример: Дано исходное множество { 7, 1, 9, 3, 6, 5, 8 }
Производится по парное сравнение элементов снизу- вверх. Найденный максимальный элемент помещается в результирующее множество.

В результате будет получено упорядоченное множество { 9,8,7,6,5,3}
-
Пирамидальная сортировка
Данный тип сортировки заключается в построение пирамидального дерева.
Пирамидальное дерево – это бинарное дерево обладающее тремя свойствами:
-
В вершине каждой триады располагается элемент с большим весом.
-
Листья бинарного дерева располагаются либо в одном уровне либо в двух соседних













на одном уровне
на соседних



уровнях









-
Листья нижнего уровня располагаются левее листьев более высокого уровня.
В ходе преобразования элементы триад сравниваются дважды , при этом
элемент с большим весом перейдет вверх, а с меньшим - вниз.



1 2
1 - первое сравнение
2 - второе сравнение
Пример: Дано исходное множество { 2, 4, 6, 3, 5, 7 }

В результате будет получено упорядоченное множество { 2,3,4,5,6,7 }
-
Функция сложности алгоритма
Для оценки эффективности алгоритмов используется функция сложности алгоритма, которая обозначается заглавной буквой “О”, в круглых скобках записывается аргумент. Например, функция сложности O(n2) читается как функция сложности порядка n2. Функция сложности алгоритма – это функция, которая определяет количество сравнений, перестановок а так временные и ресурсные затраты на реализацию алгоритма.
Функция сложности принимает следующий ряд значений:
Функция
сложности
Чем правее на оси расположена функция сложности, тем сложнее алгоритм.
Лабораторное задание
Для каждого из перечисленных методов сортировки провести анализ временных затрат для списков различной размерности.
-
Методика выполнения лабораторной работы
Для проведения лабораторной работы необходимо выполнить следующие действия.
1. Вызвать систему Sort_new, включающую в себя сортировку неупорядоченных списков в линейных и нелинейных структурах.
Путь к файлу: D:\ИПОВС\АиСД\SORT\Sort_new.exe
Система работает в диалоговом режиме с использованием “меню”. Вся необходимая информация во время работы системы отображается на экране дисплея и не требует специальных пояснений.
Основные функции системы
K - конец работы;
? - выдача краткого сообщения о командах;
U – задание условий для генерации неупорядоченного массива;
G - генерации неупорядоченного массива;
P – вывод массива;
W – вывод времени сортировки, количества элементов массива.
Сортировка методом:
1 – простого обмена;
2 – бинарной вставки;
3 – простой вставки;
4 – челночной;
5 – простого выбора;
6 – слиянием;
7 – Шелла;
8 – Хоара;
9 – пирамиды;
Esc – аварийное прерывание выполнения функции.
Краткое описание функции
U– задание условий для генерации неупорядоченного массива (задаются число элементов и границы элементов неупорядоченного массива). Заданные условия сохраняются до следующего вызова функции “U”;
G – генерация неупорядоченного массива, необходима перед каждой сортировкой;
P – вывод массива в текущем состоянии : неупорядоченный (до сортировки) или упорядоченный (после неё);
W - вывод времени сортировки ;
I – 9 – методы сортировки;
Для указанных в лабораторной работе методов сортировки провести следующие исследования:
a) выполнить сортировку массива из N чисел (варианты заданий даны в приложении ; номер варианта соответствует порядковому номеру фамилии студента в списке группы). Результаты занести в таблицу 1.
Таблица 1
-
Метод
Количество элементов сортируемого
массива N
N1
N2
N3
Время сортировки t, c
t1
t2
t3
2. Провести исследование методов сортировки упорядоченных списков с использованием программы SORTALL.
Путь к файлу: D:\ИПОВС\АиСД\SORT\Sortall.exe
Результаты занести в таблицу 1.
3. Провести исследование методов сортировки с использованием программ
WinSort и Sort.
4. Оценить сложность рассмотренных методов сортировки;
а) провести анализ отклонения полученной в результате эксперимента
сложности алгоритма от теоретической;
б) построить графические зависимости времени сортировки от количества
элементов сортируемого массива.
Требования к отчёту
Отчёт должен содержать:
-
конспект лабораторной работы;
-
примеры сортировки ;
-
результаты выполнения работы;
-
выводы по работе;
Контрольные вопросы
-
Что понимается под сортировкой?
2. Каковы особенности сортировки: вставкой, выбором, обменом , Шелла,
Хоара, турнирной, пирамидой?
3. Что включает в себя понятие сложности алгоритма?
4. В чём состоит методика анализа сложности алгоритмов сортировки?
Литература
1. Колдаев В.Д., Поддубная Л. М., Полосухин Б.М. Методы сортировки .
М.:МИЭТ, 1985.
2. Колдаев В.Д., Поддубная Л. М., Полосухин Б.М. Лабораторный практикум по
курсу « Теория алгоритов и вычислительные методы » М.:МИЭТ, 1988
3. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск.
М. : Мир, 2000.
4. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».
М.: МЦНМО, 2000.
5. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.
6. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си.
Учеб. пособие. М : Финансы и статистика, 2004.
Приложение
Варианты заданий
|
Вариант |
n1 |
n2 |
n3 |
Составить программу |
|
1,15 |
1000 |
4000 |
6000 |
Простая вставка |
|
2,16 |
800 |
3000 |
7000 |
Сортировка слиянием |
|
3,17 |
2000 |
5000 |
6800 |
Метод Шелла |
|
4,18 |
1500 |
3500 |
6000 |
Простой выбор |
|
5,19 |
1000 |
2800 |
8500 |
Метод Хоара |
|
6,20 |
500 |
2500 |
6500 |
Бинарная вставка |
|
7,21 |
900 |
3000 |
8500 |
Шейкерная сортировка |
|
8,22 |
1200 |
2000 |
7500 |
Простая вставка |
|
9,23 |
2500 |
3500 |
6500 |
Шейкерная сортировка |
|
10,24 |
1600 |
2800 |
8800 |
Метод Шелла |
|
11,25 |
2200 |
3400 |
7200 |
Простой выбор |
|
12,26 |
1900 |
2700 |
8000 |
Метод Хоара |
|
13,27 |
1300 |
3500 |
6000 |
Бинарная вставка |
|
14,28 |
1700 |
2800 |
7500 |
Сортировка слиянием |
Предусмотреть в программе учет времени сортировки для указанных значений n1, n2, n3. Для сортировок Шелла, Хоара, пирамидальной значения n1, n2, n3
удвоить. Составить программу, реализующую один из методов сортировки.
Произвести расчет функции сложности разработанного алгоритма по полученным временным затратам.
