Geum.ru

Образования Республики Беларусь А. И. Жук 2008 г. Регистрационный № тд- /тип. Построение и анализ алгоритмов типовая учебная программа

Вид материалаПрограмма

Содержание


Рекомендована к утверждению в качестве типовой
1. Пояснительная записка
2. Примерный тематический план
3. Содержание учебного материала
2. Трудоемкость алгоритмов.
3. Алгоритмы сортировки.
4. Алгоритмы поиска и выборки.
5. Алгоритмы на строках.
7. Динамическое программирование и метод “разделяй и властвуй”.
8. Основы теории сложности вычислений.
9. Алгоритмы с гарантированной оценкой точности.
10. Основные алгоритмические стратегии.
11. Задачи линейного и целочисленного линейного программирования.
12. Алгоритмы для работы с матрицами.
14. Алгоритмы сжатия информации.
16. Алгоритмы для параллельных вычислений.
М.: мцнмо, 2000
Подобный материал:



Министерство образования Республики Беларусь

Учебно-методическое объединение вузов Республики Беларусь
по естественнонаучному образованию


УТВЕРЖДАЮ

Первый заместитель Министра

Образования Республики Беларусь

________________ А.И. Жук


«___» __________ 2008 г.


Регистрационный № ТД-______/тип.


ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

Типовая учебная программа

для высших учебных заведений по направлению специальности:

1-31 03 01-05 Математика (информационные технологии)



СОГЛАСОВАНО

Председатель Учебно-методического объединения вузов Республики

Беларусь по естественнонаучному образованию

________________ В.В. Самохвал

«___» __________ 2008 г.
СОГЛАСОВАНО

Начальник управления высшего и среднего специального образования Министерства образования

Республики Беларусь

________________ Ю.И. Миксюк

«___» __________ 2008 г.


Первый проректор Государственного учреждения образования «Республиканский институт высшей школы»

________________ И.В. Казакова

«___» __________ 2008 г.





Эксперт-нормоконтролер

________________ С.М. Артемьева

«___» __________ 2008 г.


Минск 2008
Составители:



Романчик Валерий Станиславович, заведующий кафедрой численных методов и программирования Белорусского государственного университета, кандидат физико-математических наук, доцент;
Скумс Павел Валентинович, старший преподаватель кафедры численных методов и программирования Белорусского государственного университета, кандидат физико-математических наук.



Рецензенты:


Кафедра экономической информатики Учреждения образования «Белорусский государственный экономический университет» (заведующий кафедрой – кандидат технических наук, профессор Б.А. Железко);


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


РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ В КАЧЕСТВЕ ТИПОВОЙ:

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

(протокол № 8 от 6 марта 2008 г.);


Научно-методическим советом Белорусского государственного университета (протокол № 3 от 27 марта 2008 г.);

Научно-методическим советом по математике и механике Учебно-методического объединения вузов Республики Беларусь по естественнонаучному образованию

(протокол № 3 от 10 апреля 2008 г.).


Ответственный за выпуск: Скумс Павел Валентинович

1. Пояснительная записка


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

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

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

После изучения данной дисциплины студент должен

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

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

Всего – 248 часов. Из них аудиторных – 136 часов, в том числе: лекции – 66 ч., лабораторные занятия – 38 ч., практические занятия – 32 ч.


2. Примерный тематический план

№ п/п
Название темы
Лекции
Практ. занятия
Лаб. занятия
Всего

1.

Введение. Основные структуры данных
2



2
4

2.

Трудоемкость алгоритмов
2
2
-
4

3.

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

4.

Алгоритмы поиска и выборки
4
-
4
8

5.

Алгоритмы на строках
2
-
2
4

6.
Алгоритмы на графах
16
8
10
34

7.

Динамическое программирование и метод “разделяй и властвуй”
4
-
4
8

8.

Основы теории сложности вычислений
6
6
-
12

9.

Алгоритмы с гарантированной оценкой точности.


4
4
-
8

10.

Основные алгоритмические стратегии
6
4
4
14

11.

Задачи линейного и целочисленного линейного программирования
2
2



4

12.

Алгоритмы для работы с матрицами
4
2
2
8

13.

Элементы криптографии
4
2
2
8

14.

Алгоритмы сжатия информации
2
-
2
4

15.

Нейронные сети
2
-
2
4

16.

Алгоритмы для параллельных вычислений
2
2



4




Итого
66
32
38
136



3. Содержание учебного материала


1. Введение. Основные структуры данных. Предмет теория алгоритмов. Прикладное значение эффективности алгоритмов. Связь с дискретной математикой, математической кибернетикой, программированием. Стеки, очереди, связанные списки, бинарные деревья.

2. Трудоемкость алгоритмов. Предмет теория алгоритмов. Прикладное значение эффективности алгоритмов. Связь с дискретной математикой, математической кибернетикой, программированием. Необходимость оценки алгоритмов. Принципы оценки трудоемкости комбинаторных алгоритмов. Рост функций, O-нотация. Трудоемкость «в худшем», трудоемкость «в среднем», трудоемкость «почти всегда». Примеры анализа алгоритмов.

3. Алгоритмы сортировки. Элементарные методы сортировки (сортировки выбором, вставками, пузырьковая, Шелла). Быстрая сортировка. Корневая и пирамидальная сортировка. Сортировка слиянием. Внешняя сортировка. Линейные сортировки (подсчетом и вычерпыванием). Анализ эффективности сортировок. Теорема о невозможности существования алгоритма сортировки в «худшем» и «в среднем» с трудоемкостью лучшей, чем О(n log2n).

4. Алгоритмы поиска и выборки. Последовательный поиск. Бинарный поиск. Деревья бинарного поиска. Сбалансированные деревья (2-3-4 деревья, красно-черные деревья) и реализуемые с их помощью структуры. Операции над деревьями. Хеширование.

5. Алгоритмы на строках. Основные определения. Алгоритмы поиска подстроки в строке. Алгоритмы Бойера-Мура, Кнута-Морриса-Пратта и их реализации.

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

7. Динамическое программирование и метод “разделяй и властвуй”. Понятие о методах динамического программирования и “разделяй и властвуй”. Алгоритм Штрассена умножения матриц. Задача о рюкзаке. Графы с ограниченным параметром treewidth и алгоритмы для них.

8. Основы теории сложности вычислений. Детерминированные и недетерминированные машины Тьюринга. Понятие о классах Р и NР. NP-полные задачи. Теорема Кука-Карпа-Левина. NP-полнота задач “3-выполнимость”, “Клика”, “Гамильтонов цикл”. Списки наиболее известных NР-полных задач.

9. Алгоритмы с гарантированной оценкой точности. Понятие о гарантированной оценке точности алгоритма. Задача упаковки. Задача о максимальном разрезе. Задача о вершинном покрытии. Задача о коммивояжере с неравенством треугольника, О существовании алгоритма с гарантированной оценкой точности для общей задачи коммивояжера.

10. Основные алгоритмические стратегии. Эвристики и метаэвристики. Алгоритмы локального поиска, поиска с запретами. Генетические алгоритмы, алгоритмы имитации отжига. Алгоритмы полного перебора, метод ветвей и границ.

11. Задачи линейного и целочисленного линейного программирования. Понятие о задачах линейного и целочисленного линейного программирования. Формулировки основных задач дискретной оптимизации как задач целочисленного линейного программирования. Программные пакеты для решения задачи целочисленного линейного программирования. Формат MPS.

12. Алгоритмы для работы с матрицами. Решение систем линейных уравнений. LU-разложение. Обращение матриц.

13. Элементы криптографии. Криптосистемы с открытым ключом, цифровая подпись. Криптосистема RSA. Алгоритмы проверки чисел на простоту.

14. Алгоритмы сжатия информации. Коды Хаффмана, алгоритм Хаффмана.

15. Нейронные сети. Понятие о нейронной сети. Типы нейронных сетей. Обучение нейронных сетей.

16. Алгоритмы для параллельных вычислений.


4. Информационная часть

Литература


Основная
  1. Роберт Седжвик. Фундаментальные алгоритмы на JAVA. Части 1-4. Анализ, структуры данных, сортировка, поиск. DiaSoft. Москва, Санкт-Петербург, Киев, 2003.
  2. Роберт Седжвик. Фундаментальные алгоритмы на С++. Часть 5. Алгоритмы на графах. DiaSoft. Москва, Санкт-Петербург, Киев, 2002.
  3. Дж. Макконелл. Анализ алгоритмов. Техносфера. Москва, 2002.
  4. Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2000



Дополнительная

  1. Кнут Д. Искусство программирования. Т.1. Основные алгоритмы. 2000, Вильямс.
  2. Кнут Д. Искусство программирования. Т.2. Получисленные алгоритмы. 2000, Вильямс.
  3. Кнут Д. Искусство программирования. Т.3. Сортировка и поиск. 2000, Вильямс.
  4. Ахо Х., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
  5. Пападимитриу Х., Стейглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: 1985.
  6. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: 1990.
  7. Хайкин С. Нейронные сети. Полный курс. — М.: 2005.