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

Учебная программа составлена на основе ОСВО 1-31 03 01-2013 (30.05.2013)  и учебного плана (регистрационный G31-139/уч. (30.08.2013)).

СОСТАВИТЕЛЬ:

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

РЕКОМЕНДОВАНА К УТВЕРЖДЕНИЮ

кафедрой математической кибернетики механико-математического факультета Белорусского государственного университета

(протокол  № 9 от  05.05.2017);

учебно-методической комиссией механико-математического факультета  Белорусского государственного университета

(протокол  № 7 от  16.05.2017).

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Конец ХХ и начало ХХI века характеризуются бурным развитием математического моделирования. С одной стороны, моделирование является основным средством исследования практически во всех науках, включая гуманитарные, с другой стороны, могучим оружием решения практических задач. Исследование математических моделей стало возможным, благодаря интенсивному развитию вычислительной техники. Кроме того, начало ХХI ознаменовалось интенсивным развитием информационных технологий.

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

В связи с этим, дискретные математические курсы стали обычными в высших и средних специальных учебных заведений, а с 2017 года элементы дискретной математики введены в школьные программы учебного предмета «Математика».

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

Дисциплина «Дискретная математика» тесно связана с дисциплиной «Математическая логика».

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

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

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

Основной задачей дисциплины является формирование знаний разделов дискретной математики и методических приемов применения их для построения и исследования экономических моделей.

При изучении данной дисциплины предполагается, что студенты знакомы с простейшими понятиями теории множеств.

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

- роль и значение дискретной математики при построении и исследовании экономических математических моделей; роль и значение дискретной математики как теоретической базы информатики и IT-технологий;

- основные определения объектов дисциплины (теории графов и комбинаторики) и ее теорем и связи между ними;

уметь:

- решать основные задачи теории графов, комбинаторики и теории булевых функций; -

владеть:

-методикой использования отдельных тем дискретной математики для построения и исследования экономических математических моделей.

В результате изучения дисциплины «Дискретная математика» студент должен обладать следующими компетенциями:

АК-1. Уметь применять базовые научно-теоретические знания для решения теоретических и практических задач.

АК-2. Владеть системным и сравнительным анализом.

АК-3. Владеть исследовательскими навыками.

АК-4. Владеть междисциплинарным подходом при исследовании проблем. Владеть междисциплинарным подходом при решении проблем

АК-5. Уметь работать самостоятельно.

АК-6. Быть способным вырабатывать новые идеи (обладать креативностью).

АК-7. Иметь навыки, связанные с использованием технических устройств, управлением информацией и работой с компьютером.

АК-8. Обладать навыки устной и письменной коммуникаций.

АК-9. Уметь учиться, повышать свою квалификацию в течение всей жизни.

СЛК-1. Быть способным к социальному взаимодействию.

СЛК-2. Обладать способностью к межличностным коммуникациям.

СЛК-3. Быть способным к критике и самокритике.

СЛК-4. Уметь работать в команде

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

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

ПК-3. Заниматься аналитической и научно-исследовательской деятельностью в области экономики.

ПК-4. Проводить исследования в области эффективности решения производственных задач.

ПК-5. Осуществлять выбор оптимального варианта проведения исследований.

ПК-6. Взаимодействовать со специалистами смежных профилей.

ПК-7. Готовить доклады, материалы к презентациям.

ПК-8. Работать с научной, технической и патентной литературой.

ПК-9. Реализовывать инновационные проекты в профессиональной деятельности.

ПК-10. Составлять документацию (графики работ, инструкции, планы, также отчетную документацию по установленным формам.

       Учебная программа предназначена для студентов 4 курса (8 семестр) очной формы обучения.

В соответствии с учебным планом специальности на изучение дисциплины отводится 90 часов, из них 54 аудиторных часа, в том числе:

36 часов – лекции, 12 часов  - лабораторные занятия, 6 часов – УСР, текущая аттестация – зачет.

Содержание учебного материала

Тема 1. Введение

Дискретные математические дисциплины и их роль жизни общества.

Тема 2. Определение графа, простейшие свойства.

Определение графа. Примеры графов. Лемма о рукопожатии. Маршруты, цепи, циклы. Связные графы. Изоморфные графы. Двудольные графы. Теорема Кенига о двудольности.

Тема 3. Деревья.

Эквивалентные определения дерева. Минимальное остовное дерево.

Тема 4. Обходы в графах.

Эйлеровы графы. Необходимые и достаточные условия эйлеровости. Построение эйлерова цикла. Гамильтоновы графы. Необходимые условия гамильтоновости.

Тема 5. Планарность графов.

Плоские и планарные графы. Теорема Эйлера и следствия из нее. Укладка графов. Теорема Понтрягина-Куратовского (без доказательства).

Тема 6. Раскраска графов.

Правильная раскраска графов. Хроматическое число.

Тема 7. Ориентированные графы.

Определение ориентированного графа. Простейшие свойства.

Тема 8. Комбинаторные задачи.

Понятие о комбинаторике. Связь комбинаторики с другими математическими дисциплинами.

Тема 9. Комбинаторные конфигурации.

Теоремы комбинаторного сложения и умножения. Перестановки, сочетания, размещения без повторений и с повторениями.

Тема 10.Понятие о теории булевых функций.

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

Тема 11. Задание булевых функций формулами.

Формулы. Равносильные формулы. Конъюнктивные и дизъюнктивные нормальные формы. Совершенные формы.

Тема 12. Теорема Поста о полноте.

Замкнутые системы функций. Полные системы функций. Теорема Поста о полноте (без доказательства).

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

ДЛЯ СТУДЕНТОВ 1 КУРСА (ОЧНАЯ ФОРМА ОБУЧЕНИЯ)

Номер раздела, темы	Название раздела, темы	Количество аудиторных часов	Количество часов УСР	Форма контроля знаний
Лекции	Практические занятия	Семинарские занятия	Лабораторные занятия	Иное
1	2	3	4	5	6	7	8	9
1	Введение.
1.1	Дискретные математические модели и их роль в жизни общества.	1	1
2	Определение графа, простейшие свойства.
2.1	Определение графа. Примеры графов. Лемма о рукопожатии. Изоморфные графы.	1	1
2.2	Маршруты, цепи, циклы. Связные графы. Двудольные графы. Теорема Кенига о двудольности.	2	1	Проверка индивидуаль-ных заданий
3.	Деревья.
3.1	Эквивалентные определения дерева.	2	Проверка индивидуаль-ных заданий
3.2.	Минимальное остовное дерево.	2	Устный опрос
Контрольная работа № 1.	2
4.	Обходы в графах
4.1.	Эйлеровы графы. Необходимые и достаточные условия эйлеровости. Построение эйлерова цикла.	2	1	Проверка индивидуаль-ных заданий
4.2.	Гамильтоновы графы. Необхо-димые условия гамильтоновости.	2	1	Проверка индивидуаль-ных заданий
5.	Планарность графов.
5.1	Плоские и планарные графы. Тео-рема Эйлера и следствия из нее.	2	1	Проверка индивидуаль-ных заданий
5.2.	Укладка графов. Теорема Понтрягина-Куратовского.	2	Устный опрос
6	Раскраска графов.
6.1.	Правильная раскраска графов. Хроматическое число.	1	1	Проверка индивидуаль-ных заданий
7.	Ориентированные графы.
7.1.	Определение ориентированного графа. Простейшие свойства.	1	1	Проверка индивидуаль-ных заданий
Контрольная работа № 2.	2
8.	Комбинаторные задачи.
8.1.	Понятие о комбинаторике. Связь комбинаторики с другими математическими дисциплинами.	2	Устный опрос
9.	Комбинаторные конфигурации.
9.1.	Теоремы комбинаторного сложе-ния и умножения. Перестановки, сочетания, размещения без повторений.	4	1	Проверка индивидуаль-ных заданий
9.2.	Перестановки, сочетания, размещения с повторениями.	2	1	Проверка индивидуаль-ных заданий
10.	Понятие о теории булевых функций.
10.1.	Определение булевой функции. Элементарные булевы функции. Различные способы задания булевых функций.	2	1	Проверка индивидуаль-ных заданий
10.2.	Формулы. Равносильные форму-лы. Конъюнктивные и дизъюнк-тивные нормальные формы. Совершенные формы.	2	1	Проверка индивидуаль-ных заданий
10.3.	Замкнутые и полные системы функций. Теорема Поста о полноте (без доказательства).	4	Проверка индивидуаль-ных заданий
Контрольная работа № 3.	2
Итого	34	12	6

Информационно-методическая часть

Литература

Основная

1. , , . Лекции по теории графов. М.: URSS, 2017.

       2. . Теория графов для учителей, для школьников... и не только. М.: Ленанд, 2017.

       3. . Теория графов в занимательных задачах. М.: Либроком, 2008 с.

       4. . Введение в комбинаторныйи анализ. М.: Наука, 1985.

       5. . Основы теории булевых функций. М.: URSS, 2017.

Дополнительная

5. . Обучение дискретной математике. М.:ЛКИ, 2013.

6. . Незнайка в стране графов. М.: КомКнига, 2006.

7. . Задачи по комбинаторике. Минск: БГУ, 2009.

       Организация управляемой самостоятельной работы студентов

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

Примерный перечень заданий УСР

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

Сравнение различных алгоритмов построения минимального остовного дерева. Понятие о дереве Штейнера. Сравнение различных алгоритмов построения эйлерова цикла. Доказательство теоремы Понтрягина-Куратовского. Необходимые условия существования гамильтонова цикла в ориентированном графе. Теорема Брукса. Понятие о реализации гиперграфа графами. Необходимые и достаточные условия реализации гиперграфа деревьями. Описание различных комбинаторных соотношений. Минимизация нормальных форм.

Примерный перечень

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

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

Рекомендуемый перечень основных вопросов к  зачету

по дисциплине «Дискретная математика»

Определение графа. Примеры графов. Лемма о рукопожатиях. Маршруты, цепи, циклы. Связные графы. Компоненты связности. Двудольные графы. Теорема о соотношении суммы степеней вершин долей двудольного графа. Теорема Кенига о двудольности. Изоморфные графы. Эквивалентные определения дерева. Теорема о центре дерева. Минимальное остовное дерево и алгоритм его построения. Необходимые и достаточные условия эйлеровости. Необходимые условия гамильтоновости. Независимое множество вершин и оценки числа независимости. Паросочетания в графе. Плоские и планарные графы. Теорема Эйлера и следствия из нее. Теорема Понтрягина-Куратовского. Доказательство необходимости. Правильная раскраска графа. Число независимости. Хроматический полином. Определение ориентированного графа и его простейшие свойства. Теоремы комбинаторного сложения и умножения. Перестановки, сочетания, размещения без повторений. Перестановки, сочетания, размещения с повторениями. Нахождения числа всех подмножеств конечного множества. Бином Ньютона. Элементарные булевы функции. Формулы. Равносильные формулы. Нормальные формы. Совершенные нормальные формы. Замкнутость. Полнота. Теорема Поста (без доказательства).

Методика формирования итоговой оценки

Итоговая оценка формируется на основе 3-х документов:

1.Правила проведения аттестации (Постановление г.).

2.Положение о рейтинговой системе БГУ (ред.2015 г.).

3.Критерии оценки студентов (10 баллов).

ПРОТОКОЛ СОГЛАСОВАНИЯ УЧЕБНОЙ ПРОГРАММЫ

ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ

С ДРУГИМИ ДИСЦИПЛИНАМИ СПЕЦИАЛЬНОСТИ

Название дисциплины, с которой требуется согласование	Название кафедры	Предложения об изменениях в содержании учебной программы по изучаемой учебной дисциплине	Решение, принятое кафедрой, разработавшей учебную программу (с указанием даты и номера протокола)
Математичес-кая логика	кафедра математической кибернетики	нет	Вносить изменения не требуется (протокол № 9 от 01.01.2001)

ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ К УЧЕБНОЙ ПРОГРАММЕ

ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ

на _____/_____ учебный год

№№ пп	Дополнения и изменения	Основание

Учебная программа пересмотрена и одобрена на заседании кафедры МК

(протокол № ____ от __________ 20___ г.)

Заведующий кафедрой

Профессор  ____________________

(степень, звание)                        (подпись)         ()

УТВЕРЖДАЮ

Декан факультета

  доцент  __________________ 

(степень, звание)                        (подпись)                         ()