МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Томский государственный университет систем управления и радиоэлектроники»

(ТУСУР)

Кафедра автоматизированных систем управления

СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ НА ЭВМ

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

230700.62 "Прикладная информатика" Томск-2011 2 Горитов А.Н.

Структуры и алгоритмы обработки данных на ЭВМ: методические указания по самостоятельной и индивидуальной работе студентов всех форм обучения для направления подготовки: 230700.62 – "Прикладная информатика" / А.Н. Горитов. – Томск:

ТУСУР, 2011. – 9 с.

Методические указания разработаны в соответствии с решением кафедры автоматизированных систем управления Составитель: д.т.н., профессор каф. АСУ А.Н. Горитов Методические указания утверждены на заседании кафедры автоматизированных систем управлениям 30 августа 2011 г., протокол № © ТУСУР, каф. АСУ, © Горитов А.Н.

СОДЕРЖАНИЕ

2. Методы и формы организации обучения

3. Место дисциплины в структуре ООП

4. Содержание дисциплины

4.1 Теоретический материал

4.2 Лабораторные работы

4.3 Темы для самостоятельного изучения

5. Учебно-методические материалы по дисциплине

5.1 Основная

5.2 Дополнительная

1. Цели и задачи дисциплины Целью изучения дисциплины «Структуры и алгоритмы обработки данных на ЭВМ»

является изучение применяемых в программировании (и информатике) структур данных, их спецификации и реализации, а также алгоритмов обработки данных и анализ этих алгоритмов, взаимосвязь алгоритмов и структур.

В результате изучения дисциплины студент должен:

а) иметь представление об основных тенденциях в создании структур данных, методах оптимального использования памяти и времени для обработки структур данных и управления процессами обработки данных;

б) знать и использовать различные (динамические и статистические) структуры данных в соответствии с запросами алгоритмов;

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

г) знать и использовать основные алгоритмы решения классических задач информатики;

д) иметь представление о математических методах анализа алгоритмов;

классификации алгоритмических задач по сложности, сводимости алгоритмических задач к известным задачам определенного класса сложности;

е) иметь опыт работы с алгоритмическими языками программирования.

2. Методы и формы организации обучения Процесс изучения дисциплины «Структуры и алгоритмы обработки данных на ЭВМ» направлен на формирование следующих компетенций:

общекультурные компетенции (ОК):

способностью использовать, обобщать и анализировать информацию, ставить цели и находить пути их достижения в условиях формирования и развития информационного общества (ОК-1).

профессиональные компетенции (ПК):

способностью моделировать и проектировать структуры данных и знаний, прикладные и информационные процессы (ПК-9);

способностью применять к решению прикладных задач базовые алгоритмы обработки информации, выполнять оценку сложности алгоритмов, программировать и тестировать программы (ПК-10);

способностью принимать участие в создании и управлении ИС на всех этапах жизненного цикла (ПК-11);

способностью применять системный подход и математические методы в формализации решения прикладных задач (ПК-21).

Для успешного освоения дисциплины применяются различные образовательные технологии, которые обеспечивают достижение планируемых результатов обучения согласно основной образовательной программе, с учетом требований к объему занятий в интерактивной форме.

Интерактивные формы обучения, которые используются в данном курсе, включают:

«Работа в команде» и «Поисковый метод».

Для контроля освоения компетенций используются следующие формы контроля:

защита лабораторных работ, опрос по изучаемым разделам дисциплины, тесты.

Дисциплина «Структуры и алгоритмы обработки данных на ЭВМ» относится к вариативной части математического и естественнонаучного цикла ООП. Успешное овладение дисциплиной предполагает предварительные знания таких дисциплин, как «Математика», «Дискретная математика», «Информатика и программирование», «Основы алгоритмизации и языки программирования» в объеме, предусмотренном направлением 230700.62 – «Прикладная информатика».

Знания и навыки, полученные при изучении этой дисциплины, используются при изучении дисциплин «Программная инженерия», «Проектирование информационных систем», «Базы данных», «Учебно-исследовательская работа».

4.1 Теоретический материал Тема 1. Данные и ЭВМ Предмет дисциплины и ее задачи. Связь с другими дисциплинами учебного плана направления и специальности.

Алгоритм. Вычислительная сложность алгоритма и ее оценка. Использование пределов для сравнения порядка роста двух функций. Основные классы эффективности.

Литература Тема 2. Фундаментальные структуры данных Базовые типы данных, обрабатываемые командами ЭВМ. Представление чисел, символьных и логических данных, указателей в оперативной памяти. Понятие структуры данных. Классификация структур. Важнейшие операции над структурами.

Массивы, их представление в памяти. Информационный вектор. Строковые данные.

Операции над строками.

Записи и структуры. Квалифицированные имена. Иерархия данных в записях.

Записи с вариантами. Представление записей в памяти ЭВМ.

Множества. Операции над множествами. Представление в памяти.

Последовательный файл. Особенности файла как структуры данных. Основные действия над файлом. Файлы со сложной структурой. Прямой доступ.

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

Примеры алгоритмов, использующих стек, очередь, дек.

Связный список. Односвязные, двусвязные, кольцевые списки и операции над ними.

Представление и реализация (непрерывная, ссылочная в связанной памяти).

Литература 1, Тема 4. Древовидные структуры данных Определение дерева, леса, бинарного дерева. Графическое и текстовое (скобочное) представление леса. Спецификация дерева, леса, бинарного дерева: базовые функции и аксиомы. Естественное соответствие бинарного дерева и леса.

Обходы бинарных деревьев: рекурсивные и не рекурсивные алгоритмы. Обходы дерева или леса.

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

Пример использования бинарных деревьев в задаче упаковки сообщений:

префиксные коды и бинарные деревья, метод кодирования Фано-Шеннона, критерий оптимальности кода, алгоритм кодирования (сжатия) информации по Хаффману (построение дерева, кодирование и декодирование).

Литература 1, 6, 7, Тема 5. Сортировка Сортировка. Внутренняя сортировка. Стратегии внутренней сортировки. Сортировка выборкой: метод простого выбора, турнирная сортировка, пирамидальная сортировка, анализ сложности алгоритмов. Сортировка включением: метод простых вставок, метод вставки с убывающим шагом, анализ сложности алгоритмов. Обменные сортировки:

сортировка пузырьком, быстрая сортировка, анализ сложности алгоритмов. Сортировка распределением: двоичная быстрая сортировка, цифровая распределяющая сортировка, блочная сортировка, сортировка подсчетом, анализ сложности алгоритмов. Сортировка слиянием.

Нижняя граница сложности задачи сортировки.

Внешняя сортировка. Простое слияние. Естественное слияние. Многофазная сортировка.

Литература 1, 4, 5, Тема 6. Исчерпывающий поиск Исчерпывающий перебор. Примеры решения задач: задача коммивояжера, задача о рюкзаке, задача о назначениях.

Поиск с возвратом. Общий алгоритм. Пример. Другие способы программирования поиска с возвращением: рекурсия и использование макросредств.

Метод ветвей и границ. Общая схема. Примеры применения метода решения задач:

задача коммивояжера, задача о рюкзаке, задача о назначениях.

Динамическое программирование. Пример и общая идея. Вычисление чисел Фибоначчи. Восходящее и нисходящее динамическое программирование. Задача определения наиболее длинной общей подпоследовательности. Задача определения порядка умножения цепочки матриц Литература 1, 3, 7, Тема 7. Быстрый поиск Поиск и другие операции над таблицами. Последовательный и бинарный поиск.

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

Рандомизированные бинарные деревья поиска.

Сбалансированные по высоте бинарные деревья (АВЛ-деревья). Включение в АВЛдерево. Исключение из АВЛ-дерева. Оценка сложности в худшем случае: деревья Фибоначчи.

Красно-черные деревья (КЧ- деревья). Включение в КЧ- деревья. Исключение из КЧдеревьев.

Реализация упорядоченных линейных списков на базе АВЛ- деревьев, КЧ- деревьев или рандомизированных деревьев. Операции поиска, вставки и удаления элементов;

операции сцепления и расщепления списков.

2-3-деревья. Включение элемента в 2-3 дерево. Исключение элемента из 2-3 дерева.

Поиск элемента в 2-3 дереве.

2-3-4-деревья. Включение элемента в 2-3-4 дерево. Исключение элемента из 2-3- дерева. Поиск элемента в 2-3-4 дереве.

Б-деревья. Включение элемента в Б- дерево. Исключение элемента из Б- дерева.

Поиск элемента в Б- дереве.

Задача поиска подстроки. Алгоритм Кнута-Мориса-Пратта. Алгоритм Боуера-Мура.

Алгоритм Рабина-Карпа.

Метод поиска с использованием функции расстановки (хеширование). Разрешение коллизий: метод внутренних и внешних цепочек, метод открытой адресации.

Коэффициент загрузки, оценки сложности. Выбор функции расстановки.

Литература 1, 5, 7, Тема 8. Алгоритмы на графах Графы: определения и примеры. Упорядоченный граф. Представления графов:

матрица инциденций, матрица смежности, список пар, списки смежности.

Поиск в графе: Основные методы обработки графов. Поиск в ширину. Поиск в глубину.

Связные компоненты: Определение компонент связности. Топологическая сортировка.

Двусвязность: Точки сочленения и их свойства. Алгоритм выделения компонент двусвязности графа.

Эйлеров путь в графе. Алгоритм построения Эйлерова пути.

Гамильтонов путь в графе. Нахождение Гамильтонова пути в графе с помощью алгоритма с возвратом.

Циклы: Фундаментальное множество циклов графа. Алгоритм отыскания фундаментального множества циклов в графе.

Остовные деревья графа: Связные компоненты. Построение и свойства остовных деревьев при поиске в глубину и в ширину.

Остовные деревья минимального веса: Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала.

Кратчайшие пути в графе: Кратчайшие пути от фиксированной вершины. Алгоритм Форда-Беллмана. Алгоритм Дейкстры. Кратчайшие пути в бесконтурном графе.

Кратчайшие пути между всеми парами вершин: Матрица смежности, матрица достижимости и транзитивное замыкание отношения, алгоритм Уоршалла. Алгоритм Флойда-Уоршалла вычисления расстояний между всеми парами вершин, одновременное построение путей.

Литература 1, 2, 5, Тема 9. NP-полные и труднорешаемые задачи Массовая и индивидуальная задачи. Сложность алгоритма и кодирование входных и выходных данных. Полиномиальные алгоритмы и класс P. Недетерминированные алгоритмы и класс NP.

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

Полиномиальная преобразуемость задач. NP-трудные и NP-полные задачи. Задача о выполнимости булева выражения, представленного в конъюнктивной нормальной форме.

Доказательство NP-полноты задачи о выполнимости.

Практическое решение NP-полных задач.

Литература 1, 4.2 Лабораторные работы По данной дисциплине выполняются следующие лабораторные работы:

1. Интервальные и перечислимые типы данных.

2. Операции над множествами.

3. Стеки, очереди 4. Связанные списки 5. Бинарные деревья 6. Сортировка 7. Внешняя сортировка 8. Динамическое программирование 9. Поиск подстрок 10. Фундаментальные алгоритмы на графах 11. Кратчайшие пути в графе При подготовке к лабораторным работам внимательно разбирать материал, данный в лекции, а также обратиться к дополнительной литературе. Разобрать примеры, рассмотренные в лекциях и в литературе.

4.3 Темы для самостоятельного изучения Студенты самостоятельно изучают следующие разделы дисциплины:

1. Очереди с приоритетами.

2. В-деревья.

3. Порядковые статистики.

Литература 1, 4.

5. Учебно-методические материалы по дисциплине 5.1 Основная 1. Горитов А.Н. Основы структур и алгоритмов обработки данных: Учебное пособие. – Томск: ТУСУР, 2007. – 229 с. (50 экз.) 5.2 Дополнительная 2. Окулов С. М. Программирование в алгоритмах. – 2-е изд., доп. – М.: БИНОМ.

Лаборатория знаний, 2006. – 384 с. (30 экз.) 3. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие.

– М.: Лаборатория базовых знаний, 2003. – 288 с. (50 экз.) 4. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989. – 360 с. (50 экз.) 5. Макконелл Дж. Основы современных алгоритмов. 2-е дополненное издание. – Москва: Техносфера, 2004. – 368 с. (13 экз.) 6. Ускова О.Ф. и др. Программирование алгоритмов обработки данных: Учебное пособие. – СПб: БХВ-Петербург, 2003. – 188 с. (19 экз.) 7. Андерсон Д.А. Дискретная математика и комбинаторика. – М.: Издательский дом "Вильямс", 2004. – 960 с. (10 экз.) 8. Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. – СПб: Питер, 2002. – 302 с. (19 экз.) 9. Липский В. Комбинаторика для программистов. – М.: Мир,1989.– 213 с. (9 экз.) 10. Кнут Д. Искусство программирования для ЭВМ. Том 1: Основные алгоритмы. – М.: Мир, 1976. – 736 с. (3-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 720 с.) (5 экз.) 11.Кнут Д. Искусство программирования для ЭВМ. Том 3: Сортировка и поиск. М.: Мир, 1978. – 846 с. (2-е изд.: Уч. пос. – М.: Издательский дом «Вильямс», 2000. – 832 с.) (15 экз.) 12.Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах. – М.: Высшая школа, 1987. – 248 с. (9 экз.) 13.Стоун Г.С., Сиворек Д.П. Введение в организацию ЭВМ и структуры данных. – М.: Машиностроение, 1980. – 320 с. (10 экз.)