Структуры и алгоритмы компьютерной обработки данных (стр. 3 )

4. Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин
1.1	1.2	1.3	2.1	2.2	3.1	3.2	3.3
1.	Системы управления базами данных						+	+	+
2.	Методы программирования		+	+	+	+	+	+	+
3	Информационные технологии						+	+	+
4	Планирование вычислительных экспериментов						+	+	+
5	Языки программирования	+	+	+	+	+	+	+	+

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

Модуль 1.

ТЕМА 1.1. Алгоритмы: построение и анализ. Временная сложность алгоритмов. Вычисление рекуррентных отношений. Методы построения алгоритмов.

Алгоритмы, определение и основные свойства. Временная сложность алгоритмов: время выполнения в худшем случае, в среднем, в лучшем случае. Асимптотическая нотация: верхние оценки временной сложности, точные оценки, нижние оценки. Классификация алгоритмов по временной сложности.

Вычисление рекуррентных отношений в рекурсивных алгоритмах. Способы вычислений рекуррентных отношений: метод подстановки, метод итераций, основная теорема

Основные методы построения рекурсивных алгоритмов. Метод «разделяй и властвуй». Динамическое программирование (нисходящий и восходящий методы).

ТЕМА 1.2. Структуры данных. Концепция АТД. Линейные структуры данных.

Концепция АТД (абстрактных типов данных). Представление АТД в виде структуры данных. Классификация операций и структур.

Линейные структуры данных. АТД линейный список. Основные операции, представление и реализации. АТД стек, очередь, очередь с приоритетами, дек. Основные операции, представление и реализации. Применение структур данных. Метод исключения рекурсии с помощью стека.

ТЕМА 1.3. Структуры данных. Концепция АТД. Нелинейные структуры данных.

Нелинейные структуры данных. Деревья, основные определения. Ориентированные деревья, упорядоченные деревья, бинарные деревья, m-арные деревья. Основные математические свойства бинарных деревьев. Преобразование упорядоченных деревьев в бинарные. АТД деревья. Основные операции, представление в памяти. Обходы деревьев. Применение деревьев. Деревья Хаффмана.

Модуль 2.

ТЕМА 2.1. Алгоритмы поиска. Поиск в линейных таблицах.

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

ТЕМА 2.2. Поиск в нелинейных таблицах. Поиск в таблицах с вычисляемыми входами.

Поиск в нелинейных таблицах. Бинарные деревья поиска (BST). Основные операции. Анализ эффективности алгоритмов.

Сбалансированные (АВЛ) деревья. Критерий сбалансированности. Деревья Фибоначчи. Виды балансировки. Основные операции. Анализ эффективности алгоритмов.

Б-деревья. Внешний поиск. Основные операции. Анализ эффективности алгоритмов. Разновидности Б-деревьев. Применение структур данных.

Красно-черные деревья. Рандомизированные деревья поиска. Оптимальные деревья поиска. Основные операции. Анализ эффективности алгоритмов.

Поиск в таблицах с вычисляемыми входами. Хеширование. Основные методы вычисления хеш-функций: метод деления, метод умножения, комбинированный метод. Разрешение коллизий. Хеширование с цепочками. Хеширование открытой адресацией. Основные виды повторного хеширования: линейное исследование, квадратичное исследование, двойное хеширование. Основные операции. Анализ эффективности алгоритмов.

Модуль 3.

ТЕМА 3.1. Алгоритмы сортировки. Простые алгоритмы внутренней сортировки. Улучшенные алгоритмы внутренней сортировки.

Постановка задачи, основные определения. Понятие внутренней и внешней сортировки, устойчивость сортировки, основные характеристики эффективности. Простые алгоритмы внутренней сортировки. Анализ алгоритмов. Сортировка Шелла. Понятие h-сортировки, зависимость эффективности сортировки от выбора последовательности h.

Улучшенные алгоритмы внутренней сортировки. Быстрая сортировка. Модификации быстрой сортировки. Вычисление порядковых статистик. Обменная поразрядная сортировка. Пирамидальная сортировка. Определение пирамиды. Способы построения пирамиды, нисходящий и восходящий алгоритмы. Реализации АТД очередь с приоритетами. Анализ алгоритмов.

ТЕМА 3.2. Алгоритмы сортировки за линейное время. Сортировка частично упорядоченного множества.

Сортировка слиянием. Понятие двухпутевого, k-путевого слияния. Нисходящая сортировка слиянием. Вопросы устойчивости. Восходящая сортировка слиянием. Сортировка естественным слиянием. Анализ алгоритмов. Реализация алгоритмов на списках.

Алгоритмы сортировки за линейное время. Сортировка подсчетом распределения. Поразрядная (цифровая) сортировка. Анализ алгоритмов. Реализация алгоритмов на списках

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

ТЕМА 3.3. Алгоритмы внешней сортировки.

Алгоритмы внешней сортировки. Постановка задачи. Сбалансированное многопутевое слияние. Выбор с замещением. Многофазное слияние. Алгоритм горизонтального распределения серий. Анализ алгоритмов.

6. Планы семинарских занятий.

Не планируется.

7. Темы лабораторных работ (Лабораторный практикум)

Задания лабораторного практикума выполняются с использованием сред программирования (например: Delphi, C#, C++).

ТЕМА 1.1. Алгоритмы: построение и анализ.

Временная сложность алгоритмов. Асимптотическая нотация: верхние оценки временной сложности, точные оценки, нижние оценки. Вычисление рекуррентных отношений в рекурсивных алгоритмах. Способы вычислений рекуррентных отношений. Основные методы построения рекурсивных алгоритмов.

ТЕМА 1.2. Структуры данных АТД.

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

ТЕМА 1.3. Нелинейные структуры данных.

Деревья, основные определения. Ориентированные деревья, упорядоченные деревья, бинарные деревья, m-арные деревья. Основные математические свойства бинарных деревьев.
Преобразование упорядоченных деревьев в бинарные. АТД деревья. Основные операции, представление в памяти. Обходы деревьев. Деревья Хаффмана.

ТЕМА 2.1. Алгоритмы поиска. Поиск в линейных таблицах.

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

ТЕМА 2.2. Поиск в нелинейных таблицах. Поиск в таблицах с вычисляемыми входами.

Бинарные деревья поиска (BST). Основные операции и реализации на языке программирования высокого уровня. Анализ эффективности алгоритмов.
Сбалансированные (АВЛ) деревья. Критерий сбалансированности. Деревья Фибоначчи. Виды балансировки. Основные операции и реализации на языке программирования высокого уровня. Анализ эффективности алгоритмов.
Б-деревья. Внешний поиск. Основные операции и реализации на языке программирования высокого уровня. Анализ эффективности алгоритмов. Разновидности Б-деревьев. Красно-черные деревья. Оптимальные деревья поиска.
Поиск в таблицах с вычисляемыми входами. Хеширование. Основные методы вычисления хеш-функций: метод деления, метод умножения, комбинированный метод. Разрешение коллизий. Реализация методов хеширования на языке программирования высокого уровня.

ТЕМА 3.1. Алгоритмы сортировки. Простые алгоритмы внутренней сортировки. Улучшенные алгоритмы внутренней сортировки.

Понятие внутренней и внешней сортировки, устойчивость сортировки, основные характеристики эффективности. Простые алгоритмы внутренней сортировки. Реализация простых методов на языке программирования высокого уровня. Анализ алгоритмов.
Сортировка Шелла. Понятие h-сортировки, зависимость эффективности сортировки от выбора последовательности h. Реализация сортировки на языке программирования высокого уровня.

ТЕМА 3.2. Алгоритмы сортировки за линейное время. Сортировка частично упорядоченного множества.

Сортировка слиянием. Понятие двухпутевого, k-путевого слияния. Нисходящая сортировка слиянием. Реализация сортировки на языке программирования высокого уровня. Вопросы устойчивости. Восходящая сортировка слиянием. Реализация сортировки на языке программирования высокого уровня. Сортировка естественным слиянием. Реализация сортировки на языке программирования высокого уровня.
Сортировка частично упорядоченного множества. Определение, постановка задачи, алгоритм топологической сортировки, структура данных. Реализация сортировки на языке программирования высокого уровня.

ТЕМА 3.3. Алгоритмы внешней сортировки.

Постановка задачи. Сбалансированное многопутевое слияние. Выбор с замещением. Реализация сортировки на языке программирования высокого уровня.
Многофазное слияние. Реализация сортировки на языке программирования высокого уровня.

8. Примерная тематика курсовых работ

Не планируется.

9. Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля).

Контроль качества подготовки осуществляется путем проверки теоретических знаний и практических навыков с использованием

a) Текущей аттестации:

проверка промежуточных контрольных работ, выполнение учебных задач, прием лабораторных работ,

b) Промежуточной аттестации:

тестирование (письменное или компьютерное) по разделам дисциплины.

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

Текущий и промежуточный контроль освоения и усвоения материала дисциплины осуществляется в рамках рейтинговой (100-бальной) системы оценок.

Пример тестового задания по теме «Алгоритмы: построение и анализ»:

Какое утверждение является истинным?

а) (n + 5)3 = Q(n3)

b)

c)

d)

Пример лабораторного задания

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

Type Base = integer;

Tree = ^ Node;

Node = record

elem: Base;

left, right: Tree

Count: integer

end;

a). По текстовому файлу f, содержащему элементы типа Base (среди которых могут быть и одинаковые), построить дерево поиска T.

b). Добавить к дереву поиска T новый элемент Е, если его не было в T.

c). Проверить, входит ли элемент Е в дерево поиска T.

d). Удалить из дерева поиска T элемент Е, если он есть в T.

e). Записать в текстовый файл f элементы дерева поиска T в порядке их возрастания, используя обход дерева соответствующим методом. Одинаковые элементы записывать в файл в количестве Count.

Пример контрольной работы

1) Если узел А имеет трёх братьев, а узел В является родителем узла А, то чему равна а). степень узла В; б). высота дерева

2) Сколько структурно различных бинарных деревьев можно построить из трёх узлов? Нарисуйте эти структуры.

3) Сколько путей длины 3 существует на дереве, показанном на рисунке? Перечислите их.

4) Сколько листьев в дереве, показанном на рисунке?

5) Для дерева, представленного на рисунке, постройте расширенное дерево и найдите длину внешнего и внутреннего пути расширенного дерева.

6)

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

7) Преобразуйте выражение ((a + b) + c * (d + e) + f) * (g + h)

а) в префиксную форму; б) в постфиксную форму.

8) В дополнение к основным способам обхода бинарного дерева можно предложить ещё один альтернативный порядок обхода: а) посетить корень; б) перейти в правое поддерево; в) перейти в левое поддерево. Далее это правило применяется рекурсивно для всех непустых поддеревьев. Имеет ли такой порядок какую-либо простую связь с тремя другими порядками (префиксным, инфиксным, постфиксным)?

9) Пусть символы а, б, в, г, д, е имеют вероятности появления соответственно 0,17; 0,19; 0,02; 0,25; 0,11; 0,26. Найдите оптимальный код Хаффмана и нарисуйте соответствующее ему дерево. Какова средняя длина кода (сколько бит в среднем приходится на 1 символ)? Чему равен объём сообщения длиной 300 символов, закодированного с помощью кода Хаффмана?

10) Предположим, что в двоичном дереве поиска хранятся числа от 1 до 1000 и мы хотим найти число 363. Какая из следующих последовательностей не может быть последовательностью просматриваемых при этом ключей?

а) 925, 202, 911, 240, 912, 245, 363 b) 2, 252, 401, 398, 330, 344, 397, 363

с) 924, 220, 911, 244, 898, 258, 362, 363 d) 2, 399, 387, 219, 266, 382, 381, 278, 363

Вопросы к зачету

1. Алгоритмы, основные свойства. Временная сложность алгоритмов. Асимптотическая нотация.

2. Способы вычисления рекуррентных отношений.

3. Основные методы построения алгоритмов: «разделяй и властвуй», динамическое программирование.

4. Линейные списки. Основные операции. Представление и реализация.

5. Стеки. Основные операции. Представление и реализация.

6. FIFO-Очереди. Очереди с приоритетами. Деки. Основные операции. Представление и реализация.

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

8. Деревья. Основные операции. Представление и реализация. Обходы деревьев. Исключение рекурсии.

9. Деревья Хаффмана.

10. Поиск в линейной таблице: последовательный, бинарный, интерполяционный поиск.

11. Бинарные деревья поиска. Основные операции.

12. Сбалансированные (АВЛ) деревья. Основные операции.

13. Б-деревья. Основные операции.

14. Красно-черные деревья. Основные операции.

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

16. Основные методы вычисления хеш-функций.

17. Хеширование с цепочками.

18. Хеширование открытой адресацией.

19. Сортировка. Постановка задачи, основные определения, оценка эффективности. Классификация алгоритмов.

20. Простые методы внутренней сортировки.

21. Быстрая сортировка. Модификации алгоритма.

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

23. Обменная поразрядная сортировка.

24. Пирамидальная сортировка. Способы построения пирамиды.

25. Алгоритм двухпутевого слияния (реализация на массивах и списках).

26. Нисходящая сортировка слиянием.

27. Восходящая сортировка слиянием. Сортировка естественным слиянием.

28. Сортировка подсчетом распределения (на массивах и на списках).

29. Поразрядная (цифровая) сортировка.

30. Топологическая сортировка.

31. Алгоритм сбалансированного многопутевого слияние.

32. Выбор с замещением.

33. Алгоритм многофазного слияния. Алгоритм горизонтального распределения серий.

10. Образовательные технологии

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

аудиторные занятия:

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

активные и интерактивные формы

компьютерное моделирование и анализ результатов при выполнении лабораторных работ

внеаудиторные занятия:

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

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

11.1 Основная литература:

1. Искусство программирования для ЭВМ. Т1. Основные алгоритмы. – М: Изд. дом Вильямс, 2000.

2. Искусство программирования для ЭВМ. ТЗ. Сортировка и поиск. – М: Изд. дом Вильямс, 2000.

3. Алгоритмы: построение и анализ. / Т. Кормен, Ч. Р. Ривест : пер. с англ., под ред. А. Шеня. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд. стереотип. – 960 с.

4. и др. Структуры данных и алгоритмы. – М.: Изд. дом Вильямс, 2000.

5. Фундаментальные алгоритмы на С++. – Спб.: ЮП», 2002.

6. Деревнина данных и алгоритмы компьютерной обработки данных: Учебное пособие. - Тюмень: Издательство ТюмГУ, 20с.

11.2. Дополнительная литература:

1. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.

2. , Киприна и алгоритмы компьютерной обработки данных. Рабочая программа и методические рекомендации. – Тюмень: Изд-во ТюмГУ, 20с.

3. Кубенский и алгоритмы обработки данных: объектно-ориентированный подход и реализация на С++. / – СПб.: БХВ-Петербург, 2004. – 464 с.

4. Программирование алгоритмов обработки данных / , , . – СПб: БХВ - Петербург, 2003. – 192 с.

5. Хусаинов и алгоритмы обработки данных. Примеры на языке Си. – М.: Финансы и статистика, 2004.

11.3. Программное обеспечение и Интернет – ресурсы:

1. Воробьева и алгоритмы компьютерной обработки данных (2008), режим доступа: http://study.kib.ru/ по паролю.

2. . Структуры и алгоритмы (2010), режим доступа: http://study.kib.ru/ по паролю.

12. Технические средства и материально-техническое обеспечение дисциплины (модуля)

При освоении дисциплины для проведения лекционных занятий нужны учебные аудитории, оснащённые мультимедийным оборудованием, для выполнения лабораторных работ необходимы классы персональных компьютеров с набором базового программного обеспечения разработчика - системы программирования на языках Borland Delphi, С/С++.