Зинченко Людмила Анатольевна

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

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

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