Sorting problem on graths in programming contests
https://doi.org/10.26907/1562-5419-2019-22-5-384-391
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).
About the Authors
M. I. Kinder
Kazan (Volga region) Federal University
Russian Federation
Russian Federation
A. Kazantsev
Kazan (Volga region) Federal University
Russian Federation
Russian Federation
References
1. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск. 2-е изд. М.: Издательский дом «Вильямс», 2007, Т. 3, 832 с.
2. Кормен Т.X., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. М.: Издательский дом «Вильямс», 2005. 1296 с.
3. Киндер М.И. Классические комбинаторные объекты на соревнованиях по программированию // Информационные технологии в образовании и науке. ИТОН 2016: Материалы международной научно-практической конференции. Казань: Изд-во Академии наук РТ, 2016, C. 46–52.
Review
For citations:
Kinder M.I., Kazantsev A. Sorting problem on graths in programming contests. Russian Digital Libraries Journal. 2019;22(5):384-391. (In Russ.) https://doi.org/10.26907/1562-5419-2019-22-5-384-391
Views:
28
Email this article 