Задача сортировки на графах в олимпиадах по программированию

Main Article Content

Михаил Иванович Киндер
Андрей Витальевич Казанцев

Аннотация

Разобрана задача сортировки данных, отношение порядка между которыми описано в виде отношения смежности вершин на произвольном графе. Выделены подзадачи и вопросы, относящиеся к «окрестности» проблемы; их решение представляет собой своеобразные уровни «погружения» в решение общей задачи. Обсуждены алгоритмы решения отдельных подзадач для графов специального вида, а также различные подходы к решению проблемы сортировки в общем случае. Задача сортировки такого типа предлагалась на Кубке международной школы ISI-Junior по спортивному программированию в июле 2019 года (г. Иннополис).

Article Details

Как цитировать
Киндер, М. И., & Казанцев, А. В. (2019). Задача сортировки на графах в олимпиадах по программированию. Электронные библиотеки, 22(5), 384-391. https://doi.org/10.26907/1562-5419-2019-22-5-384-391
Биографии авторов

Михаил Иванович Киндер

Доцент кафедры высшей математики и математического моделирования Института математики и механики им. Н.И. Лобачевского КФУ

Андрей Витальевич Казанцев

Доцент кафедры математической статистики Института вычислительной математики и информационных технологий КФУ

Библиографические ссылки

Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск. 2-е изд. М.: Издательский дом «Вильямс», 2007, Т. 3, 832 с.
Кормен Т.X., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямс», 2005. 1296 с.
Киндер М.И. Классические комбинаторные объекты на соревнованиях по программированию // Информационные технологии в образовании и науке. ИТОН 2016: Материалы международной научно-практической конференции. Казань: Изд-во Академии наук РТ, 2016, C. 46–52.