SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Конечные автоматы в виде булевых формул и их оптимизация

Кузнецов Б. П.

д.т.н. МВАК МУФО (Великобритания, Испания, Россия, США, Шри-Ланка), декан ФВТИ

Документ в формате pdf (~570 кб)

Аннотация

Статья является второй главой учебного пособия для студентов, аспирантов и докторантов, изучающих курс информатики (компьютерных наук)

Конечные автоматы имеют разные формы представления. Одной из их моделей является булева формула, преимущественно используемая для автоматов с одним состоянием (для двоичных цифровых автоматов, функционирование которых в простейшем случае не зависит от использования дискретного времени).

Рассмотрены различные вычислительные модели булевых формул (БФ), алгоритмы взаимооднозначного преобразования форм представления БФ. Представлены статические и динамические критерии качества алгоритмов, выраженных БФ (показатели, методы расчета, оценочные формулы) и методы оптимизации БФ путем целенаправленных перестановок аргументов в структуре записи БФ, ориентированные на повышение качества алгоритмов по заданным критериям.

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