Дискретная математика
Раздел 1
Элементы теории множеств
38 часов
Тема 1.1 Основы теории множеств
Длительность изучения темы: 6 часов
Основы теории множеств
Требования к студентам:
Знать:
основные принципы теории множеств.
Уметь:
решать задачи на подсчет количества элементов, доказывать теоретико-множественные соотношения аналитически и с помощью диаграмм Эйлера-Венна.
Общие понятия теории множеств. Язык теории множеств. Понятие «множество», элемент множества. Универсальное множество. Равные множества. Мощность множества.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Изображение множеств (круги Эйлера, диаграммы Венна).
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Графическое изображение множеств на диаграммах Эйлера-Венна; мощность множества.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Тема 1.2 Операции над множествами
Длительность изучения темы: 10 часов
Операции над множествами
Требования к студентам:
Знать:
виды, свойства операций над множествами.
Уметь:
выполнять операции над множествами, формулировать задачи логического характера и применять методы математической логики для их решения.
Теоретико-множественные операции и их связь с логическими операциями: объединение, пересечение, разность, дополнение множеств.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Свойство операций над множествами. Соответствия между множествами.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Отношения. Бинарные отношения и их свойства. Теория отображений.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Алгебра подстановок.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Операции над множествами.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Тема 1.3 Алгебра логики.
Длительность изучения темы: 12 часов
Алгебра логики.
Требования к студентам:
Знать:
основные формулы алгебры высказываний.
Уметь:
применять логические операции, формулы логики,
формализовывать высказывания , строить таблицы истинности для формул логики выполнять равносильные преобразования.,
Понятие высказывания. Простые и сложные высказывания. Логические величины, операции, выражения.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Выражение логических операций в естественном языке. Таблицы истинности и методика её построения.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Формулы логики.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Законы логики. Равносильные преобразования.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Решение задач на составление таблиц истинности; определение значения истинности высказываний; решение систем логических уравнений.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Формулы алгебры высказываний; упрощение формул логики.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Тема 1.4 Приложения алгебры высказываний
Длительность изучения темы: 2 часа
Приложения алгебры высказываний
Требования к студентам:
Знать:
формулы алгебры высказываний, методы минимизации алгебраических преобразований, применение алгебры высказываний в логико- математической практике.
Уметь:
используя законы логики, решать логические задачи различными способами.
Приложения алгебры высказываний к логико- математической практике. Прямая и обратная теоремы. Необходимые и достаточные условия.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Тема 1.5 Булевы функции
Длительность изучения темы: 8 часов
Булевы функции
Требования к студентам:
Знать:
основные понятия булевой функции.
Уметь:
приводить формулы логики к ДНФ, КНФ с помощью равносильных преобразований, минимизировать булевы функции с помощью равносильных преобразований, проверять булеву функцию
на принадлежность к основным замкнутым классам.
Понятие булевой функции. Основные замкнутые классы булевых функций. Способы задания ДНФ, КНФ.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Многочлен Жегалкина.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Основные классы функций. Полнота множества. Теорема Поста.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Приведение формул логики к ДНФ, КНФ с помощью равносильных преобразований; построение полинома Жегалкина.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Раздел 2
Логика предикатов
10 часов
Тема 2.1 Основные понятия, связанные с предикатами
Длительность изучения темы: 10 часов
Основные понятия, связанные с предикатами
Требования к студентам:
Знать:
основы языка и алгебру предикатов.
Уметь:
формулировать задачи логического характера и применять методы математической логики для их решения; находить область определения и истинности предиката; выполнять логические операции над предикатами; формализовывать предложения, используя предикаты и кванторы; строить отрицания к высказываниям, содержащим кванторы.
Предикат, язык логики предикатов. Основные тождества логики предикатов.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Логические операции над предикатами.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Кванторы. Виды кванторов.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Построение отрицаний к предикатам, содержащим кванторные операции.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Нахождение области истинности предикатов; операции над предикатами, равносильность предикатов; кванторные операции логики предикатов.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Раздел 3
Элементы теории графов
8 часов
Тема 3.1 Основы теории графов
Длительность изучения темы: 8 часов
Основы теории графов
Требования к студентам:
Требования к студентам:
Знать:
основные понятия теории графов.
Уметь:
определять основные характеристики графов и решать задачи с их применением.
Основные понятия теории графов. Виды графов: ориентированные и неориентированные графы
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Способы задания графов. Матрицы смежности и инциденций для графа.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Деревья.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
Решение задач по теории графов.
Вид занятия: Практ. занятие Длительность: 2 часа Материалы: Раздаточный материал Домашнее задание: упражнения
Раздел 4
Теория алгоритмов
3 часа
Тема 4.1 Элементы теории алгоритмов
Длительность изучения темы: 3 часа
Элементы теории алгоритмов
Требования к студентам:
Знать:
основы теории алгоритмов.
Умение:
составлять алгоритмы в виде машины Тьюринга и нормальных алгоритмов Маркова
Принцип работы машины Тьюринга.
Вид занятия: Лекция Длительность: 2 часа Материалы: Разработка Домашнее задание: упражнения
по пройденному материалу
Вид занятия: Контр. работа Длительность: 1 час Материалы: Раздаточный материал Домашнее задание: упражнения