Учебно-методические материалы по дисциплине
Федеральное государственное автономное образовательное
Учреждение высшего профессионального образования
«Сибирский федеральный университет»
УТВЕРЖДАЮ
Директор института
Фундаментальной подготовки
_____________ В.М. Журавлев
«_____» _____________20__ г.
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Дисциплина
| Б2.Б.3 ДИСКРЕТНАЯ МАТЕМАТИКА
|
Укрупненная группа
| 230000 «ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА»
|
Направление
| 230700.62 «ПРИКЛАДНАЯ ИНФОРМАТИКА»
|
Профиль
| 230700.62.00.02 «ПРИКЛАДНАЯ ИНФОРМАТИКА В ЭКОНОМИКЕ»
|
| 230700.62.00.01 «ПРИКЛАДНАЯ ИНФОРМАТИКА В МЕНЕДЖМЕНТЕ»
|
|
|
Кафедра
| «Высшей математики – 2»
|
Институт
| Фундаментальной подготовки
|
Красноярск
РАБОЧАЯ программа дисциплины
составлена в соответствии с Федеральным государственным образовательным стандартом высшего профессионального образования по укрупненной группе 230000 «Информатика и вычислительная техника» для направления подготовки бакалавров 230700.62 «Прикладная информатика».
Программу составила:
доцент кафедры «Высшая математика – 2», к.ф.-м.н. Шевелева И.В. _____________
Рабочая программа обсуждена на заседании кафедры «Высшая математика – 2».
«_ __ _» _ _____ 20 __ г. протокол № _ _ _
Заведующий кафедрой «Высшая математика – 2» Дураков Б.К. ____________________
Рабочая программа обсуждена на заседании кафедры «Бизнес-информатика».
«__ __ __»_ _____ 20 __ г. протокол № _ _ _
Заведующий кафедрой «Бизнес-информатика» Пупков А.Н. _________________
Рабочая программа обсуждена на заседании НМСИ Института управления бизнес-процессами и экономики ____ _________ 20___ г. протокол № ___.
Председатель НМСИ ______________________ __________________
Дополнения и изменения в учебной программе на 20 __/20__ учебный год.
В рабочую программу вносятся следующие изменения: __________________________________
__________________________________________________________________________________
Рабочая программа пересмотрена и одобрена на заседании кафедры ________________________
«____» _____________ 20__г. протокол № ________
Заведующий кафедрой _____________________________________________
Внесенные изменения утверждаю:
Директор института ________________________________________________________________
Цели и задачи изучения дисциплины
Цель преподавания дисциплины
Дискретная математика представляет собой область математики, в которой изучаются свойства структур конечного характера, а также бесконечных структур, предполагающих скачкообразность происходящих в них процессов или отделимость составляющих их элементов. Развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
Целью преподавания дисциплины является:
- воспитание достаточно высокой математической культуры, позволяющей самостоятельно расширять математические знания и проводить математический анализ прикладных инженерных задач;
- развитие логического и алгоритмического мышления, умения оперировать с абстрактными объектами и быть корректными в употреблении математических понятий, символов для выражения количественных и качественных отношений.
Задачи изучения дисциплины
Студенты должны
Знать
- основные понятия, теоремы и методы математической логики, теории множеств и теории графов, теории автоматов и теории алгоритмов;
- элементы математической лингвистики и теории формальных языков;
- основные методы решения комбинаторных задач, упрощения логических формул и переключательных схем;
- математические модели простейших систем и процессов в естествознании и технике;
Уметь
- применять математическую символику для выражения количественных и качественных отношений объектов;
- применять аналитические и численные методы дискретной математики;
Владеть
- комбинаторным и теоретико-множественным подходами к постановке и решению задач; навыками моделирования прикладных задач методами дискретной математики;
- навыками использования математических методов при решении прикладных задач.
Одним из итогов изучения дисциплины является формирование следующих компетенций:
общекультурных:
- способность использовать, обобщать и анализировать информацию, ставить цели и находить пути их достижения в условиях формирования и развития информационного общества (ОК-1);
- способность логически верно, аргументированно и ясно строить устную и письменную речь, владеть навыками ведения дискуссии и полемики (ОК-2);
- способность самостоятельно приобретать и использовать в практической деятельности новые знания и умения, стремится к саморазвитию (ОК-5);
профессиональных:
- способность использовать основные законы естественнонаучных дисциплин в профессиональной деятельности и эксплуатировать современное электронное оборудование и информационно-коммуникационные технологии в соответствии с целями образовательной программы бакалавра (ПК-3);
способность применять системный подход и математические методы в формализации решения прикладных задач (ПК-21).
Межпредметная связь
Для изучения данной дисциплины необходимы знания по элементарной математике в объеме школьного курса.
2 Объем дисциплины и виды учебной работы
Вид учебной работы
| Всего часов
(ЗЕ)
| Семестр
|
|
Общая трудоемкость дисциплины
|
(3)
|
(3)
|
Аудиторные занятия:
|
(1,5)
|
(1,5)
|
лекции
|
(0,5)
|
(0,5)
|
практические занятия (ПЗ)
|
(1)
|
(1)
|
Самостоятельная работа:
|
(1,5)
|
(1,5)
|
изучение теоретического курса (ТО)
|
(0,5)
|
(0,5)
|
расчетные задания (РЗ)
|
(0.5)
|
(0.5)
|
подготовка к тематическому тестированию и контрольным работам
|
(0.5)
|
(0.5)
|
Вид итогового контроля
| Зачет
| Зачет
|
Содержание дисциплины
Разделы дисциплины и виды занятий в часах
(тематический план занятий)
№ п/п
| Раздел дисциплины
| Лекции
часы
(ЗЕ)
| ПЗ
часы
(ЗЕ)
| СР
часы
(ЗЕ)
| Формируемые компетенции
|
| Элементы теории множеств
|
(0,17)
|
(0,38)
|
(0,44)
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
|
| Элементы математической логики
|
(0,17)
|
(0,38)
|
(0,67)
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
|
| Элементы теории графов и конечных автоматов
|
(0,17)
|
(0,22)
|
(0,39)
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
|
Содержание разделов и тем лекционного курса
Содержание разделов и тем лекционного курса
| Объем в часах
|
Ауд.
| Сам.
|
Модуль 1. Элементы теории множеств.
|
|
|
Раздел 1.1. Множества и отношения.
|
|
|
Понятие множества, способы задания. Операции над множествами, свойства операций, диаграммы Эйлера. Алгебра Кантора. Мощность множества, равномощные множества. Счетные и несчетные множества. Декартово произведение множеств. Соответствия. Функциональные, взаимно однозначные соответствия. Понятие отношения. Бинарные отношения на множестве. Способы задания и свойства бинарных отношений. Отношение эквивалентности и отношение порядка. Алгебраические системы. Характеристическая функция. Определение нечеткого множества. Операции над нечеткими множествами. Нечеткие отношения и операции над ними.
|
|
|
Раздел 1.2. Комбинаторика.
|
|
|
Перестановки и подстановки. Размещения и сочетания. Размещения и сочетания с повторением. Разбиения. Метод включений и исключений. Рекуррентные соотношения. Возвратные последовательности.
|
|
|
Модуль 2. Элементы математической логики.
|
|
|
Раздел 2.1. Алгебра высказываний.
|
|
|
Алгебра высказываний. Логические функции, таблицы истинности. Формулы алгебры логики. Разложение логической функции по переменным.
|
|
|
Раздел 2.2. Нормальные формы.
|
|
|
Совершенные дизъюнктивные нормальные формы (СДНФ). Булева алгебра логических функций, эквивалентные преобразования в ней. Принцип двойственности. Совершенные конъюнктивные нормальные формы (СКНФ).
|
|
|
Модуль 3. Элементы теории графов и конечных автоматов.
|
|
|
Раздел 3.1. Понятие графа.
|
|
|
Понятие графа (орграфа). Матрицы смежности и инцидентности графа. Изоморфизм графов. Теорема о сумме степеней вершин графа. Части графа. Маршруты, цепи, циклы в графах. Связные графы. Обходы в графах. Эйлеровы и гамильтоновы графы. Деревья.
|
|
|
Раздел 3.2. Конечные автоматы.
|
|
|
Полуавтоматы и автоматы. Представления с помощью графа и таблицы перехода. Композиция и декомпозиция.
|
|
|
Раздел 3.3. Элементы теории формальных языков
|
|
|
Подход с точки зрения грамматик, автоматов, полугрупп. Системы родства, социальные сети.
|
|
|
Практические занятия
№
п/п
| № раздела
дисциплины
| Темы занятий
| Трудоемкость
(часы)
|
1-2
| 1.1
| Понятие множества, способы задания. Операции над множествами, свойства операций, диаграммы Эйлера. Алгебра Кантора. Декартово произведение множеств. Соответствия. Функциональные, взаимно однозначные соответствия.
|
|
3-4
| 1.1
| Понятие отношения. Бинарные отношения на множестве. Способы задания и свойства бинарных отношений. Отношение эквивалентности и отношение порядка.
|
|
5-6
| 1.2
| Комбинаторика. Перестановки и подстановки. Размещения и сочетания. Размещения и сочетания с повторением. Разбиения. Метод включений и исключений. Рекуррентные соотношения. Возвратные последовательности.
|
|
| Модуль 1
| Промежуточный контроль (тематическое тестирование, контрольная работа).
|
|
8-10
| 2.1
| Алгебра высказываний. Логические функции, таблицы истинности. Формулы алгебры логики. Разложение логической функции по переменным.
|
|
11-13
| 2.2
| Совершенные дизъюнктивные нормальные формы (СДНФ). Булева алгебра логических функций, эквивалентные преобразования в ней. Принцип двойственности. Совершенные конъюнктивные нормальные формы (СКНФ). Минимизация в классе ДНФ.
|
|
| Модуль 2
| Промежуточный контроль (тематическое тестирование, контрольная работа).
|
|
| 3.1
| Понятие графа (орграфа). Матрицы смежности и инцидентности графа. Изоморфизм графов. Теорема о сумме степеней вершин графа. Части графа.
|
|
| 3.1
| Маршруты, цепи, циклы в графах. Связные графы. Обходы в графах. Эйлеровы и гамильтоновы графы. Деревья.
|
|
| 3.3-3.4
| Автоматы. Грамматики. Элементы теории формальных языков.
|
|
| Модуль 3
| Промежуточный контроль (тематическое тестирование, контрольная работа).
|
|
Лабораторные занятия
Лабораторные занятия учебным планом не предусмотрены.
3.5 Самостоятельная работа
Самостоятельная работа студентов по дисциплине «Дискретная математика» включает: самостоятельное изучение теоретического материала, выполнение расчетных заданий, подготовку к тематическому тестированию и контрольным работам. Распределение объема самостоятельной работы по видам, по семестрам, по модулям приведено в таблице.
| Изучение теоретического курса
(ТО), час
| Выполнение расчетных заданий
(РЗ), час
| Подготовка к тематическому тестированию и контрольным работам (ПТТ), час
| Всего,
час
|
Семестр 4
|
|
|
|
|
Модуль 1
|
| 6 (5 задач)
|
|
|
Модуль 2
|
| 8 (5 задач)
|
|
|
Модуль 3
|
| 4 (3 задачи)
|
|
|
Формы отчетности: ТО – конспект в объеме, указанном преподавателем; РЗ – письменная работа, оформленная в соответствии с требованиями, утвержденными на кафедре «Высшая математика-2»; ПТТ – результат тестирования или контрольной работы.
Расчетные задания выдаются преподавателем с указанием учебно-методической литературы. Основная учебно-методическая литература по выполнению расчетных заданий в соответствии с приведенным ниже списком литературы: [1, 2, 3, 4, 5, 6].
3.6 Структура и содержание модулей дисциплины
№
п/п
| Наименование модуля,
срок его реализации
| Перечень тем лекционного курса, входящих
в модуль
| Перечень практических занятий, входящих
в модуль
| Перечень самостоятельных видов работ, входящих в модуль, их конкретное наполнение
| Формируемые компетенции
| Умения
| Знания
|
| Модуль 1.
Элементы теории множеств.
Семестр 4.
| Темы: 1.1, 1.2.
| Практические занятия: 1-7.
| Самостоятельное изучение теоретического курса по темам: 1.1-1.2.
Выполнение расчетного задания.
Подготовка к тематическому тестированию и контрольной работе.
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
| Умение решать задачи по теории множеств: выполнять операции над множествами и отношениями, сравнивать мощности множеств.
| Знание основных определений и формул, теорем теории множеств.
|
| Модуль 2.
Элементы математической логики.
Семестр 4.
| Темы: 2.1, 2.2.
| Практические занятия: 8-14.
| Самостоятельное изучение теоретического курса по темам: 2.1-2.2.
Выполнение расчетного задания.
Подготовка к тематическому тестированию и контрольной работе.
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
| Умение решать задачи по математической логике: построение таблиц истинности, составление нормальных форм.
| Знание основных определений, формул и теорем алгебры логики.
|
| Модуль 3.
Элементы теории графов и конечных автоматов.
Семестр 4.
| Темы: 3.1, 3.2, 3.3.
| Практические занятия: 15-18.
| Самостоятельное изучение теоретического курса по темам: 3.1.- 3.3.
Выполнение расчетного задания.
Подготовка к тематическому тестированию и контрольной работе.
| ОК-1, ОК-2, ОК-5, ПК-3, ПК-21
| Умение решать задачи по теории графов, выполнять операции, определять основные специальные типы графов, представлять конечные автоматы при помощи графов.
| Знание основных определений, формул и теорем теории графов и конечных автоматов.
|
Учебно-методические материалы по дисциплине
4.1 Основная и дополнительная литература, информационные ресурсы
Основная литература
1. Гаврилов Г.Г., Сапоженко А.А. Сборник задач по дискретной математике. - М. Наука, 1977.
2. Горбатов В.А. Основы дискретной математики. - М. Высш. шк.,1986.
3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М. Энергия, 1988.
4. Кук Д., Бейз Г. Компьютерная математика. - М. Наука, 1990.
5. Лавров И. А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М. Наука, 1975.
6. Логинов Б. М. Лекции и упражнения по курсу «Введение в дискретную математику». Калуга. 1998.
7. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М., ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007. – 256 с.
Воспользуйтесь поиском по сайту: