Geum.ru

Учебно-методический комплекс для студентов заочного обучения специальности Прикладная информатика ( в экономике)

Вид материалаУчебно-методический комплекс

Содержание


Цели и задачи курса
Тематический план курса
Содержание программы курса по темам
Темы для самостоятельной работы
Основная литература
Дополнительная литература
Подобный материал:
РоссийскАЯ ФедерациЯ

Министерство образования и науки

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

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

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

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ


ИНСТИТУТ ДОПОЛНИТЕЛЬНОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Кафедра экономики, финансов и учета


«Структуры и алгоритмы компьютерной обработка данных»


Учебно-методический комплекс

для студентов заочного обучения

специальности Прикладная информатика ( в экономике)


Издательство

Тюменского государственного университета

Тюмень,2008


Рабочая учебная программа

Составлена к.т.н., доцентом Воробьевой М.С, утверждена на заседании кафедры программного обеспечения, 23.04.2008 г, протокол №7.
Программа курса включает четыре основные темы и нацелена на обзор и анализ ключевых алгоритмов, которыми должен владеть каждый программист. Это алгоритмы работы с различными информационными структурами данных, реализующие в основном задачи сортировки и поиска данных. Сравнительный анализ алгоритмов неизменно сопровождается оценкой их эффективности. Конкретная реализация алгоритмов изложена на языке Паскаль, однако студенты, знакомые с другими языками программирования, могут выполнять индивидуальные задания на любом языке программирования.

^ Цели и задачи курса

Основной целью при изучении дисциплины является формирование у студентов взгляда на программирование как на предмет научного изучения и поле для интеллектуальной деятельности.
В итоге студенты должны уметь компетентно и ответственно решать на основе полученных знаний следующие комплексные задачи:
- разработки, выбора и преобразования алгоритмов;
- эффективной реализации программного продукта и проведении с его помощью исследований средствами ВТ;
- модернизации математического, алгоритмического и программного обеспечения с целью повышения надежности и эффективности его функционирования.
Изучение курса направлено также на освоение международных характеристик и особенностей областей Computer science в части построения алгоритмов.


^ Тематический план курса




Название тем и разделов


Всего часов
Аудиторные занятия (час), в том числе:
Кол-во

часов на самостоятельную работу, формы контроля


Лекции
Семинары

  1.Алгоритмы: построение и анализ.  




1
1
9

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




1
1
9

  2.Структуры данных.  




1
2
9

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




1
1
9

   




1
1
9

  3.Алгоритмы поиска.  




1
1
9

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




1
1
9

  4.Алгоритмы сортировки.  




2
1
9

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




1
1
9

  ИТОГО  

105
10
10
85


^ Содержание программы курса по темам

ТЕМА 1. Алгоритмы: построение и анализ.
Алгоритмы, определение и основные свойства. Временная сложность алгоритмов: время выполнения в худшем случае, в среднем, в лучшем случае. Асимптотическая нотация: верхние оценки временной сложности, точные оценки, нижние оценки. Классификация алгоритмов по временной сложности.
Теория сложности алгоритмов: NP-сложные и труднорешаемые задачи.
Вычисление рекуррентных отношений в рекурсивных алгоритмах. Способы вычислений рекуррентных отношений: метод подстановки, метод итераций, основная теорема
Основные методы построения рекурсивных алгоритмов. Метод «разделяй и властвуй». Динамическое программирование (нисходящий и восходящий методы).

ТЕМА 2. Структуры данных.
Концепция АТД (абстрактных типов данных). Представление АТД в виде структуры данных. Классификация операций и структур.
Линейные структуры данных. АТД линейный список. Основные операции, представление и реализации. АТД стек, очередь, очередь с приоритетами, дек. Основные операции, представление и реализации. Применение структур данных. Метод исключения рекурсии с помощью стека.
Нелинейные структуры данных. Деревья, основные определения. Ориентированные деревья, упорядоченные деревья, бинарные деревья, m-арные деревья. Основные математические свойства бинарных деревьев. Преобразование упорядоченных деревьев в бинарные. АТД деревья. Основные операции. Представление деревьев в памяти компьютера: последовательное и связанное размещение элементов. Обходы деревьев. Применение деревьев. Деревья Хаффмана.

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

ТЕМА 4. Алгоритмы сортировки.
Постановка задачи, основные определения. Понятие внутренней и внешней сортировки, устойчивость сортировки, основные характеристики эффективности. Простые алгоритмы внутренней сортировки. Анализ алгоритмов. Сортировка Шелла. Понятие h-сортировки, зависимость эффективности сортировки от выбора последовательности h.
Улучшенные алгоритмы внутренней сортировки. Быстрая сортировка. Модификации быстрой сортировки. Вычисление порядковых статистик. Обменная поразрядная сортировка. Пирамидальная сортировка. Определение пирамиды. Способы построения пирамиды, нисходящий и восходящий алгоритмы. Реализации АТД очередь с приоритетами. Анализ алгоритмов.
Сортировка слиянием. Понятие двухпутевого, k-путевого слияния. Нисходящая сортировка слиянием. Вопросы устойчивости. Восходящая сортировка слиянием. Сортировка естественным слиянием. Анализ алгоритмов. Реализация алгоритмов на списках.
Алгоритмы сортировки за линейное время. Сортировка подсчетом распределения. Поразрядная (цифровая) сортировка. Анализ алгоритмов. Реализация алгоритмов на списках.
Алгоритмы, оперирующие со структурами типа графа.
Сортировка частично упорядоченного множества. Определение, постановка задачи, алгоритм топологической сортировки, структура данных. Анализ алгоритма.
Алгоритмы внешней сортировки. Постановка задачи. Сбалансированное многопутевое слияние. Выбор с замещением. Многофазное слияние. Алгоритм горизонтального распределения серий. Анализ алгоритмов.

Темы семинаров

^ ТЕМЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1. Прошитые деревья.
2. Деревья Хаффмана.
3. Деревья оптимального поиска.
4. Деревья цифрового поиска.
5. B+-деревья
6. Trie-деревья.
7. Patricia-деревья.
8. Суффиксные деревья.
9. Биномиальные кучи.
10. Фибоначчиевы кучи.
11. Поиск образца в строке: алгоритм Рабина-Карпа.
12. Поиск образца в строке: алгоритм Кнута-Морриса-Пратта.
13. Поиск образца в строке: алгоритм Бойера-Мура.
14. Задача о наибольшей общей последовательности.
15. Задача об оптимальной триангуляции многоугольника.
16. Каскадное слияние.
17. Сортирующие сети.

Литература

^ ОСНОВНАЯ ЛИТЕРАТУРА
1. Кнут Д. Искусство программирования для ЭВМ. Т1. Основные алгоритмы. – М: Изд. дом Вильямс, 2000.
2. Кнут Д. Искусство программирования для ЭВМ. ТЗ. Сортировка и поиск. – М: Изд. дом Вильямс, 2000.
3. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. – М.: МЦНМО, 2000.
4. Ахо А. и др. Структуры данных и алгоритмы. – М.: Изд.дом Вильямс, 2000.
5. Седжвик Р. Фундаментальные алгоритмы на С++. – Спб.: ООО «Диасофт ЮП», 2002.
^ ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
1. Вирт Н. Алгоритмы + структуры данных = программы. – М.:Мир, 1985.
2. Ласло М. Вычислительная геометрия и компьютерная графика на С++. – М.: Бином, 1997.
3. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. – М.: Финансы и статистика, 2004.
4. Деревнина А.Ю. Лекции по структурам и алгоритмам обработки данных. Электронный вариант.

Контрольные вопросы к экзамену (зачету)

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.Алгоритм многофазного слияния. Алгоритм горизонтального распределения серий.

Дополнительная информация

Рабочая программа разработана доцентом кафедры Программного обеспечения Воробьевой М.С., утверждена 13 мая 2008 года