Детальная информация

Название: ДНК-вычисления как способ решения задачи о поиске гамильтонова пути в графе: выпускная квалификационная работа бакалавра: 03.03.02 - Физика ; 03.03.02_02 - Биохимическая физика
Авторы: Сергеенко Анна Николаевна
Научный руководитель: Скворцов Алексей Николаевич
Организация: Санкт-Петербургский политехнический университет Петра Великого. Институт физики, нанотехнологий и телекоммуникаций
Выходные сведения: Санкт-Петербург, 2019
Коллекция: Выпускные квалификационные работы; Общая коллекция
Тематика: ДНК-вычисления; гамильтонов путь; метод ветвей и границ; оптимизация; трудоемкость; большие данные; DNA computing; Hamiltonian path; branch and bound method; optimization; complexity; big data
Тип документа: Выпускная квалификационная работа бакалавра
Тип файла: PDF
Язык: Русский
Код специальности ФГОС: 03.03.02
Группа специальностей ФГОС: 030000 - Физика и астрономия
Ссылки: Отзыв руководителя; Отчет о проверке на объем и корректность внешних заимствований
DOI: 10.18720/SPBPU/3/2019/vr/vr19-3913
Права доступа: Доступ по паролю из сети Интернет (чтение, печать, копирование)

Разрешенные действия:

Действие 'Прочитать' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети Действие 'Загрузить' будет доступно, если вы выполните вход в систему или будете работать с сайтом на компьютере в другой сети

Группа: Анонимные пользователи

Сеть: Интернет

Аннотация

В этой работе исследуются ДНК-вычисления как способ решения задачи о поиске гамильтонова пути в графе. Подробное рассмотрение этого алгоритма необходимо для создания новой концепции вычислительного устройства, потребность в котором возникла из-за того, что современные вычислительные устройства не справляются с большим количеством данных, и их развитие приблизилось к физическим порогам реализуемости. В этой работе также рассматривается метод ветвей и границ и показывается, что время расчета этим методом растет экспоненциально с увеличением количества вершин, в то время как время расчёта алгоритмом, основанном на ДНК-вычислениях, растет линейно. Доказывается, что с помощью ДНК-вычислений возможно решить задачу о поиске гамильтонова пути в графе с большим количеством вершин, чем методом ветвей и границ.

In this work we study and compare two different approaches to one of the most popular combinatorial problem — the Hamiltonian path problem. We show that it becomes inefficient to use branch and bound method, the most popular method which is realized on a computer, from the counted number of vertices because of its exponentially growing time consumption, so we analyze one more algorithm that is based on working with DNA molecules in a laboratory. The study of this method is important to the future development of computers.

Права на использование объекта хранения

Место доступа Группа пользователей Действие
Локальная сеть ИБК СПбПУ Все Прочитать Печать Загрузить
Интернет Авторизованные пользователи СПбПУ Прочитать Печать Загрузить
Интернет Авторизованные пользователи (не СПбПУ)
-> Интернет Анонимные пользователи

Статистика использования

stat Количество обращений: 21
За последние 30 дней: 0
Подробная статистика