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

4. Виды и формы оценочных средств в период текущего контроля

Таблица 4

№ Темы	Устный опрос	Письменные работы	Технические формы контроля	Информациионные системы и технологии	Итого количество баллов
коллоквиумы	собеседование	ответ на семинаре	лабораторная работа	контрольная работа	тест	реферат	эссе	программы компьютерного тестирования	комплексные ситуационные задания	электронные практикумы	другие формы
Модуль 1. Комбинаторика
1.1					0-8				0-7				0-15
1.2					0-8				0-7				0-15
Всего					0-16				0-14				0-30
Модуль 2. Рекурсивно определяемые объекты
2.1					0-6	0-4							0-10
2.2					0-6	0-4							0-10
2.3					0-6	0-4							0-10
Всего					0-18	0-12							0-30
Модуль 3. Элементы теории графов
3.1		0-2			0-8								0-10
3.2		0-3			0-12								0-15
3.3		0-3			0-12								0-15
Всего		0-8			0-32								0-40
Итого		0-8			0-66	0-12			0-14				0-100

5. Содержание дисциплины

Модуль 1. Комбинаторика

Тема 1.1. Основные комбинаторные схемы

Предмет дискретной математики. Метод математической индукции. Основные правила комбинаторики. Перестановки и перестановки с повторениями. Размещения и размещения с повторениями. Сочетания и сочетания с повторениями. Простейшие свойства числа сочетаний, треугольник Паскаля.

Тема 1.2. Бином Ньютона и его следствия

Бином Ньютона. Бином Ньютона и логические операции. Количество элементов булеана. Суммы сочетаний. Тригонометрические формулы для углов кратных . Тригонометрические формулы для синуса и косинуса кратных углов. Формула Тейлора и бином Ньютона.

Модуль 2. Рекурсивно определяемые объекты

Тема 2.1. Рекуррентные соотношения

Понятие рекуррентного соотношения. Решение итерационным методом (метод подстановки). Рекурсивные способы. Метод полной математической индукции как эвристический метод решения рекуррентных соотношений. Конечные разности. Разностные уравнения. Конечные разности и многочлены. Решение линейных разностных уравнений.

Тема 2.2. Замечательные числовые множества

Числа Фибоначчи и их свойства. Субфакториалы. Числа Стирлинга второго и первого рода. Числа Каталана. Меандры.

Тема 2.3. Производящие функции

Понятие формального степенного ряда. Операции над формальными степенными рядами. Кольцо формальных степенных рядов. Производящая функция рекуррентной числовой последовательности. Нахождение рекуррентной последовательности по формальному степенному ряду. Примеры применения производящих функций.

Модуль 3. Элементы теории графов

Тема 3.1. Основы теории графов

Определения. Формы представления графов. Некоторые общие утверждения о конечных графах. Планарные графы. Теорема Понтрягина-Куратовского. Укладка графа на плоскости и на сфере. Теорема Эйлера. Раскраска графов. Хроматическое число графа.

Тема 3.2. Эйлеровы и гамильтоновы графы

Понятие об эйлеровых графах. Эйлеровы цепи и циклы. Критерий эйлеровости. Понятие о гамильтоновых графах. Некоторые достаточные условия гамильтоновости.

Тема 3.3. Оптимизационные алгоритмы на графах

Алгоритм Дейкстры. Алгоритм нахождения оптимального расположения охранного пункта в дорожной сети. Максимизация потока в сети. Максимизация паросочетаний в двудольном графе. Алгоритм построения минимального остовного дерева связного графа.

6. Планы семинарских занятий

Укажем тематику и обобщенные типы задач, выносимых на практику.

Занятия по теме 1.1. Основные виды комбинаций, их количество и взаимосвязь. Функциональная интерпретация основных комбинаторных схем.

Занятия по теме 1.2. Тригонометрическая и показательная форма записи комплексных чисел. Формула Муавра. Схема Горнера. Вычисление вероятностей с использованием бинома Ньютона. Практическая отработка навыков применения бинома Ньютона.

Занятия по теме 2.1. Решение задач олимпиадного типа методом составления рекуррентных соотношений (своеобразный метод обобщения ситуации). Например: "В углу шахматной доски (левый нижний) стоит король. За каждый ход ему разрешается переместиться либо на клетку вправо, либо на клетку вверх, либо на клетку по диагонали вправо-вверх. Сколькими различными путями он сможет попасть на поле g7, если ему запрещено заходить на клетку d4?"

Занятия по теме 2.2. Решение задач, связанных с использованием чисел и свойств замечательных числовых множеств (Фибоначчи, субфакториалы, Каталана, Стирлинга и т. д.).

Занятия по теме 2.3. Отработка практических навыков работы с производящими функциями. Решение задач с применением производящих функций.

Занятия по теме 3.1 и 3.2. Освоение практических способов матричного описания конечных графов с использованием различных матриц. Решение задач с использованием графов. Определение вида графа.

Занятие по теме 3.3. Решение задач с применением классических оптимизационных алгоритмов (нахождение кратчайших маршрутов, нахождение оптимального положения сервисного или охранного пункта, максимизация потока в сети и т. д.)

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

ТЕМА 1
Комбинаторика

Общие указания: Повторите основные понятия комбинаторики (дисциплина "Теория вероятностей"), решите предложенные задания и вышлите для проверки текстовым файлом (документ Word'а).

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

1.  ;

2.  при

то количество элементов в Х равно сумме количеств элементов в подмножествах разбиения, то есть

,

где ‑ обозначение для количества элементов в конечном множестве А.

Обобщенное правило произведения: Пусть рассматриваются упорядоченные последовательности элементов

,

причем:

·  элемент можно выбрать способами;

·  элемент при условии, что уже выбран, можно выбрать способами;

·  …;

·  при условии, что все предыдущие уже выбраны, можно выбрать способами.

Тогда общее количество K способов образования различных упорядоченных последовательностей рассматриваемого вида можно найти из соотношения:

.

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

Количество перестановок элементов множества обозначается , где n – количество элементов в X. Расчетная формула:

Здесь n! (эн факториал) определяется следующим образом: