Содержание
Структуры данных и алгоритмы их обработки
лабораторный практикум
Направление подготовки: 27.03.04 (220400.62) «Управление в технических системах»
Профиль подготовки: «Управление и информатика в технических системах»
Направление подготовки 09.03.01 (230100.62) «Информатика и вычислительная техника»
Профиль подготовки: «Программное обеспечение вычислительной техники и автоматизированных систем»
Квалификация (степень) выпускника - бакалавр
Формы обучения - очная, очно-заочная, заочная
Г. Коломна, 2015
Коломенский институт (филиал)
Федерального государственного бюджетного образовательного учреждения
Высшего профессионального образования
«Московский государственный машиностроительный университет (МАМИ)»
«УТВЕРЖДАЮ»
Директор КИ (филиал) МАМИ
____________________
«____»________________2015 г.
Лабораторный практикум
Структуры данных и алгоритмы их обработки
Направление подготовки «Управление в технических системах»
Профиль подготовкиУправление и информатика в технических системах
Направление подготовки «Информатика и вычислительная техника»
Профиль подготовки«Программное обеспечение вычислительной техники и автоматизированных систем»
Квалификация (степень) выпускникабакалавр
(бакалавр, магистр, дипломированный специалист)
Форма обученияочная , очно-заочная, заочная
Г. Коломна, 2015 г.
| УДК 004.4 ББК 32.97 П 78 | Печатается в соответствии с решением учебно-методического совета Коломенского института (филиала) Московского государственного университета машиностроения от 02.02.2015г.№1-10/УМС |
Структуры данных и алгоритмы их обработки: Лабораторный практикум для студентов очной и очно-заочной, заочной форм обучения направления подготовки бакалавров 220400.62 – Управление в технических системах и 230100.62 – Информатика и вычислительная техника:/ Сост. Филоненко И.Н. – Коломна: КИ (ф) МАМИ, 2014. – 41 с.
Лабораторный практикум составлен в соответствии с Государственными образовательными стандартами высшего профессионального образования по направлению подготовки бакалавров 220400.62 – Управление в технических системах и 230100.62 – Информатика и вычислительная техника.
Лабораторный практикум одобрен на заседании кафедры «Автоматизации производства и информационных технологий» Коломенского института (филиала) МАМИ, протокол № 1 от 02.09.14 и утвержден учебно-методическим советом.
УДК 004.4
ББК 32.97
© Филоненко И.Н.
© КИ (ф) МГМУ, 2014
Содержание
Введение ....................................................................................................................... 5
Лабораторная работа №1
Фундаментальные структуры данных ...................................................................... 6
Лабораторная работа №2
Алгоритмы поиска в фиксированной группе данных ........................................... 10
Лабораторная работа №3
Алгоритмы базовых и улучшенных сортировок.
Порядковые статистики ............................................................................................ 13
Лабораторная работа №4
Полустатические структуры данных ..................................................................... 18
Лабораторная работа №5
Динамические структуры данных - односвязные и двусвязные списковые структуры.................................................................................................................... 22
Лабораторная работа №6
Деревья, как динамические структуры данных ..................................................... 26
Лабораторная работа №7
Алгоритмы метода перебора с возвратами - (МПВ), "жадные" алгоритмы................................................................................................................... 29
Лабораторная работа №8
Хеширование. Алгоритмы организации и обработки хеш-таблиц ...................... 32
Лабораторная работа №9
Сетевые модели. Алгоритмы на графах .................................................................. 35
Введение
Цикл лабораторных работ направлен на освоение студентами фундаментальных принципов построения эффективных и надежных программ.
«Алгоритмы + структуры данных = программы» (Н.Вирт) - тезис, на котором базируется искусство программирования.
В процессе выполнения лабораторных работ студенты осваивают и анализируют основные алгоритмы обработки различных структур данных. Освоение достигается путем программирования учебных задач на языке Object Pascal в визуальной среде программирования Delphi.
Первая задача: (8 часов) – посвящена изучению фундаментальных структур данных (статических) – массивы, записи, множества и последовательные файлы, также алгоритмам формирования этих структур для реальных данных и их обработки.
Вторая задача: (4 часа) – посвящена алгоритмам поиска в массивах, а также в строках различной организации.
В третьей работе: (8 часов) – студентам предлагается освоение на практике: 1) базовых алгоритмов сортировки массива;
2) улучшенных методов сортировки, построенных на основе простейших, реализованных студентом при выполнении п.1).
Четвертая и пятая работы: (8 часов) – посвящены моделированию таких структур данных, как очереди, стеки (линейные, кольцевые), деки, построение как на базе полустатических данных, так же динамических списковых структур.
Шестая работа: (8 часов) – направлена на освоение алгоритмов построения, обработки и вывода (печати) деревьев различной структуры: бинарные, сбалансированные АВЛ-деревья, сильноветвящиеся Б-деревья.
Седьмая работа: (4 часа) – предназначена для изучения и реализации общих методов обработки данных: алгоритмы перебора с возвратом, динамического программирования и, так называемые, «жадные» алгоритмы для различных задач.
В восьмой работе: (4 часа) – студенты должны написать и отладить программу для быстрого поиска с помощью организации и использования
хеш-таблиц.
В девятой работе: (4 часа) – студентами осваиваются, реализуются и анализируются различные алгоритмы на графах.
Предлагаемые варианты задач для реализации достаточно небольшие, чтобы их можно было реализовать полностью в процессе выполнения лабораторных работ.