Статья

Название статьи ПРИМЕНЕНИЕ МАТРИЦЫ СМЕЖНОСТИ К РЕШЕНИЮ ЗАДАЧИ МИНИМИЗАЦИИ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ
Автор М.А. Трифонов
Рубрика РАЗДЕЛ IV. МАТЕМАТИЧЕСКИЕ МЕТОДЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
Месяц, год 06, 2012
Индекс УДК 519.85
DOI
Аннотация Рассматривается метод применения матрицы смежности из теории графов для решения задач минимизации дизъюнктивных нормальных форм. Целью применения метода является универсальность представления входных данных для последующей обработки эвристическими алгоритмами. Для большинства подобных задач на сегодняшний день нет алгоритмов, решающих их за полиномиальное время. Для некоторых задач существуют алгоритмы, имеющие сложность ниже экспоненциальной, но всѐ же достаточно высокую: например, для разложения числа на множители существуют алгоритмы, имеющие субэкспоненциальную временную сложность. Вследствие этого – несмотря на экспоненциальный рост вычислительных мощностей современных компьютеров – во многих прикладных задачах не удаѐтся найти точного решения за приемлемое время.

Скачать в PDF

Ключевые слова Оптимизация; дизъюнктивные нормальные формы; задачи дискретной оптимизации; графы, матрица смежности; оптимальное решение; булева функция.
Библиографический список 1. Адельсон-Вельский Г., Арлазаров В., Донской М. Программирование игр. – М.: Наука, 1978.
2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
3. Белозёрова А., Мельников Б. Применение комплекса эвристик в задаче составления схемы нуклидных превращений // Труды II Всеросс. науч. конф. «Методы и средства обработки информации». – М.: Изд-во МГУ, 2005. – C. 208-212.
4. Беллман Р. Динамическое программирование. – М.: ИЛ, 1960.
5. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. – М.: Наука, 1969.
6. Биркгоф Г., Барти Т. Современная прикладная алгебра. – СПб.: Лань, 2005.
7. Брауэр Э. Введение в теорию конечных автоматов. – М.: Радио и связь, 1987.

Comments are closed.