МОДИФИЦИРОВАННЫЙ АЛГОРИТМ МИНИМИЗАЦИИ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ
https://doi.org/10.35266/1999-7604-2023-2-87-91
Аннотация
В статье изложен алгоритм, позволяющий осуществить направленный перебор для поиска минимальной дизъюнктивной нормальной формы с использованием лексикографического порядка.
Об авторе
А. Г. Назин
Сургутский государственный университет, Сургут
Россия
Россия
кандидат физико-математических наук, доцент
E-mail: nazin_ag@surgu.ru
Список литературы
1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / пер. с англ. Е. В. Левнера, М. А. Фрумкина. М. : Мир, 1982. 416 с.
2. Андреев А. Е. К проблеме минимизации дизъюнктивных нормальных форм // Доклады Академии наук СССР. 1984. Т. 274, № 2. С. 265–269.
3. McGeer P., Sanghavi J., Brayton R. et al. ESPRESSOSIGNATURE: A new exact minimizer for logic functions. In: 30th ACM/IEEE Design Automation Conference, Dallas, TX, USA. 1993. p. 618‒624.
4. Hong S. J., Cain R. G., Ostapko D. L. МINI: A heueristic approach for logic minimization. IBM Journal Research and Development. 1974;18(5):443–458.
5. Hlavička J., Fišer P. BOOM – a Heuristic Boolean Minimizer. In: IEEE/ACM International Conference on Computer Aided Design ICCAD-2001, San Jose, California (USA), November 4–8, 2001. p. 439–442.
6. Brayton R. K., Hachtel G. D., McMullen C. et al. Logic minimization algorithms for VLSI synthesis. Hingham, MA: Kluwer Academic Publishers; 1984. 194 p.
7. Hachtel G. D., Somenzi F. Logic synthesis and verification algorithms. Boston, MA: Kluwer Academic Publishers; 1996. 564 p.
8. Журавлев Ю. И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // Дискретная математика и математические вопросы кибернетики / под общ. ред. С. В. Яблонского, О. Б. Лупанова. Т. 1. М. : Наука, 1974. 312 с.
9. Стрыгин В. З. Полиномиальный алгоритм минимизации случайных («почти всех») булевых функ-ций. М. : ЦАГИ, 1992. 8 с.
10. Назин А. Г. Алгоритм получения всех минимальных дизъюнктивных нормальных форм из сокращенной дизъюнктивной нормальной формы с использованием лексикографического порядка // Исследовано в России. 2002. С. 942–947. URL: https://cyberleninka.ru/article/n/algoritm-polucheniya-vseh-minimalnyh-dizyunk-tivnyh-normalnyh-form-iz-sokraschyonnoy-dizyunk-tivnoy-normalnoy-formy-s-ispolzovaniem (дата обращения: 01.03.2023).
11. Колдуэлл С. Х. Логический синтез релейных устройств / пер. с англ. Г. К. Москатова, А. Д. Таланцева ; под ред. М. А. Гаврилова. М. : Изд-во иностр. лит., 1962. 740 с.
Рецензия
Для цитирования:
Назин А.Г. МОДИФИЦИРОВАННЫЙ АЛГОРИТМ МИНИМИЗАЦИИ ДИЗЪЮНКТИВНОЙ НОРМАЛЬНОЙ ФОРМЫ. Вестник кибернетики. 2023;22(2):87-91. https://doi.org/10.35266/1999-7604-2023-2-87-91
For citation:
Nazin A.G. A MODIFIED ALGORITHM FOR MINIMIZING THE DISJUNCTIVE NORMAL FORM. Proceedings in Cybernetics. 2023;22(2):87-91. (In Russ.) https://doi.org/10.35266/1999-7604-2023-2-87-91
Просмотров:
149
Послать статью по эл. почте 