Семинар по алгоритмам и структурам данных
Семинар по алгоритмам и структурам данных ФКН создан для всех, кто интересуется последними достижениями данной дисциплины или ищет актуальные задачи для своей научной деятельности. Доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов.
Заседания проходят по вторникам с 18:10 до 19:30, ориентировочно раз в месяц (следите за объявлениями).
Организатор семинара: Мамай Игорь Борисович, доцент департамента больших данных и информационного поиска ФКН
14 октября 2025 в 18:10
Докладчик: Никита Мануйленко, ФКН НИУ ВШЭ
Тема: Полиномиальный алгоритм распознавания точной степени 3 графов-деревьев.
Аннотация: Вопрос степеней графов изучается с 1960-го года. Степень n графа G — это граф G’ на том же множестве вершин, где между парой вершин есть ребро тогда и только тогда, когда длина пути между этими вершинами в G не превосходит n. Доказано, что распознавание, является ли данный граф степенью 2 какого-то графа — NP-полная задача, и может быть решена за полиномиальное время только для некоторых подклассов графов.
Вопрос точной степени n графа G очень похож, но здесь мы ограничиваемся ребрами в графе G’ тогда, когда между соответствующей парой вершин в графе G существует простой путь длины n. Доказано, что возможно за полиномиальное время определить, является ли граф точной степенью 2 какого-то графа. В нашей работе нам удалось доказать, что задача распознавания, является ли граф точной степенью 3 графа-дерева, также является полиномиально разрешимой.
Место проведения: Покровский бульвар 11, аудитория D109.
2025
8) 10 июня, Юрий Дементьев: Алгоритмы справедливых дележей неделимых предметов
7) 18 марта, Игорь Мамай: Статическая оптимальность и другие свойства Splay-дерева
6) 17 декабря, Игорь Мамай: Вероятностная структура данных Zip-дерево
2024
5) 19 ноября, Филипп Грибов: Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время
4) 3 октября, Никита Звонков: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер
3) 14 мая, Филипп Рухович: Внешние биллиарды вне правильных многоугольников
2) 23 апреля, Филипп Грибов: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами
1) 5 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов