ВЫЧИСЛЕНИЕ АВТОМАТНОЙ СЛОЖНОСТИ БУЛЕВЫХ ФУНКЦИЙ КАК ЗАДАЧА ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

  • Николай Иванович Крайнюков Тольяттинский государственный университет
  • Светлана Валентиновна Пивнева Тольяттинский государственный университет
Ключевые слова: булевы функции, недетерминированные конечные автоматы, конечно-автоматная сложность, дизъюнктивная нормальная форма

Аннотация

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

Литература

1. Мельников Б.Ф. Эвристики в программировании недетерминированных игр. – «Программирование» (Известия РАН), 2001, №5, с.63–80.
2. Пивнева С. В. Моделирование задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Вектор науки. – № 3 (13). – Тольятти : Тольят. гос. ун-т, 2010. – С. 31-34.
3. Пивнева С. В. Программная реализация задач дискретной оптимизации / С. В. Пивнева, М. А. Трифонов // Некоторые вопросы математического моделирования дискретных систем : сб. науч. тр. – Тольятти : ТГУ, 2011. – С. 210-219.
4. Поваров Г. Конечные трансдьюсеры и недетерминированная сложность регулярного языка. Известия вузов. Математика. 2010, №6, С.23-31.
5. Хопкрофт Дж., Мотвани Р., Ульман Дж.. Введение в теорию автоматов, языков и вычислений. 2-е изд.. : Пер. с англ. – М. : Издательский дом «Вильямс», 2002. – 528 с. : ил. – Парал. тит. англ.
6. Шуткин Ю. Асимптотически оптимальная реализация булевых функций информационными графами. Дискрет. матем., 2011, 23:4, С.80–102.
7. Мельников Б. Мультиэвристический подход к задачам дискретной оптимизации. Кибернетика и системный анализ (НАН Украины), 2006, № 3, С.32–42.
Выпуск
Раздел
Естественные науки

Наиболее читаемые статьи этого автора (авторов)

1 2 > >>