Программа (стр. 2 )

ПК-13 глубокое понимание сути точности фундаментального знания

ПК-14 владение навыками контекстной обработки информации

ПК-16 выделение главных смысловых аспектов в доказательствах

ПК-19 владение методом алгоритмического моделирования при анализе постановок математических задач

ПК-20 владение методами математического и алгоритмического моделирования при анализе и решении прикладных и инженерно-технических проблем

ПК-21 владение проблемно-задачной формой представления математических и естественно-научных знаний

ПК-22 умение увидеть прикладной аспект в решении научной задачи, грамотно представить и интерпретировать результат

ПК-23 умение проанализировать результат и скорректировать математическую модель, лежащую в основе задачи

ПК-24 владение методами алгоритмического моделирования при анализе управленческих задач в научно-технической сфере, а также в экономике, бизнесе и гуманитарных областях знаний

ПК-27 умение точно представить математические знания в устной форме

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

В результате изучения дисциплины «Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках» студент должен:

Знать:

·  концепции дисциплин: Дискретная математика, Математическая логика и теория алгоритмов;

·  обладать фундаментальной подготовкой в области фундаментальной математики и компьютерных наук, готовность к использованию полученных знаний в профессиональной деятельности.

Уметь:

·  использовать основные законы теоретического исследования; решать прикладные задачи по дисциплине «Дискретная математика, математическая логика и их приложения в информатике и компьютерных науках»;

·  определять общие формы, закономерности, инструментальные средства отдельной предметной области;

·  на основе анализа увидеть и корректно сформулировать результат;

·  проанализировать результат и скорректировать математическую модель, лежащую в основе задачи;

·  грамотно пользоваться языком предметной области;

·  самостоятельно увидеть следствия сформулированного результата.

Владеть:

·  способностью к анализу и синтезу информации, полученной из любых источников;

·  способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат;

·  базовыми математическими знаниями и информационными технологиями.

4. Объем дисциплины и виды учебной работы

Общая трудоемкость дисциплины составляет ____12_______ зачетных единиц.

Вид учебной работы	Всего часов	Семестры
		1	2	3
Аудиторные занятия (всего)	216	72	72	72	-
В том числе:					-
Лекции	108	36	36	36	-
Практические занятия (ПЗ)	-	-	-	-	-
Семинары (С)	-	-	-	-	-
Лабораторные работы (ЛР)	108	36	36	36	-
Самостоятельная работа (всего)	216	72	72	72	-
В том числе:	-	-	-	-	-
Курсовой проект (работа)	-	-	-	-	-
Расчетно-графические работы	-	-	-	-	-
Реферат	-	-	-	-	-
Другие виды самостоятельной работы	-	-	-	-	-
Самостоятельная проработка дополнительного материала	216	72	72	72	-
Вид промежуточной аттестации (зачет, экзамен)		экз	экз	экз	-
Общая трудоемкость час зач. ед.	432	144	144	144	-
	12	4	4	4	-

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

5.1. Содержание разделов дисциплины

№ п/п	Наименование раздела дисциплины	Содержание раздела
1.	Введение в комбинаторику. Правило суммы и правило произведения.	Области применения комбинаторики. Основные определения теории множеств. Определение множества, мощности множества, прямого произведения множеств. Правило суммы и правило произведения множеств.
2.	Перестановки и сочетания. Мультимножества. Биномиальные коэффициенты.	Выборка объема r из n элементов, типы выборок. Определение: размещение, размещение с повторением, сочетание, сочетание с повторением, перестановка, мультимножество. Формула для вычисления различных перестановок элементов мультимножества. Доказательство основных тождеств, связанных с числом сочетаний (сумма, произведение). Общее определение биномиального коэффициента. Биномиальный коэффициент в факториальной форме. Биномиальная теорема. Произведение биномиальных коэффициентов. Доказательство основных свойств биномиальных коэффициентов. Полиномиальная теорема.
3.	Треугольник Паскаля. Разбиения множеств. Числа Стирлинга первого и второго рода.	Свойство шестиугольника треугольника Паскаля. Упорядоченные разбиения множества. Неупорядоченные разбиения множества. Разбиения чисел. Числа Стирлинга первого и второго рода. Доказательство формул для вычисления чисел Стирлинга первого и второго рода. Числа Белла. Рекуррентное соотношение для вычисления чисел Белла. Беззнаковые числа Стирлинга I рода. Свойства беззнаковых чисел Стирлинга I рода. Формула для вычисления беззнаковых чисел Стирлинга I рода.
4.	Принцип включения и исключения	Формула обращения. Задача о беспорядках. Задача о встречах. Формула для вычисления числа предметов, обладающих ровно n свойствами. Формула для вычисления числа предметов, обладающих не менее, чем k свойствами.
5.	Производящие функции. Схемы выбора.	Определение и свойства. Идея метода производящих функций. Линейные операции с производящими функциями. Сдвиг начала влево и сдвиг начала вправо. Частичные суммы и дополнительные частичные суммы. Изменение масштаба. Свёртка. Вычисление производящих функций для последовательностей. Свойства класса ПФ. Экспоненциальная ПФ. ПФ для (n, r) сочетаний с ограниченным числом повторений. ПФ для (n, r) сочетаний с неограниченным числом повторений.
6.	Однородные и неоднородные линейные рекуррентные соотношения	Однородные линейные рекуррентные соотношения. Неоднородные линейные рекуррентные соотношения. Метод решения однородных линейных рекуррентных соотношений. Доказательство 4-х положений для нахождения общих решений рекуррентных соотношений. Решение неоднородных линейных рекуррентных соотношений.
7.	Поиск с возвращением. Генерация перестановок и сочетаний	Поиск с возвращением. Использование исчерпывающего поиска. Задача прохождения лабиринта. Общий алгоритм поиска с возвращением. Дерево полного прохода алгоритма. Процедура поиска с возвращением. Оценка сложности алгоритма. Порождение перестановок. Генерация сочетаний.
8.	Введение в алгебру логики	Прямое произведение множеств. Соответствия и функции. Алгебры. Функции алгебры логики. Суперпозиции и формулы. Булева Алгебра. Принцип двойственности. Совершенная дизъюнктивная нормальная форма (СДНФ). Совершенная конъюнктивная нормальная форма (СКНФ). Разложение булевых функций по переменным. Построение СДНФ для функции, заданной таблично.
9.	Минимизация булевых функций	Проблема минимизации. Порождение простых импликантов. Алгоритм Куайна и Мак-Клоски. Таблицы простых импликантов.
10.	Полнота и замкнутость систем логических функций	Замкнутые классы. Класс логических функций, сохраняющий константы 0 и 1. Определение и доказательство замкнутости. Класс самодвойственных функций. Определение и лемма о несамодвойственной функции. Класс монотонных функций. Определение и лемма о немонотонной функции. Класс линейных функций. Определение и лемма о нелинейной функции.
11.	Исчисление высказываний и предикатов	Общие принципы построения формальной теории. Интерпретация, общезначимость, противоречивость, логическое следствие. Метод резолюций для исчисления высказываний. Понятие предиката. Кванторы. Алфавит. Предваренная нормальная форма. Алгоритм преобразования формул в предваренную нормальную форму. Скулемовская стандартная форма. Подстановка и унификация. Алгоритм унификации. Метод резолюций в исчислении предикатов.
12.	Элементы теории графов	Введение в теорию графов: основные понятия и определения. Матричные представления графов. Маршруты, цепи, циклы. Нахождение связных компонент. Метрические характеристики графов. Подграфы. Операции над графами. Двудольные графы. Поиск в ширину. Деревья. Эйлеровы графы. Гамильтоновы графы. Эйлеровы пути и циклы. Гамильтоновы пути и циклы. Связь между наличием в связном графе гамильтоновых циклов и длиной максимальных простых путей в нем. Нахождение кратчайших путей в ориентированном графе.
13.	Алгоритмы на графах	Алгоритм Краскала. Алгоритм Прима. Алгоритм Дейкстры. Алгоритм нахождения эйлерова цикла в графе. Алгоритм построения кратчайшего пути от фиксированной вершины до всех остальных вершин в ориентированном графе, случай неотрицательных весов ребер.
14.	Потоки в сетях	Прикладные модели и задачи, примеры применения методов теории графов. Оценки структурных компонент графа. Задача о максимальном потоке и о минимальном разрезе в сети. Максимальный поток в транспортной сети. Задача на нахождение «узких» мест в сети. Задача о потоке минимальной стоимости.

5.2 Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами