ВУЗ:
Составители:
Рубрика:
7.1.12 Минимизация ПФ и не полностью определенных ПФ
Виды дизъюнктивных нормальных форм (ДНФ) и конъюнктивных нор-
мальных форм (КНФ). Методы получения сокращенных ДНФ (КНФ) и их ми-
нимизации: использование булева куба, метод Блейка – Порецкого, метод
Квайна – Макласки, метод минимизирующих карт. Реализация булевых функ-
ций схемами из функциональных элементов.
7.1.13 Теорема о функциональной
полноте, примеры функционально пол-
ных базисов
Полнота и замкнутость. Важнейшие замкнутые классы. Теорема о полно-
те. Примеры функционально полных базисов.
7.1.14 Формальные языки и конечные автоматы
Основы теории формальных языков. Регулярные языки и выражения. Ко-
нечные автоматы Мили и Мура, их задание каноническими выражениями, ка-
ноническими таблицами и диаграммами. Теорема Клини
. Преобразование ав-
томата Мили в автомат Мура и автомата Мура в автомат Мили.
7.1.15 Минимизация конечных автоматов
Информативные деревья. Эквивалентность автоматов. Различимость со-
стояний автоматов. Минимизация автоматов.
7.1.16 Разрешимые и неразрешимые проблемы
Основные понятия о разрешимых и неразрешимых проблемах. Алгорит-
мы и разрешимость.
7.1.17 Схемы алгоритмов, схемы потоков данных
Схемы алгоритмов, схемы
потоков данных и использовании теории гра-
фов и теории конечных автоматов для их описания.
7.2 Форма проведения занятий
Лекции.
7.3 Материально-техническое обеспечение
Учебная литература, монографии, методические указания.
8 Практические занятия
Не запланированы.
9 Лабораторные занятия
9.1 Основные темы
9.1.1 Множества, операции над множествами.
9.1.2 Отношения, их представления и свойства.
9.1.3 Функции, их представления
и свойства.
9.1.4 Операции над алгебраическими структурами.
9.1.5 Графы и их основные свойства.
9.1.6 Маршруты, цепи, циклы, связность.
9.1.7 Задачи на графах. Паросочетания, раскраски и планарность
9.1.8 Деревья. Элементы комбинаторики.
7.1.12 Минимизация ПФ и не полностью определенных ПФ
Виды дизъюнктивных нормальных форм (ДНФ) и конъюнктивных нор-
мальных форм (КНФ). Методы получения сокращенных ДНФ (КНФ) и их ми-
нимизации: использование булева куба, метод Блейка – Порецкого, метод
Квайна – Макласки, метод минимизирующих карт. Реализация булевых функ-
ций схемами из функциональных элементов.
7.1.13 Теорема о функциональной полноте, примеры функционально пол-
ных базисов
Полнота и замкнутость. Важнейшие замкнутые классы. Теорема о полно-
те. Примеры функционально полных базисов.
7.1.14 Формальные языки и конечные автоматы
Основы теории формальных языков. Регулярные языки и выражения. Ко-
нечные автоматы Мили и Мура, их задание каноническими выражениями, ка-
ноническими таблицами и диаграммами. Теорема Клини. Преобразование ав-
томата Мили в автомат Мура и автомата Мура в автомат Мили.
7.1.15 Минимизация конечных автоматов
Информативные деревья. Эквивалентность автоматов. Различимость со-
стояний автоматов. Минимизация автоматов.
7.1.16 Разрешимые и неразрешимые проблемы
Основные понятия о разрешимых и неразрешимых проблемах. Алгорит-
мы и разрешимость.
7.1.17 Схемы алгоритмов, схемы потоков данных
Схемы алгоритмов, схемы потоков данных и использовании теории гра-
фов и теории конечных автоматов для их описания.
7.2 Форма проведения занятий
Лекции.
7.3 Материально-техническое обеспечение
Учебная литература, монографии, методические указания.
8 Практические занятия
Не запланированы.
9 Лабораторные занятия
9.1 Основные темы
9.1.1 Множества, операции над множествами.
9.1.2 Отношения, их представления и свойства.
9.1.3 Функции, их представления и свойства.
9.1.4 Операции над алгебраическими структурами.
9.1.5 Графы и их основные свойства.
9.1.6 Маршруты, цепи, циклы, связность.
9.1.7 Задачи на графах. Паросочетания, раскраски и планарность
9.1.8 Деревья. Элементы комбинаторики.
