МИНОБРНАУКИ РОССИИ
федеральное государственное бюджетное образовательное учреждение высшего образования
«Алтайский государственный университет»

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

рабочая программа дисциплины
Закреплена за кафедройКафедра экономики и эконометрики
Направление подготовки27.03.03. Системный анализ и управление
ПрофильСистемный анализ и управление экономическими системами
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план27_03_03_САиУЭС-1-2020
Часов по учебному плану 108
в том числе:
аудиторные занятия 42
самостоятельная работа 39
контроль 27
Виды контроля по семестрам
экзамены: 3

Распределение часов по семестрам

Курс (семестр) 2 (3) Итого
Недель 15
Вид занятий УПРПДУПРПД
Лекции 14 14 14 14
Практические 28 28 28 28
Сам. работа 39 39 39 39
Часы на контроль 27 27 27 27
Итого 108 108 108 108

Программу составил(и):
канд. физ. - мат. наук, Доцент, Исаева О.В.

Рецензент(ы):
канд. физ. - мат. наук, Доцент, Половникова Е.С.

Рабочая программа дисциплины
Дискретная математика

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 27.03.03 СИСТЕМНЫЙ АНАЛИЗ И УПРАВЛЕНИЕ (уровень бакалавриата) (приказ Минобрнауки России от 11.03.2015 г. № 195)

составлена на основании учебного плана:
27.03.03 Системный анализ и управление
утвержденного учёным советом вуза от 30.06.2020 протокол № 6.

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

Протокол от 20.05.2020 г. № 8
Срок действия программы: 2020-2021 уч. г.

Заведующий кафедрой
профессор, д.э.н. О.П. Мамченко


Визирование РПД для исполнения в очередном учебном году

Рабочая программа пересмотрена, обсуждена и одобрена для
исполнения в 2020-2021 учебном году на заседании кафедры

Кафедра экономики и эконометрики

Протокол от 20.05.2020 г. № 8
Заведующий кафедрой профессор, д.э.н. О.П. Мамченко


1. Цели освоения дисциплины

1.1.усвоение студентами теоретических основ дискретной математики и математической логики, составляющих фундамент ряда математических дисциплин и дисциплин прикладного характера

2. Место дисциплины в структуре ООП

Цикл (раздел) ООП: Б1.Б

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

ОПК-1 готовностью применять методы математики, физики, химии, системного анализа, теории управления, теории знаний, теории и технологии программирования, а также методов гуманитарных, экономических и социальных наук
ОПК-2 способностью применять аналитические, вычислительные и системно-аналитические методы для решения прикладных задач в области управления объектами техники, технологии, организационными системами, работать с традиционными носителями информации, базами знаний
ОПК-6 способностью к проведению измерений и наблюдений, составлению описания исследований, подготовке данных для составления обзоров, отчетов и научных публикаций, составлению отчета по заданию, к участию во внедрении результатов исследований и разработок
ПК-1 способностью принимать научно-обоснованные решения на основе математики, физики, химии, информатики, экологии, методов системного анализа и теории управления, теории знаний, осуществлять постановку и выполнять эксперименты по проверке их корректности и эффективности
В результате освоения дисциплины обучающийся должен
3.1.Знать:
3.1.1.Формулировки основных социально-экономические задач; типовые методы системного анализа;
основные понятия и принципы математического моделирования основные математические законы и современные информационно-коммуникационные технологии
3.2.Уметь:
3.2.1.применять математические методы формализации и анализа для анализа социально-экономические проблем;
применять методы системного анализа для решения типовых экономических и управленческих задач;
применять математические методы формализации и анализа, современные информационно-коммуникационные технологии для решения типовых экономических и управленческих задач и принятия обоснованных решений
3.3.Иметь навыки и (или) опыт деятельности (владеть):
3.3.1.навыками использования методов системного анализа и математического моделирования в профессиональной деятельности;
навыками использования основных теорем разделов математики и современные информационно-коммуникационные технологии в профессиональной деятельности

4. Структура и содержание дисциплины

Код занятия Наименование разделов и тем Вид занятия Семестр Часов Компетенции Литература
Раздел 1. Элементы теории множеств
1.1. Множества. Подмножества и дополнения; объединения и перечисления Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.2. Множества. Подмножества и дополнения; объединения и перечисления Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.3. Множества. Подмножества и дополнения; объединения и перечисления Сам. работа 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.4. Отношения Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.5. Отношения Сам. работа 3 3 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.6. Счетные множества Лекции 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.7. Множества. Подмножества и дополнения; объединения и перечисления Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.8. Счетные множества Сам. работа 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
1.9. Кардинальные числа. Порядковые числа Сам. работа 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
Раздел 2. Математическая логика. Алгебра высказываний
2.1. Алгебра высказываний Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.2. Алгебра высказываний Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.3. Булевы функции Лекции 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.4. Булевы функции Практические 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.5. Теорема о полноте Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.6. Теорема о полноте Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
2.7. Приложения функций логики высказываний Сам. работа 3 2 ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
Раздел 3. Теория графов
3.1. Основные понятия теории графов и способы предстовления графов Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.2. Теорема Л. Эйлера о плоских графах Практические 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.3. Основные понятия теории графов и способы предстовления графов Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.4. Оценка числа графов Сам. работа 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.5. Эйлеровы и гамельтоновы грифы Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.6. Деревья Практические 3 4 ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.7. Экстремальные задачи: алгоритм Краскаля. Задача о четырех красках Сам. работа 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
3.8. Теорема о целочисленности. Потоки в сетях. Теорема о максемальном потоке и минимальном размере Сам. работа 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
Раздел 4. Элементы теории автоматов
4.1. Определение конечного автомата, способы изображения, примеры. Эквивалентность состояний. Основные понятия алгебры. Теорема о гомоморфизмах полугрупп. Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.2. Определение конечного автомата, способы изображения, примеры. Эквивалентность состояний. Основные понятия алгебры. Теорема о гомоморфизмах полугрупп. Сам. работа 3 5 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.3. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.4. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Сам. работа 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.5. Гомоморфизмы автоматов. Теорема о каноническом разложении гомоморфизма. Подавтомат, фактор-автомат, теорема о гомоморфизмах автоматов. Сам. работа 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.6. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.7. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Практические 3 2 ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
4.8. Автоматы Мура. Автоматы Мура и универсальные автоматы. Гомоморфизмы автоматов Мура. Теорема Крона-Кроуза (без доказательства). Сам. работа 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
Раздел 5. Элементы теории алгоритмов
5.1. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Лекции 3 1 ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
5.2. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Практические 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
5.3. Вычислимые функции, машины Тьюринга, тезис Черча. Примеры вычислимых функций. Рекурсивные и рекурсивно-перечислимые множества, их алгоритмическая характеристика. Теорема Поста. Сам. работа 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
5.4. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Лекции 3 1 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
5.5. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Сам. работа 3 2 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1
5.6. Примеры алгоритмически неразрешимых проблем, неразрешимость проблем самоприменимости и применимости. Теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. Сам. работа 3 4 ОПК-1, ОПК-2, ОПК-6, ПК-1 Л1.1, Л2.1

5. Фонд оценочных средств

5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины
см. Приложения
5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.)
см. Приложения
5.3. Фонд оценочных средств для проведения промежуточной аттестации
представлен отдельным документом

6. Учебно-методическое и информационное обеспечение дисциплины

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Гашков С.Б., Фролов А.Б. ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата: Гриф УМО ВО М.:Издательство Юрайт, 2018 biblio-online.ru
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Палий И.А. ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., испр. и доп. Учебное пособие для академического бакалавриата: Гриф УМО ВО М.:Издательство Юрайт, 2018 biblio-online.ru
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Сайт библиотеки АлтГУ: www.lib.asu.ru;
Э2 электронно-библиотечная система издательства «Лань»: www.e.lanbook.com;
Э3 электронно-библиотечная система "Университетская библиотека online": www.biblioclub.ru;
Э4 свободная энциклопедия «Википедия»: http://ru.wikipedia.org
Э5 Курс в Moodle portal.edu.asu.ru
6.3. Перечень программного обеспечения
Microsft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013, (бессрочно);
Microsoft Office 10 (Office 2010 Professional, № 49464762 от 14.12.2011, (бессрочно);
7-Zip, http://www.7-zip.org/license.txt, (бессрочно);
AcrobatReader, http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf, (бессрочно).
6.4. Перечень информационных справочных систем
Информационная справочная система:
СПС Консультант Плюс (инсталлированный ресурс АлтГУ или http://www.consultant.ru/).
Профессиональные базы данных:
1. Профессиональная база данных: электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);
2. Профессиональная база данных: научная электронная библиотека elibrary (http://elibrary.ru)
3. Электронная база данных справочной правовой системы ГАРАНТ.

7. Материально-техническое обеспечение дисциплины

Аудитория Назначение Оборудование
Помещение для самостоятельной работы помещение для самостоятельной работы обучающихся Компьютеры, ноутбуки с подключением к информационно-телекоммуникационной сети «Интернет», доступом в электронную информационно-образовательную среду АлтГУ
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска)
Учебная аудитория для проведения занятий лекционного типа, занятий семинарского типа (лабораторных и(или) практических), групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации, курсового проектирования (выполнения курсовых работ), проведения практик Стандартное оборудование (учебная мебель для обучающихся, рабочее место преподавателя, доска, мультимедийное оборудование стационарное или переносное)

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

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

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