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