Алгоритмы на графах: от теории к эксперименту

Трек реализуется совместно с научно-учебной лабораторией процессно-ориентированных информационных систем (ПОИС) факультета компьютерных наук

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

На этом треке участники перестали верить на слово и начали проверять всё сами.

Что ждало участников:

• Погружение в анализ — возможность научиться оценивать скорость работы кода не «на глаз», а с помощью строгих методов и реальных замеров.
• Программирование на C++ — написание эффективных реализаций классических алгоритмов на графах и оттачивание навыков отладки.
• Битва алгоритмов — сравнение настоящих «тяжеловесов»: алгоритмов Дейкстры, A*, Флойда–Уоршелла, Беллмана–Форда и других. Участники разбирались, кто из них быстрее, кто экономичнее по памяти и почему для больших городов нужен один подход, а для лабиринтов — совсем другой.
• Измерения и визуализация — создание собственных сценариев тестирования, измерение времени работы алгоритмов на графах разного размера и структуры, а затем превращение сухих цифр в наглядные графики и диаграммы с помощью Python.
• Охота на ошибки — приобретение навыков поиска узких мест в коде, логических ловушек и скрытых багов, которые портят производительность.
• Командное исследование — объединение в команды для проведения настоящего мини-исследования: участники выбирали набор алгоритмов, проводили серию экспериментов, анализировали результаты и представляли выводы.

В результате участники не просто узнали, как работают графовые алгоритмы, но и получили навыки настоящего инженера‑исследователя — умение ставить эксперименты, анализировать данные и делать обоснованные выводы. Это пригодилось им и в олимпиадном программировании, и в будущей работе в IT.