Перечень тем лабораторных работ

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

Методические рекомендации по изучению учебной дисциплины,
задания для контрольной работы и рекомендации по их выполнению
для учащихся заочной формы обучения 2 курса

по специальности 2-40 01 01 «Программное обеспечение информационных технологий»

специализации 2-40 01 01 35 «Программное обеспечение обработки экономической и деловой информации»

Пинск 2015

Автор: Н. В. Аргер, преподаватель ПГПТК ЛП

Разработано на основе типовой учебной программы дисциплины «Структуры и алгоритмы обработки данных», утвержденной Министерством образования Республики Беларусь от 15.07.2013 г.

Обсуждено и одобрено на заседании цикловой комиссии.

Протокол № от «» 201 г.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Методические рекомендации по изучению дисциплины «Структуры и алгоритмы обработки данных» разработаны для учащихся безотрывной формы обучения специальности 2-40 01 01 «Программное обеспечение информационных технологий» в соответствии с образовательным стандартом РД РБ 02100.4.019-2004.

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

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

Дисциплина «Структуры и алгоритмы обработки данных» тесно связана с областями знаний ряда дисциплин: «Основы алгоритмизации и программирование», «Математическое моделирование» и др.

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

знать на уровне представления:

– основные этапы компьютерного решения задач;

– примеры базовых структур данных;

– статические и динамические структуры данных;

– зависимость эффективности алгоритмов от способов представления данных;

знать на уровне понимания:

– понятие алгоритма и структуры управления; традиционные структуры данных;

– методы разработки программ;

– принципы построения эффективных алгоритмов;

– основы структурного проектирования программ;

– основные требования методологии структурного программирования, как технологической основы разработки качественных программных компонентов;

уметь:

– применять требования методологии структурного программирования при проектировании информационных моделей;

– выбирать оптимальную структуру для представления данных;

– разрабатывать и записывать на языке программирования высокого уровня алгоритмы решения классических задач программирования.

Завершающим этапом изучения дисциплины является выполнение обязательной контрольной работы.

Учебный план специальности «Программное обеспечение информационных технологий» для безотрывной формы обучения предусматривает изучение дисциплины «Структуры и алгоритмы обработки данных» в объеме 18 часов, из них 8 часов отведены на выполнение лабораторных работ.

Учебная программа

1.1 Примерный тематический план дисциплины

Таблица 1

Раздел, тема	Количество учебных часов	Самостоя-тельная работа учащихся (часы)
Всего	В том числе
для дневной формы	для заочной формы	на устано-вочные занятия	на обзор-ные занятия	на лабора-торные занятия
Введение		-
Раздел 1. Алгоритмы, основанные на использовании динамических структур данных
1.1 Динамические структуры данных и их организация с помощью массивов и указателей. Динамические массивы.		-
1.2 Списковые структуры: односвязный и двусвязный списки, их использование.
1.3 Списковые структуры: стек, очередь, кольцо, их использование.
1.4 Бинарные деревья. Основные операции с бинарными деревьями.
1.5 Использование деревьев оптимального поиска для решения задач.
1.6 Прошитые бинарные деревья, операции с ними.
1.7 Красно-черные деревья, операции с ними.		-
1.8 Решение задач с применением деревьев.
Раздел 2. Использование комбинаторных алгоритмов и алгоритмов на графах для решения задач
2.1 Алгоритмы генерирования перестановок, множества всех подмножеств множества
2.2 Алгоритмы генерирования k-элементных подмножеств множества, разбиения множества на подмножества, их использование для решения задач
Продолжение таблицы 1
2.3. Основные определения графов. Ориентированные и неориентированные графы. Машинное представление графов. Матрица смежности и инцидентности
2.4 Задачи, основанные на поиске в ширину и в глубину в графе.
2.5. Алгоритмы поиска кратчайших расстояний в графе
2.6 Алгоритмы нахождения максимального потока, потока минимальной стоимости.
2.7. Задачи, решаемые полным перебором. Методы сокращения полного перебора.
2.8 Алгоритмы с возвращением.
2.9 Динамическое программирование. Примеры задач динамического программирования
2.10 Метод ветвей и границ. Решение задачи о коммивояжере методом ветвей и границ
2.11 “Жадные” алгоритмы. Общие принципы жадного метода. Жадные алгоритмы построения минимального остовного дерева
Раздел 3. Алгоритмы вычислительной геометрии
3.1. Основные понятия вычислительной геометрии. Задачи вычислительной геометрии и методы их решения.
Раздел 4. Рандомизированные алгоритмы
4.1. Генерирование случайных чисел, распределённых по заданным законам. Задачи, решаемые с помощью генераторов случайных чисел.
Раздел 5. Хеширование и хеш-таблицы		-
5.1. Открытое и закрытое хеширование. Функции хеширования. Задачи, решаемые с помощью построения хеш-таблиц.
Итого

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

Тема 1.Алгоритмы, основанные на использовании динамических структур данных.

Изучите понятие динамических структур данных, методы их организации с помощью массивов и указателей, основные операции над ними. Изучите структуру данных «динамический массив», ознакомьтесь с методами его обработки.

Изучите списковые структуры данных «односвязный и двусвязный списки», «стек», «очередь», «кольцо», основные операции над ними.

Изучите структуры данных «дерево», «бинарное дерево», основные операции над ними. Ознакомьтесь с понятием «дерево оптимального поиска», его назначением и методами использования при решении задач.

Ознакомьтесь с понятием «прошитое бинарное дерево», его назначением, видами прошивки, использованием различных структур данных для организации прошивки, операциями над прошитыми бинарными деревьями.

Изучите понятие «красно-чёрное дерево», его назначение, основные операции над ним.

Литература [13], с 21-26, 55-62, 158-197; [15], с 33-38; [16], с 240-286

Тема 2.Использование комбинаторных алгоритмов и алгоритмов на графах для решения задач.

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

Изучите основные понятия теории графов, виды графов, способы машинного представления графов в виде матриц смежности и инцидентности.

Ознакомьтесь с алгоритмами поиска в ширину и в глубину в графах, с алгоритмами поиска кратчайших расстояний в графе: алгоритмом Дейкстры, алгоритмом Беллмана-Форда, а также с основными типами задач, использующих данные виды поиска.

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

Изучите основные типы задач, решаемых полным перебором, а также методы сокращения полного перебора.

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

Ознакомьтесь с процессом разработки алгоритмов методом динамического программирования, изучите понятие оптимального решения, рассмотрите примеры задач динамического программирования.

Изучите методы улучшения перебора при поиске оптимального решения, суть метода ветвей и границ, а также алгоритма Литтла для решения задачи о коммивояжёре.

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

Литература [19], c 43-61, 72-96; 102-105, 111-114, 142-165.

Тема 3.Алгоритмы вычислительной геометрии.

Изучите основные понятия вычислительной геометрии, познакомьтесь с классами задач вычислительной геометрии и методами их решения.

Литература [13], c 74-78

Тема 4.Рандомизированные алгоритмы.

Познакомьтесь со способами получения случайных чисел: аппаратным и программным. Изучите генерирование случайных чисел, распределённых по заданным законам, задачи, решаемые с помощью ГСЧ.

Литература [15], c 194-201

Тема 5.Хеширование и хеш-таблицы.

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

Литература [16], c 241-257

Перечень тем лабораторных работ

Таблица 2

Наименование темы	Количество часов
Обработка бинарных деревьев. Решение задач с применением деревьев.
Решение задач, основанных на поиске в ширину и в глубину в графе. Реализация алгоритмов поиска кратчайших расстояний
Реализация алгоритмов с возвращением.
Реализация методов решения задач вычислительной геометрии. Реализация алгоритмов генерирования случайных чисел
Итого