МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Мурманский государственный гуманитарный университет»
(ФГБОУ ВПО «МГГУ»)
УТВЕРЖДАЮ:
проректор по учебной работе
________________ И. А.Архип
«____»____________200___ г.
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
ДИСЦИПЛИНЫ
ОПД. В.1.1 ДОПОЛНИТЕЛЬНЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Основная образовательная программа подготовки специалиста по специальности
010200 (010501) «Прикладная математика и информатика»
Утверждено на заседании кафедры
математики и математических методов
в экономике факультета
физико-математического образования,
информатики и программирования
(протокол № 6 от 27 февраля 2013 г.)
Зав. кафедрой _______________О. М. Мартынов
1.1 Автор программы: кандидат технических наук, доцент Р.
1.2 Рецензент: доктор физико-математических наук, профессор Маренич Е. Е., кандидат физико-математических наук, доцент М.
1.3 Пояснительная записка:
Целью изучения курса дискретной математики является математическая подготовка студентов на уровне, необходимом и достаточном для:
· усвоения материала специальных дисциплин;
· практической работы по специальности;
· формирования умения исследовать математические модели, обрабатывать и анализировать экспериментальные данные.
Основными задачами изучения данной дисциплины являются:
· формирование у студентов математической культуры и развитие логического мышления;
· формирование целостной системы знаний о теории производящих функций и рекуррентных уравнений, а также об основах теории алгоритмов;
· обучение составлению математических моделей и основным методам решения задач теории графов и алгебры логики;
· обучение решению прикладных задач математическими методами;
· развитие способности творчески подходить к решению профессиональных задач.
В результате изучения курса студенты
должны знать: об основных понятиях и утверждениях, входящих в содержание дисциплины, методах решения задач теории производящих функций и рекуррентных уравнений, об вычислимых функциях и неразрешимых алгоритмических проблемах.
должны уметь:
· применять производящие функции для вычисления сумм и решения задач комбинаторики;
· строить математические модели задач, решаемых с помощью рекуррентных уравнений;
· конструировать машину Тьюринга, вычисляющую заданную функцию;
· доказывать примитивную рекурсивность функций;
· использовать пакеты прикладных программ для решения задач дискретной математики с помощью новых информационных технологий.
1.4. Курс входит в раздел дисциплин регионального вузовского компонента.
1.5. Объем дисциплины и виды учебной работы.
№ п/п | Шифр и наименование специальности | Курс | Семестр | Виды учебной работы в часах | Вид итогового контроля (форма отчетности) | |||||
Трудоемкость | Всего аудит. | ЛК | ПР/ СМ | ЛБ | Сам. работа | |||||
1 | 010501 «Прикладная математика и информатика» | 2 | 3 | 110 | 66 | 36 | 30 | – | 44 | экзамен |
1.6 Содержание дисциплины.
1.6.1 Разделы дисциплины и виды занятий (в часах). Примерное распределение учебного времени:
№ п/п | Наименование раздела, темы | Количество часов | ||||
для специальности 010200 «Прикладная математика и информатика» | ||||||
Всего ауд. | ЛК | ПР | ЛБ | Сам. раб. | ||
1 | Производящие функции и их применение | 38 | 12 | 10 | – | 16 |
2 | Рекуррентные уравнения | 38 | 12 | 10 | – | 16 |
3 | Теория алгоритмов | 34 | 12 | 10 | – | 12 |
ИТОГО | 110 | 36 | 30 | – | 44 |
1.6.2 Содержание разделов дисциплины.
Производящие функции и их применение
Преобразование Паскаля. Треугольник Паскаля. Бином Ньютона. Формальные степенные ряды (ФСР). Алгебра отношений. Биномиальная алгебра. Композиция ФСР. Обратимость ФСР Интегрирование ФСР. Дифференцирование ФСР. Производящая функция (ПФ). Экспоненциальная ПФ. Основной принцип теории ПФ. Простейшие ПФ. Операции над ПФ: линейные, изменение масштаба, сдвиг начала, подобие, свертка. Применение ПФ к решению перечислительных задач: сочетания, сочетания с повторениями, размещения, размещения с повторениями, композиции, разбиения.
Рекуррентные уравнения
Задача Фибоначчи. Определение рекуррентного уравнения (РУ). Линейные однородные РУ с постоянными коэффициентами. Характеристическое уравнение. Линейные неоднородные РУ с постоянными коэффициентами. Пути решения линейных РУ с переменными коэффициентами.
Теория алгоритмов
Определение машины Тьюринга. Примеры машин Тьюринга. Функция, вычислимая по Тьюрингу. Эквивалентные машины Тьюринга. Универсальная машина. Тезис Чёрча — Тьюринга. Неразрешимые алгоритмические проблемы. Примитивно-рекурсивные функции. Примитивно-рекурсивные предикаты и операторы. Функции Аккермана. Общерекурсивные и частично-рекурсивные функции.
1.6.3 Темы для самостоятельного изучения.
№ п/п | Наименование раздела дисциплины. Тема. | Форма самостоятельной работы | Форма контроля выполнения самостоятельной работы | Количество часов |
1 | Производящие функции и их применение | Контрольная работа № 1 | Проверка контрольной работы | 16 |
2 | Рекуррентные уравнения | Контрольная работа № 1 | Проверка контрольной работы | 16 |
3 | Теория алгоритмов | Контрольная работа № 2 | Проверка контрольной работы | 12 |
1.7 Методические рекомендации по организации изучения дисциплины.
1.7.1 Тематика и планы практических занятий по изученному материалу
Практические занятия по теме «Производящие функции и их применение»
ПР № 1. Треугольник Паскаля. Бином Ньютона.
ПР № 2. Суммирование и его свойства. Вычисление сумм.
ПР № 3. Операции над формальными степенными рядами.
ПР № 4. Использование таблицы простейших производящих функций: нахождение производящих функций данных числовых последовательностей, восстановление числовой последовательности по данной производящей функции.
ПР № 5. Применение производящих функций для вычисления сумм и решения комбинаторных задач.
Литература
1. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. - 288 с.
2. Сборник упражнений по курсу “Дискретная математика” для практических и индивидуальных занятий по специальности 220400. /Сост. Н. Р.Ланина. Мурманск: Изд-во МГТУ, 2000. - 31 с.
Практические занятия по теме «Рекуррентные уравнения»
ПР № 6. Решение однородных линейных рекуррентных уравнений.
ПР № 7. Решение неоднородных линейных рекуррентных уравнений.
ПР № 8. Решение текстовых задач, сводимых к рекуррентным уравнениям.
ПР № 9. Контрольная работа № 1.
ПР № 10. Обсуждение результатов контрольной работы. Работа над ошибками.
Литература
1. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. - 288 с.
Практические занятия по теме «Теория алгоритмов»
ПР № 6. Машины Тьюринга.
ПР № 7. Конструирование машин Тьюринга.
ПР № 8. Примитивно-рекурсивные функции. Доказательство примитивной рекурсивности.
ПР № 14. Контрольная работа № 2.
ПР № 15. Обсуждение результатов контрольной работы. Работа над ошибками.
Литература
1. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. - 288 с.
2. А., Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: ФИЗМАТЛИТ, 2001. - 256 с.
1.8 Учебно-методическое обеспечение дисциплины.
1.8.1 Рекомендуемая литература:
Основная литература.
лекции
1. И. Алгоритмы и рекурсивные функции. - М.: Наука, 1986. - 368 с.
2. А., А. Лекции по дискретной математике. - М.: МПГУ, 1997.
3. Н. Введение в комбинаторные методы дискретной математики. М.: Наука, 1982. - 384 с.
4. В. Введение в дискретную математику: Учеб. пособие для вузов. М.: Высш. шк., 2001. - 384 с.
практические занятия
5. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. - М.: Лаборатория базовых знаний, 2001. - 288 с.
6. А., Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: ФИЗМАТЛИТ, 2001. - 256 с.
7. Сборник упражнений по курсу “Дискретная математика” для практических и индивидуальных занятий по специальности 220400. /Сост. Н. Р.Ланина. Мурманск: Изд-во МГТУ, 2000. - 31 с.
Дополнительная литература
лекции
1. Математические методы анализа алгоритмов. - М.: Мир, 1987. - 120 с.
2. Комбинаторные алгоритмы. Теория и практика. - М.: Мир, 1980. - 476 с.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)