Дискретная математика (стр. 4 )

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

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

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

Опишем способ решения этого соотношения.

1 шаг. Составить и решить характеристическое уравнение, соответствующее исходному разностному уравнению. Это уравнение , то есть обычное квадратичное уравнение. Пусть его корни и .

2 шаг. Составление общего решения исходного разностного уравнения. Этот вид зависит от корней характеристического уравнения.

·  Если и , то общее решение исходного уравнения имеет вид: , где и ‑ произвольные постоянные;

·  Если и , то общее решение исходного уравнения следует искать в виде ;

·  Если , то есть корни комплексные, то, как известно, они будут сопряженными комплексными числами. Пусть тригонометрическая форма записи одного из этих корней имеет вид . Тогда общее решение разностного уравнения можно искать в виде .

3 шаг. Определение значений констант из общего решения за счет использования начальных условий. Нужно составить систему двух уравнений приравнивая выражение для общего решения при п=0 значению и при п=1 значению . Решив систему нужно полученные значения констант подставить в общее решение, что и даст искомый ответ.

Пример (последовательность Фибоначчи). Последовательность задана рекуррентным соотношением и начальными условиями следующим образом: Решить рекуррентное соотношение.

Решение:

Перепишем соотношение в стандартном виде и запишем для него характеристическое уравнение . Его корнями являются числа и . Это различные вещественные числа, поэтому общее решение будет иметь вид:

.

Используем начальные условия;

.

Из последней системы легко находим решение:

откуда получаем искомое решение разностного уравнения в виде

.

Последняя формула общего члена последовательности Фибоначчи известна под названием формулы Бине.

Задания для решения

Решите следующие рекуррентные соотношения:

1. 

2. 

7. Темы лабораторных работ (Лабораторный практикум)

Лабораторные работы не предусмотрены учебным планом

8. Примерная тематика курсовых работ (если они предусмотрены учебным планом ОП).

Курсовые работы не предусмотрены учебным планом

9. Учебно-методическое обеспечение и планирование самостоятельной работы студентов.

Таблица5

№	Модули и темы	Виды СРС	Неделя семестра	Объем часов	Кол-во баллов
обязательные	дополнительные
1	2	3	4	5	6	7
Модуль 1. Комбинаторика
1.1	Основные комбинаторные схемы	Выполнение домашних заданий, решение контрольных работ	Компьютерное тестирование		10	0-15
1.2	Бином Ньютона и его следствия	Выполнение домашних заданий, решение контрольных работ	Компьютерное тестирование		10	0-15
	Всего				20	0-30
Модуль 2. Рекурсивно определяемые объекты
2.1.	Рекуррентные соотношения	Выполнение домашних заданий, решение контрольных работ	тестирование		7	0-10
2.2.	Замечательные числовые множества	Выполнение домашних заданий, решение контрольных работ	тестирование		7	0-10
2.3.	Производящие функции	Выполнение домашних заданий, решение контрольных работ	тестирование		8	0-10
	Всего				22	0-30
Модуль 3. Элементы теории графов
3.1.	Основы теории графов	Выполнение домашних заданий, решение контрольных работ	собеседование		7	0-10
3.2.	Эйлеровы и гамильтоновы графы	Выполнение домашних заданий, решение контрольных работ	собеседование		7	0-15
3.3.	Оптимизационные алгоритмы на графах	Выполнение домашних заданий, решение контрольных работ	собеседование		8	0-15
	Всего				22	0-40
	Итого				64	0-100

При дистанционной форме оценка производится по результатам выполнения контрольной работы

10.Фонд оценочных средств для проведения промежуточной аттестации по итогам освоения дисциплины (модуля).

10.1 Перечень компетенций с указанием этапов их формирования в процессе освоения образовательной программы (выдержка из матрицы компетенций):

Циклы, дисциплины (модули) учебного плана ОП
5 семестр
Индекс компетенции	Дискретная математика
Общекультурные компетенции	Код компетенции
ОК-3	Основы математической обработки информации Естественнонаучная картина мира Информационные технологии Безопасность жизнедеятельности Возрастная анатомия, физиология и гигиена Численные методы Архитектура компьютера и микроэлектроника Теоретические основы информатики Математика Дифференциальное и интегральное исчисление Программирование Исследование операций Элементы абстрактной и компьютерной алгебры Дискретная математика Информационные системы Математическая логика Теория вероятностей и математическая статистика Уравнения математической физики Психолого-педагогические технологии в образовательном процессе школы Современные образовательные технологии Современные средства оценивания результатов обучения Бизнес-информатика Информатика в экономике Математические основы информатики Научные основы школьного курса информатики Физические основы работы компьютера Основы работы современной техники Информационные и коммуникационные технологии в учебном процессе Использование современных информационных и коммуникационных технологий в учебном процессе Учебная практика Педагогическая практика
ПК-4	Методика обучения и воспитания (по профилю подготовки) Численные методы Архитектура компьютера и микроэлектроника Теоретические основы информатики Основы исследований в образовании Программное обеспечение электронно-вычислительных машин Дифференциальное и интегральное исчисление Программирование Исследование операций Элементы абстрактной и компьютерной алгебры Дискретная математика Информационные системы Математическая логика Практикум решения задач на электронно-вычислительных машинах Теория вероятностей и математическая статистика Физика Основы искусственного интеллекта Подготовка учащихся к единому государственному экзамену по информатике Внеклассная работа по информатике Компьютерные сети, Интернет, мультимедиа Информационные сетевые технологии Основы компьютерной безопасности Основы программирования Элементы офисных технологий в приложении к процессу обучения Формирование приёмов методической деятельности учителя информатики Основы создания веб-сайтов и электронных учебников Физические основы работы компьютера Основы работы современной техники Информационные и коммуникационные технологии в учебном процессе Использование современных информационных и коммуникационных технологий в учебном процессе Практикум на электронно-вычислительной машине Государственная итоговая аттестация

10.2 Описание показателей и критериев оценивания компетенций на различных этапах их формирования, описание шкал оценивания: