Добро пожаловать в репозиторий Зимней школы по алгоритмам, организуемой Сибирским государственным университетом телекоммуникаций и информатики (СибГУТИ)! В рамках этой пятидневной программы мы предлагаем вам принять участие в увлекательном проекте разработки распределённой системы социального графа. Этот проект объединяет концепции различных алгоритмов и распределённых вычислений, предоставляя уникальную возможность применить теоретические знания на практике.
Основной целью нашего проекта является создание простой модели масштабируемой и эффективной распределённой социальной сети, способной обрабатывать большие объёмы данных о пользователях и их взаимодействиях. Мы стремимся разработать систему, которая позволит:
- Управлять большими графами пользователей, где каждая вершина представляет пользователя, а рёбра обозначают взаимные связи «дружбы» с определёнными весами, отражающими степень близости или общие интересы.
- Обрабатывать и хранить текстовые посты, обеспечивая быстрый поиск и выполнение агрегирующих задач с использованием парадигмы MapReduce.
- Делегировать вычислительные задачи на множество узлов (с помощью горутин), что требует реализации механизмов выбора лидера и достижения консенсуса для согласования важных действий, таких как запись в общий лог.
Для достижения поставленных целей мы будем использовать различные алгоритмы и структуры данных, включая обходы графов (BFS, DFS), хеш-таблицы, префиксные деревья, алгоритмы сортировки, поиск кратчайших путей (Dijkstra, Bellman-Ford), остовные деревья (MST), а также распределённые алгоритмы выбора лидера и консенсуса (Raft, Paxos). Каждый из этих элементов находит своё реальное применение в разработке нашей социальной сети, обеспечивая её высокую производительность и надёжность.
Проект будет разделён на несколько этапов, соответствующих каждому дню зимней школы. В течение пяти дней мы последовательно будем разрабатывать и интегрировать различные компоненты системы:
- Хранение и управление графом пользователей с использованием списков смежности и алгоритмов обхода.
- Реализация алгоритмов поиска и анализа связности для эффективного поиска друзей и оценки степени их взаимосвязи.
- Внедрение остовных деревьев для оптимизации связей между пользователями и минимизации затрат на передачу информации.
- Применение алгоритмов кратчайших путей для определения оптимальных маршрутов взаимодействия между пользователями.
- Разработка распределённых механизмов для обеспечения согласованности данных и эффективного распределения вычислительных задач.
К окончанию проекта вы сможете получить полностью функционирующую модель распределённой социальной сети, демонстрирующую интеграцию различных алгоритмов и структур данных. Каждый участник проекта приобретёт практические навыки разработки сложных систем, научится работать с распределёнными вычислениями и освоит ключевые алгоритмические подходы, применимые в реальных задачах.