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

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

Решение:

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

.

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

.

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

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

.

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

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

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

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);

‑ способностью к самоорганизации и самообразованию (ОК – 6).

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

Таблица 6

Карта критериев оценивания компетенций

Код компетенции	Критерии в соответствии с уровнем освоения ОП	Виды занятий (лекции, семинарские, практические, лабораторные)	Оценочные средства (тесты, творческие работы, проекты и др.)
пороговый (удовл.) 61-75 баллов	базовый (хор.) 76-90 баллов	повышенный (отл.) 91-100 баллов
ОК – 3, ОК - 6	Знает: Формулы подсчета числа комбинаций стандартного вида; формулу бинома Ньютона; основные понятия теории графов	Знает: Основные понятия комбинаторики, бином Ньютона, метод решения линейных разностных уравнений, основные понятия теории графов	Знает: Понятия и формулы комбинаторики, бином Ньютона, методы решения рекуррентных соотношений, понятия теории графов и методы решения задач	Лекции, практические занятия	Домашние задания, контрольные работы, тесты, зачет
Умеет: Решать простейшие комбинаторные задачи, пользоваться формулой бинома Ньютона, решать однородные разностные уравнения, решать задачи на эйлеровость графа и нахождение кратчайших маршрутов.	Умеет: Решать комбинаторные задачи, решать разностные уравнения решать простейшие оптимизационные задачи на графах	Умеет: Решать комбинаторные задачи и задачи на бином Ньютона, решать различные рекуррентные соотношения, пользоваться производящими функциями, решать оптимизационные задачи на графах	Лекции, практические занятия	Домашние задания, контрольные работы, тесты, зачет
Владеет: Простейшими навыками использования метода полной математической индукции	Владеет: Методом математической индукции, навыками решения линейных разностных уравнений	Владеет: Методом математической индукции, навыками решения линейных разностных уравнений, навыками решения школьных олимпиадных задач	Лекции, практические занятия	Домашние задания, контрольные работы, тесты, зачет

10.3 Типовые контрольные задания или иные материалы, необходимые для оценки знаний, умений, навыков и (или) опыта деятельности, характеризующей этапы формирования компетенций в процессе освоения образовательной программы.

Вопросы для промежуточной аттестации

Основные правила комбинаторики Стандартные комбинации и формулы для подсчета их количества Перестановки без повторений и с повторениями Размещения без повторений и с повторениями Сочетания без повторений и с повторениями Простейшие свойства числа сочетаний. Треугольник Паскаля Бином Ньютона Бином Ньютона (а=1, b=1). Теорема Кантора и логика Бином Ньютона (а=1, b=‑1; n=m+s). Свойства сочетаний Бином Ньютона и тригонометрия (а=1, b=i) Бином Ньютона и тригонометрия Формула Тейлора и бином Ньютона Понятие о рекуррентных соотношениях Метод математической индукции как метод решения рекуррентных соотношений Метод подстановки (итерационный) для решения рекуррентных соотношений Использование конечных разностей для решения рекуррентных соотношений со стабилизирующимися конечными разностями Элементы теории разностных уравнений Числа Фибоначчи и их свойства Субфакториалы Числа Стирлинга первого и второго рода Понятие производящей функции Кольцо формальных степенных рядов Общее представление о графах Планарные графы Связные графы Эйлеровы графы Гамильтоновы графы Алгоритм Дейкстры Расположение охранного пункта в сети Расположение сервисного пункта в сети Максимизация потока в сети Максимизация паросочетаний в двудольных графах Алгоритм построения остовного дерева

10.4 Методические материалы, определяющие процедуры оценивания знаний, умений, навыков и (или) опыта деятельности характеризующих этапы формирования компетенций.

Оценивание отдельных контрольных точек учебного процесса осуществляется по технологии рейтинговой оценки с использованием идеи сведения многокритериальной оптимизационной задачи к однокритериальной за счет декомпозиции контрольной точки (естественное разложение по заданиям) с использованием весовых коэффициентов, учитывающих важность задания в комплексной подготовке профессионального учителя математики и информатики.

11. Образовательные технологии.

Используются: работа в малых группах (решение тренировочных вариантов, подготовка справочного материала), индивидуальная работа (тесты, контрольные работы), взаимопроверка выполненных заданий.