Details
| Title | Экспериментальное определение трудоёмкости в среднем целочисленных алгоритмов: выпускная квалификационная работа бакалавра: направление 01.03.02 «Прикладная математика и информатика» ; образовательная программа 01.03.02_01 «Математическое моделирование и искусственный интеллект» |
|---|---|
| Creators | Соколов Степан Александрович |
| Scientific adviser | Новиков Федор Александрович |
| Organization | Санкт-Петербургский политехнический университет Петра Великого. Физико-механический институт |
| Imprint | Санкт-Петербург, 2025 |
| Collection | Выпускные квалификационные работы ; Общая коллекция |
| Subjects | трудоемкость в среднем ; целочисленные алгоритмы ; алгоритм Прима ; алгоритм Краскала ; алгоритмы раскрашивания графов ; average-case time complexity ; integer algorithms ; Prims algorithm ; Kruskals algorithm ; graph coloring algorithms |
| Document type | Bachelor graduation qualification work |
| File type | |
| Language | Russian |
| Level of education | Bachelor |
| Speciality code (FGOS) | 01.03.02 |
| Speciality group (FGOS) | 010000 - Математика и механика |
| DOI | 10.18720/SPBPU/3/2025/vr/vr25-2691 |
| Rights | Доступ по паролю из сети Интернет (чтение, печать, копирование) |
| Additionally | New arrival |
| Record key | ru\spstu\vkr\36985 |
| Record create date | 8/28/2025 |
Allowed Actions
–
Action 'Read' will be available if you login or access site from another network
Action 'Download' will be available if you login or access site from another network
| Group | Anonymous |
|---|---|
| Network | Internet |
Данная работа описывает методы эксперементального определения трудоемкости в среднем, разработку стенда для его проведения на основе задач поиска минимального остовного дерева (МОД) и раскраски графа. Основные этапы работы: постановка задач, разработка программы для проведения эксперимента, анализ полученных данных для поиска ответов на поставленныу задачи. В ходе работы реализован стенд для определения трудоемкости в среднем алгоритмов Прима, Краскала, а также точной, приближенной и приближенной с эвристикой раскраски графа.
This work describes methods for the experimental determination of average-case time complexity, the development of a computational framework for its evaluation based on minimum spanning tree (MST) and graph coloring problems. The tasks addressed in this work include: problem formulation, development of a program for conducting experiments, analysis of obtained data to address the defined tasks. During the study, a framework was implemented to evaluate the average-case complexity of Prim’s and Kruskal’s algorithms, as well as exact, approximate, and heuristic-based approximate graph coloring algorithms.
| Network | User group | Action |
|---|---|---|
| ILC SPbPU Local Network | All |
|
| Internet | Authorized users SPbPU |
|
| Internet | Anonymous |
|
- Экспериментальное определение трудоёмкости в среднем целочисленных алгоритмов
- Введение
- 1. Постановка задачи
- 2. Описание методов и алгоритмов
- 3. Разработка стенда для проведения эксперимента
- 4. Результаты вычислительного эксперимента
- Заключение
- Список использованных источников
Access count: 0
Last 30 days: 0
