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

По окончанию курса студент должен обладать следующими профессиональными компетенциями (ПК) в сфере научной и научно-исследовательской деятельности:

ПК-3. Способностью демонстрации общенаучных базовых знаний естественных наук, математики и информатики, понимание основных фактов, концепций, принципов теорий, связанных с прикладной математикой и информатикой.

ПК-7. Способностью собирать, обрабатывать и интерпретировать данные современных научных исследований, необходимые для формирования выводов по соответствующим научным, профессиональным, социальным и этическим проблемам.

СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

Общая трудоемкость дисциплины составляет ___3(только у меня) ___ зачетных единиц, ___ 216 ___ часов.

Самостоятельная работа студентов

Повторение теоретического материала

Выполнение домашнего задания

№ модуль	Наименование модуля дисциплины	Недели	Виды учебной деятельности, включая самостоятельную работу студентов и трудоемкость (в часах)	Текущий контроль успеваемости (неделя, форма)	Аттестация раздела (неделя, форма)	Максимальный балл за раздел
Лекции	Практические занятия	Самостоятельная работа студента
1.	Раздел Б2.В2.Р1. Комбинаторика	1-7			21 14 4 1	ПЗ (еженед) ДЗ(еженед) ТДЗ(3-7 нед) КТР(4-нед) Кл (8 нед)	АР(8 нед)
2.	Раздел Б2.В2.Р2. Теория графов	8-16			17 8 4 1	ПЗ (еженед) ДЗ(еженед) ТДЗ(8-10 –нед) КТР(13-нед)	АР(14 нед)
	Экзамен (по Разделу Б2.В2.Р2. Теория графов)	0-30
	Итого за семестр

Раздел Б2.В2.Р1. Комбинаторика

Лекции.

Лекция 1. Вводная лекция.

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

Лекция 2. Виды выборок.

Понятие выборки. Упорядоченные выборки. Теорема о числе упорядоченных выборок без повторений. Теорема о числе упорядоченных выборок с повторениями. Неупорядоченные выборки. Теорема о числе неупорядоченных выборок без повторений. Теорема о числе неупорядоченных выборок без повторений. Метод Эйлера.

Лекция 3. Комбинаторные задачи о покрытиях, укладках, разбиениях. Теорема о числе разбиений элементов множества на 2, 3, …, k классов, без учета их порядка в классах и без ограничений на занятость класса. Теорема о числе разбиений элементов множества на 2, 3, …, k классов, с учетом их порядка в классах и без ограничений на занятость класса.

Лекция 4. Интерпретация комбинаторных операций.

Интерпретация комбинаторных операций выборки и упорядочивания как отображения множеств. Теорема о числе различных отображений N в K. Условие существования взаимно-однозначных отображений. Условия существования отображения N на K. Теорема о числе взаимно-однозначных отображений N на K. Биективные отображения.

Лекция 5. Подстановки. Принцип включения и исключения.

Понятие подстановки. Тип (класс) подстановки. Теорема о числе подстановок заданного типа. Способы представления подстановки. Геометрический способ представления подстановки. Число бинарных деревьев с n вершинами. Принцип включения и исключения. Теорема о числе элементов, не обладающих ни одним из указанных свойств (вес каждого элемента равен единице). Теорема о сумме весов элементов, не обладающих ни одним из заданных свойств. Теорема о числе элементов, обладающих в точности r-свойствами из N–множества свойств.

Лекция 6. Беспорядки. Перестановки. Рекуррентные формулы.

Задача о беспорядках. Теорема о числе беспорядков из элементов n–множества. Функция Эйлера. Функция Мебиуса. Теорема о числе перестановок элементов n–множества, в которых r остаются на своих местах. Теорема о числе сочетаний с повторениями. Теорема о числе способов выбора k-элементов, среди которых нет двух соседних, из n элементов, расположенных в ряд. Теорема о числе способов выбора k-элементов, никакие два из которых не являются соседними, из n элементов, расположенных в круг. Рекуррентные формулы.

Лекция 7. Производящие функции. Комбинаторные числа.

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

Практические занятия.

1. Правило суммы и правило произведения.

2. Комбинаторные задачи на упорядоченные и неупорядоченные выборки.

3. Задачи о покрытиях, укладках и разбиениях.

4. Подстановки.

5. Принцип включения и исключения.

6. Задачи о беспорядках. Перестановки. Рекуррентные формулы.

7. Производящие функции. Комбинаторные числа.