 |
Учебно-методические материалы по дисциплине
|
|
|
|
Федеральное государственное автономное образовательное
Учреждение высшего профессионального образования
«Сибирский федеральный университет»
УТВЕРЖДАЮ
Директор института
Фундаментальной подготовки
_____________ В.М. Журавлев
«_____» _____________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 с.
|
|
|
