Algorithms for constructing the shortest allowable partitions of finite sets both for any monotonic and nonmonotonic two components allowing functions are presented in the paper. The synthesis problem for minimal complexity PLD-circuits and the composition problem of an electronic circuit into the minimal number of cells are good examples for the application of these algorithms.
Download file
Counter downloads: 85
- Title ALGORITHMS FOR CONSTRUCTING THE SHORTEST ALLOWABLE PARTITIONS OF FINITE SETS
- Headline ALGORITHMS FOR CONSTRUCTING THE SHORTEST ALLOWABLE PARTITIONS OF FINITE SETS
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(4)
- Date:
- DOI
Keywords
компоновка , синтез , кратчайшее допустимое разбиение , метод сокращенного обхода дерева поиска Authors
References
Андреева Л. Н., Оранов А. М. Оценки погрешности двух приближенных алгоритмов разбиения // Изв. РАН. Теория и системы управления. 1999. №1. С. 89-93.
Оранов A.M. О сложности задачи кратчайшего допустимого разбиения // Всесибирские чтения по математике и механике: Материалы Междунар. конф. Томск: Изд-во Том. ун-та, 1997. Т. 1. Математика. С. 161-162.
Андреева Л. Н., Оранов A.M. О сложности некоторых задач разбиения // Изв. РАН. Теория и системы управления. 1997. №2. С. 114-116.
Оранов А. М. Метод построения дискретных схем на базе комплексных программируемых логических устройств // Вестник Томского госуниверситета. Приложение. 2002. №1(II). С. 102-107.
Оранов А. М. Алгоритм синтеза цифровых схем в базисе неоднородных ПМЛ // Моделирование интеллектуальных процессов проектирования и производства: Материалы Междунар. науч.-технич. конф. (10-12 ноября 1998 года, г. Минск). Минск: Институт технической кибернетики НАН Беларуси, 1998. С. 214-215.
Оранов А. М. К синтезу комбинационных схем в базисе ПЛИС // Автоматика и вычислительная техника. 1996. №1. С. 27-35
Оранов А. М. Алгоритм синтеза дискретных схем в базисе программируемых функциональных блоков // Вестник Томского госуниверситета. Приложение. 2004. №9. С. 240-244.
Агибалов Г. П., Оранов А. М. Покрытие логических схем модулями некоторых серийных систем // Кибернетика. 1986. №2. С. 34-38.
Агибалов Г. П., Оранов А. М. Алгоритмы покрытия схем свободными модулями // Автоматика и вычислительная техника. 1977. №4. С. 15-16.
Оранов А. М., Андреева Л. Н. Алгоритм минимального разбиения некоторого набора объектов // Автоматика и вычислительная техника. 1993. №2. С. 27-35.
Оранов А. М., Андреева Л. Н. Алгоритм синтеза и компоновки одноярусных схем в некоторых базисах // Автоматика и вычислительная техника. 1992. №5. С. 57-63.
К'ристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.
Оранов А. М., Андреева Л. Н. Алгоритм минимального разбиения системы множеств // Автоматика и вычислительная техника. 1992. №2. С. 37-44.
Андреева Л. Н., Оранов А. М. Алгоритмы построения кратчайших немонотонно допустимых разбиений конечных множеств // Вестник Томского госуниверситета. Приложение. 2003. №6. С. 188-192.
Андреева Л. Н., Оранов А. М. Модифицированный алгоритм построения кратчайших монотонно допустимых разбиений конечных множеств // Автоматизация проектирования дискретных систем: Материалы четвертой Междунар. науч.-технич. конф. (14-16 ноября 2001 года, г. Минск). Минск: Институт технической кибернетики НАН Беларуси, 2001. Т.З. С. 150-157.
Оранов А. М. Алгоритм построения кратчайших монотонно допустимых разбиений конечных множеств // Автоматизация проектирования дискретных систем: Материалы второй Междунар. конф. (12-14 ноября 1997 года, г. Минск). Минск: Институт технической кибернетики НАН Беларуси, 1997. Т. 3. С. 228-231.
Агибалов Г. П., Беляев В. А. Технология решения комбинаторно-логических задач методом сокращенного обхода дерева поиска. Томск: Изд-во Том. ун-та, 1981. 125 с.
ALGORITHMS FOR CONSTRUCTING THE SHORTEST ALLOWABLE PARTITIONS OF FINITE SETS | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2009. № 2(4).
Download full-text version
Download fileCounter downloads: 262