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