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

ВВЕДЕНИЕ.

1. АНАЛИЗ АЛГОРИТМОВ ОПРЕДЕЛЕНИЯ ПЛАНАРНОСТИ СХЕМ ЭВА.

1.1. Постановка и анализ задачи.

1.2. Анализ и выбор математической модели.

1.3. Анализ задачи определения планарности.

1.4. Матричные алгоритмы определения планарности. Алгоритм Данна -Чена.

1.5. Циклические алгоритмы определения планарности.

1.5.1. Алгоритм Винга - Фишера.

1.5.2. Алгоритм Хопкрофта - Тарьяна.

1.6. Выбор алгоритма определения планарности.

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

Следует заметить, что под термином «интегральная микросхема (ИС)» понимается микроэлектронное изделие окончательной или промежуточной формы, предназначенное для выполнения функций электронной схемы, элементы и связи которого нераздельно сформированы в объеме и(или) на поверхности материала, на основе которого изготовлено изделие [1]. Согласно [2, 3] большой интегральной микросхемой (БИС) называется интегральная микросхема содержащая 500 и более элементов, изготовленных по биполярной технологии, либо 1 ООО и более элементов, изготовленных по МДП-технологии, причем под элементом интегральной микросхемы понимается часть ИС, не выделенная в самостоятельное изделие, но реализующая функцию какого-либо элемента схемы, например, транзистора.

Однако выпускаемые промышленностью стандартные ИС зачастую не удовлетворяют специальным требованиям заказчиков. Это обстоятельство привело к появлению мелкосерийных, «заказных» БИС и СБИС. Необходимость разработки небольших серий ИС, в свою очередь, привела к увеличению их стоимости, что влечет за собой увеличение затрат на этапах проектирования и разработки. [4-6].

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

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

Иерархический подход подразумевает разбиение задачи проектирования СБИС на несколько последовательных операций [4, 7]. Обычно такой комплекс включает в себя следующие этапы: спецификация системы, функциональное проектирование, логическое проектирование, схемное проектирование, конструкторское проектирование, изготовление, сборка, тестирование и контроль.

Этап конструкторского проектирования, в свою очередь, также разбивается на несколько задач. Такими задачами являются разбиение, планирование, размещение, трассировка, упаковка, верификация [8, 9].

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

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

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

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

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

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

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

Вообще, проблема определения планарности и получения плоской укладки графа схемы относится к числу наиболее известных и популярных задач теории графов. Первые работы, посвященные задаче определения планарности, относятся к XVIII и XIX векам. Это ставшие уже классическими теоремы Эйлера и Жордана [16]. С тех пор, интерес к данной проблеме неуклонно растет. В 60 - 70 - х годах нашего столетия был предложен ряд алгоритмов решения проблемы определения планарности и получения плоской укладки [10, 11, 17-35]. Большинство этих алгоритмов решает поставленную задачу с помощью эвристических процедур, что далеко не всегда приводит к нахождению оптимального решения, т.к. даже незначительная ошибка на начальной стадии решения может привести в итоге к неверному заключению о непланарности графа. Интерес к решению данной задачи не угас и в настоящее время, что подтверждается появлением за последние несколько лет серии публикаций в отечественных и зарубежных изданий [16, 36 - 38].

Сравнительно недавно появилось новое направление, позволяющее добиваться качественного улучшения получаемых решений - генетические алгоритмы (ГА) [39]. Сущность генетических алгоритмов заключается в моделировании естественных эволюционных процессов как средства достижения оптимума. Уже имеются примеры успешного применения ГА для решения самых различных задач [40 - 52], в том числе и задач автоматизированного проектирования СБИС [53 - 78].

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

Все это, а также гибкость структуры ГА, возможность ее настройки (перенастройки) дают возможность получения лучших, по сравнению с традиционными методами результатов [44, 50, 52, 55 - 60, 63 - 66, 74].

Разработка эффективных методов и алгоритмов определения планарности и построения плоской укладки моделей схем представляет большой практический интерес при проектировании с помощью ЭВМ. Несмотря на то, что планарность является только необходимым условием плоской реализации схемы, так как ограниченные размеры конструкции и конечная толщина проводников порождают дополнительные условия, во многих случаях именно правильный ответ на вопрос о планарности схемы может оказать решающее значение на качество проектирования [15].

Из всего вышеизложенного следует, что задача определения планарности модели схемы является АКТУАЛЬНОЙ ПРОБЛЕМОЙ автоматизированного проектирования.

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

Для достижения поставленной цели были решены следующие задачи:

1) Проведен анализ поставленной задачи и определено ее место в общей задаче проектирования ЭВА, а также анализ и обоснование выбора математической модели схемы для разрабатываемого алгоритма планаризации;

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

3) Построена общая схема алгоритма планаризации, функциональное назначение блоков алгоритма, а также состав и структура информационных потоков между различными блоками алгоритма. Для блока генетических операторов алгоритма планаризации разработана концепция использования ГА и схема применения генетических операторов;

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

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

Для решения поставленных задач использовались следующие МЕТОДЫ

ИССЛЕДОВАНИЙ: элементы высшей математики, теории множеств, алгоритмов, статистических вычислений, генетического поиска.

НАУЧНАЯ НОВИЗНА диссертационной работы заключается в:

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

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

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

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

ПРАКТИЧЕСКУЮ ЦЕННОСТЬ работы представляют:

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

2) Генетический алгоритм и программа определения планарности и построения плоской укладки соединений схемы;

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

РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические результаты диссертационной работы использованы в госбюджетной работе «Разработка интеллектуальных систем проектирования на основе эволюционной адаптации» (№ ГР 01.9.60004346), а также научно-исследовательских работах, выполняемых по грантам Российского фонда фундаментальных исследований «Эволюционно-генетические технологии в однородных электронных средах» (№ 98-01-01022), «Генетические алгоритмы в интеллектуальных САПР» (№ 99-01-00050) и научно-исследовательской работе, выполняемой в рамках межвузовской научно-технической программы «Механика, машиноведение и процессы управления». Результаты работы внедрены в МЭИ (г. Москва). Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТРТУ при чтении лекций и в цикле лабораторных работ по курсам «Методы генетического поиска», «Методы оптимизации» и «Математические основы дискретной техники».

АПРОБАЦИЯ основных теоретических и практических результатов работы проводилась на научных семинарах "Генетические алгоритмы" (с 1996 по 1999 гг., ТРТУ), Всероссийской научной конференции студентов и аспирантов «Техническая кибернетика, радиоэлектроника и системы управления» (г. Таганрог, 1996 - 1998 гг.), I Всероссийской научной конференции молодых ученых и аспирантов (г. Таганрог, 1998 г.), Международной научно-технической конференции «Интеллектуальные САПР» (г. Геленджик, 1995 - 1998 гг.).

ПУБЛИКАЦИИ. Результаты диссертации отражены в 16 печатных работах.

СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИОННОЙ РАБОТЫ. Диссертационная работа состоит из введения, четырех глав, заключения, и списка использованных источников. Работа содержит 155 стр., включая 37 рис., 5 табл., список использованных источников из 154 наименований, 4 стр. приложений и актов об использовании.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

3. Определена методика и общая схема алгоритма планаризации. Предложены модифицированная форма представления исходных данных, позволяющая на 7 - 10% сократить сроки решения и объем требуемой памяти и процедура генерации циклов.

4. Разработана методика кодирования, учитывающая специфику решаемой задачи и позволяющая улучшить качество получаемых решений, а также модифицированные генетические операторы, адаптированные к особенностям решаемой задачи. Определены, теоретические оценки пространственной 0(а]Ч) и временной 0((31\)

138 сложности разработанного генетического алгоритма.

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

6. Для разработанного алгоритма реализован пакет прикладных программ на языка программирования Borland С++ Builder 3.0. Приведено описание разработанного универсального пакета прикладных программ для генерации и исследования графов с любыми свойствами (регулярные, заданные с помощью генератора случайных чисел и т.д.) и для любых типов задач, в том числе и задачи определения планарности.

1. Закон РФ № 3526 - 1 от 23.09.92г. «О правовой охране топологий интегральных микросхем»

2. ГОСТ 17021 75 «Микросхемы интегральные. Термины и определения».

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

4. Петренко А.И., Лошаков В.Н., Тетельбаум А.Я., Шрамченко Б.Л. Автоматизированное проектирование СБИС на базовых кристаллах. М.: Радио и связь, 1988. 160 е., ил.

5. Корячко В.П., Курейчик В.М., Норенков И.П. Теоретические основы САПР: Учебник для вузов. М.: Энергоатомиздат, 1987.-400 е.: ил.

6. Системы автоматизированного проектирования: В 9-ти кн. Кн. 6. Автоматизация конструкторского и технологического проектирования: Учеб. пособие для втузов/ Под ред. Норенкова И.П.-М.: Высшая школа, 1986.-160 с.:ил.

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

8. Sherwani N.A. Algoritms for VLSI Physical Design Automation. Norwell, Kluwer Academic Publishers, 1995, 538 p.

9. Курейчик В.М. Математическое обеспечение конструкторского и технологического проектирования с применением САПР. М.: Радио и связь, 1990. - 352 е.: ил.

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

11. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов-на-Дону: издательство Ростовского университета, 1981. - 112 с.

12. Berge С. Graphes et hypergraphes. Dunod, Paris, 1970.

13. Зыков A.A. Гиперграфы 11 Успехи математических наук. М. 1979, т.29, вып. 6.

14. Горбатов В.А. Теория частично упорядоченных систем. М., 1976.

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

16. Ольшанский Ю.А. Плоские графы // Соросовский образовательный журнал, № 11, 1996, стр. 117-122.

17. Auslander L., Parter S.V. On embedding graphs in the plane. // J. Math, and Mech. 10, № 3, May 1961, p. 517 523.

18. Hopcroft J., Tarjan R. Efficient planarity testing. // Journal of Association Computing Machinery, Vol. 21, № 4, October 1974, pp. 549 568

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

20. Bader W. Das topologishe Problem der gedruckten Schaltung und seine Losung. //Electrotechnik, 1964, № 1, p.49.

21. Плесневич Г.С. Расположение графа на плоскости. // Вычислительные системы, вып. 6, 1964.

22. Fisher G.J. Computer recognition and extraction of planar graphs from the incidence matrix. // IEEE Trans. On Circuit Theory CT-13, 2 (June 1966), 154 -163.

23. Sechu S., Reed M. Linear graphs and electrical networks. Reading, Mass Addition Wesley, 1961.

24. Дамбит Я.Я. Метод построения плоского графа. // Латвийский математический ежегодник, Рига, 1969, № 6.

25. Дамбит Я.Я., Матисоне Э.К. Алгоритм автоматизированного построения плоского чертежа графа. Вычислительная техника. - Каунас, 1978. - т. 10,с. 8 -9.

26. Gold R. Graphs and vector spaces. I. Mathematics and Physics, 1958, № 3, p. 37.

27. Dunn W.R.Jr., Chan S.P. An algorithm for testing the planarity of a graph. // IEEE Trans. Circuit theory, 1968, № 2, p. 15.

28. Dunn W.R., Chan S.P. Realizability of a planar graph from its circuit matrix presented. // At the Hidwest Symposium on circuit theory, May, 1967.

29. Зыков A.A. Теория конечных графов. Новосибирск: Наука, Сибирское отделение, 1969.

30. Дамбит Я.Я. О наложении графа на плоскость, // Латвийский математический ежегодник, Рига, 1966, № 2.

31. Tutte W.T. Matroids and graphs. // Trans. American Mathematics Society, 1959, №3, p. 90.

32. VanCleemput W.M. Mathematical models for the circuit layout problem. IEEE Trans, 1976. - v. CAS - 23, № 12, p. 759 - 767.

33. VanCleemput W.M. Automated drawing of planar circuit layout graphs. Proc. 18th Midwest Symp. Circuits and Syst, Montreal, Canada, 1975. - p. 500 - 503.

34. Stallings J.R. In: Combinatorial Group Theory and Topology / Ed. S.M. Gersten, J.R. Stallings. Princeton (N.J.): Princeton Univ. Press, 1987. 552 p.

35. Klyachko An. A. // Commun. in Algebra. 1993, V. 21. № 21, p. 2555 2575.

36. Junger M, Leipert S, Mutzel P. A note on computing a maximal planar subgraph using PQ trees. // IEEE Trans. Vol. 17, № 7, July 1998.

37. Chen H.-F. S, Lee D.T. On crossing minimization problem. // IEEE Trans. Vol. 17, №5, May 1998.

38. Holland, John H, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. University of Michigan, 1975.

39. Goldberg David E, Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, Inc. 1989.

40. Davis L.D. Handbook of Genetic Algorithms. Van Nostrand Reinold, New York, 1991,-385p.

41. Goldberg D.E., Kalyanmoy D. A comparative analysis of selection schemes used in genetic algorithms. In Rawlings G.(Ed.). Foundations of Genetic Algorithms. Indiana University. Mogan Kaufmann, San Mateo, CA, 1991.

42. Syswerda G. Uniform Crossover in Genetic Algorithms. Proc. of the 3-rd Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1989. p.2-9.

43. Foundation of Genetic Algorithms, edited by Rawlins Gregory. Morgan Kaufman Publishers, San Mateo, California, 1991, -473p.

44. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. 69 с.

45. Батищев Д.И., Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород, Нижегородский госуниверситет, 1994.

46. Practical Handbook of Genetic Algorithms Complex Coding Systems. Volume 3. / Edited by Lance D. Chambers. CRC Press, Boca Raton, London, New York, Washington D.C., 1999. - 572 p.

47. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1992.

48. Kureichik V.M. et all. Some new features in Genetic Solution of the Traveling Salesman Problem. // Proc. of the Second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, 1996. pp. 294-296.

49. Liu, X., Sakamoto, A., Shimamoto, T. Restrictive Channel Routing with Evolution Programs. // Trans. IEICE, vol.E76-A, no.10, 1993. pp.1738-1745.

50. Rahmani, A.T. and Ono N. A Genetic Algorithm for Channel Routing Problem. // in Proc. 5th Intl. Conf. on GAs, 1993. pp. 494-498.

51. Курейчик B.M., Лебедев Б.К., Гладков Л.А. и др. Разработка интеллектуальных систем проектирования на основе эволюционной адаптации // Отчет по НИР (промежуточный). Депонир. в ВНТИ № ГР 01.9.60004346, М: 1998, 43 стр.

52. Давиденко В.Н. Автореферат кандидатской диссертации "Разработка и исследование алгоритмов канальной трассировки, основанных на методах генетического поиска". Таганрог.: ТРТУ, 1998, 16 с.

53. Давиденко В.Н., Курейчик В.М. Генетический алгоритм решения двухслойных каналов. // Тезисы докладов международной конференции "Новые информационные технологии в науке, образовании и бизнесе" (IT+SE'97). Гурзуф, 1997. стр. 39-42.

54. Davidenko V.N., Kureichik V.M., and Miagkikh V.V. Genetic Algorithm for Restrictive Channel Routing Problem. // Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 636-642.

55. Лебедев Б.К. Канальная трассировка на основе генетических процедур. // Известия ТРТУ, №3, Таганрог, 1997. с. 53-60.

56. Lieng, J., Thulasiraman, К. A Genetic Algorithm for Channel Routing in VLSI Circuits. Evolutionary Computation, 1(4), MIT, 1994. pp. 293-311.

57. Курейчик В.М. Генетические алгоритмы и их применение в САПР. // Интеллектуальные САПР, меж. сб., Таганрог, 1995. стр. 7-11.

58. Чернышев Ю.О., Курейчик В.В. Генетические алгоритмы размещения //

59. XXII International School And Conference On Computer Aided Design, CAD-95, Gurzuff, 1995. c. 329-330.

60. Dergatchev S. Genetic approach to training neural networks: application to a forecast of stockmarket volatility. // Известия ТРТУ, № 2, Таганрог, 1998. с. 51 -53.

61. Cohoon J.P. and Paris W.D. Genetic placement. // IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.6, № 6, 1987. pp.956-964.

62. Goodman, E. Tetelbaum, A. and Kureichik, V. (1994). A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems. // Case Center Technical Report #940702, Michigan State University

63. Chan, H.M. and Mazmunder, P. A genetic algorithm for macro cell placement. // Technical report, Department of Electrical Engineering and Computer Science, University of Michigan, 1989

64. Kureichik, V.M. Genetic Algorithms In CAD. // Proc. Russia Conf. AI in CAD, Gelendzik, September 1993.

65. Родзин С.И. Проектирование самотестируемых СБИС с применением метода генетического поиска. // Известия ТРТУ, №3, Таганрог, 1997. стр. 84-86.

66. Lin S.C., Goodman Е.Р., Punch W.F. A Genetic Algorithm Approach to Dynamic Job Shop Scheduling Problems. // Proc. of the 7th International Conf. on Genetic Algorithms, M. Kaufmann Publisher, San Mateo, California, 1997. pp. 481-488.

67. Schnecke V., Vornberger O. A Genetic Algorithms for VLSI Design Automation. // Proc. of the Second Intl. Conf. Adaptive Computing in Engeneering, Design and Control, Plymouth, UK, March 1996. pp. 53-58.

68. Батищев Д.И., Власов C.E., Булгаков И.В. Плотное размещение разногабаритных объектов на плоскости с помощью генетическихалгоритмов. // XXIII International School and Conference on Computer Aided Design.Yalta-Gurzuff, 1996. 354 с

69. Курейчик В.В. Автореферат кандидатской диссертации "Исследование и разработка генетических алгоритмов для конструкторского синтеза элементов СБИС".- Таганрог.: ТРТУ, 1995, 16 с.

70. Бондалетов А.В. Применение группирующего генетического алгоритма для решения задач одномерной упаковки. // Известия ТРТУ, № 2, Таганрог, 1998. с. 28 33.

71. Лебедев Б.К. Трассировка в коммутационном блоке на основе генетических процедур. // Известия ТРТУ, № 2, Таганрог, 1998. с. 7 22.

72. Shahookar К., Mazmunder P. A Genetic Approach to standart Cell Placement Using Meta-Genetic Parameter Optimization, IEEE Trans, on CAD, Vol.9, No.5, May, 1990, -377p.

73. Burstein, M. Channel routing, Layout Design and Verification. Elsevier Science, 1986. pp. 133-167.

74. Yoshimura, T. And Kuh, E.S. Efficient algorithms for channel routing. IEEE Trans. Computer Aided Design Integrated Circuits & Syst., vol.1, no.l, 1982. pp.25-35.

75. Автоматизация проектирования больших и сверхбольших интегральных схем. / А.И. Петренко, В.М. Курейчик, А.Я. Тетельбаум и др. // Зарубежная радиоэлектроника, 1981, № 6, с. 47 - 66.

76. Автоматизация проектирования топологии БИС на базовых матричных кристаллах / А.И. Петренко, А.Я. Тетельбаум, Б.Л. Шрамченко, Н.В. Лугпнский // Зарубежная радиоэлектроника, 1985, № 8, с. 26 - 40.

77. Селютин В.А. Автоматизированное проектирование топологии БИС. М.: Радио и связь, 1983. - 112с.

78. Крегер Д., Тозун О. Автоматизированное проектирование обостряет конкуренцию приборов со стандартами. //Электроника, 1980, т.ЗЗ, № 15, -с.28 34.

79. Vernon I. A ULA is More than Silicon // Proc. 5th SSCC. 1979 - p.51.

80. Hurst S. Universal Logic Gates for Custom Design I.C. Requirements //

81. Microel. Reliab. 1980 - Vol. 19 - p.51.

82. Goldstein A.J., Schweikert D.G. A Proper Model for Testing the Planarity of Electrical Circuits. Bell Syst. Tech. J., 1973, v. 52, № 1, p. 135 - 142.

83. Тетельбаум А.Я., Шрамченко Б.Л. Применение гиперграфов при исследовании планарности электронных схем. // Известия АН СССР. Техническая кибернетика, 1978, № 5, с. 127 136.

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

85. Татт У. Теория графов. М.: Мир, 1988. 424 е., ил.

86. Оре О. Теория графов. М.: Наука, 1980. 336.

87. Зыков А.А. Основы теории графов. М.: Наука, 1987. 384 с.

88. Уилсон Р. Введение в теорию графов. М.: Мир, 1977. 208 с.

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

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

91. Bruno J., Steiglitz К., Weinberg L. A new planarity test based on 3-connectivity. // IEEE Trans. On Circuit Theory CT-17, 2 (May 1970), 197 206.

92. MacLane S. A combinatorial condition for planar graphs. // Fund. Math., vol.28, pp. 22-32, 1937.

93. Wing O. On drawing a planar graph. // IEEE Trans. On Circuit Theory CT-13, 1 (March 1966), 112- 114.

94. Shirey R.W. Implementation and analysis of efficient graph planarity testing algorithms. Ph. D. Thesis, U. Of Wisconsin, June 1969

95. Lempel A., Even S., Cederbaum I. An algorithm for planarity testing of graphs. // Theory of Graphs: International Symposium: Rome, July, 1966, P. Rosenstiehl, Ed., Gordon and Breach, New York, 1967, pp. 215 232.

96. Tarjan R. Implementation of an efficient algorithm for planarity testing of graphs. Dec. 1969 (unpublished).

97. Mondshein L. Combinatorial orderings and embedding of graphs. Tech. Note 1971 35, Lincoln Lab., M.I.T., Aug. 1971.

98. Hopcroft J., Tarjan R. Planarity testing in V log V steps: Extended abstract. //

99. Proc. IFIP Cong. 1971: Foundations of Information Processing, Ljubljana, Yugoslavia, Aug. 1971, North Holland Pub. Co., Amsterdam, pp.18 - 22. 102. Tarjan R. An efficient planarity algorithm. STAN-CS-244-71, Comput. Sci.

100. Dep., Stanford U., Nov. 1971. ЮЗ.Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи.-М.: Мир, 1982.-416 с.

101. Курейчик В.М. Генетические алгоритмы. Монография. Таганрог: Изд во ТРТУ, 1998, 185 стр.

102. Петров Д.Ф. Генетика с основами селекции. М.:Высшая школа, 1971 г. -410 с.

103. Mange А.Р.,Mange E.J., Genetics: Human Aspects. Saunder Colledge, Philadelphia, 1982.-305 p.

104. Джеральд Ф. Джойс. "Направленная молекулярная эволюция". Журнал "В мире науки". №2,3 1993 г. стр.32/всего 160 стр. Издательство "Мир". Москва

105. Яблоков В.А. Фенетика. М.: Наука, 1980 г. 132 с.

106. Ауэрбах Ш. Проблемы мутагенеза. Пер. с англ. Гнездицкой Э.В., Маршак М.И., Полукаровой Л.Г. Под ред. Шапиро Н.И. М.:Мир, 1978 Г.-464 стр.

107. Ляпунова Н.А. О мутациях случайных и направленных. Наука и жизнь. 1989 г. №8 с.60-61.

108. Бейсон Ж. Генетика. Пер с франц. Назарова В.И., М.: Атомиздат, 1978 г. -128 стр.

109. Ваганов А. Как понять генетическую информацию. // Инженерная газета. 1995 г. №43.

110. Вороновский Г.К., Махотило К.В., Петрашев С.Н., Сергеев С.А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА, 1997.- 112с.

111. Grefenstette D.E., Gopal G., Rosmaita В. et al. Genetic Algorithms for the Traveling Salesman Problem // Proc. 1st Intern. Conf. Of Genetic Algorithms and Their Applications. New Jersey, 1998.

112. Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы.

113. Перспективы. // Известия Академии Наук. Теория и системы управления. -М.: Наука, МАИК «Наука/Интерпериодика», № 1, 1999. стр. 144 - 160.

114. Курейчик В.М. Генетические алгоритмы в технике. // Методы кибернетики и информационной технологии. Саратов: РАЕН, 1997 - стр. 45 - 54.

115. Гладков JI.A, Гулевич А.И. Эвристический алгоритм определения планарности на основе теоремы Бадера. // Всероссийская научная конференция аспирантов и студентов. Тезисы докладов. // Таганрог, изд -во ТРТУ, 1997. - 296 стр., стр. 94.

116. Гладков JI.A, Гулевич А.И. Эффективный алгоритм определения планарности // IV Всероссийская научная конференция аспирантов и студентов. Тезисы докладов. // Таганрог, изд - во ТРТУ, 1998. - 430 стр.,стр. 70.

117. Гладков Л.А., Павлов Б.И., Фоменко И.А. Тестирование планарности графа с помощью матрицы его циклов // IV Всероссийская научная конференция аспирантов и студентов. Тезисы докладов. // Таганрог, изд -во ТРТУ, 1998. - 430 стр., стр. 78.

118. Tarjan R. Е. Depth first search and linear graph algorithms. SIAM J. Comput., 1972, 1, s. 146- 160.

119. Гладков JI.A. Алгоритм определения планарности графа // Известия ТРТУ, № 3, Таганрог, 1997. с. 144 148.

120. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность.-М.: Мир, 1985.-512 с.

121. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир,- 1979.-536 с.

122. Липский В. Комбинаторика для программистов/ Пер. с польского Евстигнеева В.А., Логиновой О.А.-М.: Мир, 1988.-213 с.:ил.

123. Митропольский А.К. Техника статистических исследований. М., "Наука".,1971.- 576 е.: ил.

124. Применение математических методов и ЭВМ. Планирование и обработкарезультатов эксперимента: Учеб. пособие./ Под общ. ред. Останина А.Н.Минск.: Вышэйшая школа., 1989. 218 е.: ил.

125. Львовский E.H. Статистические методы построения эмпирических формул: Учеб.пособие для втузов.-М.: Высшая школа, 1988.-239 е.: ил.

126. Адлер Ю.П. Введение в планирование эксперимента.-М.Металлургия, 1969. 157 с.:ил.

127. Ежов И.И., Скороход A.B., Ядренко М.И. Элементы комбинаторики.-М.: Наука, 1977.-264 с.

128. Гроппен В.О. Принципы оптимизации комбинаторных процедур. Ростов-на-Дону : Издательство РГУ,-1988.-195 с.:ил.

129. Курейчик В.М., Глушань В.М., Щербаков Л.И. Комбинаторные аппаратные модели и алгоритмы в САПР. М.: Радио и связь, 1990 г. 216 с.

130. Зайченко Ю.П. Исследование операций. Киев: Вища школа, 1975. - 320 с.

131. Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов.-М.: Наука, 1986.-544 с.:ил.

132. Линник Ю.В. Метод наименьших квадратов и основы математико-статистической теории обработки наблюдений.-М.:Физматгиз, 1962. 349 с.:ил.

133. Адлер Ю.П. Планирование эксперимента при поиске оптимальных условий.-М.: Наука, 1971. 283 с.:ил.

134. Андерсон Т. Введение в многомерный статистический анализ./ Пер. с англ. КичатоваЮ.Ф.-М.:Физматгиз, 1963. 500 е.: ил.

135. Большов Л.Н., Смирнов Н.В. Таблицы математической статистики.-М. :Наука, 1965. 464 с.

136. Гурский Е.И. Теория вероятностей с элементами математической статистики.-М.: Высшая школа, 1971. 328 с.

137. Гренандер У. Случайные процессы и статистические выводы/ Пер. с англ. и доп. Яглоба А.М.-М.:Изд-во иностранной лит., 1961. 167 с.

138. Даймонд С. Статистика в науке/ Пер. с англ. Дружининой А.Л.-М.: Статистика, 1970. 155 с.151

139. Подбельский B.B. Язык Си++: Учебное пособие. М., Финансы и статистика, 1995. - 560 с.

140. Голуб А.И. С и С++. Правила программирования. М., БИНОМ, 1996. -272 с.

141. Бабэ Б. Просто и ясно о Borland С++. М.: БИНОМ, 1994. - 400 с.

142. Бентли Д. Жемчужины творчества программистов / пер. с англ. М., Радио и связь, 1990. -244 с.

143. Лэнгсам Й., Огенстайн М., Тетельбаум А. Структура данных для персональных ЭВМ. М., Мир, 1989. - 568 с.