- Какая структура данных реализуется? Topological Sort - Топологоческая сортировка.
- Что она из себя представляет (сбалансированное дерево, линейный список и пр.)? Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.
- Где и как она используется (приложения)? Топологическая сортировка применяется в самых разных ситуациях, например при распараллеливании алгоритмов, когда по некоторому описанию алгоритма нужно составить граф зависимостей его операций и, отсортировав его топологически, определить, какие из операций являются независимыми и могут выполняться параллельно (одновременно). Примером использования топологической сортировки может служить создание карты сайта, где имеет место древовидная система разделов.
- Какие операции над ней можно выполнять (поиск, удаление, добавление, вставка и пр.)? Сортировка.
- Какова теоретическая сложность операций (поиск за
O(log(n)), вставка заO(n^2)и т.д.)? Сложность времени такая же, как и у DFS (обход в глубину), которая равна O(V+E). - Какая-то другая справочная информация о проекте. Задача топологической сортировки графа состоит в следующем: указать такой линейный порядок на его вершинах, чтобы любое ребро вело от вершины с меньшим номером к вершине с большим номером. Очевидно, что если в графе есть циклы, то такого порядка не существует.
| Фамилия Имя | Вклад (%) | Прозвище |
|---|---|---|
| Усанов Илья | 50 | Мадара Учиха |
| Сабитов Данияр | 50 | Обито Учиха |
Девиз команды
Миру нет необходимости развиваться дальше. Человечеству будет лучше, если оно заснёт в вечном Гендзюцу Тсукуёми.
Описание основных частей семестрового проекта.
Пример. Проект состоит из следующих частей:
src/include- реализация структуры данных (исходный код и заголовочные файлы);benchmark- контрольные тесты производительности структуры данных (операции добавления, удаления, поиска и пр.);examples- примеры работы со структурой данных;dataset- наборы данных для запуска контрольных тестов и их генерация;
- С++ компилятор c поддержкой стандарта C++17 (например, GNU GCC 8.1.x и выше).
- Система автоматизации сборки CMake (версия 3.12.x и выше).
- Интерпретатор Python (версия 3.7.x и выше).
- Рекомендуемый объем оперативной памяти - не менее 4 ГБ.
- Свободное дисковое пространство объемом ~ 3 ГБ (набор данных для контрольных тестов).
Склонируйте проект к себе на устройство через Git for Windows (либо используйте возможности IDE):
git clone https://github.com/Algorithms-and-Data-Structures-2021/semester-work-topological-sort.git