Реферат: Программа дисциплины структуры и алгоритмы компьютерной обработки данных для специальности 351500 математическое обеспечение и

ПРАВОСЛАВНЫЙ СВЯТО-ТИХОНОВСКИЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ


КАФЕДРА ИНФОРМАТИКИ


УТВЕРЖДАЮ

Проректор по учебной работе

_______________ Г. Ореханов

«___»_______________ 200__ г.


ПРОГРАММА ДИСЦИПЛИНЫ


СТРУКТУРЫ И АЛГОРИТМЫ КОМПЬЮТЕРНОЙ ОБРАБОТКИ ДАННЫХ


Для специальности 351500 –

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ И

АДМИНИСТРИРОВАНИЕ ИНФОРМАЦИОННЫХ СИСТЕМ


Автор

к. т. н. Буянов С.В.


Москва 2006


1. Цель, задачи изучения дисциплины

Целью курса является изучение основных алгоритмов работы с дискретными объектами, структур данных и методов их исследования.

Задачи

Изучение методов разработки и анализа эффективных алгоритмов;

изучение известных алгоритмов решения часто встречающихся на практике задач дискретного характера;

формирование устойчивого алгоритмического мышления у студентов;

изучение фундаментальных свойств алгоритмов.


2. Требования к уровню освоения содержания дисциплины. Дословно: «Студенты, изучившие дисциплину, должны:


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

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


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

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


3. ^ ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ
Вид учебной работы Всего часов Семестры
Общая трудоемкость

144

4

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

57

4

Лекции

38

4

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

19

4

Самостоятельная работа

83

4

Реферат/курсовая работа/выпускная квалификационная работа

4

Вид итогового контроля
Экзамен
4




^ СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

РАЗДЕЛЫ ДИСЦИПЛИНЫ И ВИДЫ ЗАНЯТИЙ

№ п/п
Тематический план Лекции
Лабораторные работы

1

2

3

4

1

Доказательство правильности алгоритмов

2




2

Исследование сложности алгоритмов

2




3

Структуры данных и методы разработки эффективных алгоритмов

2




4

Задача сортировки

2




5

Алгоритмы внутренней сортировки

2

2

6

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

2

2

7

Внешняя сортировка

2

2

8

Поиск в таблицах и массивах

2




9

Хеширование

2

2

10

Деревья поиска

2




11

Поиск цепочек символов

2

1

12

Поиск решения в комбинаторных задачах

2

1

13

Комбинаторные задачи на графах. Эффективные алгоритмы на графах

2

2

14

Коды, информация, энтропия. Помехоустойчивое кодирование

2

2

15

Случайные числа

2

1

16

Алгоритмы над сверхдлинными числами

2

2

17

Криптография

2

2

18

Модели вычислений и машины Тьюринга. Теория алгоритмов

2




19

NP-полнота задачи выполнимости Связь NP-полных задач Связь задач по сложности.

2




^ СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИН

Раздел 1. МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ
1.1. Доказательство правильности алгоритмов
Вход и выход алгоритма. Пред- и постусловие. Математическая индукция. Инвариант. Эквивалентность
алгоритмов. Поэтапное доказательство сложных алгоритмов.
1.2. Исследование сложности алгоритмов
Представление алгоритмов в командах компьютера и на языке высокого уровня. Временная и емкостная сложности алгоритма. Полиномиальные и экспоненциальные виды функций сложности. Исследование временной сложности в наихудшем и в среднем. Теоремы о рекуррентных соотношениях для сложности. Экспериментальное исследование сложности алгоритмов. Генерация случайных входных данных. Статистическая обработка результатов исследования сложности алгоритмов.
1.3. Структуры данных и методы разработки эффективных алгоритмов
Стеки, очереди, списки, их моделирование с помощью массивов. Представления множеств в виде массивов и списков. Графы и различные способы их представления. Прошитые списки. Выбор наиболее эффективных структур данных. Методы разработки эффективных алгоритмов: "разделяй и властвуй", "балансировка", "жадный метод", "динамическое программирование".
Раздел 2. СОРТИРОВКА
2.1. Задача сортировки
Дерево решений в задаче сортировки. Минимально возможная трудоемкость в наихудшем. Оптимальные алгоритмы. Инверсии. Перестановки.
2.2. Алгоритмы внутренней сортировки
Простейшие алгоритмы. Алгоритм Шелла. Быстрая сортировка Хоара, оценка его сложности в среднем.
Пирамидальная сортировка. Сортировка слиянием. Цифровая сортировка. Цифровая сортировка строк.
2.3. Порядковые статистики
Задача определения k-го элемента. Алгоритм, основанный на быстрой сортировке, его сложность в среднем. Алгоритм, эффективный в наихудшем случае.
2.4. Внешняя сортировка
Особенности задачи сортировки информации на файлах. Сбалансированное слияние. Многофазная сортировка, ее анализ. Особенности практической реализации.
Раздел 3. ПОИСК
3.1. Поиск в таблицах и массивах
Задача поиска. Поиск в неупорядоченном массиве. Минимально возможная трудоемкость в наихудшем.
Дихотомический поиск в упорядоченном массиве. Таблица, как база данных. Иерархическая упорядоченность в таблице. Косвенная адресация. Поиск по нескольким ключам. Включающий поиск.
Операции проекции и соединения таблиц, как обобщение поиска.
3.2. Хеширование
Задача хеширования. Хеш-функция. Хеш-таблица с областью переполнения, поиск, удаление элементов.
Хеш-таблица с открытой адресацией, эффективность поиска в среднем. Применение хеш-таблиц в файлах.
3.3. Деревья поиска
Построение случайного дерева. Поиск в случайном дереве, его средняя трудоемкость. Идеально сбалансированные деревья. Удаление элементов из дерева. АВЛ-деревья. Фибоначчиевы деревья, их максимальная высота. Добавление и удаление в АВЛ-дереве. Деревья для задачи объединения множеств. В-деpевья, их пpименение для файлов. 2-3-деревья, их применение для словарей, сцепляемых очередей, очередей с приоритетами. Прошитые словари и очереди.
3.4. Поиск цепочек символов
Алфавит. Цепочка. Автоматные грамматики. Порождение цепочек.Задача распознавания. Конечный автомат (КА), его функционирование. Недетерминированный КА. Регулярные множества и выражения.Распознавание цепочек с помощью КА. Алгоритм распознавания по функции отказов. Алгоритм Бауэра-Мура. Распознавание множества цепочек.
Раздел 4. КОМБИНАТОРНЫЕ АЛГОРИТМЫ, АЛГОРИТМЫ НА ГРАФАХ
4.1. Поиск решения в комбинаторных задачах
Перебор вариантов. Бэктрекинг, общий алгоритм. Генерация цепочек символов по грамматике.Оптимизационные задачи. Метод ветвей и границ для решения оптимизационных задач. Задача коммивояжера. Оценки трудоемкости. Приближенные решения задачи коммивояжера. Жадный алгоритм ближайшего города и локальная оптимизация, оценки качества решения. Приближенное решение задачи коммивояжера с помощью минимального остова.
4.2. Комбинаторные задачи на графах
Минимальная раскраска графа, переборный алгоритм. Приближенные алгоритмы раскраски графа,основанные на понятии соцветных веpшин. Раскраска методом ветвей и границ. Гамильтонов цикл.Поиск клик в графе. Узельное покрытие.
4.3. Эффективные алгоритмы на графах.
Эйлеров путь в графе. Остовное дерево наименьшей стоимости, алгоритмы Прима и Крускала. Поиск в глубину в неориентированном графе. Выделение компонент связности. Двусвязные компоненты. Сильно связные компоненты. Нахождение кратчайших путей во взвешенном графе, алгоритмы Флойда и Дейкстры. Транзитивное замыкание, алгоритм Воршалла.
Раздел 5. КОДИРОВАНИЕ
5.1. Коды, информация, энтропия
Канал связи и сообщение. Информация дискретного сообщения. Энтропия. Кодирование. Избыточность.
Кодирование Хаффмана. Методы сжатия сообщений.
5.2. Помехоустойчивое кодирование
Коды проверки на четность. Кодовое расстояние, его влияние на свойства кода. Линейные коды, их
свойства. Простой и расширенный код Хемминга. Полиномиальная арифметика. Циклические коды, их
свойства.
5.3. Случайные числа
Случайная и псевдослучайная последовательность. Линейные конгруэнтные последовательности, их свойства. Дважды случайный датчик. Статистические тесты. Генерирование случайных чисел для произвольных распределений.
5.4. Алгоритмы над сверхдлинными числами
Двоичное представление сверхдлинных целых чисел. Сложение, вычитание и умножение чисел в двоичном виде и в виде машинных слов. Русский крестьянский метод деления двоичных чисел. Деление "в столбик" для чисел в виде машинных слов. Наибольший общий делитель (алгоритм Евклида) для сверхдлинных чисел. Обобщенный алгоритм Евклида, вычисление обратных по модулю чисел.Рекурсивный алгоритм умножения по методу "разделяй и властвуй". Модульная арифметика. Китайская теорема об остатках. Алгоритм Гарнера восстановления чисел по остаткам.
5.5. Криптография
Задачи криптографии. Требования к надежности кода. Шифрование симметричными ключами. Подстановки. Перестановки. Битовые преобразования. Использование случайных последовательностей. Возведение в степень по модулю. Необратимые функции и их применение. Метод Диффи-Хелмана рассылки ключей. Шифрование двумя ключами. Электронная подпись. Метод RSA. Генерация парных ключей в методе RSA. Проверка чисел на простоту.
Раздел 6. ТЕОРИЯ АЛГОРИТМОВ И NP-ПОЛНЫЕ ЗАДАЧИ
6.1. Модели вычислений и машины Тьюринга
Модель равнодоступной адресной машины (РАМ), ее связь с языком программирования. Машина Тьюринга. Связь машины Тьюринга и РАМ. Детерминированная (ДМТ) и недетерминированная (НМТ) машины Тьюринга. Детерминированное моделирование НМТ.
6.2. Теория алгоритмов
Языки и задачи. Машина Тьюринга, как распознаватель цепочки языка. Тезис Черча. Частичные алгоритмы. Алгоритмически неразрешимые проблемы.
6.3. NP-полнота задачи выполнимости
Классы P и NP задач. Теорема Кука о задаче выполнимости булевых формул. NP-полнота задачи выполнимости. Связь NP-полных задач
Задача 3-выполнимости. Раскраска графа. Клики. Узельное покрытие. Гамильтоновы циклы. Задача коммивояжера. Связь задач по сложности. NP-трудные задачи. Связь ДМТ и НМТ по емкостной сложности.

^ 2.2. Практические и семинарские занятия

По курсу не предусмотрены практические занятия.

2.3. Лабораторные работы

Лабораторные работы выполняются по
^ ИНДИВИДУАЛЬНЫМ ЗАДАНИЯМ:
1. Сортировка Шелла.
2. Быстрая сортировка Хоара. Рекурсивный вариант.
3. Быстрая сортировка Хоара. Улучшенный вариант с одним рекурсивным вызовом.
4. Пирамидальная сортировка. Рекурсивный вариант.
5. Пирамидальная сортировка. Нерекурсивный вариант.
6. Цифровая сортировка однобайтовых чисел.
7. Цифровая сортировка строк одинаковой длины.
8. Цифровая сортировка строк различной длины.
9. Сортировка слиянием. Рекурсивный вариант.
10. Сортировка слиянием. Нерекурсивный вариант.
11. Вычисление k-го элемента методом Хоара.
12. Внешняя сортировка сбалансированным двухпутевым слиянием.
13. Внешняя многофазная сортировка двухпутевым слиянием.
14. Дихотомический поиск одного элемента массива.
15. Дихотомический поиск всех одинаковых элементов.
16. Хеширование с открытой адресацией. Вставка, поиск элементов.
17. Хеширование, метод цепочек. Вставка, поиск элементов.
18. Хеширование, метод цепочек. Вставка, поиск, удаление элементов.
19. Построение случайного дерева, поиск в дереве.
20. Построение случайного дерева, поиск, удаление вершин в дереве.
21. Построение выровненного дерева, поиск в дереве.
22. Построение выровненного дерева, поиск, удаление вершин в дереве.
23. Построение АВЛ-дерева, добавление вершин.
24. Построение АВЛ-дерева, добавление и удаление вершин.
25. Построение АВЛ-дерева, поиск минимального и максимального элемента.
26. Построение прошитого АВЛ-дерева, поиск соседнего элемента.
27. Построение 2-3-дерева, добавление вершин.
28. Построение 2-3-дерева, добавление и удаление вершин.
29. Построение 2-3-дерева, поиск минимального и максимального элемента.
30. Построение прошитого 2-3-дерева, поиск соседнего элемента.
31. Иерархическая сортировка таблицы.
32. Независимая сортировка ссылками таблицы по двум ключам.
33. Хеширование для независимого поиска в таблице по двум ключам. Добавление и поиск.
34. Хеширование для независимого поиска в таблице по двум ключам. Добавление, поиск и удаление.
35. Вычисление проекции таблицы с помощью иерархической сортировки.
36. Вычисление проекции таблицы с помощью предварительной независимой сортировки по двум ключам.
37. Вычисление проекции таблицы с помощью хеширования.
38. Вычисление соединения двух таблиц по одному ключу. Таблицы отсортированы по этому ключу.
39. Вычисление соединения двух таблиц по одному ключу. Имеется сортировка ссылками таблиц по этому ключу.
40. Вычисление соединения двух таблиц по одному ключу. Имеются хеш-таблицы со ссылками по этому ключу.
41. Детерминированный автомат для грамматики, задаваемой таблицей.
42. Недетерминированный автомат для грамматики, задаваемой списком правил.
43. Простейший алгоритм распознавания подцепочки.
44. Алгоритм распознавания подцепочки, вычисляющий функцию отказов.
45. Алгоритм Бауэра-Мура распознавания подцепочки.
46. Поиск в лабиринте. Рекурсивный вариант.
47. Поиск в лабиринте. Нерекурсивный вариант.
48. Бэктрекинг для какой-либо головоломки.Рекурсивный вариант.
49. Алгоритм порождения всех цепочек автоматной грамматики.
50. Алгоритм порождения всех цепочек КС-грамматики.
51. Задача коммивояжера. Полный перебор, рекурсивный вариант.
52. Задача коммивояжера. Алгоритм ближайшего соседа.
53. Задача коммивояжера. Алгоритм ближайшего города.
54. Задача коммивояжера. Алгоритм, основанный на построении остовного дерева наименьшей стоимости.
55. Минимальная раскраска графа переборным алгоритмом с отсечениями.
56. Минимальная раскраска транзитивно-ориентированного графа.
57. Приближенная раскраска графа методом склеивания соцветных вершин.
58. Поиск гамильтонового цикла переборным алгоритмом.
59. Нахождение наибольшей максимальной клики переборным алгоритмом с отсечениями.
60. Вычисление эйлерова цикла в графе.
61. Остовное дерево наименьшей стоимости, алгоритм Прима.
62. Остовное дерево наименьшей стоимости, алгоритм Крускала.
63. Остовное дерево наименьшей стоимости, алгоритм Крускала с алгоритмом быстрого объединения множеств (сжатие путей).
64. Остовное дерево наименьшей стоимости c предварительным построением пирамиды для весов ребер.
65. Поиск в глубину, выделение компонент связности графа. Рекурсивный вариант.
66. Поиск в глубину, выделение компонент связности графа. Нерекурсивный вариант.
67. Поиск в глубину, выделение компонент сильной связности графа. Рекурсивный вариант.
68. Поиск в глубину, выделение компонент сильной связности графа. Нерекурсивный вариант.
69. Нахождение всех кратчайших путей в графе.
70. Нахождение кратчайшего пути из одной вершины в графе. Алгоритм Дейкстры.
71. Транзитивное замыкание, алгоритм Воршалла.
72. Транзитивное замыкание, алгоритм Воршалла с использованием битовых операций.
73. Построение кода Хаффмана для символов конкретного текста.
74. Кодирование и декодирование текста заданным неравномерным кодом.
75. Построение кода со сжатием повторяющихся символов. Кодирование и декодирование для этого кода.
76. Линейный случайный датчик и его исследование.
77. Дважды случайный датчик.
78. Датчик для битовых последовательностей.
79. Шифрование и дешифрование случайной последовательностью.
80. Шифрование и дешифрование методом подстановки.
81. Шифрование и дешифрование методом перестановки.
82. Шифрование и дешифрование методом воэведения в степень по модулю.
83. Кодирование и декодирование линейным корректирующим кодом.
84. Кодирование и декодирование кодом Хемминга.
85. Кодирование и декодирование циклическим кодом.
86. Деление длинных чисел "в столбик".
87. Быстрое возведение в степень длинных чисел.
88. Быстрое возведение в степень длинных чисел по модулю.
89. Быстрое умножение длинных чисел рекурсивным разрезанием пополам.
90. Обобщенный алгоритм Евклида для коротких чисел.
91. Проверка делимости сверхдлинного числа на короткие простые числа.

^ ПРИМЕРНЫЕ ТЕМЫ КУРСОВЫХ РАБОТ

Сравнение эффективности различных методов сортировки. сортировка Хоара, Пирамидальная сортировка, Сортировка слиянием.

Дихотомический поиск .

Алгоритмы хеширования.

Сравнение эффективности построения случайного дерева и выровненного дерева.

АВЛ-деревья. добавление и удаление вершин, поиск минимального и максимального элемента, поиск соседнего элемента.

Задача коммивояжера. Алгоритмы решения.

Алгоритмы нахождения минимальной раскраски графа

Нахождение кратчайших путей в графе

Методы Шифрования и дешифрования


ЛИТЕРАТУРА

ОСНОВНАЯ

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

Никлаус Вирт. Алгоримы и структуры данных. СПб., Невский диалект, 2005

Хэзфилд Р., Кирби Л. Искусство программирования на С: Фундаментальные алгоримы, структуры данных и примеры приложений (пер. с англ.). Серия: Энциклопедия программиста. 2001 г.

ДОПОЛНИТЕЛЬНАЯ


Абрамов В. Г., Трифонов Н. П., Трифонова Г. Н. Введение в язык Паскаль: Учебное пособие для вузов. – М.: Наука. 1988.

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир,1979.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1. Синтаксический анализ. – М.: Мир, 1978.

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: Вильямс, 2001.

Баррон Г. Рекурсивные методы в программировании. – М.: Мир, 1974.

Брукшир Дж. Введение в компьютерные науки: Общий обзор. – М.: Вильямс, 2001.

Буч Г. Объектно-ориентированный анализ и программирование. – М.: Бином, 1998.

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

Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, 2001.

Галлагер Р. Теория информации и надежная связь. М.: Советское радио, 1974.

Грис Д. Наука программирования. – М.: Мир, 1984.

Грэхем Р., Кнут Д., Паташник О. Конкретная математика: Основание информатики. – М.: Мир, 1998.

Гудман С., Хидетмиеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981, 368 с.

Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М.: Мир, 1975.

Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978.

Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы. М.:Мир, 1982.

Ершов А.П. Теоретическое программирование.

Йенсен К., Вирт Н. Паскаль: Руководство для пользователя. – М.: Финансы и статистика, 1989.

Кнут Д. Искусство программирования для ЭВМ. Т.1-3. – М.: Вильямс, 2000.

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. М.: МЦНМО, 2001.

Королев Л.Н., Миков А.И. Информатика: Введение в компьютерные науки: Учебник для вузов. – М.: Высшая школа, 2003.

Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

Лорин Г. Сортировка и системы сортировки. – М.: Наука, 1983.

Любимский Э. З., Мартынюк В. В., Трифонов Н. П. Программи­ро­ва­ние: Учебное пособие для вузов. – М.: Наука, 1980.

Макконелл Дж. Анализ алгоритмов: Вводный курс. – М.: Техносфера, 2002.

Мальцев А. М. Алгоритмы и рекурсивные функции. – М.: Наука, 1986.

Минский М. Вычисления и автоматы. – М.: Мир, 1971.

Пильщиков В. Н. Язык Паскаль: Упражнения и задачи: Учебное пособие для вузов. – М.: Научный мир, 2003.

Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир,1980, 476 с.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы: Теория и практика. – М.: Мир, 1980.

Сибуя М., Ямомото Т. Алгоритмы обработки данных. – М.: Мир, 1986.

Трифонов Н. П., Пильщиков В. Н. Задания практикума на ЭВМ (первый курс): Учебное пособие для вузов. – М.: МАКС-Пресс, 2001.

Холл П. Вычислительные структуры. Введение в нечисленное программирование. – М.: Мир, 1978.

Холстед М. Х. Начала науки о программах. – М.: Финансы и статистика, 1981.

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