МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Томский государственный университет систем управления и радиоэлектроники»
(ТУСУР)
Кафедра автоматизированных систем управления
(АСУ)
Структуры и алгоритмы обработки данных на ЭВМ
Методические указания по выполнению лабораторных работ студентов всех форм обучения для направления подготовки 010400.62 "Прикладная математика и информатика" 2011 г.
2 Горитов А.Н.
Структуры и алгоритмы обработки данных на ЭВМ: методические указания по выполнению лабораторных работ студентов всех форм обучения для направления подготовки: 010400.62 – "Прикладная математика и информатика" / А.Н. Горитов. – Томск: ТУСУР, 2011. – 16 с.
Методические указания разработаны в соответствии с решением кафедры автоматизированных систем управления Составитель: д.т.н., профессор каф. АСУ А.Н. Горитов Методические указания утверждены на заседании кафедры автоматизированных систем управлениям 30 августа 2011 г., протокол № © А.Н. Горитов, 2011 г.
Содержание 1. Цели и задачи дисциплины
2. Методы и формы организации обучения
3. Место дисциплины в структуре ООП
4. Лабораторный практикум
4.1 Перечислимые и интервальные типы
4.2 Множества
4.3 Стеки, очереди
4.4 Связанные списки
4.5 Деревья
4.6 Бинарные деревья
4.7 Сортировка
4.8 Метод ветвей и границ
4.9 Динамическое программирование
4.10 Хеш-таблицы
4.11 Поиск подстрок
4.12 Фундаментальные алгоритмы на графах
4.13 Кратчайшие пути в графе
5. Учебно-методическое и информационное обеспечение дисциплины.... 5.1 Основная литература
5.2 Дополнительная литература
1. Цели и задачи дисциплины Целью изучения дисциплины «Структуры и алгоритмы обработки данных на ЭВМ» является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации, а также алгоритмов обработки данных и анализ этих алгоритмов, взаимосвязь алгоритмов и структур.
В результате изучения дисциплины студент должен:
а) иметь представление об основных тенденциях в создании структур данных, методах оптимального использования памяти и времени для обработки структур данных и управления процессами обработки данных;
б) знать и использовать различные (динамические и статистические) структуры данных в соответствии с запросами алгоритмов;
в) создавать списковые и древообразные структуры и управлять организацией этих структур (изменение списков и деревьев посредством включения исключения, замены элементов структур) знать, использовать оптимальные методы поиска и сортировки данных;
г) знать и использовать основные алгоритмы решения классических задач информатики;
д) иметь представление о математических методах анализа алгоритмов; классификации алгоритмических задач по сложности, сводимости алгоритмических задач к известным задачам определенного класса сложности;
е) иметь опыт работы с алгоритмическими языками программирования.
2. Методы и формы организации обучения Процесс изучения дисциплины «Структуры и алгоритмы обработки данных на ЭВМ» направлен на формирование следующих компетенций:
общекультурные компетенции (ОК):
способностью осознавать социальную значимость своей будущей профессии, обладать высокой мотивацией к выполнению профессиональной деятельности (ОК-9);
способностью работы с информацией из различных источников, включая сетевые ресурсы сети Интернет, для решения профессиональных и социальных задач (ОК-15).
профессиональные компетенции (ПК):
способностью приобретать новые научные и профессиональные знания, используя современные образовательные и информационные технологии (ПК-2);
способностью решать задачи производственной и технологической деятельности на профессиональном уровне, включая: разработку алгоритмических и программных решений в области системного и прикладного программирования (ПК-9);
способностью применять в профессиональной деятельности современные языки программирования и языки баз знаний, операционные системы, электронные библиотеки и пакеты программ, сетевые технологии (ПК-10).
Для успешного освоения дисциплины применяются различные образовательные технологии, которые обеспечивают достижение планируемых результатов обучения согласно основной образовательной программе, с учетом требований к объему занятий в интерактивной форме.
Интерактивные формы обучения, которые используются в данном курсе, включают: «Работа в команде» и «Поисковый метод».
Для контроля освоения компетенций используются следующие формы контроля: защита лабораторных работ, опрос по изучаемым разделам дисциплины, тесты.
Дисциплина «Структуры и алгоритмы обработки данных на ЭВМ»
относится к вариативной части математического и естественнонаучного цикла ООП. Успешное овладение дисциплиной предполагает предварительные знания математического анализа, вычислительных методов, дискретной математики в объеме, предусмотренном специальностью «Прикладная математика и информатика», а также навыки программирования на языках высокого уровня.
Лабораторный практикум дисциплины "Структуры и алгоритмы обработки данных на ЭВМ" позволяет получить практические навыки использования изучаемых структур данных и эффективных алгоритмов решения различных задач.
Результаты выполнения лабораторных работ представляются в виде отчета, который состоит из следующих пунктов:
4. Алгоритм решения задачи 5. Текст программы 6. Результаты работы программы Порядок выполнения лабораторных работ 1) изучить теоретический материал по теме лабораторной работы;
2) составить программу на одном из алгоритмических языков программирования для заданного варианта задания;
3) выполнить отладку составленной программы и показать преподавателю;
4) составить и защитить отчет по лабораторной работе.
Целью лабораторной работы – изучение основных способов работы с перечислимыми и интервальными типами данных.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Типы данных, определяемые программистом. Интервальные типы данных При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме лабораторной работы.
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. Перечислимый тип. Представление в памяти.
2. Операции, выполняемые над перечислимым типом.
3. Отличия перечислимого типа данных от стандартного типа данных 4. Задание интервального типа данных.
5. Что дает для программиста использование перечислимых и интервальных типов данных?
Цель лабораторной работы – изучение основных способов использования множеств.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Множества. Операции над множествами. Представление в памяти.
При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме «Множества».
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. Как задается тип данных «Множество»?
2. Как множества представляются в памяти ЭВМ.
3. Операции, выполняемые над множествами.
Целью лабораторной работы является изучение способов представления стеков и очередей в оперативной памяти ЭВМ и реализация основных операций работы с ними.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Стек, очередь и дек. Стек, очередь и дек как абстрактные типы данных. Представление и реализация.
Примеры алгоритмов, использующих стек, очередь, дек.
При выполнении лабораторной работы необходимо дать описание абстрактного типа данных «Стек» или «Очередь». Реализация основных операции АТД выполняется в виде процедур или функций. Все данные в процедуры или функции передаются через формальные параметры.
Перед завершением выполнения программы необходимо убедиться, что вся динамическая память, использованная для создания динамических структур данных, освобождена. В противном случае обеспечить ее полное освобождение.
1. Понятие стека. Операции, выполняемые над стеком.
2. Понятие очереди. Операции, выполняемые над очередью.
3. Понятие дека. Операции, выполняемые над деком.
4. Представление стека с помощью массива. Выполнение основных операций.
5. Представление очереди с помощью массива. Выполнение основных операций.
Целью лабораторной работы является изучение основных способов представления связанных списков в оперативной памяти ЭВМ и реализация основных операций работы со списками.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Односвязные, двусвязные, кольцевые списки и операции над ними.
Представление и реализация (непрерывная, ссылочная в связанной памяти).
При выполнении лабораторной работы необходимо дать описание абстрактного типа данных «Список». Реализация основных операции АТД выполняется в виде процедур или функций. Все данные в процедуры или функции передаются через формальные параметры.
Перед завершением выполнения программы необходимо убедиться, что вся динамическая память, использованная для создания динамических структур данных, освобождена. В противном случае обеспечить ее полное освобождение.
1. Отличие динамических структур от статических и полустатических.
2. Основные операции, выполняемые над списками.
3. Что такое кольцевой список.
Целью лабораторной работы – изучение основных способов представления деревьев в оперативной памяти ЭВМ и практическая реализация алгоритма работы с деревьями.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса.
Необходимо дать описание «дерева» как абстрактного типа данных.
Затем реализовать основные операции АТД «Дерево» в виде процедур или функций, при этом данные в процедуры или функции должны передаваться через формальные параметры.
Во всех заданиях предполагается вывод сформированного дерева на экран.
Перед завершением выполнения программы необходимо убедиться, что вся динамическая память, использованная для создания динамических структур данных, освобождена. В противном случае обеспечить ее полное освобождение.
1. Степень дерева.
2. Бинарное дерево.
3. Основные операции, выполняемые над бинарными деревьями.
4. Обход двоичного дерева.
5. Сильно ветвящиеся деревья.
Цель лабораторной работы – изучение основных способов представления бинарных деревьев в оперативной памяти ЭВМ и практическая реализация алгоритма работы с деревьями.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса.
Представления и реализации бинарных деревьев: ссылочная реализация в связанной памяти, ссылочная реализация ограниченного бинарного дерева на базе вектора.
Необходимо дать описание «дерева» как абстрактного типа данных.
Затем реализовать основные операции АТД «Дерево» в виде процедур или функций, при этом данные в процедуры или функции должны передаваться через формальные параметры.
Во всех заданиях предполагается вывод сформированного дерева на экран.
Перед завершением выполнения программы необходимо убедиться, что вся динамическая память, использованная для создания динамических структур данных, освобождена. В противном случае обеспечить ее полное освобождение.
1. Что такое «полное бинарное дерево»?
2. Что такое «почти полное бинарное дерево»?
3. Сколько узлов в полном бинарном дереве высоты h?
4. Какова минимальная высота бинарного дерева с n узлами?
5. Какие операции определены на АТД «Бинарное дерево поиска»?
Цель лабораторной работы – изучение основных способов сортировки данных.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Стратегии внутренней сортировки. Сортировка выборкой: метод простого выбора, турнирная сортировка, пирамидальная сортировка, анализ сложности алгоритмов. Сортировка включением: метод простых вставок, метод вставки с убывающим шагом, анализ сложности алгоритмов.
Обменные сортировки: сортировка пузырьком, быстрая сортировка, анализ сложности алгоритмов. Сортировка распределением: двоичная быстрая сортировка, цифровая распределяющая сортировка, блочная сортировка, сортировка подсчетом, анализ сложности алгоритмов. Сортировка слиянием.
Нижняя граница сложности задачи сортировки.
При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме «Сортировка».
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. В чем заключается сортировка методом вставки с убывающим шагом?
2. В чем заключается быстрая сортировка?
3. В чем заключается двоичная быстрая сортировка?
4. В чем заключается цифровая распределяющая сортировка?
5. В чем заключается сортировка слиянием?
Цель лабораторной работы – изучение основных особенностей применения метода исчерпывающего перебора и метода ветвей и границ.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Исчерпывающий перебор. Примеры решения задач: задача коммивояжера, задача о рюкзаке, задача о назначениях.
Поиск с возвратом. Общий алгоритм. Пример. Другие способы программирования поиска с возвращением: рекурсия и использование макросредств.
Метод ветвей и границ. Общая схема. Примеры применения метода решения задач: задача коммивояжера, задача о рюкзаке, задача о назначениях.
При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме лабораторной работы.
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. В чем заключается метод исчерпывающего перебора?
2. При решении каких задач прибегают к методу исчерпывающего перебора?
3. В чем заключается поиск с возвратом?
4. В чем заключается метод ветвей и границ?
5. Приведите примеры построения оценочных функций.
Цель лабораторной работы – изучение основных способов применения динамического программирования.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Динамическое программирование. Пример и общая идея. Вычисление чисел Фибоначчи. Восходящее и нисходящее динамическое программирование. Задача определения наиболее длинной общей подпоследовательности. Задача определения порядка умножения цепочки матриц.
При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме «Динамическое программирование».
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. В чем заключается метод динамического программирования?
2. Для каких задач эффективен метод динамического программирования?
3. За счет чего этот метод позволяет получить более быстрые алгоритмы?
4. В чем отличия восходящего и нисходящего динамического программирования?
Цель лабораторной работы – изучение основных способов построения хеш-таблиц.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
Метод поиска с использованием функции расстановки (хеширование). Разрешение коллизий: метод внутренних и внешних цепочек, метод открытой адресации. Коэффициент загрузки, оценки сложности. Выбор функции расстановки.
При выполнении лабораторной работы рекомендуется следующая последовательность:
1. Изучить теорию по теме лабораторной работы.
2. Получить задание на выполнение лабораторной работы.
3. Используя один из алгоритмических языков выполнить задание на лабораторную работу.
4. Подготовить отчет по лабораторной работе.
5. Защитить выполненную лабораторную работу.
1. Что такое хеш-таблица и как она используется?
2. Что такое открытое хеширование и для чего оно применяется?
3. Какие структуры данных используются для реализации открытого хеширования?
4. Какие шаги выполняет алгоритм построения хеш-таблицы при открытом хешировании?
5. Какие шаги выполняет алгоритм поиска в хеш-таблице при открытом хешировании?
Цель лабораторной работы – изучение эффективных алгоритмов поиска подстрок.
Для выполнения лабораторной работы необходимо ознакомиться со следующими разделами дисциплины:
«