Таганрогский государственный радиотехнический университет
Факультет автоматики и вычислительной техники
Кафедра математического обеспечения и применения ЭВМ
Программа
государственного экзамена итоговой аттестации
студентов, обучающихся по специальности 010503
«Математическое обеспечение и администрирование
информационных систем»
Таганрог 2009
Раздел 1. Структуры и алгоритмы обработки данных
■ 1.. Сцепленные структуры данных. Линейные списки. Односвязные и двусвязные списки. Кольцевые списки. Использование списков для представления стеков и очередей. Деревья как структуры данных. Представление деревьев. Бинарные деревья и основные операции над ними. Обход дерева.
Оценка эффективности алгоритмов и программ. Максимальное, среднее и минимальное время выполнения. Теоретический и экспериментальный подход к оценке эффективности. Размерность задачи. Оценки «в смысле 0-большое». Экспоненциальные и полиномиальные оценки. Примеры оценок для типовых алгоритмов.
Сортировка и поиск в массивах. Линейный поиск в массиве. Барьерный поиск. Бинарный поиск в массиве. Оценка эффективности линейного и бинарного поиска. Простые алгоритмы сортировки массивов. Оценка эффективности простых алгоритмов.
Усовершенствованные алгоритмы сортировки массивов. Алгоритм Quicksort. Выбор разделяющего элемента. Нерекурсивная реализация Quicksort. Алгоритм HeapSort. Понятие ' пирамиды. Фазы работы алгоритма. Оценка эффективности усовершенствованных алгоритмов.
Алгоритмы слияния. Операция слияния массивов. Простое слияние. Фазы разделения и слияния. Естественное слияние. Внешняя сортировка.
Бинарные деревья поиска. Поиск с включением в дерево. АВЛ-деревья. Операция балансировки АВЛ-дерева при вставке и удалении ключей.
Поиск в фашюх. Страничные деревья поиска. Понятие В-дерева. Операции вставки и удаления ключей для В-дерева.
Хеширование. Понятие хеширования. Требования к хеш-функции. Способы построения хеш-функции. Коллизии хеширования и способы их разрешения. Сравнение хеширования с другими стратегиями поиска.
9. Комбинаторные задачи. Задачи поиска, перечисления и оптимизации. Задачи с фиксированной и нефиксированной размерностью. Способы организации исчерпывающего перебора. Способы сокращения перебора.
10. Метод ветвей и границ. Нижние и верхние оценки. Алгоритм ветвей и границ для задачи о коммивояжере. Метод ос- Р-отсечений для позиционных игр.
11. Метод динамического программирования. Функция Беллмана. Уравнения Беллмана для дискретных задач. Алгоритм Беллмана для задачи о рюкзаке.
12. Приближенные и эвристические алгоритмы. Примеры приближенных алгоритмов. Локально оптимальные («жадные») алгоритмы. Алгоритмы последовательного выбора и последовательных улучшений. Случайный поиск. Генетические алгоритмы.
Понятие сложности задачи. Массовые и индивидуальные задачи. Длина задачи. Задачи распознавания. Полиномиальные и экспоненциальные алгоритмы. Полиномиальная сводимость.
Недетерминированные машины Тьюринга (НМТ). Машина Тьюринга и класс задач Р. Определение НМТ. Функционирование НМТ. Класс задач NP. Полиномиально проверяемые задачи.
Понятие NP-полноты задачи. Определения NP-трудных и NP-полных задач. Соотношение между классами Р, NP и NPC. Возможность сведения всех NP-задач к конкретной задаче. Задача о выполнимости КНФ. Теорема Кука.
Примеры доказательства NP-полноты задач. Способы доказательства NP-полноты. NP-полнота задачи «3-выполнимость» и задачи о вершинном покрытии графа.
Основные понятия теории графов. Неориентированные и ориентированные графы. Способы представления графов: матрицы смежности и инцидентности, списки ребер, списки смежных вершин.
Организация поиска в графе. Поиск в глубину и в ширину. Примеры применения алгоритмов поиска.
Построение минимального остовного дерева. Постановка задачи. Алгоритмы Прима и Крускала. Оценка эффективности алгоритмов.
Задача о кратчайшем пути в графе. Постановка задачи. Алгоритмы Флойда и Дейкстры. Оценка эффективности алгоритмов.
Задача о максимальном потоке в сети. Варианты постановки задачи. Аугментальные цепи. Алгоритм Форда-Фалкерсона.
Задача о максимальном паросочетании. Постановка задачи. Решение задачи для двудольных графов.
Задача о раскраске графа. Постановка задачи. Эвристические алгоритмы раскраски. Алгоритм неявного перебора.
Основные понятия теории информации. Задачи сжатия данных. Префиксные коды. Кодовые деревья. Оптимальные префиксные коды (коды Хаффмена) и их построение.
ЛИТЕРАТУРА
Вирт Н. Алгоритмы + структуры данных = программы. - М.: «Мир», 1985. - 544 с, ил.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. - М.: Издательский дом «Вильяме», 2001. - 384 с, ил.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. - М.: МЦНМО, 2000. - 960 с, ил.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. - М.: «Мир», 1980. - 476 с, ил.
Гудман С, Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: «Мир», 1981. - 366 с, ил.
Кнут Д. Искусство программирования для ЭВМ. т.1. Основные алгоритмы. М.: Вильяме, 2002. - 736 с, ил.; т.2. Получисленные алгоритмы. М.: Вильяме, 2002. - 724 с, ил.; т.З. Сортировка и поиск. - М.: Вильяме, 2002. - 826 с, ил.
Кристофидес Н. Теория графов. Алгоритмический подход. -М.:Мир, 1978.-432с, ил.
8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М.: «Мир», 1982. - 416 е., ил.
9. Дроздов С.Н. Комбинаторные задачи и элементы теории вычислительной сложности. Учебное пособие. - Таганрог: Изд- воТРТУ,2000.-62с.