- •В. Д. Колдаев Лабораторный практикум по курсу « Структуры и алгоритмы обработки данных »
- •Часть 1
- •Лабораторная работа № 1 « Методы сортировки »
- •Теоретические сведения
- •Методы сортировки
- •Сортировка вставкой
- •Сортировка обменом
- •Сортировка Шелла
- •Быстрая сортировка (сортировка Хоара)
- •Сортировка в нелинейных структурах
- •Турнирная сортировка
- •Пирамидальная сортировка
- •Функция сложности алгоритма
- •Лабораторное задание
- •Методика выполнения лабораторной работы
- •Основные функции системы
- •Варианты заданий
- •Лабораторная работа №2 «Методы поиска».
- •Теоретические сведения
- •Методы поиска
- •Последовательный поиск.
- •Бинарный поиск.
- •Фибоначчиев поиск.
- •Интерполяционный поиск.
- •Поиск по бинарному дереву.
- •Поиск по бору.
- •Поиск хешированием.
- •Алгоритмы поиска словесной информации
- •Алгоритм Бойера - Мура
- •Лабораторное задание
- •Методика выполнения лабораторной работы
- •Варианты заданий
- •Использовать алгоритмы Кнута - Морриса – Пратта, Бойера – Мура, Рабина для поиска текстовой информации. Лабораторная работа № 3 «итеративные и рекурсивные алгоритмы»
- •Теоретические сведения
- •Рекурсивные структуры данных
- •Лабораторное задание
- •Требования к отчету
- •Контрольные вопросы
- •Литература
- •Лабораторная работа № 4 «Алгоритмы построения остовного дерева сети».
- •Теоретические сведения
- •Лабораторное задание
- •Литература
- •Задание : Построить остовное дерево графа методами Крускала и Прима.
- •Решить задачи
- •Лабораторная работа № 5. Алгоритмы нахождения на графах кратчайших путей.
- •Теоретические сведения
- •Метод динамического программирования.
- •Метод Дейкстры
- •Алгоритм Флойда
- •Алгоритм Йена
- •Литература
- •Лабораторное задание.
- •Варианты заданий
- •Задание 2: Найти кратчайший путь между тремя парами вершин методом Дейкстры
- •Решить задачи
- •Составить программу для нахождения кратчайшего пути
- •Лабораторная работа № 6 « Эвристические алгоритмы »
- •Теоретические сведения
- •Волновой алгоритм.
- •Двухлучевой алгоритм.
- •Пример 2. Осуществить трассировку элементов а и в .
- •Четырехлучевой алгоритм.
- •Маршрутный алгоритм.
- •Геометрическая модель задачи о лабиринте
- •Алгоритмы составления расписания.
- •Литература
- •Лабораторное задание.
- •Решить задачи
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОННОЙ ТЕХНИКИ
( ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ )
В. Д. Колдаев Лабораторный практикум по курсу « Структуры и алгоритмы обработки данных »
Часть 1
В лабораторном практикуме рассмотрен широкий круг алгоритмов обработки линейных и нелинейных структур данных, без знания которых невозможно современное компьютерное моделирование. Приведены основные понятия и определения, технология работы и фрагменты программ. В конце каждой лабораторной работы имеются варианты заданий и задачи для самостоятельного решения. При выполнении лабораторных работ используются компьютерные обучающее- контролирующие программы,
разработанные на кафедре ИПОВС.
Практикум предназначен для студентов, аспирантов и преподавателей всех специальностей МИЭТ.
Лабораторная работа № 1 « Методы сортировки »
Цель работы:ознакомление с алгоритмами сортировки линейных и нелинейных структур и методикой оценки эффективности алгоритмов.
Продолжительность работы:- 2 часа.
Теоретические сведения
Упорядочение элементов множества в возрастающем или убывающем порядке называется сортировкой.
С упорядоченными элементами проще работать, чем с произвольно расположенными: легче найти необходимые элементы, исключить ,вставить новые. Сортировка применяется при трансляции программ, при организации наборов данных на внешних носителях, при создании библиотек, каталогов, баз данных и т.д.
Алгоритмы сортировки можно разбить на следующие группы:
Методы сортировки
Турнирная
Пирамидальная
Простая Простой Стандартный
вставка выбор обмен
Бинарная Метод
вставка Шелла
Метод
Хоара
Обычно сортируемые элементы множества называют записями и обозначают через
k1, k2, …,kn .
Сортировка выбором
Сортировка выбором состоит в том, что сначала в неупорядоченном списке выбирается и отделяется от остальных наименьший элемент. После этого исходный список оказывается изменённым. Изменённый список принимается за исходный и процесс продолжается до тех пор, пока все элементы не будут выбраны. Очевидно, что выбранные элементы образуют упорядоченный список.
Например, требуется найти минимальный элемент списка:
{5, 11, 6, 4, 9, 2, 15, 7}
Процесс выбора показан на рис.1, где в каждой строчке выписаны сравниваемые пары. Выбираемые элементы с меньшим весом обведены кружком. Нетрудно видеть, что число сравнений соответствует на рисунке числу строк, а число перемещений – количеству изменений выбранного элемента.
{5, 11, 6, 4, 9, 2, 15, 7}
Рис.1. Сортировка выбором
Выбранный в исходном списке минимальный элемент размещается на предназначенном ему месте несколькими способами:
Минимальный элемент после i-го просмотра перемещается наi-ое место нового списка (i = 1, 2, .… , n), а в исходном списке на место выбранного элемента записывается какое-то очень большое число, превосходящее по величине любой элемент списка, при этом длина заданного списка остаётся постоянной. Изменённый таким образом список можно принимать за исходный.
Минимальный элемент записывается на i-ое место исходного списка (i = 1, 2, .… , n), а элемент сi-го места - на место выбранного. При этом очевидно, что уже упорядоченные элементы (а они будут расположены, начиная с первого места ) исключаются из дальнейшей сортировки, поэтому длина каждого последующего списка (списка, участвующего в каждом последующем просмотре) должна быть на 1 элемент меньше предыдущего.
Выбранный минимальный элемент, как и в предыдущем случае, перемещается на i-ое место заданного списка, а чтобы этоi-ое место освободилось для записи очередного минимального элемента, левая от выбранного элемента часть списка перемещается вправо на одну позицию так, чтобы заполнилось место, занимаемое до этого выбранным элементом.
Сложность метода сортировки выбором порядка O(n²).