Главная > Программа


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

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

УТВЕРЖДАЮ

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

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

________________ А.И. Жук

«___» __________ 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.



Скачать документ

Похожие документы:

  1. Введение в разработку и анализ алгоритмов программа элективного курса по информатике

    Элективный курс
    ... интуитивного понятия алгоритма, рассмотрению различных типов алгоритмов, методов их построения и анализа. Алгоритмы имеют первостепенное ... методическая установка курса – обучение построению и анализу алгоритмов при решении различных задач, развитие ...
  2. ПОСТРОЕНИЕ И АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ИНТЕГРАЛЬНЫХ СХЕМ В ГЕОМЕТРИЧЕСКОЙ ФОРМЕ

    Документ
    ПОСТРОЕНИЕ И АНАЛИЗ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ИНТЕГРАЛЬНЫХ СХЕМ В ГЕОМЕТРИЧЕСКОЙ ... обработки сигналов, реализуемых с помощью ПЛИС – алгоритмы, основанные на применении ортогональных преобразований ...
  3. Построение и анализ комбинаторных алгоритмов (дисциплина по выбору)

    Документ
    Построение и анализ комбинаторных алгоритмов (дисциплина по выбору) Преподаватель: Стеценко В.А., ... а) основная литература: Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М.: МЦНМО, 1999. б) дополнительная литература: А.В. Ахо ...
  4. Построение и анализ комбинаторных алгоритмов (дисциплина по выбору)

    Документ
    Построение и анализ комбинаторных алгоритмов (дисциплина по выбору) Преподаватель: Стеценко В.А., ... а) основная литература: Т. Кормен, Ч. Лейзерсон, Р. Ривест Алгоритмы. Построение и анализ, М.: МЦНМО, 1999. б) дополнительная литература: А.В. Ахо ...
  5. Алгоритмы и структуры данных в построении и анализе сбис

    Лекция
    ... кибернетики" Кафедра "Теоретической кибернетики" Алгоритмы и структуры данных в построении и анализе СБИС Курс лекций Лектор ... ВМК КГУ и посвященных анализу алгоритмов и структур данных, используемых в построении и анализе СБИС1. Несмотря на ...

Другие похожие документы..