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

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

рабочая программа дисциплины
Закреплена за кафедройНЕТ (реорганизована) 16
Направление подготовки09.03.03. Прикладная информатика
ПрофильПрикладная информатика в экономике
Форма обученияОчная
Общая трудоемкость3 ЗЕТ
Учебный план09_03_03_ПИЭ-1-2019
Часов по учебному плану 108
в том числе:
аудиторные занятия 42
самостоятельная работа 39
контроль 27
Виды контроля по семестрам
экзамены: 2

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

Курс (семестр) 1 (2) Итого
Недель 20
Вид занятий УПРПДУПРПД
Лекции 16 20 16 20
Лабораторные 26 4 26 4
Сам. работа 39 58 39 58
Часы на контроль 27 27 27 27
Итого 108 109 108 109

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

Рецензент(ы):

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

разработана в соответствии с ФГОС:
Федеральный государственный образовательный стандарт высшего образования по направлению подготовки 09.03.03 Прикладная информатика (уровень бакалавриата) (приказ Минобрнауки России от 20.09.2017г. №922)

составлена на основании учебного плана:
09.03.03 Прикладная информатика: Прикладная информатика в экономике
утвержденного учёным советом вуза от 25.06.2019 протокол № 9.

Рабочая программа одобрена на заседании кафедры
НЕТ (реорганизована) 16

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

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


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

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

НЕТ (реорганизована) 16

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


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

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

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

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

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

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

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

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

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

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

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

6.1. Рекомендуемая литература
6.1.1. Основная литература
Авторы Заглавие Издательство, год Эл. адрес
Л1.1 Гашков С.Б., Фролов А.Б. ДИСКРЕТНАЯ МАТЕМАТИКА 2-е изд., испр. и доп. Учебник и практикум для академического бакалавриата: Гриф УМО ВО М.:Издательство Юрайт, 2018 biblio-online.ru
Л1.2 Шевелев Ю.П. Дискретная математика: учеб. пособие для вузов СПб.: Лань // ЭБС "Лань", 2008 e.lanbook.com
Л1.3 Редькин Н.П. Дискретная математика: Учебник "Физматлит" // ЭБС "Лань", 2009
6.1.2. Дополнительная литература
Авторы Заглавие Издательство, год Эл. адрес
Л2.1 Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы: Учебник СПб.: Лань // ЭБС "Лань", 2010// ЭБС "Лань"
Л2.2 Соболева Т.С., Чечкин А.В. Дискретная математика: учеб. для вузов М.: Академия, 2006
Л2.3 Микони С.В. Дискретная математика для бакалавра: множества, отношения, функции, графы: СПб.: Лань // ЭБС "Лань", 2012 e.lanbook.com
6.1.3. Дополнительные источники
Авторы Заглавие Издательство, год Эл. адрес
Л3.1 Гаврилов Г. П. , Сапоженко А. А. Задачи и упражнения по дискретной математике: усеб. пособие М.: Физматлит, 2005
6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет"
Название Эл. адрес
Э1 Сайт библиотеки АлтГУ: www.lib.asu.ru;
Э2 электронно-библиотечная система издательства «Лань»: www.e.lanbook.com;
Э3 электронно-библиотечная система "Университетская библиотека online": www.biblioclub.ru;
Э4 свободная энциклопедия «Википедия»: http://ru.wikipedia.org
6.3. Перечень программного обеспечения
Microsoft Windows
Microsoft Office
7-Zip
AcrobatReader
6.4. Перечень информационных справочных систем
Информационная справочная система:
СПС КонсультантПлюс (инсталлированный ресурс АлтГУ или http://www.consultant.ru/).
Профессиональные базы данных:
1. Электронная база данных «Scopus» (http://www.scopus.com);
2. Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/);
3. Научная электронная библиотека elibrary (http://elibrary.ru)

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

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

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

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

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