Учебная программа для специальностей 1-310303-02 Прикладная математика 1-310306 Экономическая кибернетика
| Вид материала | Программа |
- Учебная программа для специальностей 1-31 03 03-02 «Прикладная математика», 1-31, 204.5kb.
- Учебная программа для специальности: ( рабочий вариант) 1-310306 Экономическая кибернетика, 111.14kb.
- Программа дисциплины по кафедре «Экономическая кибернетика» специальностей «Математические, 195.68kb.
- Учебная программа для специальности: 1-31 03 06 Экономическая кибернетика (код специальности), 177.23kb.
- Учебная программа для специальности: 1-31 03 06 Экономическая кибернетика (код специальности), 187.17kb.
- Программа дисциплины по кафедре «Экономическая кибернетика» для специальности «Математические, 205.71kb.
- Программа дисциплины по кафедре Экономическая кибернетика экономическая информатика, 271.22kb.
- Программа дисциплины по кафедре «Экономическая кибернетика» организация и планирование, 238.78kb.
- Программа дисциплины по кафедре «Экономическая кибернетика» основы управленческого, 356.46kb.
- Программа дисциплины по кафедре "Экономическая кибернетика" эконометрика, 340.04kb.
Ф27-015
Учреждение образования
“Гродненский государственный университет имени Янки Купалы”
УТВЕРЖДАЮ
Ректор
Учреждения образования
“Гродненский государственный
университет имени Янки Купалы”
___________________ Е.А.Ровба
«_18__» июня_ 2010 г.
Регистрационный № УД- 10/МИ-061/баз.
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Учебная программа для специальностей
1-310303-02 Прикладная математика
1-310306 Экономическая кибернетика
(код, наименование специальности)
Гродно 2010
СОСТАВИТЕЛЬ: Статкевич С.Э., старший преподаватель кафедры стохастического анализа и эконометрического моделирования Учреждения образования “Гродненский государственный университет им. Я. Купалы”.
РЕЦЕНЗЕНТЫ:
доктор физ. - мат. наук, профессор, заведующий кафедрой ТВ и МС БГУ Н.Н. Труш;
кандидат физ.-мат. наук, доцент Ю.М. Вувуникян
РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ:
Кафедрой стохастического анализа и эконометрического моделирования (протокол № 4 от 20.04.2010г.);
Методической комиссией по специальности
(протокол № 5 от 18.05.2010г.);
Советом факультета математики и информатики
(протокол № 5 от 19.05.2010г.)
Научно-методическим советом Учреждения образования “Гродненский государственный университет имени Янки Купалы”
(протокол № __от _______);
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Курс «Алгоритмы и структуры данных» читается на 2 курсе для студентов специальностей «Экономическая кибернетика” и «Прикладная математика”.
Цель курса состоит в выработке практических навыков вычисления сложности алгоритмов и построению эффективных алгоритмов.
Задачами дисциплины являются получение практических навыков по представлению данных в программе, по применению методов поиска информации, выработке навыков построения алгоритмов для решения прикладных задач.
В результате изучения дисциплины студенты должны быть компетентными в
- основных элементах классической теории алгоритмов и структурах данных;
- представлении данных, теории сложности;
- методах, необходимых для построения алгоритмов, анализа их сложности и эффективности.
Общее количество часов — 68, из них лекционных — 34 часа, лабораторных — 34 часов.
ПРИМЕРНЫЙ ТЕМАТИЧЕСКИЙ ПЛАН
| № п/п | Название раздела | Количество часов | |
| лекционных | лабораторных | ||
| | Введение в курс «Алгоритмы и структуры данных» | 2 | |
| | Теория рекурсивных функций | 20 | 6 |
| | Теория графов | 10 | 24 |
| | Теория кодирования | 2 | 4 |
СОДЕРЖАНИЕ УЧЕБНОГО МАТЕРИАЛА
Введение. Понятие алгоритма. Различные модели вычислений, машина Тьюринга, машина Поста, рекурсивные функции. Уточнение понятия алгоритма и пять его параметров. Область применимости алгоритма. Конструктивные объекты.
Теория рекурсивных функций. Понятие алгоритма. Различные модели вычислений, машина Тьюринга, машина Поста, рекурсивные функции. Уточнение понятия алгоритма и пять его параметров. Область применимости алгоритма. Конструктивные объекты. Базисные функции, операции на базисных функциях. Операция минимизации. Частично рекурсивные и общерекурсивные функции. Операции суммы и произведения. Ограниченная рекурсия. Примитивная рекурсивность некоторых функций теории чисел. Нумерация пар. Нумерация n-ок. Возвратная рекурсия. Рекурсия второй ступени. Рекуррентные уравнения. Понятие трудоемкости алгоритма. Полиномиальные и полиномиально-полные задачи. Алгоритмы сортировки, их сложность.
Теория графов. Деревья. Поисковые деревья. Сбалансированные деревья: АВЛ-деревья и 2-3 деревья. Базовые операции над деревьями. Трудоемкость операций. Методы хранения графов и деревьев. Организация поиска в графах и деревьях. Связность. Маршруты. Подграфы.
Теория кодирования. Методы кодирования информации: алгоритмы Хаффмена, Лемпеля-Зива, Левенштейна. Арифметическое кодирование.
ИНФОРМАЦИОННО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
Основная литература
- Ахо, А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М.: Мир, 1979. - 536 с.
- Белов В.В., Воробьев Е.М., Шаталов В.Е. Теория графов. М.: Высш. шк., 1976.
- Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. - М.: Мир, 1978. – 336 с.
- Кушниренко, А.Г. Программирование для математиков / А.Г. Кушниренко, Г.В. Лебедев. - М.: Наука, 1988.- 384 с.
- Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. – М.: Наука, 1976. – 298 с.
- Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергельт, Н. Део. - М.: Мир, 1980. – 412 с.
Дополнительная литература
- Вирт, Н. Алгоритмы+структуры данных=программы / Н. Вирт. - М.: Мир -1985. – 289 с.
- Липский, В. Комбинаторика для программистов / В. Липский. - М.: Мир, 1988. – 124 с.
- Лекции по теории графов / В.А.Емеличев , О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. - М.: Наука, 1990. – 312 c.