Разработка и исследование комбинаторных алгоритмов для решения оптимизационных задач конструкторского проектирования ЭВА тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Горин, Валентин Сергеевич

• Горин, Валентин Сергеевич
• кандидат технических наук
• 1985

Оглавление диссертации кандидат технических наук Горин, Валентин Сергеевич

ВВЕДЕНИЕ

1. ВЫБОР И ОБОСНОВАНИЕ МЕТОДОВ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ

ЗАДАЧ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ В АДАПТИРУЕМЫХ

САПР . II

1.1. Создание адаптируемых САПР на базе формальных комбинаторных процедур . II

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

1.3. Общая схема решения оптимизационных задач конструкторского проектирования

1.4. Эвристические методы снижения вычислительной сложности комбинаторных методов ••••••••.

Введение диссертации (часть автореферата) на тему «Разработка и исследование комбинаторных алгоритмов для решения оптимизационных задач конструкторского проектирования ЭВА»

В материалах ХХУ1 съезда КПСС "Основные направления экономического развития СССР на 1981-1985 годы и на период до 1990 года" в качестве одного из основных направлений развития науки и ускорения технического прогресса определено "расширение автоматизации проектно-конструкторских и научно-исследовательских работ с применением средств вычислительной техники". Упор на внедрение электронно-вычислительной техники обусловлен неуклонным повышением требований к качеству, возросшими объемом и сложностью выпускаемой аппаратуры, а также совершенствованием и изменением ее элементно-конструктивной базы и технологии изготовления* В соответствии с этим на первый план выдвигается проблема комплексной автоматизации процесса проектирования и изготовления электронно-вычислительной аппаратуры и, в частности, проблема автоматизации этапа конструкторского проектирования, как одного из наиболее сложных, а также связанная с ней задача разработки и совершенствования алгоритмической базы современных систем автоматизации проектирования (САПР)» Большой вклад в развитие теории и практическую реализацию САПР внесли основополагающие работы: Л.Б.Абрайтиса, Р.П.Базилевича, Д.И. Батищева, В.М.Глушкова, М.А.Гаврилова, Ю.П.Зимана, А.М.Карапетяна, В.М.Курейчика, Н.Я.Матюхина, А.Н.Мелихова, С.А.Майорова, Б.Н.День-добренко, А.И.Петренко, Г.Г.Рябова, В.А.Селютина, А.Я.Тетельбаума, М.Е.Штейна, О.Н.Юрина и других, а также многих зарубежных специалистов.

При создании САПР ведущую роль играет разработка комплекса алгоритмов и программ, реализующих процесс проектирования и предназначенных для решения отдельных задач конструкторского проектирования. в связи с этим важной с математической точки зрения особенностью большинства задач конструкторского проектирования является то, что все они сводятся к моделям целочисленного программирования, имеющим чрезвычайно сложные и громоздкие решения из-за большой размерности, существенно нелинейных оптимизируемых функций и функционалов, большого числа нелинейных ограничений. Это обуславливает широкое применение в реально существующих САПР эвристических алгоритмов, которые, не являясь формально обоснованными Г1,2] , нередко приводят к неудовлетворительным результатам.

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

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

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

Теория гиперграфов развита в работах К.Бержа и А.А.Зыкова, а наиболее существенные результаты по применению гиперграфов в автоматизации конструкторского проектирования содержатся в работах: А.М.Бершадского, Л.С.Берштейна, В.М.Курейчика, А.Н.Мелихова, А.И. Петренко, А.Я.Тетельбаума.

Комбинаторные алгоритмы на графах и гиперграфах обладают рядом достоинств, основным из которых является простота вычислительных процедур, сводящихся, как правило, к логическим операциям и получению оценок. В то же время недостаток алгоритмов - огромный комбинаторный перебор, возникающий при решении задач, приводит к чрезвычайно высокой сложности их реализации. Поэтому важным направлением исследований следует считать разработку методов снижения перебора, опирающихся на особенности вычислительных схем самих комбинаторных методов, а также на специфику решаемых задач. Существенные результаты в этом направлении получены: В.А.Емеличевым, A.A. Корбутом, В.С.Михалевичем, Ю.Ю.Финкельштейном, А.Ахо, Р.Беллманом, Г.Вагнером, Х.Мюллер-Мербахом, Э.Рейнгольдом, Дж.Хопкрофтом, Дж. Ульманом. Применительно к задачам конструкторского проектирования идеи снижения трудоемкости комбинаторных алгоритмов содержатся в работах: Г.А.Акрамовского, Л.С.Берштейна, В.М.Курейчика, Б.К.Лебедева, К.К.Морозова, А.В.Петросяна, В.А.Селютина, М.Е.Штейна, П. Джилмора, Т.Оцуки и других ученых.

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

В соответствии с этой целью в диссертации отражены следующие вопросы:

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

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

- разработан комплекс программ для приближенного решения конструкторских задач реальной размерности в условиях ограниченного объема памяти и времени, используемый в системах автоматизации конструкторского проектирования на ЕС ЭВМ$ проведено исследование и сопоставление разработанных программ с известными.

Настоящая работа выполнялась в рамках госбюджетной и хоздоговорной тематики в соответствии с планами работы секций радиоэлектроники и приборостроения Программ САПР Минвуза РСФСР и Минвуза СССР, а также планами работы Рязанского радиотехнического института и специальными постановлениями.

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

Разработанные алгоритмы реализованы в виде программ для ЕС ЭВМ и включены в системы автоматизации конструкторского проектирования, эксплуатируемые на предприятиях п/я М-5783, п/я А-3756 и КБМ г.Коломна. На базе предложенных методов решения задач конструкторского проектирования ЭВА поставлен цикл лабораторных работ по курсу "Автоматизация конструирования", а теоретические достижения используются при чтении лекций по тому же курсу на кафедре Конструирования электронно-вычислительной аппаратуры Рязанского радиотехнического института.

Основные результаты работы докладывались и обсуждались на 15 конференциях и семинарах в г.г. Пензе, Каунасе, Ереване, Запорожье, Славском, Владимире, а также на профессорско-преподавательских конференциях РРТИ.

Результаты исследований изложены в четырех разделах, заключении и приложениях.

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

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

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

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

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

I. ВЫБОР И ОБОСНОВАНИЕ МЕТОДОВ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗДАЧ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ

В АДАПТИРУЕМЫХ САПР

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Горин, Валентин Сергеевич

4.4. Выводы и рекомендации

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

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

3. Предложенный метод решения задачи (4.20) - (4.23) можно использовать для приближенного определения конфигурации соединений при жгутовом монтаже многорядных блоков. В то же время задача определения оптимальной укладки многозвенных цепей в жгуты для многорядных блоков требует дальнейшего исследования.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

4. Проведено исследование и сформулированы требования к эвристическим алгоритмам, применяемым для сокращения перебора в вычислительных схемах комбинаторных методов, используемых в САПР для решения оптимизационных задач конструкторского проектирования.

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

6. На основе специальных оценок, полученных путем аппроксимации точного выражения для оптимизируемого критерия качества, разработан эффективный последовательный алгоритм компоновки, который использован в качестве эвристики для снижения перебора в приближенных комбинаторных алгоритмах компоновки и покрытия схем ЭВА.

7. Аналитически решена задача определения минимального набора не связанных интегральных модулей, требуемого для покрытия произвольной схемы ЭВА.

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

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

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

II, Разработан пакет прикладных программ адаптируемой системы автоматизации конструкторского проектирования, реализующий предложенные комбинаторные алгоритмы и обеспечивающий решение задач реальной размерности. Экономический эффект от внедрения системы автоматизации проектирования на предприятиях п/я М-5783 и п/я А-3756 составил свыше 85 тыс#руб.

Список литературы диссертационного исследования кандидат технических наук Горин, Валентин Сергеевич, 1985 год

1. Корбут A.A., Сигал И.Л., Финкельштейн Ю.Ю. Об эффективности комбинаторных методов в дискретном программировании. В кн.: Современное состояние теории исследования операций. М.: Наука, 1979, с.283-310.

2. Корбут A.A., Финкелыптейн Ю.Ю. Приближенные методы дискретного программирования. Техническая кибернетика, 1983, № I, с.165-176.

3. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978. - 352 с.

4. Йодан Э. Структурное программирование и конструирование программ. М.: Мир, 1979. - 415 с.

5. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. М.: Наука, 1983. - 208 с.

6. Бусленко Н.П. Моделирование сложных систем. М.: Наука, 1978. - 400 с.

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

8. Акрамовский ГЛД. Применение метода динамического программирования для решения задачи размещения микросхем на печатных платах. В кн.: Автоматизация проектирования средств автоматики и вычислительной техники. Саратов, 1976, с.19-22.

9. Автоматизация проектирования цифровых устройств / С.И.Баг-ранов, С.А.Майоров, Ю.П. Сахаров, В.А.Селютин. Л.: Судостроение, 1979. - 264 с.

10. Гавриленко В.Й., Юсим Г.В. Теоретические основы конструирования и надежности электронно-вычислительной аппаратуры. Рязань: РРТИ, 1976. - 208 с.

11. Гайфуллин Э.Ш., Егоров А.Г., Юсим Г.В. Оптимальное разбиение функционально-логических схем с учетом контактных ограничений. Электронная техника, серия 3, Микроэлектроника, 1975, вып. 2 (56), с.108-112.

12. Деньдобренко Б.Н., Малика A.C. Автоматизация конструирования ЭВА. М.: Высшая школа, 1980. - 384 с.

13. Егоров А.Г., Юсим Г.В. О покрытии функционально-логических схем набором несвязных модулей. В кн1: Автоматизация проектирования средств автоматики и вычислительной техники. Саратов, 1976, с.9-10.

14. Карапетян А.М. Автоматизация оптимального конструирования ЭВМ. М.: Сов.радио, 1973. - 152 с.

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

16. Медведев A.C., Штейн М.Е. О задачах компоновки и размещения компонентов цифровых узлов. Управляющие системы и машины, 1979, № I, с.70-73.18» Методы разбиения схем на конструктивно законченные части / под ред. К.К.Морозова. М.: Сов.радио, 1978. - 136 с.

17. Проектирование монтажных плат на ЭВМ / под ред. К.К.Морозова. М.: Сов.радио, 1979. - 224 с.

18. Морозов К.К., Одиноков В.Г. Использование ЭЦВМ при конструировании некоторых узлов РЭА. М.: Сов.радио, 1972. - 104 с.

19. Петренко А.И., Тетельбаум А.Я. Формальное конструирование электронно-вычислительной аппаратуры. М.: Сов.радио, 1979. -256 с.

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

21. Теория и методы автоматизации проектирования вычислительных систем / под ред. М.Брейера. М.: Мир, 1977. - T.I, 298 с.

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

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

24. Юсим Г.В., Горин B.C. О совместном решении задач разбиения и покрытия, В кн.: Автоматизация конструкторского проектирования РЭА и ЭВА. Пенза, 1977, с.20-24.

25. Курейчик В.М., Лисяк В.В., Перельман A.JI. Автоматизированные системы проектирования фотошаблонов БИС. Зарубежная радиоэлектроника, № 5, 1979, с.74-89.

26. Рр/ггрг/t. /УррА . "9 /977 , У. /!/27 р. 264- 2 ТР.

27. Spfr/gtscA/ Yas/z/r/ /I ¿s/7/fy//?g fra/new* 0/ юлvSf/rato/v'at 0/>f//n/zaf/0/? ; fape yö^oj?-/г0/гт/гт//?£ а/г/У /Лг ^¿/¿У'2'j/ . CZ ¿fops*. #PS. S0P. Уд/Ъ. "9 /äf/, x w, 67-p4.

28. Моисеев H.H. Численные методы в теории оптимальных систем. M.j Наука, 197I. - 424 с.

29. Петренко А.И. Основы автоматизации проектирования. Киев: Техника, 1982. - 295 с.

30. Уздемир А.П. Схема последовательной декомпозиции в задачах оптимизации. Автомат, и телемех., 1980, № II, с.94-105.

31. Бондаренко В.А. Неполиномиальная нижняя оценка сложности задачи коммивояжера в одном классе алгоритмов. Автомат, и телемех., 1983, 9, с.45-50.

32. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.37 .¿а/7 С/ /!.//., XI. ¿Р. А 77 C?7/t0/770f/0 /77£>¿/700/ 0/so/v/siß ¿//s0/*pfp jb/i^/ta/v/rt/^ jOsi/p&p/ks . -„£¿>0/70-/7iPfs*/00 " SP60, X Si , Л73.

33. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965. - 458 с.39. /ягс/р/* £.1. Г/гр assiß/7/770/2 f у>/*£>#/р/,77\ -„At0/?ap. Sei. *9 /¿>66 > к j? л/4} р. £-££-£№.

34. Z>S/*P0to/* S. И/., /¡.Р.7 S/pV/'0/*p£ Л Я, T60/770S1.*

35. Л£. T/tP ¿bw/y/p ¿/¿>¿¿0/7 iz/r/ws/ty ¿fes/g/t ¿?г//0*7/7 ¿S0/z tySte/rt : ¿/a///S ¿7гг/У J/z/u^P ¿?/>*PPt/0/z.

36. MI££E 1/7?. Sy/np. £/>/>///fs a/z/У ¿¿/sf. /^00. r9 ¿¿/рядя, Mr W, А ¿7-20, W, />• 4M

37. Рустамов H.A., Тютин A.A. Об одной реализации алгоритма размещения графа на плоскости. В кн.: Вычислительная техника. Каунас, 1976, т.8, с.83-85.

38. Норенков И.П., Маничев В.Б. Системы автоматизированного проектирования электронной и вычислительной аппаратуры. М.: Высшая школа, 1983. - 272 с.

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

40. Лебедев Б.К. Использование точных методов для решения задач технического проектирования вычислительных структур. В кн.: Автоматизация конструкторского проектирования РЭА и ЭВА. Пенза, 1977, с.5-8.

41. Лебедев Б.К. Исследование и разработка программного обеспечения для систем автоматизированного конструкторского проектирования вычислительных структур на базе поисковых алгоритмических методов: Автореф. дис. канд. техн. наук. Л., 1980. - 26 с.

42. Берштейн Л.С., Селянкин В.В. Применение гиперграфОЕ для точного решения задачи линейного размещения элементов. В кн.: Вычислительная техника. Каунас, 1974, т.6, с.54-56.

43. Курейчик В.М., Лебедев Б.К. Система проектирования печатного монтажа. В кн.: Автоматизированное проектирование в радиоэлектронике и приборостроении. Изв. ЛЭТИ, Л., 1980, вып.266,с.67-73.

44. Пучиньян В.К., Шеин П.Д., Штейн М.Е. Задача оптимального разбиения графа и компоновка устройств ЦВМ. В кн.: Системы распределения ресурсов на графах. М.: ВЦ АН СССР, 1970, с.118-125.

45. Берштейн Л.С., Селянкин В.В. О минимальном разрезании графов со взвешенными ребрами. Электронная техника, серия АСУ

46. ЦНИИ Электроники, 1976, № 4, с.91-96.

47. Горинштейн Л.Д. О разрезании графов. Техническая кибернетика, 1969, )Ь I, с.79-85.51» Абрайтис Л.Б. Алгоритм определения максимально связанных наборов элементов. Автоматика и вычислительная техника. Рига, 1970, № 5, с.40-47.

48. Курейчик В.М., Лебедев Б.К. Минимизация внутрисхемных пересечений методом ветвей и границ. В кн.: Машинные методы проектирования электронных схем. М.: МДНТП, 1975.

49. Петренко А.И., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизация конструирования электронной аппаратуры. Киев: Вища школа, 1980. - 176 с.

50. Юеим Г.В., Таганов А.Й., Пимахин В.М# Реализация совместного решения задач, предшествующих трассировке. В кн.: Вычислительная техника. Вильнюс, 1979, т.12, с.93-95.

51. Пимахин В.М., Юсим Г.В. Алгоритм параллельной трассировки. В кн.: Автоматизация проектирования ЭВМ и систем (тезисы докладов Всесоюзной научно-технической конференции). Ереван, 1983, ч.2, с.167-169.

52. Pvsso /Р./, Ос/р/? P.//., k/oljf Р. Л*. А ¿pv^/slS* р/>0СРб/г/"£> jbs* ¿¿р а/гс/ ¿>/ wn/wtps* ¿¿?p/'s> ^¿г^Лр. # TP EE TwrS. "7 /Р7/,v. ec-2d, ///2, /¿¿2.

53. Морозов К.К., Одиноков В.Г., Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. -М.: Радио и связь, 1983. 280 с.

54. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. -Львов: Вшца школа, 1981. 168 с.

55. Петренко А.И., Тетельбаум А.Я., Забалуев H.H. Топологические алгоритмы трассировки многослойных печатных плат. М.: Радио и связь, 1983. - 152 с.

56. Сапожков К.А., Бершадский A.M., Соловьев В.В. Разрезание графа схемы волновым алгоритмом. В кн.: Вычислительная техника, Каунас, 1975, т.7, с.292-294.

57. Бойко В.Н., Герасименко Е.П., Кот В.И. Размещение модулей волновым алгоритмом с учетом метрико-топологических требова^-ний. В кн.: Вычислительная техника. Каунас, 1976, т.8, с.80-82«

58. Автоматизация проектирования печатных блоков с модулями произвольной форш / Е.П.Герасименко, В.И.Кот, И.Я.Ландау, В.М. Сомкин. М.: Машиностроение, 1979. - 167 с.

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

60. Акрамовский Г.М., Тюленев С.А., Кандауров Ю.Г. Алгоритм трассировки двусторонних печатных плат. В кн.: Автоматизация проектирования средств автоматики и вычислительной техники. Саратов, 1976, с.39-42.

61. Петросян A.B. и др. Об одном подходе к автоматизации проектирования печатных плат. Кибернетика, 1974, № I, с.50-57.

62. Горин B.C. Комбинаторный алгоритм размещения микросхем на печатной плате. В кн.: Конструирование специализированной электронно-вычислительной аппаратуры. - Рязань, 1984, с.102-106.

63. Терещенко B.JI. Метод повышения качества машинной трассировки печатных соединений. В кн.: Вычислительная техника. Каунас, 1974, т.6, с.101-102.

64. Петросян A.B. и др. Этап размещения при МИ АППП. В кн.: Вычислительная техника. Каунас, 1974, т.6, с.66-69.

65. Петросян A.B. и др. О реализации этапа размещения методом интервалов. Вопросы радиоэлектроники. Серия ЭВТ, 1974, вып.6, с.46-51.

66. Базилевич Р.П., Ткаченко С.П. Решение задачи разбиения методом параллельного свертывания. В кн.: Вычислительная техника. Каунас, 1975, т.7, с.295-298.

67. Базилевич Р.П., Ткаченко С.П. Применение параллельного подхода к решению задачи покрытия схемы подсхемами из заданного набора. Вестн. Львов, политехи, ин-та, 1977, № 8. Доклады и научные сообщения, с.120-122.

68. Геолецян Г.Г. О задаче оптимального размещения вершин графа на отрезке. ДАН Арм.ССР, 1973, № 5, с.269-271.

69. Маркосян С.Е., Геолецян Г.Г. Оптимальное линейное размещение схем при помощи гиперграфов. В кн.: Вычислительная техника. Каунас, 1975, т.7, с.315-317.

70. Горин B.C., Чикин В.А., Юсим Г.В. Подсистема компоновки ТЭЗов. В кн.: Автоматизированное проектирование в радиоэлектронике и приборостроении. Изв. ЛЭТЙ, Л., 1980, вып.266, с.89-92.

71. Мухачева Э.А., Рубинштейн Г.Ш. Математическое программирование. Новосибирск: Наука, 1977. - 319 с.

72. Одиноков В.Г., Теребенков А.П. Математическая модель оптимизации жгутового монтажа. В кн.: Конструкторско-технологи-ческие аспекты проектирования РЭА. М., 1981, с.98-103. (Труды / МИРЗА).

73. F/rartcpsPo /У. Г/?р рр/ярРрх/Ту о/ 0/>f//?r/*aJ/£>/7 ¿?/7¿У /¿р pAattps/g'P ¿?f

74. Ap/y/i/sf/ps. -Z/?: „ ¿P/} ¿f/ Wr/7. /Pct. Su/r?/r7Ps S<?/?,

75. W? fyfrm/s. ¿fr&Wfi, W7/MSfApstps* P.a., /&7Р, p. /07-/Ж

76. Sa/*faJ S.7 /¡/и/ S. T6P pa/rrfiJpx/ty ¿?f ¿/ps/£M /na//0/t />/r0#/p#rs, -I/r „ /7 J>ps. £0/7/. P/<00.? /7//7/fP0p07/\s, /У//?*., /№"№>*/ , *№,/>. 402-4/t

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

78. Емеличев В.А. Дискретная оптимизация. Последовательност-ные схемы решения. Кибернетика, 197I, № б, с.109-121; 1972,2, с.92-103.

79. Емеличев В.А., Комлик В.И. Метод построения последовательности планов для решения задач дискретной оптимизации. М.: Наука, I98I. - 208 с.

80. Нильсон Н. Искусственный интеллект. М.: Мир, 1973. -270 с.86 • Z. O/t P/ip/rrp/ipZ/as? yö/*0PP£ZP/*£>s fop ZAw<p/r?

81. Ja* Z/z/typs* /?/*aß/*a/#/?7//zg. Z"/7; Ap/P^pza ¿a/tpuepp р/гр/ /&7£t/>. 4/-52.

82. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования, М.: Наука, 1976. - 264 с.

83. C/p/rrps /?. Tpu/ps**/ ¿7 J/fp/np-wp/*/? /а* App/*/s-z/p p/öz//7?/\zpz/p/?, -7/?:/fA!»0p £р/*//т^ Ap/zp. Oppf. a/rt/

84. Филоненко H.B. Вопросы приближенного решения задач целочисленного параметрического программирования. Кибернетика, 1979, № 5, с.91-94.

85. Минаев Ю.Н. Унифицированный формально-эвристический алгоритм решения задачи целочисленного линейного программирования. Кибернетика, 1980, № 4, с.131-135.

86. HQ рчр^тр/77/г7/A/P/Apc/S ¿2/rat App//PP//^/7S.

87. Dps<p//*ppA/ Ab//a/?a/, /?.

88. Кани К., Оцуки Т. Применение теории графов и комбинатор« ных алгоритмов в автоматизации проектирования. Дзёхо сёри, 1975, т.16, № 7, с.581-590.

89. Fpp/c/p/?fp/c/s «7, /Ур/а/т^/У/г ¿7.7). d Ap///*/'s//'ptf/*a/?p/? -¿?/?pf- ¿?/б?р/>///?/77 ¿/р/* /р/рр/?р/7р Jppp/p/*

90. РР/?РР/У^ р>//эаля//?/?, -„¿ррл /?ps."/ к 27, ж ^$67-5*2.

91. J>zp^P/* £. ^ /?-p~a/7S ¿fa/vps /?. A &<а/7р/? -0/7р/-#рг//гг/ a/^p/t/t/г/к Jp/* /Ар ¿/¿/ £p/pp//p/? /> ¿//~ /<рр/ /па// aabrs ¿/st/up. „ /%?/?&¿7. SP/. ", /Ж/, К 27/ л/6, p. 652-££7.

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

93. Горин B.C., Юсим Г.В. Сокращение комбинаторного перебора при решении задачи разбиения электронных схем. В кн.: Автоматизация проектирования ЭВМ и систем (тезисы докладов Всесоюзной научно-технической конференции). Ереван, 1983, ч.2, с.166-167.

94. Юсим Г.В., Горин B.C. Компоновка схем, содержащих "разногабаритные" базовые элементы. В кн.: Специализированные и комбинированные вычислительные устройства. Рязань, 1978, с.120-122.

95. Gamó/S* yawtfs Га/7/j f. У. Autowat/e pactaа/ /vZ/r/fr f¿/"/\s£>¿/ ¿7/>¿7¿//fs. -7/?: Bleetia/r/p ¿?//*¿>¿// f PasA'ap/*^ ^¿//п/эаз/г//??. /#¿2,1. V. 2, p. 2/9-232.

96. Юсим Г.В. Алгоритм компоновки цепей. В кн.: Автоматизированное проектирование в радиоэлектронике и приборостроении. Изв. ЛЭТИ, Л., 1979, вып.249, C.II4-II7.

97. Блонскис И.С., Лапене П.П., Ришкус А.Б. Алгоритм генерации случайных схем цифровых устройств. В кн.: Вычислительная техника, Т.8. Каунас, 1976, с.41-42.

98. Щтейн М.Е., Медведев A.C. К задаче размещения компонент.-Управляющие системы и машины, 1974, № 2, с.77-80.

99. Горин B.C. Реализация методов сокращения перебора при решении задачи размещения. В кн.: Микроминиатюризация радиоэлектронных устройств. Рязань, 1983, с.21-25.

100. Вепринский Г.Ю., Райз Е.Ш., Фридман И.Я. Один алгоритм распределения проводов по каналам. В кн.: Вычислительная техника. Каунас, 1975, т.7, с.374-376.

101. НО. Форд Л., Фалкерсон Д. Потоки в сетях. М.: Мир, 1966. -276 с.

102. F/s/гр/* Ml. h/psst -fasp а/7û¿уs/s а/¿pw/s/Zps. -7* ' „ Ts? fes*fa PPS 6Р£*О>РР/? ¿Ь/ярг/?. SP/, œ/ггУ ¿Рррг*.

103. Pes. Sy/72/).; /¡/ffs/p^tfa/ff, /#76, VM/^aä;1. S07£, p. £7-/04.113. ¿ÛWP/7PF h/.A. //puf/st/p a/ta/^s's, ¿/VtPûf1аяс/ fra/îp/r „ //а//2.

104. P/tpya/77. S/г/аЬ/", ffJû, к p- /2/-/34.

105. Вепринский Г.Ю. и др. Проектирование проводного монтажа для ЭВМ третьего поколения. В кн.: Вычислительная техника. Каунас, 1974, т.6, с.138-141.

106. Грекович A.B. и др. Od автоматизации проектирования про> водного монтажа модульно-блочной аппаратуры. В кн.: Вычислительная техника. Каунас, 1974, т.6, с.134-137.

107. Виват Ю.Л., Забатов Л.И., Салмов Н.В., Чеблукова Т.Ф. Обработка схем связей узлов и подготовка управляющих монтажных перфолент на ЭВМ. Обмен опытом в радиопромышленности, 1983, № 2, с.15-18.

108. Лобов B.C. Проектирование жгутов блоков РЭА с использованием ЭВМ. Обмен опытом в радиопромышленности, 1980, № 4,с.13-14.

109. Моргун Н.В. Трассировка электрических цепей проводного монтажа с учетом специальных требований к их структуре. В кн.: Теория и методы автоматизации проектирования. Минск, 1982, вып. 2, с.116-123.

110. Аналоговые и цифровые интегральные схемы / под ред. C.B. Якубовского. M.s Сов.радио, 1979. - 335 с.120» Интегральные микросхемы: Справочник / Б.В.Тарабрин, Л.Ф.Лунин, Ю.Н.Смирнов и др.; Под ред. Б.В.Тарабрина. М.: Радио и связь, 1984. - 528с.

111. Горин B.C. Решение задачи покрытия для наборов модулей специального вида. В кн.: Автоматизация проектирования электронной аппаратуры. Таганрог: ТРТИ, 1984, с.101-104.