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