Межпредметная связь

На материале данной дисциплины базируется теоретический материал следующих дисциплин:

· теория информационных процессов и систем;

· управление данными;

· моделирование систем;

· информационная безопасность и защита информации,

а также других дисциплин обще профессионального и специального циклов, а также специализаций, реализуемых в ГУАП.

Знания и навыки, полученные при изучении материала данной дисциплины в соответствии с учебным планом направления, имеют как самостоятельное значение, так и используются при изучении других дисциплин: «Языки и методы программирования», «Базы данных», «Операционные системы».

СТРУКТУРА И Содержание дисциплины

Распределение трудоемкости дисциплины по разделам дисциплины и видам занятий

Таблица 2.1. – Разделы дисциплины и их трудоемкость

Разделы, темы дисциплины	Лекции (час)	ПЗ (СЗ) (час)	ЛР (час)	КП (час)	СРС (час)
Семестр № 2
Раздел 1
Раздел 2
Раздел 3
Раздел 4
Раздел 5

Лекционные занятия

Таблица 2.2 Содержание разделов и тем лекционного курса

КУРС	СЕМЕСТР	Номера разделов	Наименование разделов и дидактических единиц	ВСЕГО	АУДИТОРНЫЕ	Самостоятельная работа студентов
ВСЕГО/ в том числе в интерактивной форме	Лекции	Аудиторный практикум (семинар)	Лабораторный практикум
			Лекционные занятия Раздел 1. Множества и операции над ними 1.1 Множество. Равенство множеств. Подмножество. Пустое множество, универсум. Диаграммы Эйлера-Венна. Булеан. Способы задания множеств. Основные операции над множествами. Алгебра множеств, её основные формулы. Конституенты. 1.2.Декартовы произведения множеств. Бинарные отношения. Отображения множеств. Образы, прообразы, обратные отображения, виды отображений. Функции, их свойства. Бинарные отношения специального вида. Отношения порядка. 1.3. Эквивалентность и мощность множеств. Кардинальные числа, шкала кардинальных чисел. Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства. Арифметика кардинальных чисел.		12/6		6/6
			Раздел 2. Комбинаторика. 2.1 Основные формулы комбинаторики. Выборки. Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Бином Ньютона. Свойства биномиальных коэффициентов. 2.2 Принцип включений и исключений. Формула включений и исключений. Применение принципа включений и исключений к решению некоторых комбинаторных задач. 2.3 Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей. Метод рекуррентных соотношений. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Числа Фибоначчи.		16/8		8/8
			Раздел 3. Основы теории графов. 3.1 Основные понятия теории графов Граф (орграф), его элементы. Виды графов (орграфов). Отношения между элементами графа (орграфа). Способы задания. Степень вершины. Изоморфизм. Связность. 3.2 Маршруты, пути, циклыМаршруты в графах, их виды. Цепь, цикл. Пути в орграфах, их виды. Контур. Теоремы о маршрутах и циклах. Определение экстремальных путей на графах. Выявление маршрутов с заданным количеством ребер. Метод Шимбелла. Алгоритмы Дейкстры и Беллмана - Мура построения кратчайшего пути. Задача о нахождении максимального пути на ациклических графах. Контур. Теоремы о маршрутах и циклах. Обходы графов. Фундаментальные циклы. 3.3 Деревья. Дерево (ордерево). Корневые, бинарные деревья. Теоремы о деревьях. Остовный граф. Задача об остове минимального веса. Алгоритм Прима расчета кратчайшего остова.		16/8		8/8
			Раздел 4. Планарные и хроматические графы. 4.1 Планарные графы. Укладка графа на плоскости, один из алгоритмов укладки графов. Хроматические графы. Раскраски графов. Теорема о пяти красках, история её доказательства.		12/6		6/6
			Раздел 5. Элементы сетевого планирования. 5.1. Сети, потоки в сетяхОпределения двухполюсной направленной сети, потока. Задача о максимальном потоке. Разрез. Теорема Форда-Фалкерсона. 5.2 Основные параметры сетевых графов. Критические пути, работы, резервы. Резервы для событий и работ сетевого графа. Линейные графики. 5.3. Планирование потребления ресурса. Составление расписаний при ограничениях на ресурсы.		12/6		6/6
ВСЕГО ПО ДИСЦИПЛИНЕ (БЕЗ ЭКЗАМЕНА)		68/34		34/34