Разработка и исследование нейросетевых алгоритмов распознавания изоморфизма и изоморфного вложения моделирующих графов топологий БИС

• Автор: Пономарев, Дмитрий Петрович
• Шифр специальности: 05.13.12, 05.13.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Шахты
• Количество страниц: 123 с. : ил.

Введение. АНАЛИЗ МЕТОДОВ РЕШЕИЯ ЗАДАЧИ РАСПОЗНАВАНИЯ ИЗОМОРФИЗМА И ИЗОМОРФНОГО ВЛОЖЕНИЯ ГРАФОВ. Постановка задачи распознавания изоморфизма и изоморфного вложения графов. Анализ существующих подходов и алгоритмов решения поставленной задачи. Анализ типов и алгоритмов обучения нейронных сетей. Обобщенный нсйросетевой алгоритм распознавания изоморфных моделирующих графов в системах САПР. Обобщенный нсйросетевой алгоритм распознавания изоморфного вложения моделирующих графовв системах . САПР. МОДЕЛИРУЮЩИХ ГРАФОВ В СИСТЕМАХ САПР БИС. Общая структура нейросетевого алгоритма распознавания изоморфных графов топологий. Получение матрицы перестановки для изоморфных графов. Теоретические оценки алгоритма. РАЗРАБОТКА АЛГОРИТМА РАСПОЗНАВАНИЯ ИЗОМОРФНОГО ВЛОЖЕНИЯ ГРАФОВ В СИСТЕМАХ САПР БИС. Определение опорных вершин. Ыейросетевой алгоритм отсечения по глубине. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ. Цель экспериментального исследования. Оценка пространственной и временной сложности алгоритмов.


В ЗАКЛЮЧЕНИИ изложены основные выводы диссертационной работы. В приложении даны копии актов внедрения. В данной главе приводится постановка задам распознавания изоморфизма и изоморфного вложения графов. Рассматриваются особенности графов и графовых моделей в ситемах автоматизированного проектирования. Проводится анализ существующих подходов и алгоритмов решения задачи определения изоморфности и изоморфного вложения двух графов. Устанавливаются достоинства и недостатки этих алгоритмов. Проводится анализ методов построения и моделирования искусственных нейронных сетей с точки зрения представления графовых моделей САПР. Дается обобщенное описание предлагаемых подходов и алгоритмов решения задач распознавания изоморфизма и изоморфного вложения моделирующих графов топологий ВИС. Важным разделом современной дискретной математики является теория графов. Эта теория стала мощным средством исследования и решения многих задач, возникающих при изучении больших и сложных систем. Язык теории графов удобен при проведении различных исследований в таких областях как теоретическая физика, химия, биология, экономика, социология, лингвистика, теория игр, комбинаторная оптимизация. Практическая роль графов особенно возросла за последние годы в связи с интенсивным развитием таких направлений, как автоматизированные системы планирования, проектирования и управления, разработка и создание интеллектуальных систем обработки информации, представление задач, данных, знаний и методов поиска решений в искусственном интеллекте и т.