Sorting problem on graths in programming contests

Main Article Content

Mihail Ivanovich Kinder
Andrei Kazantsev

Abstract

The problem of sorting data is analyzed, the order relation between which is described as the adjacency relation of vertices on an arbitrary graph. Subtasks and issues related to the ‘neighborhood‘ of the problem are highlighted; their solution is the level of ‘immersion‘ in the solution of the general problem. Algorithms for solving individual subtasks for graphs of a special kind are discussed, as well as various approaches to solving the sorting problem in the general case. A sorting task of this type was proposed at the ISI-Junior School Programming Cup in July 2019 (Innopolis).

Article Details

Author Biographies

Mihail Ivanovich Kinder

Associate professor, Department of Further Mathematics and Mathematical Modelling of N.I. Lobachevsky Institute of Mathematics and Mechanics KFU

Andrei Kazantsev

Associate professor at Institute of Computer Mathematics and Information Technologies KFU.

References

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