Приближенные методы решения таблиц покрытий для синтеза комбинационных схем из ПЛМ
Диссертация
Задача покрытия относится к классу переборных задач, процесс поиска решения которых носит комбинаторный характер. Тривиальный способ их решения заключается в полном переборе всех возможных вариантов, из которых выбирается решение. Полный перебор гарантирует получение оптимального решения. Этот простой метод, несмотря на то, что множество, среди элементов которого ищется решение, конечно… Читать ещё >
Список литературы
- Кузюрин H.H. Асимптотическое исследование задачи о покрытии. — Б кн.: Проблемы кибернетики, вып.37, М.: Наука, 1980, с.19−56.
- Закревский А.Д., Островский В. И. Оптимизация поиска кратчайшего покрытия. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.84−95.
- Закревский А.Д. О приближенных методах ранения логических задач. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.2−13.
- Карп P.M. Сводимость комбинаторных проблем. В кн.: Кибернетический сборник (новая серия), вып.12. М- Мир, 1975, с.16−38.
- Корбут A.A., Финкельштейн Ю. Ю. Дискретное программирование. М.: Наука, 1969.
- Каспанов Э.Ш. Глубина кронекерова произведения /0,1/-мат-риц. В кн.: Дискретный анализ, вып-22. Новосибирск, 1973, с.34−38.
- Кристофидес Н. Теория графов. Алгоритмический подход. -М., :Мир, 1978.
- Кузюрин H.H. О минимальных покрытиях и максимальных упаковках (к-1) — подмножеств к-подмножествами. В сб.: Матем, заметки, 1977, т.21, Ju 4, с.565−571.
- Кузюрин H.H. Об асимптотической сводимости покрытий и упаковок в единичном п-мерном кубе. 1У Всесоюзная конференция по проблемам теоретической кибернетики (тезисы докладов). Новосибирск, 1977, с.173−174.
- Кук С. А. Сложность процедур вывода теорем. В кн.: Кибернетический сборник (новая серия), вып.12. М.: Мир, 1975, с.5−15.
- Леонтьев В.К. Верхняя оценка cL -глубины (0,1)-матриц. -В сб. :матем.заметки, 1974, т.15, $ 3, с.421−429.
- Маматов Ю.А. Асимптотические свойства кратчайших покрытий. ДАН СССР, 1976, т.229, & 4, с.801−803.
- Нигматулин Р.Г. Метод наискорейшего спуска в задачах на покрытие. В сб.: Вопросы точности и эффективности алгоритмов (труды симпозиума), вып.5, Киев, 1969, с.116−126.
- Роджерс К. Укладки и покрытия. М.: Мир, 1968.
- Асратян A.C., Кузюрин H.H., Сапоженко A.A. Обзор некоторых результатов по задачам о покрытии. В кн.: Методы дискретного анализа в решении комбинаторных задач, вып.30. Новосибирск, 1977, с.46−75.
- Тараканов В.Е. О минимальной глубине одного класса (0,1-матриц. Матем. сборник, 1968, т.75(117), № 1, с.4−14.
- Тараканов В.Е. Максимальная глубина произвольных классов (0,1)-матриц и некоторые её применения. Матем. сборник, 1973, т.92(134), с.472−490.
- ГэриМ., Джонсон Д. Вычислительные машины и труднореша-емые задачи. М.: Мир, 1982.
- Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980, 476 с.
- Закревский А.Д. Нахождение множества безызбыточных покрытий. Труды СФТИ, вып.48, 1966.
- Новоселов А.Г. Нахождение кратчайших покрытий. Труды СФТИ, вып.48, 1966.
- Закревекий А.Д. О сокращении переборов при решении некоторых задач синтеза дискретных автоматов. Изв. ВУЗов, Радиофизика, т.7, № I, 1964.
- Алексеев А.Г. Алгоритм решения задачи о покрытии. Изв. АН СССР, Техническая кибернетика, № 5, 1980, с.12−16.
- Фролов А.Б., Чернова Т. В. Алгоритмы оптимизации приведенных покрытий. Логическое управление, M., 1981, $ 3.
- Адельсон-Вельский Г. М., Кузнецов О. П. Дискретная математика для инженера. М.: Энергия, 1980, 344 с.
- Гаврилов М.А., Девятков В. В., Пупырев Е. И. Логическое проектирование дискретных автоматов. М.: Наука, 1977, 351 с.
- Яблонский C.B. Об алгоритмических трудностях синтеза минимальных контактных схем. В кн.: Проблемы кибернетики, вып.2, М.: Физматгиз, 1959, с. ПО-138.
- Журавлев Ю.И. Локальные алгоритмы вычисления информации.- Кибернетика, 1965, В I.
- Журавлев Ю.И. Локальные алгоритмы вычисления информации.- Кибернетика, 1966, № 2.
- Коршунов А.Ф. Верхняя оценка сложности кратчайших ДШ> для почти всех булевых функций. Кибернетика, 1969, № 6,c.I-II.
- Сапоженко А.А. О сложности ДЩ, получаемых с помощью градиентного алгоритма. В кн.: Дискретный анализ, вып.21. Новосибирск, 1972.
- Нигматулин Р.Г. О покрытии графа рёбрами. В кн.: Проблемы кибернетики, 1969, Л 21.
- Журавлев Ю.И. Теоретико-множественные методы в алгебре логики. В кн.: Проблемы кибернетики, 1962, вып.8.
- Закревекий А.Д. Логический синтез каскадных схем.1. М.: Наука, 1981, 414 с.
- Миллер Б. Теория переключательных схем. М.: Наука, 1970, т.1, 416 с-.
- Миллер В. Теория переключательных схем. М.: Наука, 1971, т.2, 304 с.
- Журавлев Ю.И. 0 несущественных переменных не всюду определенных функций алгебры логики. В кн.: Дискретный анализ, вып.Г. Новосибирск, 1963.
- Журавлев Ю.И. Об алгоритмах, выделения совокупностей не всюду определенных функций алгебры логики. В кн.: Проблемы кибернетики, вып.II. М., 1964, с.221−275.
- Агибалов Г. П. Минимизация числа аргументов булевых функций. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.96−100.
- Розенфельд Т.К. Минимизация числа входных и выходных переменных частичных булевых функций. В кн.: Материалы семинара по кибернетике. АН Молд. ССР, Кишинев, 1974, вып.68,с.10−18.
- Гриншпон М.С. Критерий выбора потенциально несущественных аргументов, исключаемых из неполностью определенной логической функции. А и ВТ, 1975, № 5, с.17−21.
- Рейлинг Г. Программируемые логические матрицы новый элемент сизтем обработки данных. — Электроника, 1974, № 16, с.38−46.
- Баранов С.И., Синев В. Н. Программируемые логические матрицы в цифровых системах. Зарубежная радиоэлектроника, 1979, * I, с.65−82.
- Логические матрицы, программируемые в условиях эксплуатации. Электроника, 1975, № 6, с.89−90.
- Ачасова С.М., Бандман О. Л. Матричный метод синтеза комбинационных схем и логических преобразователей конечных автоматов. Изв. АН СССР. Техническая кибернетика, 1975, № 6, с.99−105.
- Двинский Б.И. Реализация микропрограммного автомата на БИС. Электронная техника. Серия 3, Микроэлектроника, 1974, вып.5 (55).
- Баранов С.И. Автоматы на матрицах. В кн.: Оптимизация дискретных устройств. Материалы семинара. Л., 1976, с.5−26.
- Баранов С.И., Синев В. Н. Синтез автоматов на црограмми-руемых логических матрицах. УС и M, 1979, № 2, с.58−64.
- Якубайтис Э. А. Буль Е.С., Ланге Э. Э. и др. Методика синтеза асинхронных автоматов на ШМ. А и ВТ, 1980, № 4, с.23−31.
- Якубайтис Э.А. Синтез структуры программируемой логической матрицы. А и ВТ, 1976, № 4, с.1−10.
- Лемберский И.Г. Сокращение числа членов ДНФ при кодировании внутренних состояний асинхронного автомата, реализуемого на программируемой логической матрице. А и ВТ, 1979, № 2,с.59−65.
- Якубайтис Э.А. Программрруемый логический автомат. -А и ВТ, 1975, № 5, с.1−6.
- Новиков C.B. Синтез схем на программируемых логических матрицах. А и ВТ, 1977, № 5, с. 1−4.
- Новиков C.B. Метод реализации системы частичных булевых функций схемой на программируемых логических матрицах. А и ВТ, 1980, № 6, с.33−37.
- Супрун В.Н. Реализация слабоопределенных булевых функций на программируемых логических матрицах. Деп. рукопись, М. :1. ВИНИТИ, № 824−80.
- Буль Е.С., Чапенко В. П. Подход к синтезу комбинационных схем. В кн.: Теория автоматов и её приложения. Синтез автоматов с престраиваемой структурой. Тезисы докладов 1У советско-болгарского семинара. Рига, 1977, с.46−49.
- Бабкин Е.А., Тупикин А. П. Вопросы синтеза устройств управления на программируемых логических матрицаз. В кн.: Микропроцессоры. Тезисы докладов II Всесоюзного совещания. Рига, 1977.
- Денисенко Е.Л., Кобылинский А. В., Палагин А. В. Синтез управляющих блоков микро-ЭВМ на основе программируемых логических матриц. В кн.: Микропроцессоры. Тезисы дколадов II Всесоюзного совещания, Рига, 1977,
- Бутов А.А. Использование ПЛМ при синтезе комбинационных схем. В кн.: Автоматизация логического проектирования дискретных устройств. Минск: ИТК АН БССР, 1980.
- Поваров Г. Н. О функциональной разделимости булевых функций. ДАН СССР, 1954, т.94, № 5.
- Чень Дзюнь-лян. К использованию свойства функциональной разделимости булевых функций для синтеза электронных схем. В кн.: Труды учебных институтов связи. Л.: ЛЭШ, 1961, вып.7, с.87−96.
- Закревский А.Д. Алгоритм разделения булевой функции. -Труды СФТИ, вып.44. Томск, 1964.
- Фадеев И. Л. Реализация алгоритма разделения полностью определенной булевой функции на УЦЕМ. В кн.: Доклады II Сибирской конференции по математике и механике. Томке: Т1УД962.
- Фадеев И.Л. Анализ полностью определенной булевой функции на разделимость по заданному разбиению. Труды (ЖГИ, вып.48. Томск, 1966.
- Фадеев И. Л. Задача разделения Нулевой функции. В кн.: Логический язык для представления алгоритмов синтеза релейных устройств. М.: Наука, 1966.
- Фадеев И.Л. Некоторые задачи декомпозиции систем булевых функций. В кн.: Автоматизация логического проектирования цифровых устройств. Киев, 1974.
- Бутов A.A. Метод функционального разделения полностью определенной булевой функции. А и Т, 1978, I 9, с.121−125.
- Либих А.Н. О пересекающейся декомпозиции булевых функций. В кн.: Автоматы, вып.1. Саратов: С1У, 1974, с.54−61.
- Павловский А. И. К вопросу об итеративной декомпозиции булевых функций. ДАН БССР, 1977, т.21, № 10.
- Ващенко В.П. Общий случай простого функционального разделения. ДАН СССР, 1977, т.234, jfc 3, с.73−75.
- Шоломов Л.А. О функционалах, характеризующих сложность систем недогшределенных булевых функций. В кн.: Проблемы кибернетики, вып.19. М.: Наука, 1967, с.123−140.
- Белявский В.Л., Сабадаш И. Г. Некоторые вопросы симметрической дизъюнктивной декомпозиции. В кн.: Вопросы теории ЭЦВМ. Труды семинара. Киев, 1968, вып.2.
- Ващенко И.В. Общее теоретико-множественное решение задачи функциональной декомпозиции. Тр. Моск, энерг. ин-та, 1975, вып.247, с.5−10.
- Степаненко С.А. Реализация функций алгебры логики программируемыми элементами. А и Т, 1980, $ II, с.124−133.
- Граммалин В.В., Першев В. Г., Шамров В. И. Реализациякомбинационных преобразователей большими интегральными схемами. -УС и M, 1980, № 6, с.30−35.
- Буль Е.С. Реализация переключательных функций схемой на программируемых логических матрицах. № А и ВТ, 1980, № 2,с.13−18.
- Буль Е.С. Использование декомпозиционных свойств переключательных функций при синтезе на программируемых логических матрицах. В кн.: Теория конечных автоматов и её приложения. 1980, вып. II, сД16−133.
- Буль Е.С. Совместная реализация систем переключательных функций схемой из ШМ. А и ВТ, 1981, J? 3.
- Бибило П.Н., Енин С ¿-В. Совместная декомпозиция системы булевых функций. Изв. АН СССР. Техническая кибернетика. 1980, № 2, с. 123−129.
- Библо П.Н., Енин C.B. Декомпозиция булевой функции с минимальным числом существенных аргументов подфункций. Изв. АН СССР. Техническая кибернетика. 1980, В 3, с.116−122.
- Бибило П.Н., Енин C.B. Декомпозиционный метод синтеза комбинационных схем из универсальных логических модулей. В кн.: Автоматизация проектирования НЕМ. Киев, 1979, с.55−65,
- Бибило П.Н., Енин C.B. Несущественность аргументов и декомпозиция булевых функций. А и ВТ, 1978, № 4.
- Соловьев H.A. Тесты (теория, построение, применение). -Новосибирск,: Наука, 1978.
- Береснев B.I., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибщхж: Наука, 1978.
- Менон П., Фридман А. Теория и проектирование переключательных схем. М.: Мир, 1978, 581 с.
- Крамер Г. Математические методы статистики. М.: Мир, 1975, 648 с.
- Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980, 399 с.
- Варфоломеева Е.П., Васькин П. И., Губкин А. Ф., Дудкин B.C. Плотников А. В. Система синтеза микроцрограммных автоматов. -Обмен опытом в радиопромышленности, 1975, № 6, с.62−83.
- Ko-/fer-I. Some oSseri/oution on ?/te pro-?creufistic (x?$oruthm CL/bd A/P~ Actrd. ~Zn.f. Process Lett., /Ж, v./4, Л//.
- С. Ь/ъсипгьоп. ТАе sy/zthesis of? wo-terminai switching circuits. 3ei? St/stem 7ech.2S (I949), pp. f9~9S.
- S. CaCdwei?. Switching circuits cLnoi? ogiccr? design. John Wi?? ee/ cL/tci Sons, A/ew-i/or49 /96/.
- Of.sAenhurst /?./,. The decomposition of switching functions. Proc. of Tnter/?. Symposium of the ?^eorc/ of su/itcJzin.g circuits. t/arwas-d, v. 29y959.
- She/i V.J., /%/ieEEar /… /in algorithm for the (disjunctive cLecampostiion of switching fe/n.c-itons. «IEEE Transactions on Computers 9 McLrcA} /970, ir. C-/%/V3.
- Shen V.7., Ma Ke?? ar /??.y Weiner P/7.fust algorithm for? he disjunctive decomposition of switching functions. ~ZE?E Transactions on Computers, A/arch, fP?/, v. C-29f A73 .
- S04. /arson T.L., 2) owneyC. Fietd program-maS^e ?ogic de vi s es. Electronic Engineering ,
- JcLKit&rt, mo, V/. S2, #633, pp. 37-S4.
- Б.1. Бабушкин В. И., Васькин П. И. Определение совокупностей существенных переменных неполностью определенных булевых функций. Изв.ЛЭТИ. Науч.тр. (Ленингр.электротехн.ин-т им. В. И. Ульянова (Ленина), 1980, вып.278, с.77−80.
- Б.2. Бабушкин Б. И., Васькин П. И. Реализация системы булевых функций на программируемых логических матрицах. Известия ВУЗов. Приборостроение, 1981, № 6, с.42−45.
- Б.З. Бабушкин В. И., Васькин П. И. Вероятностные оценки решений таблицы покрытий, Изв.ЛЭТИ. Науч.тр.(Ленинграэлектротехн. ин-т им. В. И. Ульянова (Ленина), 1981, вып.296, с.100−104.
- Б.4. Бабушкин В. И. и др. Система автоматизщюванного про-ектированш дискретных управляющих устройств. Информационный листок В 1171−81, Л., 1981.
- Б. 5. Бабушкин В. И. Псевдослучайный датчик таблиц покрытий. Деп. рукопись, М.: ВИНИТИ,? 5682−82, 1982.
- Б.6. Бабушкин В. И. и др. Трансляторы с языков описания булевых функций и систем булевых функций. Информационный листок № 611−83, Л., 1983.
- Б.7. Бабушкин В. И., Васькин П. И. Алгоритмы решения таблиц покрытий. Изв.ЛЭТИ. Науч.тр. (Ленингр.электротехн.ин-т им. В. И. Ульянова (Ленина), 1983, вып.324, с.86−89.
- Б.8. Бабушкин В. И. Определение мощности решения таблицы покрытий. Деп. рукопись, М.: ВИНИТИ, № 6681−83, 1983.