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

Введение.

Глава I. Обзор основных задач конструкторского проектирования SBM.

§ I. Некоторые оптимизационные задачи комбинаторного типа, возникающие на этапе конструкторского проектирования и методы их решения.

§ 2. Основные подходы, применяемые при решении оптимизационных задач проектирования.II

§ 3. Формальная постановка задачи компоновки, размещения, трассировки и распределения инвариантных выводов.

Глава IX. Математические модели и алгоритмы решения задач проектирования узлов ЭВМ.

§ I. Компоновка базовых элементов в модули.

§ 2. Размещение компонентов на монтажном поле. 46.

§ 3. Распределение внешних выводов узлов ЭВМ.

Глава III. Формирование графической информации при проектировании печатных плат.

5 I. Принципы подготовки управляющих программ для автоматизации изготовления узлов ЗВМ.

§ 2. Математическая модель и алгоритм решения одной задачи типа задачи коммивояжера.

Глава 1У. Система автоматизированного проектирования цифровой аппаратуры ДИСИО.•.

§ I. Назначение и структура системы.

§ 2. Принципы функционирования системы ДИСИО.

§ 3. Входной язык системы ДИСИО.-.

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

Согласно [I] , проектирование ЭВМ разделяют на этапы: системное проектирование, проектирование математического обеспечения, логическое, конструкторское проектирование, проектирование электронных схем.

В настоящее время в разных организациях реализованы и используются ряд систем и подсистем автоматизированного проектирования (САПР), имеющие различное целевое назначение (см. например [1-27])» Большой вклад в развитие автоматизации конструкторского проектирования внесли различные коллективы под руководством Абрайтиса Л.Б., Глушкова В.М., Ландау И.Я., Майорова С.А., Матюхина Н.Я., Пескова М.И., Петренко А.И., Рябова Г.Г., Рябова Л.П., Селютина В.А. и ряда других советских ученых,

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

1) компоновка базовых элементов в модули;

2) распределение инвариантных выводов модулей;

3) размещение радиоэлементов на поверхности печатной платы;

4) распределение инвариантных контактов разъема;

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

Исходной информацией при проектировании узлов ЭВМ являются техническое задание на конструкцию, электрическая схема и перечень элементов. В техническом задании указаны требования, предъявляемые к конструкции, различные технические ограничения, Перечень элементов содержит описание типов элементов, которые входят в электрическую схему, их обозначения по ГОСТу, электрические параметры.

Электрическую схему можно представить в виде графа G[19J, в котором различают несколько типов ребер и вершин. Введем вершины трех типов ^ }■ Вершины V соответствуют элементам схемы, ^ - Pix количество, вершиныX -выводам элементов,включая внешние выводы схемы,/I-их количество, а вершины Т - цепям схемы, С - количество цепей. Среди ребер графа G различают элементные ребра F и сигнальные W , Элементные ребра определяют принадлежность выводов из множества X элементам из множества и задаются парами вершин fe^J , Сигнальные ребра определяют вхождение выводов из X в отдельные цепи и описываются парами вершин föj, V, J~ l- i,C . при подготовке информации электрическую схему задают в виде списка цепей. Граф G также задают и в виде матрицы ai/HtAS » гДе ^ - количество модулей,

5 - максимальное количество выводов модуля -го типа, а элемент номеру цепи в схеме, если вывод модуля £ -го типа входит в данную цепь, О в противном случае.

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

ЭВМ.

12-13,15-18,21-22]отсутствует автоматизированный этап: компоновки базовых элементов в модули. САПР [5,8,13,18,21] не обеспечивает автоматизацию размещения разногабаритных элементов. В большинстве САПР реализован один алгоритм для решения задач определенного класса, причем, как правило, выбор оптимального решения производится по одному критерию, т.е. оптимизируется скалярная целевая функция. Так как целевая функция в задачах проектирования является не скалярной, а векторной, то результаты решения, полученные при помощи такого алгоритма, не всегда удовлетворяют технологическим и конструкторским требованиям. Часто на производстве используют несколько САПР, которые отличаются кругом решаемых задач, но их совместная эксплуатация и передача информации между ними затруднены из-за различия во входных языках. На эффективное использование САПР в большой мере влияют и технические средства, выбранные разработчиком при проектировании системы.

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

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

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

Работа состоит из четырех глав.

Основные результаты диссертационной работы опубликованы в следующих работах:

I. Тимофеева Н.К, Один алгоритм оптимальной компоновки базовых элементов в корпуса интегральных микросхем.- В кн.: Алгоритмы и программы решения задач дискретной оптимизации.Киев: Ж АН УССР, 1980, с. 3-19.

2. Тимофеева Н.К. О разработке математического обеспечения САПР ЭВМ, предназначенного для решения некоторых задач конструкторского проектирования,- В кн.: Программное обеспечение ЭВМ, Сб. научн. тр. Киев: ИК АН УССР, 1982, с. 10-15.

3. Тимофеева Н.К,, Гуляницкий Л.Ф. О размещении разногабаритных элементов ЭВМ на печатных платах,- Управляющие системы и машинв, 1982, № 3, с. 50-53.

4. Тимофеева Н.К. Об оптимальном распределении внешних контактов печатной платы.-В кн.: Программное обеспечение экстремальных задач и пакеты прикладных программ. Сборник научных трудов. Киев: Ж АН УССР, 1982, с. 50-56.

5. Тимофеева Н.К, Решение одной задачи типа задачи коммивояжера при проектировании компонентов ЭВМ,- Кибернетика, 1983, 5, с. 73-76.

6. Тимофеева Н.К. Анализ и апробация некоторых алгоритмов автоматизированного проектирования узлов ЭВМ,- В кн.: Математическое обеспечение пакетов программ. Сборник научных трудов.

Киев: Ж АН УССР, 1983, с. 26-34.

ЗАКЛЮЧЕНИЕ Основные результаты и выводы

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

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

3. На основе предложенных моделей и алгоритмов разработана и внедрена в практику САПР ДИСИО, предназначенная для автоматизации конструкторского проектирования цифровой аппаратуры.

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

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

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

2. Петренко А.И., Шурин О.Ф., Киселев Г.Д. Автоматизация проектирования цифровых схем. Киев: Вида школа, 1978. - 151 с.

3. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем. -М: Высшая школа, 1980.- 312с.

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

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

6. Арустамов С.А., Кузнецов Л.Л., Петухов Г.А., Яковлева С.Ю. Промышленная система автоматизированного проектирования топологии многослойных печатных плат.- Управляющие системы и машины, 1983, 16, с. 28-32.

7. Вольфензон А.Я., Демидов Г.П., Заполоцкий Д.Е., Песков В.Ш., Штейман Д. М. Диалоговая система проектирования печатных плат на комплексе АРМ.- Управляющие системы и машины, 1983,$ 2,с. 32-36.

8. Бахтин Б.И. Автоматизация в проектировании и производстве печатных плат радиоэлектронной аппаратуры.,- Л.: Знергия, 1979. 120 с.

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

10. Ю. Автоматизированная система проектирования двухсторонних платпечатного монтажа (ППП-АСППП),-М.: Научно-исследовательский институт информации по машиностроению, 1982,- 82 с.

11. Батанов I.A. Автоматизация проектирования цифровых вычислительных систем,- М.: Энергия, 1978,- 81 с,

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

13. Гурвич Е.И., Крапчин H.A., Гольдин В.В. и др. Автоматизированная система проектирования цифровых устройств и систем,- В кн.: Обмен опытом в радиопромышленности: Сб. статей,- М.: НИИЭИР, 1975, вып.6, с. 20-23.

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

15. Дмитриевич Г.Д., Антропов А.Н., Стрельников Ю.Н. Интерактивно-алгоритмический метод автоматизированного проектирования печатных плат. В кн.: Автоматизация конструкторского проектирования РЭА и ЗВА. Тезисы докладов.',-Пенза, 1982, с. 19-21.

16. Елшин Ю.М, Проектирование печатных плат с использованием-АРМ-Р,- В кн.: обмен опытом в радиопромышленности: сб. статей.- М.: НИИЭИР,1979, вып.10, с. 1-9.

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

18. Орловский Г.В., Козенова И.М., Квальвассер О.Г. и др. Архитектура системы автоматизированного проектирования радиоэлектронной аппаратуры,- В кн,: Обмен опытом в радиопромышленности: сб. статей.- М.: НИИЭИР, 1975, вып.6, с. 11-14.

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

20. OdaviïQta Gobato^JcJc/na KdiiLfiifaJcHihata Haolo,Kiyomatsii Jetsuto, PAS-LOP:M automatic modute iocatioiz system, fot> PWB-ACM/1EEE /8tâ Ûes.dutom. Conf. Ргоо. UfosfiriMeTennJune г9-30f ¿и. ty J, ¿981, NEY Yozt, N. Y., ¿921, /55- /59.

21. Тютин A.A., Рустамов И.A., Решетько A.И. Информационно- техническое обеспечение системы автоматизированного проектирования печатных плат.- Управляющие системы и машины, 1976,1. J5 3, с. 66-73.

22. Винигзенко ЙД^, Мирных Ю.Ф. Карл -3 система автоматизированного конструирования печатных плат.- В.кн.: Автоматизация конструкторского проектирования РЭА и SBA. Тезисы доклад ов.-Пенза, 1982, с, 65-68.

23. Львов Ю.М., Свечникова Л.И., Векшин Е.В. Автоматизация изготовления фотошаблонов с выпуском детальных и сборочных чертежей печатных плат.- В кн.: Автоматизация конструкторского проектирования РЭА и ЗВА. Тезисы докладов.- Пенза, 1982, с. 9-II.

24. Аксенов Ю.П.,Антропов Г.Е., Туганков В.Н., Федоров А.П. Система автоматизированного проектирования фотошаблонов печатных плат (САПР "Фотошаблон").- В кн.: Автоматизация конструкторского проектирования РЭА и ЗВА. Тезисы докладов.- Пенза,1982, с. 12-13.

25. Забара С.С. Задачи и программное обеспечение интерактивной графической системы. Управляющие системы и машины, 1978, В 4, с. 95-102.

26. Пахомов В,Л. Система "Граф" Дубна, 1979.-7с./0бъедшенный ин-т ядерных исследований; Препринт-РП-12665/

27. Пахомов В.Л., Хуторный Н.В. Программное обеспечение фотокоординатографа АДМАП-3, сверлильного станка ВП-910 и оцифровщи-ка ЗМ-709.-Дубна, 1981,-4с.-/Объединенный ин-т ядерных исследований; Препринт-П-81-817/.

28. Подиновский В.В., Гаврилов В.М. Оптимизация по последовательно применяемым критериям,- М,: Сов, радио, 1975,- 192 с,

29. Глушков В,М. О системной оптимизации,- Кибернетика, 1980, J!> 5, с. 88-90,

30. П0диновский В.В., Ногин В.Д. Парето- оптимальные решения многокритериальных задач,- М.: Наука, 1982,- 256 с,

31. Кузьмин Б.А., Эйдес A.A. О критериях качества размещения.-Управляющие системы и машины. 1982, J3 3, с. 53-56.

32. Рожанковский Р.В., Гук В.К. Улучшение качества проектирования двухслойных печатных плат путем итерационного переразмещения элементов.- В кн.: Автоматизация конструкторского проектирования РЭА и ЗВА. Тезисы докладов.- Пенза, 1982, с. 41-43.

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

34. Гулянщкий Л.Ф., Каспшицкая М.Ф., Сергиенко И.В. О подходахи алгоритмах решения некоторых оптимизационных задач автоматизации проектирования ЭВМ и систем.- Кибернетика, 1976, JS 5, с. 61-71.

35. Кейс П., Грагоф Г., и др. Автоматизация проектирования вычислительных систем с использованием логических схем на ".'твердом теле.- В кн.: Кибернетический сборник. Новая серия. Вып.1. М.: Мир, 1965, с. 162-190.35.962, V2, р. г/9-252,

36. Крыжановский Ю.И.компоновка конструкторских элементов цифровых устройств,- В кн.: Применение вычислительных машин для проектирования цифровых устройств,jvU: Сов. радио, оборщщ статей;. I9ß8, е., 153^164,

37. Абрайтис Л.В., Шимайтис А.П. Алгоритмы компоновки узлов и исследование их эффективности,- В кн.: Вычислительная техника. III, Каунас, политех, ин-т. 1971. с.66-76.

38. Keinigfran ß.W,LLn $Jn efficient Aeutistic pwcQduze fot pottitionin.дpapfis- "Ш Syst. TechnJWO, к U9. Иг, p. 29f-bo 7.

39. Мелихов A.H., Берштейн Л.С., Селянкин В.В., Хиль М.И. Применение гиперграфов для компоновки схем в ячейки.- Изв. АН СССР. Техническая кибернетика, 1974,$ 3, с, 202-207.

40. Тетелъбаум А.Я, Метод разбиения сложной системы на малосвязанные подсистемы.- В кн.: Автоматизация проектирования в электронике. Вып.12, Киев, ТехнГка, 1975, с. I08-112.

41. Гильдбурд М.М. Об эвристических методах решения задачи разбиения множества взаимосвязанных объектовт— Автоматика и телемеханика, 1984:, Ж, с. 107-ИЗ.

42. Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации,- Киев: Вища школа, 1983.- 511 с.

43. Перепелица В.А. Асимптотический подход к решению некоторых экстремальных задач на графах,-В кн.: Проблемы кибернетики, Вып.26. М.: Наука, 1973, с. 291-514.

44. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации,- К.: Наукова думка, 1981,- 288 с.

45. Линский B.C. Алгоритмическое проектирование вычислительных цифровых устройств.- М.: ВЦ АН СССР, 1963.- 134 с.

46. Заполоцкий Д.Е., Вольфензин А.Я. Алгоритм размещения одногабаритных элементов методом потенциалов,- Управляющие системы и машины, 1983, № 5, с. 32-34.

47. Серг1енко I.B, Один метод розв'язування задач на в1дшукання екстремальних значень,- Автоматика, 1964,Ji 5, с. 15-21.

48. Гуляницкш! Л.Ф., Ходзинский А.Н. Особенности реализации алгоритмов метода ветвей и границ и метода вектора спада в пакете ВЕКТОР -IB.-В кн.: Вычислительные аспекты в пакетах прикладных программ: сб.статей,- Киев: ИК АН УССР, 1979, с. 45-48.

49. Тютин А.А, Улучшенный алгоритм размещения.интегральных схем на плате.- Киев, 1972,-23 с. -/ АН УССР. Ин-т кибернетики; Препринт 72-3,

50. StelriBeiy I., The Back доагсЬ Wiling РгоВСет-.Л рвасетепТ JLtcjotLtflrn, "61 AM HevLew"l, v.3, Noi. I96it p.67,

51. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение.- 1,11-Кибернетика, 1965, JS I, с. 45-56; J3 2, с. 55-88.

52. Герасименко Е.П., Кот В.И. Автоматизированная система конструкторского проектирования печатных плат с модулями произвольной формы,-Управляющие системы и машины, 1975, Ж, с. II6-I2I.

53. Гуляницкий Л.Ф. ,Сергиенко И.В., Ходзинский А.Н. Диалоговый пакет программ ВЕКТОР-2. Киев, 1981,- 55 с. / АН УССР. Ин-т кибернетики; Препринт-81-63/.

54. Эрперт A.M., Васецкий Г.Е. Графотеоретический метод размеще -ния модулей на печатной плате.- В кн.: Вычислительная математика в современном научно-техническом прогрессе: Материалы

55. Респ. конф./Пуща-Водица, 1978/, Киев,изд. Киев, ун-та, 1978,с. 2II-2I2.

56. Сосницкий A.B. Об одном подходе к размещению цифровых схем на печатных платах.- Управляющие системы и машины, 1977,5,с. 123-130.

57. Тюренков В.А. Алгоритмы нахождения кратчайшего пути.- В кн.: Вычислительные системы. Новосибирск. ИМСО АН СССР, 1963, вып. 6,с. 41-44.

58. Гурвич Е.И., Кралчин А.И. Быстродействующий алгоритм трассировки двухслойных печатных плат,- В кн.: Вычислительная техника, т, 1У. Каунас, политехи, ин-т, 1973, с. 132-136.

59. РгрИао И, design automation, fot Eatqe.

60. Sea Be Lntecjt-œtLorL.- In.: We scon TecfuilcciL Papers, Los Ange ees, Coiif, /966.

61. Андреев Г.Д., Петухов Г.А., Скорубский В.Н. Компенсирующий алгоритм поиска малоповоротных путей.- В кн.: Вычислительная: техника,т III. Каунас, политехи, ин-т, 1972, с. 380-386.

62. Gtesst М.А, Une méthode destace en Ucfaiotogie^tocs (ten$es",-îfiiCoCCoyue ¿ntetnationaí виг 6& тссгоебесНо-nic^iie a van ceé" Pa lis, Pa nod, i9 ÏO, p. 393- 4 Oí\

63. Гурвич Д.З., Селютин В.А. Алгоритмические методы проектирования топологии БИС ячеечного типа,- В кн.: Методы расчета и автоматизация проектирования устройств микроэлектронных ЦВМ,-Киев.: Ж АН УССР, 1973, с. 83- 92.

64. Лазарева Т.С. Алгоритм трассировки печатных соединений на основе представления о каналах.- Автоматика и вычислительная техника, 1969, JS 5, с. 12-15.

65. Лошаков В.Н. Система автоматизации проектирования БИС с применением ЭВМ.- Электронная промышленность, 1970, 2, с, 45-49,

66. Герасименко В.П., Кот В.И. Проектирование печатного монтажа путем моделирования его с помощью рецепторных полей на ЦВМ,-В кн.: Конструирование и внедрение новых средств вычислительной техники. Вып.2. Киев: Ж АН УССР. 1970, о. 97-108.

67. Зыков A.A. Теория графов.- Новосибирск. Т I, 1969, 543 с.

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

69. Селютин В.А., Львов Н.П., Першурич A.A., Сердюк Т.В. Реализация теоретико-графового подхода к автоматизированному синтезу топологии интегральных микросхем,- В кн.: Вычислительная техника. Т. УШ. Каунас, политехи, ин-т. 1976, о. 22-25.

70. Гинзбург Б.Д. , Никитина P.K. Новый подход к задачам размещения микросхем на плате и закрепление внешних контактов.- Вопросы радиоэлектроники. Сер» УН. Злектронная вычислительная техника, 1972. Вып.З, с. 85- 92,

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

72. Рощин Г.Б. 0 двух подходах к распределению инвариантных контактов разъема,- В кн.: Вычислительная техника. Т 1У. Каунас, политехи, ин-т. 1973, с. 170-174.

73. Плотников A.B., Марков Ю.К. Рациональное распределение контактов схемы узла РЭА.- В кн.: Обмен опытом в радиопромышленн-ности: сб. статей,- М.: НИИЗИР, 1979, вып. 10, с. 13-15.

74. Абрайтис А.Б.', Шайнаускас Р.И., Шимайтис А.П. Распределение инвариантных контактов,соблюдая плоскостные ограничения:

75. В кн.: Вычислительная техника. Каунас. 1972, т III, с. 368372.

76. Меркурьев В.В., Молдавский М.А. Поиск нескольких эффективных решений в непрерывных задачах оптимального проектирования.-Управляющие системы и машины, 1979, $ I, с. 77- 81.

77. Глушков В.М.Введение в АСУ,-Киев: Техн1ка, 1974. 319 с.

78. Дымков''M.П. Исследование задач многокритериального линейного программирования.- Проблемы оптимального управления. МиН.ск, 1981, с. 25-42,

79. В eon, and Ñatfi. Syst, i9U, J90,

80. Рустамов И.А., Тютин A.A. О решении задачи размещения конструктивных компонентов с учетом требований трассировки.- Управляющие системы и машины, té 6, 1975, с. 107-115.

81. Мелихов А.Н., Берштейн Л.С., Селянкин В.В. Решение задачи размещения элементов с помощью гиперграфов.- В кн.: Методы расчета и автоматизация проектирования устройств микроэлектронных ЦВМ. ИК АН УССР, 1973, с. 38-53.

82. Петросян A.B., Шукурян Ю.Г., Маркосян С.Е., Амбарян С.Л. Об одном подходе к автоматизации проектирования печатных плат,-Кибернетика, té I, 1974, с. 50-г57.

83. Жованик П.И., Ткачев Э.И. Алгоритм размещения элементов на печатной плате с использованием изменяющихся критериев оптимизации.- В кн.: Автоматизация проектирования радиоэлектронной аппаратуры на промышленных предприятиях.-. Запорожье: 1977,с. 7.

84. Олейник Б.Т. К вопрсу о расстановке элементов.- В кн.: Вычислительная техника. Материалы конференции. Каунас, 1974, с. 87-89.

85. Перепелица В.А. Об одном классе многокритериальных задач на графах и гиперграфах.- Кибернетика, 1984, № 4, с. 62-67.

86. Широ Г.Э,, Осипов Л.Б. Размещение компонентов интегральных схем.- В кн.: Применение вычислительных машин для проектирования цифровых устройств:сб.статей.- Сов.радио, 1968,с. 183-198.

87. Арустамов С.А.Цроцедура параллельного размещения компонент и трассировки микросборок 1БИС.- В кн.: Вычислительная техника, Каунас, 1976 т. УШ, с. 95-97.

88. Абрайтис Л.Б., Рубляускас Д.А., Штуйкис В.А., Матицкас И-К.Л. Подисистема автоматизации проектирования топологии БИС ячеечного типа,- Управляющие системы и машины, 1974, №5, с. 79«*81.

89. Зиньковский Ю.Ф., Усатенко А.Н., Парахин В.В. Метод совместного решения задач размещения элементов и трассировки соединении,- Управляющие системы и машины, 1983, № 3, с. 27-32.

90. Абрайтис Л.Б., Килявичюс В.А., Шимаитис А.П. Распределение коммутаций по слоям с использованием свойства инвариантности некоторых контактов,- Управляющие системы и машины, 1976, )М, с. 104-108,

91. Медведев A.C., Штейн М.Е. 0 задачах компоновки и размещения компонент цифровых узлов,- Управляющие системы и машины, 1979, № I, с. 70-73.

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

93. Тимофеева Н.К. Один алгоритм оптимальной компоновки базовых элементов в корпуса интегральных микросхем,- В кн.: Алгоритмы и программы решения задач дискретной оптимизации. Киев:. . Ж "АН, УССР,' ,1980;,-с; .3-19.

94. Комяк В.М., Гиль Н.И., Гернет В.Д. К вопросу о размещении радиоэлементов на плате,- В кн.: Вычислительная техника (Каунас, июль, 1975)!, Материалы конференции. Каунас: Политехи, ин-т, 1975, Т.1У, с. 328-332.

95. Арбузов В.А., Антонова Н.В. Релаксационный алгоритм размещения методом групповых перестановок.- В кн.: Автоматизация конструктоокого проектирования РЭА и ЗВА. Тезисы докладов. Пенза, политехи, ин-т, 1982, с. 49-50.

96. Герасим Г. А., Тяшпкин С. А., Чуксин Ю.Д. Размещение разногабаритных элементов с учетом ресурса печатной платы.- В кн.: Автоматизация конструкторского проектирования РЭА и SBA. Тезисы докладов. Пенза, политехи, ин-т, 1982, с. 67-68.

97. Матицкас И.-К.Л. Алгоритм размещения разногабаритных элементов в кратные позиции.- Управляющие системы и машины, 1979, $ 4, с. 120-123.

98. Артемов В.Б.', Рябов Л.П. Алгоритм размещения модулей различных габаритов на печатной плате.- Обмен опытом в радиопромышленности, 1977, $ 2, с. 23-31.

99. Тимофеева Н.К., Гулянщкий Л.Ф. 0 размещении разногабаритных элементов ЭВМ на печатных платах.- Управляющие системы и машины, 1982,$ 3, с. '50-53.

100. Тимофеева H.K.Qö' оптимальном распределении внешних контактов печатной платы,- В кн.: Программное обеспечение экстремальных за,дач и пакеты прикладных программ. Сборник научн. тр. Киев: Ж АН УССР, 1982, с. 50-56.

101. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы.- М.: Мир, 1973.- 304 с.

102. Килевичюс В.Л., Руткаускас И.И. Применение дискретного рабочего поля при подготовке перфоленты для управления координатографом.- В кн.: Вычислительная техника: Материалы конференции по развитию технических наук, Каунас, 1974, с. 142-144.

103. Зайцева Ж.Н., Штейн М.Е. Один способ построения кратчайшего замкнутого маршрута в графе .-В кн.: Вычислительная техника, Каунас. 1972, T.III, с. 417-422.

104. Никитин А.И., Нуриев У.Г., Красиловец Л.В. Математическое обеспечение ВЦКП. Некоторые алгоритмы дискретной оптимизации.-Киев, 1983,- 30с. -/ АН УССР. Ин-т Кибернетики; Препринт-33-6/

105. Тимофеева Н.К. Решение одной задачи типа задачи коммивояжера при проектированиии компонентов ЭВМ.- Кибернетика, 1983, J55, с. 73-76.

106. Гутер Г.С. Оптимизация методом улучшения по группам переменных,-В кн.: Математические методы решения экономических задач. М.: Наука, 1969, вып,1. с. 50-55.

107. Ху Т. Целочисленное программирование и потоки в сетях.- М.: Мир, 1974.- 519 с.

108. Окунев Л.Я. Высшая алгебра.- М.: Просвещение, 1966,- 335 с.

109. Тимофеева Н.К. О разработке математического обеспечения САПР ЭВМ, предназначенного для решения некоторых задачконатрукторикого проектирования.- В кн,: Программное обеспечение ЭВМ. Сб науч. тр. Киев: ИК АН УССР, 1982, с. 10-15.