Детальная информация
| Название | Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_02 «Системное программирование» |
|---|---|
| Авторы | Овечкин Данил Александрович |
| Научный руководитель | Пастор Алексей Владимирович |
| Другие авторы | Чуканов В.С. |
| Организация | Санкт-Петербургский политехнический университет Петра Великого. Физико-механический институт |
| Выходные сведения | Санкт-Петербург, 2022 |
| Коллекция | Выпускные квалификационные работы ; Общая коллекция |
| Тематика | задача штейнера ; приближенные алгоритмы ; графы ; С++ ; параллельные алгоритмы ; steiner tree problem ; approximation algorithm ; graphs ; C++ ; parallel algorithm |
| Тип документа | Выпускная квалификационная работа бакалавра |
| Тип файла | |
| Язык | Русский |
| Уровень высшего образования | Бакалавриат |
| Код специальности ФГОС | 01.03.02 |
| Группа специальностей ФГОС | 010000 - Математика и механика |
| DOI | 10.18720/SPBPU/3/2022/vr/vr22-3058 |
| Права доступа | Доступ по паролю из сети Интернет (чтение, печать) |
| Ключ записи | ru\spstu\vkr\18873 |
| Дата создания записи | 19.12.2022 |
Разрешенные действия
–
Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети
| Группа | Анонимные пользователи |
|---|---|
| Сеть | Интернет |
Данная работа посвящена реализации приближенного алгоритма 11/6 для решения задачи поиска минимального дерева Штейнера. Целью данной работы было изучение статьи про алгоритм 11/6 и реализация предложенного алгоритма на языке С++. В рамках данной работы также было проведено сравнение полученного алгоритма с алгоритмом KMB. В результате данного исследования были сделаны выводы, что решение поставленной задачи с помощью алгоритма 11/6 получается точнее, чем с помощью алгоритма KMB, но время работы алгоритма 11/6 больше, чем у KMB. Также было произведено распараллеливание блока алгоритма 11/6, что дало прирост производительности почти в 2 раза. Были также сделаны выводы о зависимости времени работы от количества потоков на четырехъядерном процессоре.
The present work is devoted to the implementation of the approximate algorithm 11/6 for solving Steiner tree problem. The purpose of this work was to research the article about the 11/6 algorithm and the implementation of the proposed algorithm in C++. As part of this work, the obtained algorithm was also compared with the KMB algorithm. As a result of this research, it was concluded that the solution of the problem using the 11/6 algorithm is obtained more accurately than using the KMB algorithm, but the running time of the 11/6 algorithm is longer that that of KMB. Also, the block of the 11/6 algorithm was parallelized, which gave a performance increase of almost 2 times. Conclusions were also drawn about the dependence of the algorithm’s runtime on the number of threads on a quad-core processor.
| Место доступа | Группа пользователей | Действие |
|---|---|---|
| Локальная сеть ИБК СПбПУ | Все |
|
| Интернет | Авторизованные пользователи СПбПУ |
|
| Интернет | Анонимные пользователи |
|
- Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации
- Алгоритм 11/6 для решения задач построения дерева Штейнера в приложениях к телекоммуникации
- Введение
- 1. Постановка задачи поиска минимального дерева Штейнера. Основные определения.
- 2. Алгоритм 11/6 и другие алгоритмы решения
- 3. Программная реализация алгоритма
- 4. Результаты исследования работы алгоритма
- Заключение
- Список использованных источников
Количество обращений: 16
За последние 30 дней: 1
