И «информационные и управляющие системы»

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ

Дискретная математика

Направление/ специальность подготовки

09.03.02 Информационные системы и технологии

Специализация/про-филь/программа подготовки

Информационно-управляющие системы

Уровень высшего образования

бакалавриат

Форма обучения

очная

Факультет

И «ИНФОРМАЦИОННЫЕ И УПРАВЛЯЮЩИЕ СИСТЕМЫ»

Выпускающая кафедра

И9 Систем управления и компьютерных технологий

Кафедра-разработчик

 рабочей программы

О6 Высшая математика

 

КУРС

Семестр

ОБЩАЯ ТРУДОЁМКОСТЬ (ЗАЧЕТНЫХ ЕДИНИЦ)

ЧАСЫ (по наличию видов занятий)

Вид промежуточного контроля

 

ОБЩАЯ

ТРУДОЁМКОСТЬ

АУДИТОРНЫЕ ЗАНЯТИЯ

САМОСТОЯТЕЛЬНАЯ РАБОТА

 

ВСЕГО

ЛЕКЦИИ

ЛАБОРАТОРНЫЙ ПРАКТИКУМ

АУДИТОРНЫЙ

ПРАКТИКУМ

Другие виды

занятий

ВСЕГО

КУРСОВОЙ

ПРОЕКТ

КУРСОВАЯ

РАБОТА

Расчётно - граф.

работа

РЕФЕРАТ

Другие виды

самост. работы

 

ПРАКТИЧЕСКИЕ Занятия

СЕМИНАРЫ   1 2 5

180

68

34  

34

    112     112    

Диф. зачёт

 

ИТОГО

5

180

68

34  

34

    112     112    

Диф.зачёт

                                               

 

Начальник отдела основных образовательных программ

_____________/Русина А.А.

«____» ___________2018

САНКТ – ПЕТЕРБУРГ

2018

ЛИСТ СОГЛАСОВАНИЯ

Рабочая программа составлена в соответствии с требованиями Федерального Государственного Образовательного Стандарта ВЫСШЕГО ОБРАЗОВАНИЯ (ФГОС ВО) для направлений: 09.03.02 Информационные системы и технологии

Программу составили:

кафедра_________ О6 Высшая математика______________________________________________       __

Белкова А.Л.	доцент, кандидат физико-математических наук
Гришина О.А.	старший преподаватель

Эксперт(ы):

Груздков А.А., д.ф.-м.н., зав.кафедрой математики СПГТИ(ТУ) ______________________________

 

Программа рассмотрена на заседании кафедры-разработчика рабочей программы О6 Высшая математика_ «___» _______ 2018 г.
Заведующий кафедрой _Винник П.М, к.ф.-м.н., доцент                                               /                          /

 

Программа рассмотрена на заседаниях выпускающих кафедр:

__ И9 Систем управления и компьютерных технологий ______                                      ____________

«___» _______ 2018____ г. Заведующий кафедрой _______Матвеев С.А., к.т.н./                         /

 

Рабочая программа одобрена на заседаниях Учебно-методических комиссий по укрупненной группе направлений и специальностей подготовки (УМК по УГНиСП) протокол №2 от 31.08.2018:

09.00.00__Информатика и вычислительная техника_______________________________________

«___» _____ 2018г. Председатель УМК по УГНиСП Страхов С.Ю., д.т.н, проф._ /                             /

                                                                                                                                                                                       (Ф.И.О., уч.степень, уч.звание)                             (подпись)

Учебная дисциплина обеспечена основной литературой

«___» _____ _2018_ г.    Директор библиотеки БГТУ ____Сесина Н.В. _____/                 /

                                                                                                                                                                                  

Разделы рабочей программы

 

1. ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ... 4

2. МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВО.. 5

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

4. ФОРМЫ КОНТРОЛЯ ОСВОЕНИЯ ДИСЦИПЛИНЫ... 12

5. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ... 13

6. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ... 13

 

 

Приложения к рабочей программе дисциплины

Приложение 1. Аннотация рабочей программы

Приложение 2. Технологии и формы преподавания

Приложение 3. Учебно-методическое обеспечение самостоятельной работы

Приложение 4. Методические указания для обучающихся по освоению дисциплины

Приложение 5. Фонды оценочных средств

Приложение 6. Справка о наличии в библиотеке БГТУ «ВОЕНМЕХ» им. Д.Ф.Устинова учебной литературы

Приложение 7. Лист изменений, вносимых в рабочую программу

ЦЕЛИ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Целью освоения дисциплины является формирование у выпускника следующих компетенций на уровнях:

Для направления 09.03.02 Информационные системы и технологии Общепрофессиональные

ОПК-01: владение широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий	Базовый уровень
ОПК-02: способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования	Базовый уровень

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

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

знания:

1. развивает способности студентов к строгому абстрактно-формальному логическому мышлению, формирует навыки комбинаторного мышления;

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

Умения:

1. решать типовые задачи теории множеств, комбинаторики, теории графов, теории кодирования, применять навыки решения таких задач для практических целей;
2. строить сетевые модели, планировать и управлять сложными комплексами работ, владеть алгоритмами построения экстремальных путей и подходов на графах;
3. иметь опыт в использовании возможностей современных ЭВМ и опыт работы с математическими программными системами.

навыки:

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

Студенты приобретут опыт деятельности:

1. постановки задачи и построения математической модели для реальных условий;
2. представления результатов своих исследований в виде полной математической модели.

 

МЕСТО ДИСЦИПЛИНЫ В СТРУКТУРЕ ООП ВО

 

Дисциплина «Дискретная математика» является дисциплиной базовой части Блока 1 программы. Содержание курса является основой для освоения всех дисциплин в областях «Технические науки» и «Экономические науки».

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

Требования к уровню подготовки обучающихся определены Федеральным государственным образовательным стандартом среднего (полного) общего образования

 

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

 (с распределением общего бюджета времени в часах)

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

Содержание (дидактика) дисциплины:

КУРС	СЕМЕСТР	Номера разделов	Наименование разделов и дидактических единиц	ВСЕГО	АУДИТОРНЫЕ ЗАНЯТИЯ В КОНТАКТНОЙ ФОРМЕ				Самостоятельная работа студентов
					ВСЕГО	Лекции	Аудиторный практикум (семинар)	Лабораторный практикум
1	2	1	Раздел 1. Множества и операции над ними. Множество. Равенство множеств. Подмножество. Пустое множество, универсум. Диаграммы Эйлера-Венна. Булеан. Способы задания множеств. Основные операции над множествами. Алгебра множеств, её основные формулы. Конституенты. Декартовы произведения множеств. Бинарные отношения. Отображения множеств. Образы, прообразы, обратные отображения, виды отображений. Функции, их свойства. Бинарные отношения специального вида. Отношения порядка. Эквивалентность и мощность множеств. Кардинальные числа, шкала кардинальных чисел. Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства. Арифметика кардинальных чисел.	30	12	6	6		18
1	2	2	Раздел 2. Комбинаторика. Основные формулы комбинаторики. Выборки. Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Бином Ньютона. Свойства биномиальных коэффициентов.  Принцип включений и исключений. Формула включений и исключений. Применение принципа включений и исключений к решению некоторых комбинаторных задач. Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей. Метод рекуррентных соотношений. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Числа Фибоначчи.	38	16	8	8		22
1	2	3	Раздел 3. Основы теории графов. Основные понятия теории графов Граф (орграф), его элементы. Виды графов (орграфов). Отношения между элементами графа (орграфа). Способы задания. Степень вершины. Изоморфизм. Связность. Маршруты, пути, циклы. Маршруты в графах, их виды. Цепь, цикл. Пути в орграфах, их виды. Контур. Теоремы о маршрутах и циклах. Определение экстремальных путей на графах. Выявление маршрутов с заданным количеством ребер. Метод Шимбелла. Алгоритмы Дейкстры и Беллмана - Мура построения кратчайшего пути. Задача о нахождении максимального пути на ациклических графах. Обходы графов. Фундаментальные циклы. Деревья. Дерево (ордерево). Корневые, бинарные деревья. Теоремы о деревьях. Остовный граф. Задача об остове минимального веса. Алгоритм Прима расчета кратчайшего остова.	30	12	6	6		18
1	2	4	Раздел 4 Планарные и хроматические графы. Планарные графы. Укладка графа на плоскости, один из алгоритмов укладки графов. Хроматические графы. Раскраски графов. Теорема о пяти красках, история её доказательства.	22	4	2	2		18
1	2	5	Раздел 5. Элементы сетевого планирования. Сети, потоки в сетях. Определения двухполюсной направленной сети, потока. Задача о максимальном потоке. Разрез. Теорема Форда-Фалкерсона. Основные параметры сетевых графов. Критические пути, работы, резервы. Резервы для событий и работ сетевого графа. Линейные графики. Планирование потребления ресурса. Составление расписаний при ограничениях на ресурсы.	30	12	6	6		18
1	2	6	Раздел 6. Теория булевых функций. Алгебра высказываний. Высказывание как первичное понятие алгебры логики. Основные операции над высказываниями. Пропозициональные связки. Истинностные функции. Формулы алгебры высказываний, их виды. Метод истинностных таблиц. Основные понятия теории булевых функций. Понятие булевой функции (функции двузначной логики). Элементарные булевы функции, логические связки. Формулы алгебры логики, функции, их реализующие. Основные эквивалентные формулы алгебры логики. Представления булевых функций Нормальные формы. Алгоритмы приведения к совершенным дизъюнктивной и конъюнктивной нормальным формам. Полиномы Жегалкина. Двойственная функция. Принцип двойственности. Релейно-контактные схемы, их математическое описание и методы построения. Полнота и замкнутые классы. Понятия функциональной замкнутости и полноты. Классы самодвойственных, линейных, сохраняющих константы и монотонных функций. Теорема Поста о функциональной полноте. Минимизация булевых функций. Задача минимизации булевых функций. Структура n-мерного куба. Сокращённая дизъюнктивная форма (ДНФ). Методы Блейка, Нельсона, Квайна их построения, карты Карно. Тупиковая, минимальная, кратчайшая ДНФ, методы их построения.	30	12	6	6		18
ВСЕГО ПО ДИСЦИПЛИНЕ				180	68	34	34		112

Формируемые компетенции

Раздел	ОПК-01	ОПК-02
Раздел 1. Множества и операции над ними	10%	10%
Раздел 2. Комбинаторика.	20%	20%
Раздел 3. Основы теории графов.	30%	30%
Раздел 4. Планарные и хроматические графы.	10%	10%
Раздел 5. Элементы сетевого планирования.	20%	20%
Раздел 6. Теория булевых функций.	10%	10%
Всего по дисциплине	100%	100%

Аудиторный практикум

№ п / п	Номер и наименование раздела дисциплины	Тема практического занятия	Объем, ауд. часов
1	1	Диаграммы Эйлера-Венна. Булеан. Основные операции над множествами. Алгебра множеств, её основные формулы. Декартовы произведения множеств. Бинарные отношения. Действия над кардинальными числа.	6
2	2	Перестановки, размещения, сочетания с повторениями и без повторений. Решение простых перечислительных задач. Производящие функции некоторых комбинаторных последовательностей. Метод рекуррентных соотношений. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Применение принципа включений и исключений к решению некоторых комбинаторных задач.	8
3	3	Решение экстремальных задач теории графов. Алгоритмы Дейкстры и Беллмана - Мура построения кратчайшего пути. Задача о нахождении максимального пути на ациклических графах. Обходы и фундаментальные циклы.	6
4	4	Алгоритмы укладки графа на плоскость и раскраски графа. Числовые характеристики планарности и цветности.	2
5	5	Алгоритм Форда-Фалкерсона. Резервы для событий и работ сетевого графа. Линейные графики. Планирование потребления ресурса.	6
6	6	Элементарные булевы функции, их таблицы истинности. Приведение булевых функций к дизъюнктивной и конъюнктивной нормальным формам, совершенным нормальным формам. Полиномы Жегалкина. Реализация булевой функции релейно-контактной схемой.	6
Итого:			34

3.2 Самостоятельная работа студента (СРС)

Номер и наименование раздела дисциплины	СОДЕРЖАНИЕ учебного задания	время (час)
		СРС
Раздел 1. Множества и операции над ними	Выполнение домашнего задания	18
Раздел 2. Комбинаторика.	Выполнение домашнего задания	22
Раздел 3. Основы теории графов.	Выполнение домашнего задания	18
Раздел 4. Планарные и хроматические графы.	Выполнение домашнего задания	18
Раздел 5. Элементы сетевого планирования.	Выполнение домашнего задания	18
Раздел 6. Теория булевых функций.	Выполнение домашнего задания	18
ВСЕГО:		112

 

ФОРМЫ КОНТРОЛЯ ОСВОЕНИЯ ДИСЦИПЛИНЫ

 

НЕДЕЛИ СЕМЕСТРА

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 2     ДЗ     ДЗ   ДЗ   ДЗ     ДЗ   ДЗ   Дифференцированный зачёт

Условные обозначения:

- ДЗ – домашнее задание;

Текущая аттестация студентов производится в дискретные временные интервалы лектором и преподавателем (ями), ведущимипрактические занятия по дисциплинев следующий форме:

· письменные домашние задания;

· промежуточные аудиторные контрольные работы;

· отдельно оцениваются личностные качества студента (аккуратность, исполнительность, инициативность) – работа у доски, своевременная сдача письменных домашних заданий.

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

Фонды оценочных средств, позволяющие оценить результаты образованияпо данной дисциплине, включены в состав УМК дисциплины и перечислены в Приложении 5.

УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

5.1. Основная литература:

1. Шапорев, Сергей Дмитриевич. Дискретная математика [Текст]: курс лекций и практических занятий: учебное пособие для вузов / С. Д. Шапорев. - СПб.: БХВ-Петербург, 2006. - 396 с. (198 экз.)

2. Дискретная математика [Электронный ресурс]: учебное пособие [для вузов] / БГТУ "ВОЕНМЕХ"; сост. Б. П. Родин. - Электрон. текстовые дан. - СПб.: [б. и.], 2015. - 1 эл. жестк. диск

3. Таранников, Юрий Валерьевич. Дискретная математика. Задачник [Электронный ресурс]: учебное пособие для академического бакалавриата / Ю. В. Таранников. - М.: Юрайт, 2018. - 385 с. - (ЭБС Юрайт).

5.2. Дополнительная литература:

1. Редькин, Н. П. Дискретная математика [Текст]: курс лекций для студентов-механиков: учебное пособие для вузов / Н. П. Редькин. - Изд. 2-е, стер. - СПб.; М.; Краснодар: Лань, 2006. (3 экз.)

2. Мальцев, Иван Анатольевич. Дискретная математика [Текст]: учебное пособие [для вузов] / И. А. Мальцев. - Изд. 2-е, испр. - СПб.: Лань, 2011. - 290 с.

3. Асанов, Магаз Оразкимович. Дискретная математика: графы, матроиды, алгоритмы [Текст]: учебное пособие [для вузов] / М. О. Асанов, В. А. Баранский, В. В. Расин. - Изд. 2-е, испр. и доп. - СПб.: Лань, 2010. - 362 с. (7 экз.)

4. Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов [Текст]: учебное пособие для вузов / М. М. Глухов [и др.]. - СПб.: Лань, 2008. - 111 с. (5 экз.)

5.3. Перечень ресурсов информационно-телекоммуникационной сети "Интернет", необходимых для освоения дисциплины, электронные библиотечные системы:
www.e.lanbook.com
library.voenmeh.ru

biblio-online.ru.

5.4. Программное обеспечение не требуется.

5.5. Информационные технологии, используемые при осуществлении образовательного процесса

Студентам доступны через сеть электронный конспект лекций, задания для самостоятельной работы, экзаменационные вопросы с ответами на них. Возможна заочная консультация и проверка задания через электронную почту.

МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Учебная аудитория с доской.

 

Приложение 1
к рабочей программе дисциплины
«Дискретная математика»

Аннотация рабочей программы

Дисциплина «Дискретная математика» является дисциплиной базовой части блока Б1 программы. Читается для студентов по направлениям подготовки 09.03.02 Информационные системы и технологии. Дисциплина реализуется на И факультете Балтийского государственного технического университета «ВОЕНМЕХ» имени Д.Ф. Устинова кафедрой О6 «Высшая математика».

Дисциплина нацелена на формирование общекультурных компетенций: владение широкой общей подготовкой (базовыми знаниями) для решения практических задач в области информационных систем и технологий (ОПК-01); способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности, применять методы математического анализа и моделирования, теоретического и экспериментального исследования (ОПК-02).

Содержание дисциплины включает круг вопросов из четырёх разделов математики: теории множеств, комбинаторики, теории графов и алгебры высказываний. В первом разделе рассматриваются простейшие свойства множеств и бинарных отношений, а также отношения эквивалентности и порядка. Обсуждается употребляемая в современной математике система аксиом теории множеств.

Во втором разделе изучаются существующие четыре схемы выбора подмножеств, а также подходы к решению комбинаторных задач в рамках алгебраического метода, методов рекуррентных соотношений, производящих функций, включений и исключений.

В разделе теории графов даются необходимые сведения о типах графов, их свойствах и рассматриваются некоторые оптимизационные алгоритмы построения графов с заданными свойствами, в том числе алгоритмы решения экономических задач на сетевых графах.

Наконец, в последнем разделе рассматривается теория булевых функций, именно: формы их представления, способы задания и разновидности, существующие классы этих функций и их минимизация при определённых условиях.

Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции, практические занятия, самостоятельная работа студента, консультации.

Программой дисциплины предусмотрены следующие виды контроля: текущий контроль успеваемости в форме контрольной работы, контроля выполнения этапов и защиты расчетно-графической работы, итоговый контроль в форме дифференцированного зачёта.

Общая трудоемкость освоения дисциплины составляет 5 зачетных единиц, 180 часов. Программой дисциплины предусмотрены лекционные (34 часа), практические (34 часа) занятия и 112 часов самостоятельной работы студента.

 

 

Приложение 2
к рабочей программе дисциплины
«Дискретная математика»

Рекомендации по организации и технологиям обучения для преподавателя

I. Образовательные технологии

Преподавание дисциплины ведется с применением следующих видов образовательных технологий:

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

II. Виды и содержание учебных занятий

Теоретические занятия (лекции) - _____34__________ часа.

Раздел 1.Множества и операции над ними.

Лекция 1. Множество. Равенство множеств. Подмножество. Пустое множество, универсум. Диаграммы Эйлера-Венна. Булеан. Способы задания множеств. Основные операции над множествами. Алгебра множеств, её основные формулы, законы алгебры множеств. Понятие булевой алгебры. Алгебра множеств как модель булевой алгебры. Конституенты.

Лекция 2. Декартовы произведения множеств. Бинарные отношения. Отображения множеств. Образы, прообразы, обратные отображения, виды отображений. Функции, их свойства. Бинарные отношения специального вида. Отношения порядка.

Лекция 3. Эквивалентность и мощность множеств. Кардинальные числа, шкала кардинальных чисел. Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства. Арифметика кардинальных чисел. Обсуждение понятия математической бесконечности на примере шкалы алефов и мировоззренческая роль этого понятия.

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

Лекция 4. Выборки. Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Бином Ньютона, полиномиальная теорема. Свойства биномиальных коэффициентов.

Лекция 5. Метод рекуррентных соотношений, и его использование для вывода формул, связывающих биномиальные коэффициенты. Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей (с ограниченным и неограниченным числом повторений). Однородные и неоднородные линейные рекуррентные соотношения.

Лекция 6. Формула включений и исключений. Вывод и обсуждение соответствующих формул. Применение принципа включений и исключений к решению некоторых комбинаторных задач.

Лекция 7. Учёт весов в формуле включений и исключений. Функции Эйлера и Мёбиуса. Разбор и решение задач практического содержания с использованием весов в формуле включений и исключений. Функция Эйлера и порождаемый ею класс комбинаторных задач.

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

Алгебра множеств, её основные формулы. Решение задач на доказательство тождеств и графическое представление множеств и действий с ними.

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

Декартовы произведения множеств. Бинарные отношения. Доказательство свойств декартова произведения, бинарных отношений функций. Отношения порядка. Элементарные функции и их свойства рефлексивности (иррефлексивности), симметричности, антисимметричности, транзитивности и эквивалентности.

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

Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства. Действия над кардинальными числами. Решения простейших задач на конечные, счетные и несчётные множества, их мощности и соотношения.

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

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

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

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

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

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

Формула включений и исключений. Применение принципа включений и исключений к решению некоторых комбинаторных задач. Разбор и решение задач практического содержания с использованием весов в формуле включений и исключений. Функция Эйлера и порождаемый ею класс комбинаторных задач.

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

Контрольная работа.

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

Решение задач на способы задания графов по матрицам смежности вершин, смежности рёбер и инциденций. Нахождение маршрутов, состоящих из фиксированного количества ребер. Упорядочение дуг и вершин орграфа, алгоритм Фалкерсона. Алгоритм Дейкстры.

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

Задачи на вычисление максимального пути, алгоритм Беллмана-Мура, построение минимального остова графа. Эйлеровы и гамильтоновы циклы. Алгоритм Флери.

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

Алгоритм Прима построения остова дерева. Вычисление клик ордерева, построение матрицы клик. Вычисление числовых характеристик деревьев.

Раздел 4.Планарные и хроматические графы.

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

Алгоритм укладки графа на плоскости. Практический алгоритм раскраски графов. Решение задач на планарные графы. Раскраски графов. Решение примеров по индивидуальным вариантам.

Раздел 5. Элементы сетевого планирования.

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

Числовые характеристики планарности и цветности, один из алгоритмов укладки графов. Хроматические графы. Раскраски графов.

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

Укладка графа на плоскости. Расчёт числовых характеристик планарности и цветности.

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

Разбор задач расчётно-графической работы. Ответы на вопросы по РГР. Защита РГР.

Раздел 6.Теория булевых функций.

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

Высказывания, основные операции над высказываниями, пропозициональные связки. Формулы алгебры высказываний. Применение метода таблиц истинности к доказательству тождественной истинности (ложности), выполнимости, опровержимости формул алгебры высказываний. Функции алгебры логики. Элементарные булевы функции, их таблицы истинности. Решение тех же задач методом эквивалентных преобразований.

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

Приведение булевых функций к дизъюнктивной и конъюнктивной нормальным формам, совершенным нормальным формам по таблице истинности и с помощью эквивалентных преобразований. Приведение булевых функций к полиному Жегалкина методом неопределённых коэффициентов и с помощью эквивалентных преобразований. Построение двойственных функций по определению и с помощью принципа двойственности.

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

Производные от булевых функций. Реализация булевой функции релейно-контактной схемой. Нахождение по релейно-контактной схеме булевой функции, которую она реализует.

Управление самостоятельной работой студента по всем разделам - __12______ часов.

Консультации по выполнению домашних заданий работ;

Консультации по материалам лекций и практических занятий.

Приложение 3
к рабочей программе дисциплины
«Дискретная математика»

 

УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

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

Трудоемкость освоения дисциплины составляет 180 часов, из них 68 часов аудиторных занятий и 112 часов, отведенных на самостоятельную работу студента.

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

Контроль освоения дисциплины производится в соответствии с Положением о порядке проведения промежуточной аттестации студентов БГТУ «ВОЕНМЕХ» им. Д.Ф.Устинова.

Формы контроля и критерии оценивания приведены в п.4 Рабочей программы и в Приложении 5 к Рабочей программе.

Вид работы	Содержание (перечень вопросов)	Трудоемкость, час.	Рекомендации

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

Повторение и осознание теоретического материала лекций № 4-7. Правила суммы и произведения. Перестановки, размещения, сочетания с повторениями и без повторений. Бином Ньютона. Алгебраический подход изучения комбинаторных объектов и чисел. Метод рекуррентных соотношений и его применение при решении перечислительных задач. Решение линейных рекуррентных уравнений с постоянными коэффициентами. Числа Фибоначчи. Формула включений и исключений. Производящие функции, экспоненциальные производящие функции, действия над ними. Производящие функции некоторых комбинаторных последовательностей. Решение линейных рекуррентных уравнений с постоянными коэффициентами. 10 Конспект лекций, материалы практических занятий, раздел 2 источника 3 из списка основной литературы. Подготовка к практическим занятиям 4-6, решение типовых задач по комбинаторике. Решение комбинаторных задач на правило суммы и правило произведения, бином Ньютона и полиномиальную теорему, метод рекуррентных соотношений, метод производящих функций, метод включений и исключений. 6 Конспект лекций, материалы практических занятий, практические занятия 3-5 из источника 3 из списка основной литературы (стр. 43, стр.67, стр.86). Подготовка к контрольной работе Решение задач по разделам 1-2. 6 Конспект лекций, материалы практических занятий, разделы 1-2 источника 3 из списка основной литературы. Итого по разделу 2   22 часа  

Раздел 4. Планарные и хроматические графы.

Повторение и осознание теоретического материала лекции № 11. Планарность графов, алгоритм укладки графа на плоскости. Хроматические графы, алгоритмы раскраски графов. 4 Конспект лекций, материалы практических занятий, раздел 3 источника 3 из списка основной литературы. Подготовка к практическим занятиям 11 Задачи на операции над графами. Фундаментальные циклы и клики, укладка графов. Хроматические графы. 4 Конспект лекций, материалы практических занятий, практическое занятие 9 из источника 3 из списка основной литературы (стр. 172). Выполнение расчётно-графической работы Укладка графа на плоскости, один из алгоритмов укладки графов. Хроматические графы. Раскраски графов. 10 Конспект лекций, материалы практических занятий, раздел 3 источника 3 из списка основной литературы. Итого по разделу 4   18часов  

Раздел 5. Элементы сетевого планирования.

Повторение и осознание теоретического материала лекций № 12-14. Задача о максимальном потоке. Разрезы в сетях, пропускная способность разреза. Основные параметры сетевых графов. Критические пути, работы, резервы. Резервы для событий и работ сетевого графа. Линейные графики, расчёт их характеристик. 6 Конспект лекций, материалы практических занятий, раздел 3 источника 3 из списка основной литературы. Подготовка к практическим занятиям 12-14. Задачи на анализ сетевых графов. 6 Конспект лекций, материалы практических занятий, практическое занятие 10 (стр. 198) из источника 3 из списка основной литературы. Выполнение и подготовка к защите расчётно-графической работы Решение задач расчётно-графической работы. Вычисление потоков по алгоритмам Форда-Фалкерсона, вычисление параметров сетевых графиков. 6 Конспект лекций, материалы практических занятий, задачи типового расчёта (стр. 198, стр. 206) из источника 3 из списка основной литературы. Итого по разделу 5   18часов  

ПЕРЕЧЕНЬ ТЕМ ЗАДАНИЙ

(по видам СРС)

Перечень домашних заданий:

1. Нахождение минимального по весу пути в ориентированном графе методом Дейкстры;

2. Нахождение максимального по весу пути в ориентированном графе перечислительным методом;

3. Нахождение минимального по весу пути в ориентированном графе методом Беллмана-Мура;

4. Нахождение минимального по весу остова неориентированного графа по методу ближайшего соседа (Прима);