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

Article Sidebar

PDF
Опубликован: 13.11.2019
УДК 519.85
DOI: https://doi.org/10.26907/1562-5419-2019-22-5-384-391
Выпуск
Том 22 № 5 (2019): Тематический выпуск «Математическое образование в школе и вузе». Часть 1

Main Article Content

Михаил Иванович Киндер
Казанский (Приволжский) федеральный университет, г. Казань
Андрей Витальевич Казанцев
Казанский (Приволжский) федеральный университет, г. Казань

Аннотация

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

Article Details

Биографии авторов

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

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

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

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

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

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


Представляя статьи для публикации в журнале «Электронные библиотеки», авторы автоматически дают согласие предоставить ограниченную лицензию на использование материалов Казанскому (Приволжскому) федеральному университету (КФУ) (разумеется, лишь в том случае, если статья будет принята к публикации). Это означает, что КФУ имеет право опубликовать статью в ближайшем выпуске журнала (на веб-сайте или в печатной форме), а также переиздавать эту статью на архивных компакт-дисках журнала или включить в ту или иную информационную систему или базу данных, производимую КФУ.

Все авторские материалы размещены в журнале «Электронные библиотеки» с ведома авторов. В случае, если у кого-либо из авторов есть возражения против публикации его материалов на данном сайте, материал может быть снят при условии уведомления редакции журнала в письменной форме.

Документы, изданные в журнале «Электронные библиотеки», защищены законодательством об авторских правах, и все авторские права сохраняются за авторами. Авторы самостоятельно следят за соблюдением своих прав на воспроизводство или перевод их работ, опубликованных в журнале. Если материал, опубликованный в журнале «Электронные библиотеки», с разрешения автора переиздается другим издателем или переводится на другой язык, то ссылка на оригинальную публикацию обязательна.

Передавая статьи для опубликования в журнале «Электронные библиотеки», авторы должны принимать в расчет, что публикации в интернете, с одной стороны, предоставляют уникальные возможности доступа к их материалам, но, с другой, являются новой формой обмена информацией в глобальном информационном обществе, где авторы и издатели пока не всегда обеспечены защитой от неправомочного копирования или иного использования материалов, защищенных авторским правом.

При использовании материалов из журнала обязательна ссылка на URL: http://rdl-journal.ru. Любые изменения, дополнения или редактирования авторского текста недопустимы. Копирование отдельных фрагментов статей из журнала разрешается для научных исследований, персонального использования, коммерческого использования до тех пор, пока есть ссылка на оригинальную статью.

Запросы на право переиздания или использования любых материалов, опубликованных в журнале «Электронные библиотеки», следует направлять главному редактору Елизарову А.М. по адресу: amelizarov@gmail.com

Издатели журнала «Электронные библиотеки» не несут ответственности за точки зрения, излагаемые в публикуемых авторских статьях.

Предлагаем авторам статей загрузить с этой страницы, подписать и выслать в адрес издателя журнала по электронной почте скан Авторского договора о передаче неисключительных прав на использование произведения.