автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка и исследование алгоритмов структурной декомпозиции управляющих систем

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОД СОКРАЩЁННОГО ОБХОДА ДЕРЕВА ПОИСКА

И ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ДЕКОМПОЗИЦИИ.

1.1 ОПРЕДЕЛЕНИЕ СХЕМЫ.

1.2 ПОСТАНОВКА ЗАДАЧ ДЕКОМПОЗИЦИИ.

1.3 ОБЗОР МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ДЕКОМПОЗИЦИИ.

1.4 Т-ЗАДАЧА КАК МОДЕЛЬ ЗАДАЧ СТРУКТУРНОЙ ДЕКОМПОЗИЦИИ.

1.5 МЕТОД СОКРАЩЁННОГО ОБХОДА ДЕРЕВА ПОИСКА.

1.6. СОКРАЩЕНИЕ ПЕРЕБОРА.

1.7. ФОРМУЛИРОВКА МЕТОДА.

1.7.1. Алгоритм обхода.

1.7.2. Технология решения задач декомпозиции.

ГЛАВА 2. ДЕКОМПОЗИЦИЯ НА КОМПОНЕНТЫ

ОГРАНИЧЕННОГО ОБЪЁМА.

ВВЕДЕНИЕ.

2.1. ПОСТАНОВКА ЗАДАЧИ.

2.2. Т-ИНТЕРПРЕТАЦИЯ.

2.3. ПАРАМЕТРЫ МЕТОДА.

2.4 АЛГОРИТМЫ НАЧАЛЬНОГО РАЗБИЕНИЯ.

2.5. АЛГОРИТМ ПЕРЕЧИСЛЕНИЯ МАКСИМАЛЬНЫХ СОВМЕСТИМЫХ ПОДМНОЖЕСТВ.

2.6. ПРИМЕР.

2.7. ДОПУСТИМОСТЬ АЛГОРИТМА ПЕРЕЧИСЛЕНИЯ И ОПЕРАЦИИ СОКРАЩЕНИЯ.

2.8. РЕАЛИЗАЦИЯ АЛГОРИТМА ДЕКОМПОЗИЦИИ НА ЭВМ.

ГЛАВА 3. ДЕКОМПОЗИЦИЯ НА КОМПОНЕНТЫ

ОГРАНИЧЕННОЙ СЛОЖНОСТИ.

ВВЕДЕНИЕ.

3.1. ПОСТАНОВКА ЗАДАЧИ И ЕЁ СВЯЗЬ С ЗАДАЧЕЙ КОМПОНОВКИ СХЕМ.

3.2. Т-ИНТЕРПРЕТАЦИЯ И ПАРАМЕТРЫ МЕТОДА.

3.3. СВОЙСТВА ПЛОТНЫХ МНОЖЕСТВ И ДОПУСТИМОСТЬ АЛГОРИТМА ПЕРЕЧИСЛЕНИЯ.

3.4. ПЕРЕЧИСЛЕНИЕ СОВМЕСТИМЫХ ПОДМНОЖЕСТВ.

3.5. АЛГОРИТМЫ НАЧАЛЬНОГО РАЗБИЕНИЯ.

3.6. ПРИМЕР.

ГЛАВА 4. ДЕКОМПОЗИЦИЯ НА КОМПОНЕНТЫ

СОВМЕСТИМОСТИ.

ВВЕДЕНИЕ.

4.1. ПОСТАНОВКА ЗАДАЧИ.

4.2. Т-ИНТЕРПРЕТАЦИЯ.

4.3. ПАРАМЕТРЫ МЕТОДА И ИХ ДОПУСТИМОСТЬ.

4.4. ПРИМЕР.

4.5. РАСКРАСКА ГРАФОВ, СОДЕРЖАЩИХ РАЗДЕЛЯЮЩИЙ ПОЛНЫЙ ПОДГРАФ.

4.6. РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ АЛГОРИТМА НА ЭВМ.

ГЛАВА 5. ПОКРЫТИЕ СХЕМ СВОБОДНЫМИ МОДУЛЯМИ.

5.1. ПОСТАНОВКА ЗАДАЧИ И ЕЁ МОДЕЛЬ.

5.2. Т-ИНТЕРПРЕТАЦИЯ И ПАРАМЕТРЫ МЕТОДА.

5.3. АЛГОРИТМ ПЕРЕЧИСЛЕНИЯ.

5.4. ПРИМЕР.

Актуальность проблемы.

Управляющие системы представляют собой объекты дискретной природы и характеризуются функцией и структурой [106]. Способы задания функциональных характеристик очень многообразны и включают в себя системы уравнений, формулы, микропрограммы и пр. [41-42,58,75]. Структура управляющей системы задаётся схемой. Под структурной декомпозицией управляющих систем в данной работе понимается задача декомпозиции соответствующих схем. Задачи структурной декомпозиции возникают при исследовании управляющих систем на стыке логического и конструкторского этапов проектирования, когда требуется распределить заданную схему устройства по конструктивным блокам - интегральным микросхемам, базовым ячейкам или стандартным элементам БИС, а те, в свою очередь, - по печатным платам, базовым кристаллам или матричным БИС в заданном монтажном пространстве с обеспечением конструкторских и технологических ограничений.

В силу дискретности объекта задачи структурной декомпозиции являются комбинаторно-логическими задачами и имеют множество допустимых решений, поэтому дополнительно требуется, чтобы искомое решение достигало экстремума по некоторому параметру или группе параметров. По содержанию этих задач, по используемым математическим моделям задачи структурной декомпозиции имеют много общего и требуют для своего решения разработки специализированных комбинаторных подходов.

Основные теоретические исследования в этой области получили широкое развитие с конца 30-х годов нашего столетия и продолжают оставаться в центре внимания исследователей по настоящее время [1-4,29-30,38,4344,51,58,75,78,87-89,93-94,96-99,103-106]. За эти годы конструктивная база управляющих систем быстро изменялась, пройдя путь от релейноконтактных элементов, микросхем малого и среднего уровня интеграции к программным устройствам, а затем к большим и сверхбольшим интегральным схемам, включая микропроцессоры и микроконтроллеры [4142,58,66,71,75,78].

В процессе изучения управляющих систем при рассмотрении задач анализа и синтеза каждый тйп конструктивной базы порождает в постановке задач структурной декомпозиции свои критерии и ограничения. Это обстоятельство приводит к необходимости разработки многих математических моделей и методов, а на их основе - алгоритмов решения возникающих задач структурной декомпозиции, позволяющих выполнить выдвигаемые практикой требования [1-4,6-8,19,29-30,38,41-43,58,93,97, 103,113,119].

С дальнейшим развитием технологической и конструктивной базы современных управляющих систем в связи с использованием в их структуре сложных дорогостоящих блоков, а также в связи с организацией их взаимодействия с учётом технологических ограничений возрастает число и разнообразие задач структурной декомпозиции, требующих своего решения в процессе исследования таких систем. Создание математических и программных средств решения подобных задач заметно отстаёт от потребностей практики. Поэтому создание общей математической модели, общего подхода (метода) и хорошо развитой системы алгоритмов и программ решения задач декомпозиции, существенно облегчает и ускоряет процесс исследования управляющих систем.

В абстрактной постановке, очищенной от содержательных понятий, задачи структурной декомпозиции управляющих систем часто допускают множество других полезных интерпретаций. Алгоритмы и программы, разработанные для их решения, могут быть использованы при решении задач, встречающихся не только в исследовании управляющих систем, но и в дискретной математике, в экономике, в социологии и других областях науки и техники [12,17,59,68,72,74,79-80,90-91,98,108,110,114,116,121].

Существующие математические модели и методы решения задач декомпозиции разрабатывались исторически по мере обращения науки к тем или иным новым задачам. Как и в любой другой отрасли знания, находящейся в начальной стадии развития, этот процесс носил (и продолжает носить) довольно стихийный и бессистемный характер, следствием чего явилось создание великого множества частных моделей и методов, перегруженных, за редким исключением, содержательными понятиями и ориентированных тем самым не на классы задач, а на некоторых отдельных их представителей. Что касается обобщений, достаточно абстрактных для ориентации на широкие классы задач и вместе с тем, хоть как-то претендующих на практическую реализуемость, то среди таковых сегодня трудно назвать что-либо, кроме метода ветвей и границ, который имеет известные недостатки, ограничивающие его применение. В этих условиях процесс решения каждой новой задачи начинается практически с нуля (с создания новой модели) и завершается разработкой нового (а по существу -часто известного) метода решения. Получение желаемого результата при этом нередко затягивается на многие месяцы, а иногда и годы. Между тем, наличие достаточно общей математической модели задач декомпозиции и эффективного метода решения последних на базе этой модели позволяет процесс (поиска метода) решения любой такой задачи представить как некий технологический процесс с чёткими правилами относительно того, что и в каком порядке следует делать, чтобы решить задачу данным методом. Осуществление этой возможности исключает ненужное дублирование результатов, повышает производительность научного труда.

Вышеизложенное показывает, что актуальность темы определяется:

• отсутствием общей математической модели и общего подхода к решению широкого класса задач структурной декомпозиции управляющих систем;

• отсутствием практически применимых эффективных алгоритмов точного решения задач структурной декомпозиции управляющих систем;

• трудоёмкостью известных подходов и методов решения некоторых задач структурной декомпозиции схем;

• отсутствием для ряда задач структурной декомпозиции схем машинно-ориентированных алгоритмов и программ их решения.

Целью работы является

1. Разработка общей математической модели, метода и эффективной технологии решения широкого класса задач структурной декомпозиции, возникающих при исследовании управляющих систем.

2. Разработка при помощи этой технологии практических алгоритмов решения конкретных задач структурной декомпозиции.

3. Реализация и исследование разработанных алгоритмов на ЭВМ. Методы исследования базируются на комбинаторном анализе, теории синтеза управляющих систем, теории графов, теории алгоритмов и теоретическом программировании.

Научную новизну полученных в работе результатов составляют:

- общая математическая модель широкого класса задач структурной декомпозиции управляющих систем - Г-задача, заключающаяся в нахождении для заданной схемы и заданных условий допустимости кратчайшего (с наименьшей длиной) разбиения схемы на допустимые подсхемы;

- параметрический метод решения Г-задачи - метод сокращённого обхода дерева поиска в пространстве разбиений, представляющий собой общий алгоритм поиска с возвращением и сохранением более короткого разбиения, в который включены средства ускорения поиска (параметры метода): алгоритм начального разбиения, алгоритм перечисления некоторой достаточной совокупности допустимых блоков, операция их сокращения с сохранением свойства достаточности и функция нижней оценки;

- технология решения задач структурной декомпозиции, состоящая в формулировке решаемой задачи как Г-задачи и в подборе подходящих (допустимых) параметров для метода сокращённого обхода дерева поиска;

- конкретные варианты допустимых параметров метода сокращённого обхода дерева поиска (алгоритма начального разбиения, алгоритма перечисления, операции сокращения, функции нижней оценки) для четырёх задач декомпозиции управляющих систем:

1) на компоненты ограниченного объёма,

2) на компоненты ограниченной сложности,

3) на совместимые компоненты и

4) на компоненты, покрываемые свободными модулями;

- оригинальные алгоритмы решения данных задач, разработанные на основе предложенной технологии.

Достоверность полученных результатов. Все научные положения и выводы, содержащиеся в диссертации, основаны на утверждениях, доказанных с использованием аппарата дискретной математики. Эффективность предложенных методов структурной декомпозиции подтверждена компьютерными экспериментами.

Практическую значимость работы представляют технология решения широкого класса задач структурной декомпозиции и совокупность практических алгоритмов и программ, полученных в ходе выполнения диссертационной работы. Использование этих результатов приводит к повышению производительности труда при исследованиях управляющих систем и создаёт возможность для их дальнейшего совершенствования путём концентрации усилий на организации процесса проектирования в целом.

Внедрение результатов. Работа выполнялась в рамках проектов:

1. Госбюджетная тема Сибирского физико-технического института при Томском государственном университете (ТГУ), программа «Исследование и разработка новых методов электромагнитного контроля и диагностики материалов, сред и технических систем», 1995-2000 гг., шифр «Диаконт», раздел «Разработка методик и аппаратуры исследований».

2. Хоздоговорные темы Сибирского физико-технического института при Томском государственном университете (ТГУ) «Разработка математических и программных средств проектирования цифровых автоматов на базе матричных КМОП БИС», 1990-1995 гг., шифр «Сток», раздел «Функционально-логическое и структурное проектирование».

3. Хоздоговорные темы Сибирского физико-технического института при Томском государственном университете (ТГУ), программа «Разработка метода автоматического синтеза асинхронных автоматов для использования при проектировании АУ СКППО», 1971-1975гг., шифр «Сапфир», раздел «Разбиение схемы на технологические блоки».

4. Межвузовская научно-техническая программа "Конверсия и высокие технологии. 1994-2000гг." Раздел "Информатизация". Проект 59-1-7 (19941996гг.). Раздел "Информационные технологии, электроника и связь". Проект 95-1-21 (1997-2000). Раздел "Информационные компьютерные технологии дискретного математического моделирования, анализа, синтеза и тестирования сверхскоростных интегральных схем логического управления".

5. Грант РФФИ № 98-01-00288 "Исследование полурешёточной модели динамического поведения интегральных схем логического управления", руководитель д.т.н., профессор Агибалов Г.П.

Полученные в ходе выполнения диссертационной работы результаты использовались при создании пакетов прикладных программ решения комбинаторно-логических задач дискретной математики, а также при создании реальных систем автоматизированного проектирования дискретных управляющих систем: Сапфир, Автосинтез, Автоконструктор, которые были внедрены на ряде предприятий, в том числе:

- в Киевском институте автоматики,

- в Специальном опытном проектном конструкторском технологическом бюро (СОПКТБ) при СО ВАСХНИЛ, г. Новосибирск,

- Новосибирском заводе полупроводниковых приборов (Изомер). Теоретические результаты работы внедрены в учебный процесс на факультете прикладной математики и кибернетики Томского государственного университета: используются в курсе лекций «Разработка и анализ комбинаторных алгоритмов».

Апробация работы. Научные результаты диссертационной работы докладывались и обсуждались на заседаниях объединенного семинара кафедр программирования, математической логики и проектирования ТГУ и лаборатории синтеза дискретных автоматов Сибирского физико-технического института при ТГУ, на семинаре Института математики СО РАН (Новосибирск, 1988), а также докладывались и обсуждались на конференции молодых учёных и специалистов по кибернетике (Ленинград, 1971), на П Всесоюзном совещании по теории релейных устройств и конечных автоматов (Рига, 1971), на I и II Всесоюзных совещаниях по автоматизации проектирования интегральных схем (Киев, 1973, 1977), на III Всесоюзной конференции по проблемам теоретической кибернетики (Новосибирск, 1974), на региональной научно-практической конференции (Томск, 1977), на Ш Всесоюзной школе «Дискретная оптимизация и компьютеры» (Таштагол, 1987), на международной конференции «Всесибирские чтения по математике и механике» (Томск, 1997).

Публикации. По тематике диссертации опубликовано 17 печатных научных работ, в том числе: 1 монография, 9 статей, 2 доклада и 5 тезисов докладов в трудах всероссийских и международных конференций.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и списка используемой литературы, содержит 18 рисунков. Объем работы составляет 101 е., список литературы включает 122 наименования.

ЗАКЛЮЧЕНИЕ

В соответствии с поставленными целями исследования в диссертационной работе получены следующие результаты:

- создана общая математическая модель широкого класса задач структурной декомпозиции управляющих систем - Т-задача, заключающаяся в нахождении для заданной схемы и заданных условий допустимости кратчайшего (с наименьшей длиной) разбиения схемы на допустимые подсхемы;

- предложен метод решения Т-задачи - метод сокращённого обхода дерева поиска в пространстве разбиений, представляющий собой общий алгоритм поиска с возвращением и сохранением более короткого разбиения, в который включены средства ускорения поиска (параметры метода): алгоритм начального разбиения, алгоритм перечисления некоторой достаточной совокупности допустимых блоков, операции их сокращения с сохранением свойства достаточности и функции нижней оценки (алгоритм начального разбиения позволяет быстро построить некоторое допустимое разбиение, принимаемое за начальное; алгоритм перечисления и операция сокращения для каждой достигаемой вершины дерева поиска порождает часть его рёбер, исходящих го данной вершины, содержащих хотя бы одно ребро некоторого кратчайшего пути, проходящего через данную вершину и соединяющего корень с листом дерева; функция нижней оценки позволяет отсечь каждое поддерево дерева поиска, для которого сумма значения функции нижней оценки длины кратчайшего пути и его расстояния от корня не меньше, чем длина известного наиболее короткого допустимого разбиения);

- предложена технология решения задач структурной декомпозиции, состоящая в формулировке решаемой задачи как Т-задачи, в подборе подходящих допустимых параметров метода сокращённого обхода дерева поиска и их подстановке в алгоритм обхода;

- разработаны конкретные варианты допустимых параметров метода сокращённого обхода дерева поиска (алгоритм начального разбиения, алгоритм перечисления, операция сокращения, функция нижней оценки) для четырёх задач декомпозиции управляющих систем: 1) на компоненты ограниченного объёма, 2) на компоненты ограниченной сложности, 3) на совместимые компоненты и 4) на компоненты, покрываемые свободными модулями;

-созданы оригинальные алгоритмы решения данных задач, разработанные на основе предложенной технологии, и получены оценки их эффективности в компьютерном эксперименте, показывающие границы применимости алгоритмов.

В целом полученные в работе результаты представляют собой новое математическое и алгоритмическое обеспечение для решения задач структурной декомпозиции управляющих систем и могут быть использованы в исследовательских и промышленных системах автоматизированного проектирования устройств логического управления.

1. Абрайтис Л.Б., Шейнаускас Р.И., Жилевичус В.А. Автоматизация проектирования ЭВМ. М.: Советское радио, 1978. - 272 с.

2. Абрайтис Л.Б., Шимайтис А.П. Разбиение произвольных графов. // «Вычислительная техника». Материалы конференции «Автоматизированное техническое проектирование цифровых устройств». Каунас, 1976. - с. 102-105.

3. Агибалов Г. П. Дискретные автоматы на полурешётках. Томск: Изд-во Томского ун-та, 1993. - 227 с.

4. Агибалов Г. П., Беляев В. А. Технология решения комбинаторно-логических задач методом сокращённого обхода дерева поиска. Томск: Изд-во Томского ун-та, 1981. -125 с.

5. Агибалов Г. П., Беляев В. А. Метод сокращённого обхода дерева поиска и его применение в синтезе интегральных схем.// Управляющие системы и машины. 1977. - № 6. - с. 99-103.

6. Агибалов Т.П. Ободном подходе к размещению аппаратуры. //Автоматика и вычислительная техника. Рига: «Зинатне», 1971. - № 1. - с.56-61.

7. Агибалов Г.П., Беляев В.А., Оранов A.M. Некоторые алгоритмы разбиения, покрытия и размещения логических схем. //. Управляющие системы и машины. 1974. - № 5. - с. 86-92.

8. Агибалов Г.П., Беляев В.А., Янковская А.Е. Алгоритм компоновки схем в модули ограниченной вместимости. // Управляющие системы и машины. -1976,- Ш1.-С. 84-89.

9. Агибалов Г.П., Оранов A.M. Алгоритмы покрытия схем свободными модулями. //Автоматика и вычислительная техника. -Рига:«3инатне»,1977. № 4-с. 15-16.

10. И. Агибалов Г.П., Оранов A.M. О покрытии схем модулями. // Вопросы автоматизации проектирования интегральных схем. К.: ИК АН УССР, 1978.-с. 46-57.

11. Алексеев О.Г. Об одном классе задач целочисленного программирования. //ЖВМиМФ, 1977, №4.- с. 1047-1052.

12. Алипов Н.В., Шумейко H.A. Об одном алгоритме решения задачи соединения монтажных проводов в виде замкнутой цепи. .// Управляющие системы и машины. -1978. № 5. — с. 111-114.

13. Бабаев A.A. О применимости одного алгоритма к решению задачи упаковки. // Управляющие системы и машины. 1978. - № 6. - с. 55-56.

14. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. -М.: Наука. Гл. ред. физ.-мат. лит., 1989. 160 с.

15. Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. - 368 с.

16. Белицкий Р.И., Денисенко E.JL, Палагин A.B. Метод покрытия в задаче кодирования микрокоманд. // Управляющие системы и машины, 1977. - № 6. — с. 74-81.

17. Беляев В.А. Алгоритм раскраски графа методом сокращённого обхода дерева поиска. // Алгоритмы решения задач дискретной математики. Вып. 2. Томск: Изд-во Томского ун-та, 1987. - с. 165-172.

18. Беляев В.А. Декомпозиция схем в конструкторском проектировании РЭА. // Материалы областной научно-технической конференции «Радиотехнические средства и методы измерения». Томск: 1985. - с. 127.

19. Беляев В.А. Покрытие схем свободными модулями. // Материалы региональной научно-практической конференции «Молодые учёные испециалисты народному хозяйству», секция математики, кибернетики, АСУ. - Томск: Изд-во Томского ун-та, 1977. - с. 77-79.

20. Беляев В.А. Разбиение графа на подграфы с заданными свойствами. // Проблемы кибернетики. Материалы конференции молодых учёных и специалистов по кибернетике. 2-4 июня 1971. Ленинград: 1971.-е. 77.

21. Беляев В.А. Раскраска вершин графа. // Международная конференция «Всесибирские чтения по математике и механике». Тезисы докладов. Т. 1. Математика / Под ред. И.А. Александрова и др. Томск: Изд-во Том. унта, 1997.-е. 150-151.

22. Беляев В.А. Усовершенствованный алгоритм минимального разбиения системы чисел. // Прикладная математика и кибернетика. Вып. 1. Томск: Изд-во Томского ун-та, 1976. - с. 17-22.

23. Беляев В.А., Елисеева H.A. Графический вывод схем. // Автоматизация, математические методы и управление народным хозяйством. Томск: Изд-во Томского ун-та, 1989. - с. 66-70.

24. Берж К. Теория графов и её применения. -М.: ИЛ, 1962. 319с.

25. Бреуэр М. Последние достижения в области автоматизации проектирования и анализа цифровых систем. // Автоматизация в проектировании. -М.: Мир, 1972. с.19-48.

26. Бронин Е.И., Вермишев Ю.Х., Машков В.В., Преснухин В.В. Основные технические характеристики комплекса автоматизированного проектирования радиоэлектронной аппаратуры. // Обмен опытом в радиопромышленности. -М.: 1975. вып. 6. - с. 7-10.

27. Бухгольц Н.В., Дьяченко В.Ф., Лазарев В.Г., Чернышов К.К., Шаров В.А. Алгоритм минимизации оперативной памяти ЦВМ. // Проблемы синтеза цифровых автоматов. -М.: Наука, 1967. с. 112-118.

28. Бухгольц Н.В., Дьяченко В.Ф., Лазарев В.Г., Чернышов К.К., Шаров В.А. К вопросу экономии оперативной памяти ЦВМ. //Вычислительные системы. Новосибирск: СО АН СССР, 1965,- вып. 18. - с.119-137.

29. Быкова C.B. Минимизация числа операндов в Л-программах. //Тезисы докладов к предстоящему Всесоюзному колоквиуму по автоматизации синтеза дискретных вычислительных устройств. Новосибирск, 1966. -с. 19-22.

30. Быкова C.B. Разработка и исследование алгоритмов решения некоторых логико-комбинаторных задач логического синтеза и системного программирования. //Диссертация на соискание учёной степени кандидата технических наук Томск, 1975. - 157 с.

31. Быкова C.B. Система алгоритмов кратчайшего покрытия. // Труды Сибирского физ.-техн. ин-та. Вып. 64. Проблемы кибернетики. Томск: Изд-во Томского ун-та, 1973. - с. 3-11.

32. Быкова C.B., Иволга В.П. Оценка эффективности некоторых алгоритмов минимального разбиения. // Вычислительная техника в машиностроении. Минск: ИТК АН БССР, июнь, 1974. - с. 79-86.

33. Гаврилов М.А. Минимизация булевых функций, характеризующих релейные цепи. //Автоматика и телемеханика. — 1959. № 9. - с. 36-43.

34. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. -М.: Наука, 1977. 352 с.

35. Гладких Б.А., Ивашинцов H.A., Матушевский В.В. Приближённый алгоритм раскраски графов большой размерности. // Труды Сибирского физ.-техн. ин-та. Вып.62. Проблемы кибернетики- Томск: Изд-во Томского ун-та, 1971.-е. 49-57.

36. Глущков В.М. Синтез цифровых автоматов. -М.: ФМЛ, 1962. 476 с.

37. Глушков В.М., Деркач В.П., Кияшко Г.Ф. Важнейшие задачи в области автоматизации проектирования больших интегральных схем. // Управляющие системы и машины. 1977. - № 6. - с. 88-92.

38. Глушков В.М., Деркач В.П., Кияшко Г.Ф. К вопросу о состоянии проблемы автоматизации проектирования больших интегральных схем. // Кибернетика. 1976. - № 6. - с. 44-49.

39. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Автоматизация проектирования вычислительных машин. К.: Наукова думка, 1975. 232 с.

40. Горбатов В.А., Демьянов В.Ф., Кулиев Г.Б. и др. Автоматизация проектирования сложных логических структур. М.: Энергия, 1978. -352 с.

41. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982. 416 с.

42. Емеличев B.À., Мельников О.И., СарвановВ.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, Гл. ред. физ.-мат. лит., 1990. - 384 с.

43. Ершов А. П. Введение в теоретическое программирование. М.: Наука, 1977.-288 с.

44. Ершов А.П., Кожухин Г.И. Об оценках хроматического числа связных графов. //Доклады АН СССР, т. 142. -М.: 1962. № 2. - с. 270-273.

45. Журавлёв Ю.И. О построении минимальных дизъюнктивных нормальных форм для функций алгебры логики. // Доклады АН СССР, т.126. -М.:1959. № 2, с.263-266.

46. Зайцева Ж.Н., Штейн М.Е. Гамильтоновы циклы в решении задач размещения. // Кибернетика. 1976. - № 3. - с. 70-73.

47. Закревский А. Д. Алгоритмы синтеза дискретных автоматов. М.: Наука, 1971.-512 с.

48. Закревский А.Д. Алгоритмический язык ЛЯПАС и автоматизация синтеза дискретных автоматов. Томск: Изд-во Томского ун-та, 1966. -266 с.

49. Закревский А.Д. Логические уравнения Минск: «Наука и техника», 1975,- 96 с.

50. Закревский А.Д. О сокращении переборов при решении некоторых задач синтеза дискретных автоматов. // Изв. Вузов. «Радиофизика». -Горький:изд-во Горьковского ун-та, 1964. т. УП, № I. - с. 166-174.

51. Закревский А.Д. Оптимизация покрытий множеств. //Логический язык для представления алгоритмов синтеза релейных устройств. М.: Наука, 1966. - с. 136-148.

52. Закревский А.Д. Принципы организации систем автоматического синтеза. // II Всесоюзное совещание по теории релейных устройств и конечных автоматов. Тезисы докладов. 28 сент.-1 окт. 1971 г. Рига: 1971.-с. 139-140.

53. Закревский А.Д., Торопов Н.Р. Система программирования ЛЯПАС. -М.: Наука и техника. Минск, 1978. - 220 с.

54. Зубков Г.Н. Применение моделей и методов структурного анализа систем в градостроительстве. М.: Стройиздат, 1984. - 152 с.

55. Зыков A.A. Теория конечных графов. Новосибирск: Наука СО АН СССР, 1969. - 544 с.

56. Ивани A.M. Оценка эффективности алгоритмов упаковки в контейнеры. //Проблемы кибернетики. М.: Наука, 1984. - вып. 41. - с. 253-256.

57. Илзиня И.Г., Фрицнович Г.Ф. Ободном подходе к решению проблемы кратчайшего покрытия. //Автоматика и вычислительная техника. Рига: «Зинатне», 1972. - № 1. - с. 18-19.

58. Кириенко H.A. Разбиение системы логических уравнений на подсистемы с заданными ограничениями. //Новые информационные технологии в исследовании дискретных структур. Научное издание. -Томск: ТНЦ СО РАН, «Спектр», 2000. с. 236-241.

59. Кобзева Т.В. К задаче размещения разногабаритных элементов. // Управляющие системы и машины. 1982. - №1. - с, 87-89.

60. Кожухарь А.Ф., Оранов A.M. Алгоритмы размещения множества вершин взвешенного графа в произвольном связном графе. // Управляющие системы и машины. 1978. - № 3. - с. 100-103.

61. Колдуэлл С. Логический синтез релейных устройств. М.: ИЛ, 1963. -740 с.

62. Корбут A.A., Финкелыптейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.

63. Кофман А. Введение в прикладную комбинаторику. М.: Наука, Гл. ред. физ.-мат. лит., 1975. - 480 с.

64. Кристофидес Н. Теория графов. Ажоритмический подход. М.: Мир, 1978.-432 с.

65. Курош А.Г. Лекции по общей алгебре. М.: ФМЛ, 1962. - 396 с.

66. Ландау И.Я. Применение ЦВМ для проектирования ЦВМ. М.: Энергия, 1974. - 152 с.

67. Левин A.A. Универсальные задачи перебора. // Проблемы передачи информации. 9, №3,1973. - с. 115-116.

68. Липский В. Комбинаторика для программистов. М.: Мир, 1988. - 216 с.

69. Литтл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивояжёра. //Экономика и математические методы. М.: 1965. - № 1. - с.94-107.

70. Майоров С.А., Новиков Г.И. Принципы организации цифровых машин. -Ленинград: «Машиностроение», 1974. 432 с.

71. Максименков A.B. Нахождение пути в графе, удовлетворяющего определённым ограничениям. //Кибернетика. 1974. - № 5. - с. 90-92.

72. Мелихов А.Н., Берпггейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 304 с.

73. Мотоока Т., Томита С., Танака X., Сайто Т., Уэхара Т. Компьютеры на СБИС. М.: Мир, 1988. - 392 с.

74. Нивергельт Ю., Фаррар Дж., Рейнгольд Э. Машинный подход к решению математических задач. М.: Мир, 1977. - 347 с.

75. Нильсон Н. Искусственный интеллект. -М.: Мир, 1973. 272 с.

76. Оранов A.M. Автоматизированная подсистема конструкторского проектирования дискретных устройств. //Вопросы автоматизации проектирования интегральных схем. К.: ИК АН УССР, 1978. - с. 5761.

77. Островский В.И. Генератор псевдослучайных булевых матриц с заданной плотностью единичных элементов. //Отчёт по НИР

78. Исследование путей повышения надёжности дискретных управляющих систем». Севастополь: 1970. - гос. per. № 69038288.

79. Островский В.И., Поттосин Ю.В. Исследование алгоритмов поиска максимальных полных подграфов в симметрическом графе. //Автоматика и вычислительная техника. Рига: «Зинатне», 1970. - № 2. - с. 19-26.

80. Палагин A.B., Писарский A.B., Погорелый С.Д. Об одной задаче оптимизации размещения данных. // Управляющие системы и машины. -1976.-№4.-с. 54-58.

81. Петренко А.И., Тетельбаум А.Я. Модели электронных устройств при решении конструкторских задач. . // Кибернетика. 1978. - № 2. - с. 4754.

82. Петухов Г.А., Смолич Г.Г., Юлин Б.й. Алгоритмические методы конструкторского проектирования узлов с печатным монтажом. М.: Радио и связь, 1987. - 152 с.

83. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.-368 с.

84. Применение вычислительных машин для проектирования цифровых устройств. //Под ред. МатюхинаН.Я. -М.: Советское радио, 1968. 256 с.

85. Проектирование цифровых вычислительных машин. //Под ред. Майорова С.А. М.: Высшая школа, 1972. - 344 с.

86. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980. - 476 с.

87. Рыбников К.А. Введение в комбинаторный анализ. М.: изд-во Московского ун-та, 1972. - 256 с.

88. Рыжков А.П. Разбиение графа на минимальное число полных подграфов. // Кибернетика. 1975. - № 6. - с. 90-95.

89. Селютин В.А. Машинное конструирование электронных устройств. -М.: Советское радио, 1977. 384 с.

90. Синтез асинхронных автоматов на ЭВМ. //Под общ. Ред. Закревского А. Д. Минск: Наука и техника, 1975. - 184 с.

91. Справочник по полупроводниковым диодам, транзисторам и интегральным схемам. //Под ред. Горюнова H.H., изд.4-е, перераб. И доп. -М.: Энергия, 1976. 744 с.

92. Теория и методы автоматизации проектирования вычислительных систем. //Под ред. Брейера M. М.: Мир, 1977. - 288 с.

93. Тетельбаум А.Я., Шрамченко Б.Л. Метода машинного проектирования электронных устройств. //Зарубежная радиоэлектроника. М.: Советское радио, 1977. -№ 2. - с. 24-50.

94. Филиппович В.В. Задача размещения данных в памяти ЦВМ. . // Управляющие системы и машины. 1975. - № 1. - с. 87-92.

95. Фридман А., Менон П. Теория и проектирование переключательных схем. -М.: Мир, 1978. 584 с.

96. Фрицнович Г.Ф. Синтез асинхронных конечных автоматов и раскраска вершин графов. // II Всесоюзное совещание по теории релейных устройств и конечных автоматов. Тезисы докладов. 28 сент.-1 окт. 1971 г.-Рига: 1971.-с. 33-34.

97. Харари Ф. Теория графов. -М.: Мир, 1973. 304 с.

98. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.-347 с.

99. Чистов В.П., Шакиров Р.Н. Оболочка модульных программных систем со встроенными средствами развития. // Автоматизация проектирования дискретных систем./ Материалы Третьей международной конференции 10-12 ноября 1999 г. Минск: 1999. -т.З,- с. 116-123.

100. Штейн М.Е., Штейн М.Е. Методы машинного проектирования цифровой аппаратуры. М.: Советское радио, 1973. - 296 с.

101. Юрин О.Н. Единая система автоматизации проектирования ЭВМ. М.: Советское радио, 1976. - 176 с.

102. Яблонский С.В. Основные понятия кибернетики. // Проблемы кибернетики./ Под ред. Ляпунова А.А. М.: Государственное изд-во физ.-мат. литературы, 1959. - Вып. 2. - с. 7-38.

103. Bondy I.A. Bounds for the chromatic number of a graph. // J. Combin. Theory. 1969. - 7, № 1. - p. 96-98.

104. Dantzig G.B. On the Significance of Solving Linear Programming Problems with Some Integer Variables. // Econometrica. 1960. - vol. 28. - p. 3044.

105. Eilon S., Christofides N. The loading problem. // Manag. Sci. 1971. -vol.17. - p.259-268.

106. Geoffrion A. M., Marsten R. E. Integer programming: a framework and state-of-the-art survey // Management Science. 1972. - Vol. 18. - № 9. -p. 465-491.

107. Hung M.S., Broun J.R. An algorithm for a class of loading problems. // Naval research log. Quart. 1978. - vol. 25. - p. 289-297.

108. Ibaraki T. The power of dominance relations in branch and-bound algorithms. // J. ASM. 1977. - vol. 24. ^ № 2. - p. 264-279.

109. Kernigan B.W. Optimal Sequential Partitions of Graphs. // J. Of the association for computing machinery, January, 1971. voL18. - №1. - p. 34-40.

110. Knodel W. A bin packing algorithm with complexity 0(n logn) and performance 1 in the stochastic limit. // Lect. Notes Comput. Sci., 1981. -118.- p. 369-377.- 101

111. Luccio F., Sami M. On the Decomposition of Networks in Minimally Interconnected Subnetworks. // IEEE Trans. On Circuit Theory. CT-16. -May 1969. № 2. - pp. 184-188.

112. Quine W. V. The problem of simplifying of truth functions. // Amer. Math. Monthly. -1952. v. 59, № 8.-p. 521-531.

113. Ramamoorthy C.V. Analysis of graphs by connectivity considerations. // J. ASM. 1966. - vol. 13. - p. 211-222.

114. Randall-Brown J. Chromatic scheduling and the chromatic number problems. //Manag. Sci. 1972. - vol. 19. - №4. - p. 456-463.

115. Russo R.L., Wolff P.K. A Computer-Based-Design Approach to Partitioning and Mapping of Computer Logic Graphs. // Proc. of the IEEE. 1972. -vol. 60. -№1- p. 28-34.

116. Salkin H.M., Koncal R.D. Set Covering by all integer algorithm: computational experience. // J. ASM. 1973. - vol. 20. - №2. - p. 189193.

117. Sekiquchi Y. A Unifying framework of combinatorial optimization Algorithms; tree programming and its validity. // J. of the Oper. Research Society of Japan. 1981. - vol. 24. -№1 - p. 67-94.

118. Wilkov R.S., Kim W.H. A practical approach to the chromatic partition problem. //J. Franclin Inst. 1970. - 289. - № 5. - p. 333-349.