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

Стр.

1. Паспорт рабочей программы учебной дисциплины

4

2. Структура и примерное содержание учебной дисциплины

5

3. Условия реализации программы учебной дисциплины

11

4. Контроль и оценка результатов освоения учебной дисциплины

12

Вид учебной работы

Объем часов

Максимальная учебная нагрузка (всего)

114

Обязательная аудиторная учебная нагрузка (всего)

76

в том числе

- теоретические занятия

44

- практические занятия

30

- контрольные работы

2

Самостоятельная работа студента (всего)

38

в том числе

- систематическая проработка конспектов занятий, учебной литературы

10

- выполнение домашней работы

18

- подготовка  рефератов

10

Итоговая аттестация в форме контрольной работы

Наименование разделов и тем

Содержание учебного материала, лабораторные и практические работы, самостоятельная работа студентов

Объем часов

Уровень освоения

1

2

3

4

Введение

4

Введение.

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

2

2

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

Самостоятельная работа студентов

Подготовка рефератов по теме.

2

Раздел 1.

Множества

30

Тема 1.1.

Общие понятия теории множеств.

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

2

2

Понятие множества. Способы задания. Сравнение множеств. Подмножества. Универсальное множество. Изображение множеств. Равенство множеств. Понятие мощности.

Самостоятельная работа студентов

Выполнение домашнего задания по теме 1.1

1

Тема 1.2.

Основные операции над множествами.

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

2

2

Основные операции над множествами: пересечение, объединение, разность, дополнение, симметрическая разность. Свойства операций над множествами. Декартово произведение.

Практические занятия

Операции на множествах.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 1.2

1

Тема 1.3.

Соответствия между множествами. Отображения.

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

2

2

Соответствие между множествами. Образ и прообраз. Множество значений и область определения соответствия. Понятие отображения. Задание отображений. Виды отображений. Композиция функций.  Тождественное отображение.

Практические занятия

Отображения: их представление и свойства.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 1.3

2

Тема 1.4.

Классификация множеств.  Мощность множества.

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

2

2

Мощность множества. Эквивалентные множества. Классификация множеств в зависимости от их мощности. Булеан множества. Основная теорема о конечных множествах. Множество мощности континуума. Сравнение множеств.

Самостоятельная работа студентов

Подготовка рефератов по теме «Математические и общелогические парадоксы теории множеств»

2

Тема 1.5.

Отношения. Бинарные отношения и их свойства.

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

2

2

Понятие отношения на множестве. Бинарные отношения. Примеры бинарных отношений. Свойства бинарных отношений. Отношение эквивалентности. Отношение толерантности. Отношение порядка. Функциональные отношения.

Практические занятия

Способы задания отношений. Свойства отношения.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 1.5

2

Тема 1.6.

Элементы комбинаторики.

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

2

3

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

Практические занятия

Решение комбинаторных задач.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 1.6

2

Раздел 2.  Графы.

20

Тема 2.1.

Основные понятия и определения графа и его элементов

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

2

2

Понятие графа. Виды графов. Элементы графов, маршруты, циклы. Ориентированные и неориентированные графы. Пути и цепи, контуры и циклы в графе. Изоморфные графы. Планарные и плоские графы. Теорема Эйлера.

Самостоятельная работа студентов

Подготовка рефератов по теме «Исторические задачи о графах»

2

Тема 2.2.

Операции над графами.

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

2

2

Операции над графами: объединение и пересечение. Подграфы. Кольцевая сумма.

Практические занятия

Операции над графами.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 2.2

2

Тема 2.3.

Деревья. Лес. Бинарные деревья.

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

2

2

Деревья и их свойства. Лес. Упорядоченное дерево. Бинарные деревья.

Практические занятия

Ориентированные, упорядоченные и бинарные деревья. Обходы бинарных деревьев.

2

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 2.3

1

Тема 2.4.

Способы задания графа. Изоморфные графы.

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

2

2

Способы задания графов. Изоморфные графы. Матрица инцидентности. Матрица смежности.  

Практические занятия

Способы задания графов.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 2.4

1

Раздел 3.

Математическая логика.

20

Тема 3.1.

Суждения как форма мышления. Простые высказывания.

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

2

2

Суждение. Высказывание. Примеры простых высказываний. Формализация высказываний.

Самостоятельная работа студентов 

Подготовка рефератов по теме.

2

Тема 3.2.

Булевы функции.

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

2

2

Логические функции. Равенство функций. Формулы. Булевы функции одной переменной. Булевы функции двух переменных. Таблицы истинности. Симметрические функции. Стрелка Пирса. Штрих Шеффера. Импликации. Способы задания булевых функций.

Практические занятия

Булевы функции и логические исчисления.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 3.2

1

Тема 3.3.

Сложные высказывания.

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

2

2

Образование сложных высказываний. Логические операции над сложными высказываниями. Таблицы истинности логических операций. Словарь перевода на язык алгебры логики. Формулы алгебры логики.

Практические занятия

Операции над сложными высказываниями.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 3.3

2

Тема 3.4.

Основные классы функций. Полнота множества функций.

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

2

2

Функциональная замкнутость. Функционально полные системы функций. Теорема Поста. Критерии функциональной полноты булевых функций.

Практические занятия

Исследование полноты системы логических функций (использование теоремы Поста).

2

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 3.4

1

Раздел 4.

Формальные системы и умозаключения. Логика предикатов.

22

Тема 4.1.

Формальные системы. Исчисление высказываний.

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

2

2

Понятие о формальных системах. Представление системы. Средства, аксиомы и правила вывода. Интерпретация формальной теории. Требования, предъявляемые к формальным системам. Исчисление высказываний.

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 4.1

2

Тема 4.2.

Логика предикатов.

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

2

2

Определение исчисления предикатов как формальной теории. Понятие предиката. Язык логики предикатов. Множество истинности предиката. Логические операции над предикатами.

Практические занятия

Логические операции над предикатами.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 4.2

2

Тема 4.3.

Умозаключения как форма мышления. Дедуктивные умозаключения и их виды.

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

2

2

Умозаключение. Посылки. Заключение Вывод. Виды умозаключений: индуктивные и дедуктивные; достоверные и вероятностные. Дедуктивные умозаключения и их виды.

Практические занятия

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

2

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 4.3

2

Тема 4.4.

Индуктивные умозаключения и их виды. Метод математической индукции.

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

2

3

Индукция. Виды индукции. Метод математической индукции.

Практические занятия

Применение метода математической индукции к решению задач.

2

Самостоятельная работа студентов

Выполнение домашнего задания по теме 4.3

2

Раздел 5.

Конечные автоматы.

16

Тема 5.1.

Определение конечных автоматов.

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

2

2

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

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 5.1

2

Тема 5.2.

Способы задания конечных автоматов.

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

2

2

Табличный, графический и аналитический способы задания конечных автоматов.

Практические занятия

Способы задания конечных автоматов.

2

Самостоятельная работа студентов

Проработка конспекта и учебной литературы по вопросам к теме 5.2

2

Тема 5.3.

Общие задачи теории автоматов.

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

2

2

Три основные задачи теории автоматов: задача синтеза, задача анализа и задача декомпозиции. Перспективы применения теории конечных автоматов.

Практические занятия

Построение автоматов, распознающих заданные свойства.

2

Самостоятельная работа студентов

Подготовка рефератов по теме 5.3

2

Итоговая контрольная работа.

2

3

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

2

Итоговая контрольная работа по изученным темам.

ВСЕГО:

114

Результаты обучения (освоенные умения, усвоенные знания)

Формы и методы контроля и оценки результатов обучения

Умения:

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

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

- применять законы алгебры логики;

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

- определять типы графов и давать их характеристики;

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

- строить простейшие автоматы.

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

Знания:

- основные понятия и приемы дискретной математики;

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

- логические операции, формулы логики, законы алгебры логики;

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

- основные классы функций, полнота множества функций, теорема Поста;

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

- основные понятия теории множеств, теоретико-множествнные операции и их связь  с логическими операциями;

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

- логика предикатов, бинарные отношения и их виды; элементы теории отображений и алгебры подстановок;

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

- метод математической индукции; алгоритмическое перечисление основных комбинаторных объектов;

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

- основные понятия теории графов, характеристики и виды графов;

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

- элементы теории автоматов.

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