Составители:
Рубрика:
3
Предисловие
В связи с широким внедрением вычислительной техники необходимо
знать основные принципы, которые используются при подготовке решения
задач на ЭВМ (формализация задач, ее дискретизация, составление логических
выражений и т.д.)
Изучив раздел «Основы дискретной математики» студенты смогут на
предварительном этапе так подготовить задачу, чтобы свести к минимуму как,
время решения задач, так и объем используемой оперативной памяти ЭВМ.
Рабочая программа
(объем курса 14 часов)
Раздел 1. Элементы теории графов
. (4 часа)
Определение графа. Геометрическая реализация графа. Основные
понятия и определения теории графов. Классификация задач теории графов.
Задача о минимальном числе аварий. Задача о кратчайшем пути. Алгоритм
Дейкстры.
Раздел 2. Элементы алгебры логики.
(6 часов)
Высказывания, значение истинности высказывания, эквивалентные
высказывания. Понятие двоичной переменной и булевой функции.
Элементарные функции алгебры логики, сложные функции. Формулы Мограна.
Совершенная дизъюнкция и конъюнкция нормальной формы. Полные
системы функций.
Построение минимальных ДНФ и КНФ.
Применение алгебры логики к анализу и синтезу контактных схем.
Раздел 3. Формальные языки и автоматы.
(4 часа).
Основные понятия и определения формальных языков. Изображение
языков в виде графа. Понятия и типы дискретных автоматов. Задачи
математического исследования дискретных автоматов:
1.анализ поведения ДА.
2. дискретные автоматы с памятью.
3. применение алгебры логики к анализу дискретных автоматов.
Тематический план лекций
Лекция 1.понятие Булевой функции. Элементарные и сложные функции
алгебры логики. Формулы Моргана. (2 часа)
