Logo-do Home
Дистанционное обучение в СумГУ: дисциплины » Дискретна математика

1.1 Мета і завдання викладання дисципліни

Мета викладання дисципліни - ознайомити студентів з основними розділами курсу: алгебра логіки, теорія множин, алгоритмів , графів автоматів. Завдання викладача полягає в навчанні студентів практичному використанню придбаних знань.

Оволодіння теоретичним матеріалом навчить студентів знаходити мінімальні ДНФ, аналізувати системи логічних функцій , розв’язувати задачі на транспортних мережах, мінімізувати автомати.

1.2 Місце дисципліни у навчальному процесі

Забезпечуючі навчальні дисципліни: інформатика і математика в обсязі середньої школи. Дискретна математика логічно зв’язана з дисциплінами: ‘персональні комп’ютери’, ‘алгоритмічні мови’, ‘теорія алгоритмів та математична логіка’, архітектура ЕОМ

Автор(и)

Маслова Зоя Іванівна, кандидат технічних наук, доцент кафедри інформатики, працює за напрямом технічна кібернетика.

Базові дисципліни:

Дисципліна є базовою для:


Содержание дисциплины Множества и операции над ними
    Информационный блок
   Способы задания множеств
   Операции над множествами
Логика
    Информационный блок
   Логические функции
     Логические функции одной переменной
     Логические функции от двух переменных
   Булева алгебра
     Разложение функций по переменным СДНФ
     Булева алгебра функций и эквивалентные преобразования в ней
     Основные свойства булевых операций
     Упрощение формул
     Приведение к ДНФ (в том числе СДНФ)
     Приведение к конъюнктивной нормальной форме (КНФ)
     Нахождение минимальной ДНФ методом Квайна
   Полнота и замкнутость
     Функционально полные системы (ф.п.с.)
     Двойственность
     Алгебра Жегалкина и линейные функции
     Замкнутые классы. Монотонные функции
     Две теоремы о функциональной полноте
Графы
    Информационный блок
   Основные понятия и операции
     Графы, их вершины, ребра и дуги
     Изображение графов
     Матрица инцидентности и список ребер
     Матрица смежности графа
   Маршруты, цепи и циклы
     Определения
     Связные компоненты графа
     Расстояния
   Задача о кратчайшем пути
     Постановка задачи
     Нахождение кратчайшего пути в графе с ребрами единичной длины
     Нахождение кратчайшего пути в графе c ребрами произвольной длины
   Транспортные сети
     Основные понятия
     Задача о наибольшем потоке
       Нахождение полного потока
       Нахождение наибольшего потока
   Транспортная задача
Автоматы
    Информационный блок
   Автоматы
   Изоморфизм и эквивалентность автоматов
   Минимизация автоматов
   Частичные автоматы и их минимизация
   Распознавание множеств автоматами
     Автоматы Мура
   Программная реализация логических функций и автоматов