Preview

Информатика

Расширенный поиск

АЛГОРИТМ ПОКРЫТИЯ РАЗРЕЖЕННЫХ БУЛЕВЫХ МАТРИЦ

Аннотация

Предлагается алгоритм решения задачи о наименьшем покрытии множества, известной в литературе как задача нахождения кратчайшего столбцового покрытия булевой матрицы. Сравнивается эффективность разработанного алгоритма, реализованного в программе Tie, c эффектив­ностью алгоритма программы Espresso и алгоритма GANP. Приводятся результаты экспериментально-статистических испытаний алгоритма на  стандартных примерах серий Benchmark, CLR и Stein, а также на псевдослучайных системах булевых функций.

Об авторе

П. В. Леончик
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

1. Сапоженко, А.А. Минимизация булевых функций в классе дизъюнктивных нормальных форм / А.А. Сапоженко, И.П. Чухров // Итоги науки и техники. – М., 1987. – Т. 25. – С. 68–116.

2. Леончик, П.В. Минимизация систем булевых функций в классе дизъюнктивных нормальных форм / П.В. Леончик // Информатика. – 2006. – № 1(9). – C. 88–96.

3. Закревский, А.Д. Основы логического проектирования. Комбинаторные алгоритмы дискретной математики. Кн. 1 / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004.

4. Yang, S. Logic synthesis and optimization benchmarks user guide version 3.0. Technical Report / S. Yang. – Microelectronics Center of North Carolina, 1991.

5. Закревский, А.Д. Генераторы псевдослучайных логико-комбинаторных объектов / А.Д. Закревский, Н.Р. Торопов // Логическое проектирование: сб. науч. тр. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – С. 49–63.

6. Beasley, J.E. OR-Library: Distributing test problems by electronic mail / J.E. Beasley // Journal of the Operational Research Society. – 1990. – Vol. 41, № 11. – P. 1069–1072.

7. Logic Minimization Algorithms for VLSI synthesis / R.K. Brayton [et al.]. – Boston: Kluwer Academic Publishers, 1984.

8. ESPRESSO-II: a New Logic Minimizer for PLA / R.K. Brayton [et al.] // IEEE Pros. Custom Integrated Circuits Conf. – Rochester, 1984.

9. Rudel, R. Multiple-Valued Minimization for PLA Optimization / R. Rudel, A. Sangiovanni Vincentelli // IEEE Trans. Computer-Aided Des. – 1987. – Vol. CAD-6, № 5. – Р. 727–751.

10. Еремеев, А.В. Генетический алгоритм для задачи о покрытии / А.В. Еремеев // Дискретный анализ и исследование операций. – 2000. – Сер. 2. – Т. 7, № 1. – С. 47–60.


Рецензия

Для цитирования:


Леончик П.В. АЛГОРИТМ ПОКРЫТИЯ РАЗРЕЖЕННЫХ БУЛЕВЫХ МАТРИЦ. Информатика. 2007;(2(14)):53-61.

Просмотров: 537


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)