|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
О сложности укладки деревьев на плоскостьдипломная работа (Магистр)
- Научный руководитель: Гасанов Э.Э.
- Автор: Ли Валентина Александровна
- Тип: Магистр
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2012
- Аннотация: Одним из этапов синтеза СБИС является укладка элементов схемы на плоскость. При этом одной из основных целевых функций является минимизация длин проводов. С математической точки зрения эта задача сводится укладке графов на целочисленную плоскую решетку. Главными минимизируемыми сложностными функционалами при этом являются суммарная длина ребер графа и площадь укладки. Одним из важных классов графов являются деревья. В работе Валентины Ли рассматривается 2 основных случая вычисления длин проводов. В первом случае длина ребра равна расстоянию по Манхеттену между вершинами ребра. Эта метрика соответствует тем технологиям, в которых провода можно прокладывать только в двух направлениях: по вертикали и горизонтали. Во втором случае провода можно прокладывать в трех направлениях, в результате чего мы получаем покрытие плоскости правильными треугольниками. Для обоих случаев Валентиной разработаны оптимальные по порядку алгоритмы укладки произвольного дерева на прямоугольную и соответственно треугольную решетки. Для более узкого класса полных деревьев предложены более эффективные алгоритмы. Полученные результаты близки к окончательным и представляют несомненный интерес, как с теоретической, так и практической точки зрения. Результаты по прямоугольной решетке опубликованы в рецензируемом журнале, а результаты по треугольной решетке могут быть рекомендованы к опубликованию в открытой печати.
- Добавил в систему: Гасанов Эльяр Эльдарович