Дорогие слушатели!
В субботу 25 ноября с 16:45 до 18:20 во втором учебном корпусе МГУ состоится лекция
"Задача Штейнера о минимальном дереве в Манхэттенской метрике.".
Докладчик – А.А. Часовских, д.ф.м.н., профессор кафедры интеллектуальных систем мехмата МГУ.

Будет показано, как изменяется классическая задача Штейнера о минимальном дереве при переходе от обычной метрики Эвклида к Манхэттенской метрике и возникает задача построения минимального прямоугольного штейнерова дерева (МПШД), как возникающая задача связана с проектированием больших интегральных схем. Выяснено, почему задача построения МПШД для конечного множества точек плоскости имеет алгоритмическое решение, но является сложной. Найдены некоторые свойства МПШД, позволяющие получить затратный по времени алгоритм их построения. Показано, как с использованием быстрого алгоритма Прима построения минимального остовного дерева графа получить алгоритм приближенного решения задачи построения МПШД.

Адрес: Ленинские горы, д.1с.52, второй учебный корпус МГУ, северный вход (ближе к главному зданию). Аудитория П-14.

http://mmmf.msu.ru/feedback/

бесплатно