Дискретная математика (стр. 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 Перечень компетенций с указанием этапов их формирования в процессе освоения образовательной программы (выдержка из матрицы компетенций):

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

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