Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы дискретной математики основная образовательная программа подготовки специалиста по специальности 010200 (010501) «Прикладная математика и информатика»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Мурманский государственный гуманитарный университет» (ФГБОУ ВПО «МГГУ») УТВЕРЖДАЮ: проректор по учебной работе ________________ И.А.Архип «____»____________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 с. практические занятия 3. Нефедов В.Н., Осипова В.А. Курс дискретной математики. М.: Издательство МАИ, 1992. - 264 с. 1.9 Материально-техническое обеспечение дисциплины. 1.9.1 Электронный конспект лекций 1.10 Примерные зачетные тестовые задания. Контрольная работа №1. «Производящие функции и рекуррентные уравнения» Пример одного варианта 1. Даны последовательности: 2, 3, 6, 11, 18, 27, 38, 51, ... и 6, 36, 216, 1296, ... а) Составить их ПФ a(x), b(x) и вычислить коэффициент при x3 в произведении a(x)  b(x); б) Составить их ЭПФ ae(x), be(x) и вычислить коэффициент при x2 в произведении ae(x)  be(x). 2. По данной ПФ восстановить числовую последовательность: a*(x) = (2x2 + 13x + 27) / (4 + x)3 3. Решить уравнение: f(n+4) = 2 f(n+3) + 12 f(n+2) + 14 f(n+1) + 5 f(n) при заданных начальных условиях: f(0) = 4, f(1) = 1; f(2) = 34; f(3) = 107. 4. Решить уравнение: f(n+2) = 7 f(n+1) + 18 f(n) + ( 44n  8) 2n; при заданных начальных условиях: f(0) = 11, f(1) = 0. Контрольная работа №2 «Теория алгоритмов» Пример одного варианта  1 1. Изображая на каждом такте работы машины Тьюринга получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов (в начальный момент времени машина находится в состоянии q1 и обозревает крайнюю правую ячейку, в которой записан пустой символ , в следующей слева ячейке уже записан символ 1): а) 111111, б) 111111111, в) 1111111111. 2. Доказать, что функция f(x) = x! примитивно-рекурсивна.. q1  L q2 1 E q0 q2  E q5  E q3 q3  L q4 1 E q0 q4 1 E q5 1 L q4 q5  E q0 1 L q6 q6  E q0  E q7 q7  R q8 1 E q0 q8 1 E q9 1 R q8 q9  E q0 1 L q10 q10  E q0  E q11 q11  L q12 1 E q0 q12 1 E q13 1 L q12 q13  E q0 1 E q0 1.11 Примерный перечень вопросов к зачету (экзамену). Производящие функции и их применение 1. Алгебра отношений. Биномиальная алгебра. Доказательство того факта, что обе алгебры являются целостными кольцами 2. Формальные степенные ряды (ФСР). Композиция ФСР. Условие, при котором осуществима композиция (с доказательством) 3. Формальные степенные ряды (ФСР). Обратимость ФСР. Условие существования обратного ряда (с доказательством) 4. Формальные степенные ряды (ФСР). Интегрирование и дифференцирование ФСР (с доказательством любых двух свойств). 5. Производящая функция (ПФ). Экспоненциальная ПФ. Основной принцип теории ПФ. 6. Операции над ПФ: линейные, изменение масштаба, сдвиг начала, подобие, свёртка (с доказательством). 7. Применение ПФ к решению перечислительных задач: сочетания, сочетания с повторениями, размещения, размещения с повторениями. 8. Применение ПФ к решению перечислительных задач: композиции, разбиения. Рекуррентные уравнения 9. Рекуррентные уравнения. Основные определения. Задача Фибоначчи. 10. Линейные рекуррентные уравнения с постоянными коэффициентами. Теорема о виде общего решения (с доказательством). 11. Однородные линейные рекуррентные уравнения с постоянными коэффициентами. Теорема об общем решении (с доказательством). 12. Пути решения нелинейных рекуррентных уравнений. Теория алгоритмов 13. Определение машины Тьюринга, ее четыре составные части: лента, читающая головка, алфавиты и множество команд. 14. Конструирование машин Тьюринга на примере машины, стирающей последний символ исходного слова и машины, дописывающей три единицы к исходному слову. 15. Проблема остановки машины Тьюринга (с доказательством). 16. Тезис Черча-Тьюринга, его научный “статус” и применение в теории алгоритмов. 17. Проблема распознавания нетривиального инвариантного свойства машины Тьюринга (с доказательством). 18. Эквивалентные машины Тьюринга. Примеры эквивалентных машин. 19. Оператор суперпозиции. Оператор примитивной рекурсии. Определение примитивно-рекурсивной функции. 20. Примеры построения примитивно-рекурсивных функций. 21. Примитивно-рекурсивные операторы. Ограниченный оператор минимизации. Оператор обращения. 22. Функции Аккермана и их свойства. 23. Доказательство того факта, что функция Аккермана не является примитивно-рекурсивной. 24. Общерекурсивные и частично-рекурсивные функции. 1.12 Комплект экзаменационных билетов. Билет № 1. 1. Теорема о целостных кольцах. 2. Функция Аккермана и её свойства. Билет № 2. 1. Композиция формальных степенных рядов. Условие существования композиции. 2. Неразрешимая алгоритмическая проблема  проблема распознавания нетривиального инвариантного свойства. Билет № 3. 1. Обратимость формальных степенных рядов. Условие существования обратного ряда. 2. Теорема о том, что функция Аккермана не является примитивно-рекурсивной. Билет № 4. 1. Вывод формулы дифференцирования произведения формальных степенных рядов. 2. Ограниченный и неограниченный оператор минимизации. Оператор обращения. Частично-рекурсивные и общерекурсивные функции. Билет № 5. 1. Шесть операций над производящими функциями, соответствующих операциями над числовыми последовательностями. 2. Неразрешимая алгоритмическая проблема  проблема остановки. Билет № 6. 1. Производящие функции числа сочетаний, сочетаний с повторениями. Число сочетаний с повторениями без ограничения на кратность элементов. 2. Схема примитивной рекурсии. Примитивно-рекурсивные функции: определение, примеры (с доказательством примитивной рекурсивности). Билет № 7. 1. Экспоненциальные производящие функции числа размещений, размещений с повторениями. Число размещений с повторениями без ограничения на кратность элементов. 2. Теорема о том, что функция Аккермана не является примитивно-рекурсивной. Билет № 8. 1. Производящие функции числа композиций (на m частей, на произвольное количество частей). 2. Функция Аккермана и её свойства. Билет № 9. 1. Производящие функции числа разбиений на m частей. Число решений в целых неотрицательных числах уравнения x1 + 2x2 + 3x3 + ... + mxm = k. 2. Неразрешимая алгоритмическая проблема  проблема распознавания нетривиального инвариантного свойства. Билет № 10. 1. Теорема об общем виде решения линейного рекуррентного соотношения с постоянными коэффициентами. 2. Машина Тьюринга. Примеры машин Тьюринга. Функция, вычислимая по Тьюрингу. Тезис Чёрча-Тьюринга. Билет № 11. 1. Лемма о нулях многочлена Pm(x) = i (ki)m xki. 2. Ограниченный и неограниченный оператор минимизации. Оператор обращения. Частично-рекурсивные и общерекурсивные функции. Билет № 12. 1. Основная теорема об линейных однородных рекуррентных соотношениях: 1  2 (если an  решение ... , то ее производящая функция представима в виде ...). 2. Неразрешимая алгоритмическая проблема  проблема остановки. Билет № 13. 1. Основная теорема об линейных однородных рекуррентных соотношениях: 2  3 (если производящая функция представима в виде ... , то an представима в виде ...). 2. Схема примитивной рекурсии. Примитивно-рекурсивные функции: определение, примеры (с доказательством примитивной рекурсивности). Билет № 14. 1. Основная теорема об линейных однородных рекуррентных соотношениях: 3  1 (если an представима в виде ... , то an  решение ... ). 2. Машина Тьюринга. Примеры машин Тьюринга. Функция, вычислимая по Тьюрингу. Тезис Чёрча-Тьюринга. 1.13 Примерная тематика рефератов. Треугольник Паскаля и его свойства. Последовательность Фибоначчи и её свойства. Универсальная машина Тьюринга и способ ее построения. 1.14 Примерная тематика курсовых работ. Свойства интегралов для формальных степенных рядов. Решение рекуррентных уравнений путём сведения их к дифференциальным уравнениям. Подходы к решению нелинейных рекуррентных уравнений. Примитивная рекурсивность функции, перечисляющей по порядку числа Фибоначчи. Примерная тематика квалификационных (дипломных) работ. не предусмотрено учебным планом по данной дисциплине. Методика(и) исследования (если есть) - нет. Бально-рейтинговая система, используемая преподавателем для оценивания знаний студентов по данной дисциплине. Используется пятибалльная система оценивания знаний студентов.

Похожие:

	Учебно-методический комплекс дисциплины опд. В. 4 Математические... Целями изучения дисциплины являются: формирование профессиональных навыков по изучению, анализу и оптимизации экономических процессов...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Учебно-методический комплекс дисциплины дс компьютерные сети и системы... Рецензенты: кандидат физико-математических наук, доцент Маренич А. С., кандидат технических наук, доцент Ланина Н. Р		Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 10, Опд. Ф. 12, Опд.... А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета...		Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. В 2 опд. В 1 Современный... Педагогика и методика начального образования со специализацией «Обучение информатике в начальной школе»		Учебно-методический комплекс гсэ. В 1 история математической науки... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна
	Учебно-методический комплекс фтд: универсальная алгебра основная... ...		Учебно-методический комплекс дисциплины опд. Ф. 8 Религиоведение... Пащенко Л. В., к ф н., старший преподаватель кафедры связей с общественностью и лингвистики мгту
	Учебно-методический комплекс дисциплины математическая логика Основная... Автор программы: Шиманский Сергей Александрович, ст преподаватель кафедры информатики и отд		Учебно-методический комплекс дисциплины опд. Ф. 4 История религии... ...
	Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 2 Геоморфология основная... Цель дисциплины. В соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности...