Учебная программа для высших учебных заведений по специальности 1- 31 03 04 Информатика

Вид материала

Содержание

Е. П. Соболевская
Кузнецов А.Т.
Рекомендована к утверждению в качестве типовой
Научно-методическим советом
Пояснительная записка
Теория графов

Подобный материал:

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

УТВЕРЖДАЮ

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

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

« 30 » 06 2006 г.

Регистрационный № ТД – G.060/тип.

ТЕОРИЯ АЛГОРИТМОВ

Учебная программа

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

1- 31 03 04 Информатика

СОГЛАСОВАНО

Председатель
научно-методического совета
по прикладной математике и информатике
_______________ П.А. Мандрик

_______________ 2006

Первый проректор

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

«Республиканский институт высшей школы»

_____________ В.И. Дынич
_____________ 2006

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

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

_______________ 2006

Минск

2006

Составители:

В. М. Котов, заведующий кафедрой дискретной математики и алгоритмики Белорусского государственного университета, доктор физ.-матем. наук, профессор;

Е. П. Соболевская, доцент кафедры дискретной математики и алгоритмики Белорусского государственного университета, кандидат физ.-матем. наук, доцент

Рецензенты:

Рецензенты:

Кафедра вычислительных методов и программирования Учреждения образования «Белорусский государственный университет информатики и радиоэлектроники»

Кузнецов А.Т.  доцент кафедры прикладной математики и информатики Учреждения образования «Белорусский государственный педагогический университет им. М. Танка», канд. пед. наук, доцент

Рекомендована к утверждению в качестве типовой:

Кафедрой дискретной математики и алгоритмики Белорусского государственного университета

(протокол № 12 от 31 января 2006г.).

Научно-методическим советом Белорусского государственного университета

(протокол № ___ от ____ ___________2006г.).

Ответственный за редакцию: Е.П. Соболевская

Ответственный за выпуск: О.А. Кастрица

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

Курс «Теория алгоритмов» знакомит студентов с такими фундаментальными понятиями как информация, размерность задачи и трудоемкость алгоритмов. Особое внимание уделено способам определения трудоемкости алгоритмов с помощью таких методов, как составление и решение рекуррентных уравнений. Наряду с классическим подходом оценки трудоемкости рассматриваются также способы определения усредненной оценки трудоемкости алгоритма для группы операций.

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

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

В курсе также рассматриваются различные модели вычислений (в том числе и параллельных), и вопросы теории кодирования.

Основой для изучения теории алгоритмов являются следующие курсы: «Дискретная математика и математическая логика», «Теория вероятностей и математическая статистика», «Программирование». Методы, излагаемые в курсе, используются при изучении дисциплин «Исследование операций», «Модели данных и СУБД», а также при изучении ряда дисциплин специализации. Изучение курса теории алгоритмов позволяет дать студентам базу, необходимую для успешного усвоения материала перечисленных выше учебных дисциплин, а также получить знания, необходимые им в дальнейшем для успешной работы.

В соответствии с образовательным стандартом специальности 1- 31 03 04 «Информатика» учебная программа предусматривает для изучения дисциплины 135 аудиторных часов, в том числе лекционных  64 ч., лабораторных  46 ч, контролируемой самостоятещльной работы – 25 ч.

Содержание

Введение

Понятие информации. Мера информации. Размерность задачи. Трудоемкость алгоритмов: наилучший случай, наихудший случай, трудоемкость в среднем, усредненная оценка трудоемкости группы операций. Ассимптотики Ο, Ω, Θ. Полиномиальные и неполиномиальные алгоритмы. Примеры.

Проектирование и анализ

Понятие рекуррентного уравнения. Правильные и неправильные рекуррентные уравнения. Полное рекуррентное уравнение. Основные методы решения рекуррентных уравнений: метод итераций и метод рекурсивных деревьев. Оценка решения рекуррентного уравнения: метод подстановок. Теорема о решении рекуррентного уравнения вида T(n)=aT(n/c)+b*n. Рекуррентные уравнения базовых алгоритмов и их трудоемкость.

Способы упорядочивания информации: основные алгоритмы внутренней и внешней сортировки и их трудоемкость.

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

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

Сложные структуры данных: бинарные кучи, биномиальные кучи и кучи Фибоначчи. Реализация базовых операций над ними. Усредненная трудоемкость базовой операции.

Множества. Различные способы представление множеств и реализация базовых операций над ними. Применение множеств для решения задач.

Организация поиска

Поисковые деревья. Сбалансированные деревья: АВЛ-деревья, 2-3 деревья, красно-черные дереья. Базовые операции над ними и их трудоемкость в наихудшем случае.

Хэш-таблицы и хэш-функции. Коллизии. Методы разрешения коллизий. Открытое и закрытое хэширование.

Теория графов

Методы хранения графов и деревьев. Связность. Двудольность. Маршруты. Подграфы.

Использование современных структур данных в основных алгоритмах на графах: поиск в глубину (стек), поиск в ширину (очередь), кратчайший путь (приоритетная очередь). Трудоемкость алгоритмов. Максимальный поток в графе и его приложения. Топологическая сортировка. Алгоритмы построения минимального остовного дерева, использующие при своей реализации приоритетую очередь и множества, и их трудоемкость.

Стратегии решения задач

Принцип «Разделяй и властвуй», динамическое программирование, градиентные алгоритмы. Примеры решения задач с использованием данных методов и их трудоемкость.

NP-трудные задачи

Организация перебора при решении NP-трудных задач. Методы уменьшения перебора. Метод ветвей и границ. Полиномиально разрешимые случаи.

Приближенные алгоритмы

Типы эвристик: локальный поиск, алгоритмы локального улучшения, генетические алгоритмы, табу-поиск.

Градиентные алгоритмы. Матроидные структуры.

Оценка погрешности приближенных алгоритмов. -приближенные и быстрые -приближенные алгоритмы. On-line и semi on-line версии задач (задачи с неполной информацией о входных данных), алгоритмы их решения и способы оценки качества решений. Рандомизированные алгоритмы.

Сортирующие сети

Компараторы. Сети слияния. 0-1 принцип. В-последовательности. Полуочиститель. В-сортировщик. Сети слияния.

Модели параллельных вычислений

Понятие PRAM-машины. Различные типы машин: EREW PRAM, CREW PRAM, CRCW PRAN (Weak, Common, Arbitrary, Priority, Strong). Связь между ними. Общие методы распараллеливания: метод сдваивания, матричная техника, сепараторы.

Теория кодирования

Методы кодирования информации: алгоритмы Хаффмена, Лемпеля-Зива, Левенштейна. Арифметическое кодирование.

Литература

Основная

Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Структуры данных и алгоритмы.  М.: Издательский дом “Вильямс”, 2000.  384 c.
Ахо Альфред В., Хопкрофт Джон Э., Ульман Джеффри Д. Построение и анализ вычислительных алгоритмов.  М.: Мир,1979.  536 c.
Котов В.М., Соболевская Е.П. Структуры данных и алгоритмы: теория и практика.  Мн.: БГУ. 2004.  252 с.
Ковалев М.Я., Котов В.М.,Лепин В.В. Теория алгоритмов. Часть 2. Приближенные алгоритмы. – Мн.: БГУ, 2003. – 147 с.
Котов В.М., Пилипчук Л.А., Соболевская Е.П. Теория алгоритмов. Ч.1.  Мн.: БГУ. 2001.  192 с.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.  М.: МЦНМО, 1999.  960 с., 263 ил.

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

Вирт Н. Алгоритмы и структуры данных.  СПб.: Невский Диалект, 2001. 352с.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов.  М.: Наука, 1990. 383с.
Котов В.М. Алгоритмы для задач разбиения и упаковки. Научное издание.  Мн.: БГУ. 2001.  97 с.
Липский В. Комбинаторика для программистов.  М.: Мир,1988.  214 с.
Пападдимитриу Х.,Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.  М.: Мир,1971.  512с.
Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы теория и практика.  М.: Мир, 1980.  476 c.
Mark Allen Weiss. Data structures and algorithm analysis.  Benjamin/Cummings Publishing Company, 1992.  455 p.
C. Shaffer. A Practical Introduction to Data Structure and Algorithm Analysis.  London: Prentice Hall International, 1997.  494 p.

Blog