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

Тема 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! (эн факториал) определяется следующим образом:

1.  0!=1;

2.  .

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

1.  ;

2.  при .

Если при этом , то , где .

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

Количество перестановок с повторениями обозначается и может быть вычислено по формуле:

.

Размещениями (без повторений) из n элементов по m называют упорядоченные последовательности n – элементного множества Х длиной в т элементов, состоящие из различных элементов.

Количество размещений из п элементов по т обозначают . Формула для вычислений имеет вид:

.

Размещениями с повторениями из п элементов по т называют элементы т-ой декартовой степени п-элементного множества, то есть упорядоченные последовательности длины т, в которых допускается повторение элементов.

Количество размещений с повторениями обозначается . Оно может быть вычислено по формуле:

.

Сочетанием (без повторений) из п элементов по т называется всякое т-элементное подмножество п-элементного множества с различными элементами.

Таким образом, сочетание отличается от размещения тем, что в данном случае порядок следования элементов не играет роли. Количество сочетаний обозначается и может быть вычислено следующим образом:

.

Количество сочетаний для краткости также называют просто сочетаниями. Сочетания обладают рядом важных свойств. Отметим несколько простейших, основополагающих свойств:

1°. ;

2°. Для имеем ;

3°. Для выполняется .

Совокупность этих свойств позволяет легко построить часть так называемого треугольника Паскаля, элементами которого являются сочетания: