Geum.ru

Программа курса для студентов специальностей 1-31 03 06

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

Содержание


РЕЦЕНЗЕНТЫ: научный сотрудник ИМ НАН РБ, канд. физ.-мат. наук, Ковалевская Э.И.
Рекомендована к утверждению кафедрой
Содержание курса
Подобный материал:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ




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


УТВЕРЖДАЮ

Ректор _______________С.А.Маскевич

(подпись)


«___ » ____________________ 200 __г.




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




ПРОГРАММА КУРСА


ДЛЯ СТУДЕНТОВ СПЕЦИАЛЬНОСТЕЙ

1-31 03 06 Экономическая кибернетика

1-31 03 03 –02 Прикладная математика





Гродно 2004




АВТОР: Статкевич С.Э., преподаватель кафедры ТФФАВ и ПМ, ГрГУ


РЕЦЕНЗЕНТЫ:

научный сотрудник ИМ НАН РБ, канд. физ.-мат. наук, Ковалевская Э.И.


канд.физ.-мат. наук, ст. преподаватель кафедры ДУ и ОУ Гончарова М.Н.



Рекомендована к утверждению кафедрой теории функций, функционального анализа, вероятностей и прикладной математики

Протокол № _10_ от «_26_» _мая_ 2004 г.


Рекомендована к утверждению методической комиссией по специальности __________

Протокол № _____ от «___» ________________________ 200__ г.


Рекомендована к утверждению Советом математического факультета

Протокол № 9 от «29 » _ июня 2004 г.


Рекомендована к утверждению Советом университета

Протокол № _____ от «___» ________________________ 200__ г.






Предисловие

Курс Теория алгоритмов читается на 2 курсе для студентов специальностей Экономическая кибернетика и Прикладная математика Цель курса:
  • ознакомить с классической теорией алгоритмов;
  • дать знания по основам теории алгоритмов, представлении данных, теории сложности;
  • обеспечить навыки в построении алгоритмов и анализе их эффективности.



Введение

Курс Теория алгоритмов содержит лекционные и лабораторные занятия. На лекциях излагаются классические вопросы теории алгоритмов, современные подходы в теории сложности, приемы построения эффективных алгоритмов. Устанавливается связь с курсами ЭВМ и программирование, Матричный анализ, Вычислительные методы алгебры, Методы численного анализа. Особое внимание уделяется практическим методам вычисления сложности алгоритмов и построению эффективных алгоритмов. На лабораторных занятиях студенты получают практические навыки по представлению данных в программе, по применению методов поиска информации.

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


Содержание курса

Введение. Понятие алгоритмы. Различные модели вычислений, машина Тьюринга, машина Поста, рекурсивные функции. Уточнение понятия алгоритма и пять его параметров. Область применимости алгоритма. Конструктивные объекты. Примитивно рекурсивные функции. Операция минимизации. Нумерация n-ок. Примитивная рекурсивность сумм, произведений, оператора ограниченной рекурсии. Частично рекурсивные и общерекурсивные функции. Функция Аккермана. Диагонализация. Машина Тьюринга. Эквивалентность общерекурсивных функций и вычислений на машине Тьюринга. Примитивно рекурсивные и рекурсивные множества. Проблема останова. Основные результаты теории алгоритмов.

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

Процесс разработки алгоритма, итерация, применение рекурсии. Алгоритмы сортировки, их сложность. Дерево поиска, балансировка дерева. Динамическое программирование. Способы представления данных, зависимость сложности алгоритма от представления данных.

Алгоритмы на графах. Примеры алгоритмов с различными оценками сложности. Приближенные алгоритмы, точность, оценки сложности. Различные типы алгоритмов: точные, приближенные вероятностные, эвристические, алгоритмы реального времени.

Литература

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

Кушниренко А.Г., Лебедев Г.В. Программирование для математиков. М:Наука, 1988.- 384 с.

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

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

Липский В. Комбинаторика для программистов. М.:Мир, 1988.

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

Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высш. шк., 1976.

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

Лекции по теории графов. В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. М.: Наука, 1990.