Сортировка блинов - Pancake sorting

Демонстрация основной операции. Лопатка переворачивает три верхних блина, и результат показан ниже. В задаче о подгоревших блинах теперь будут обожжены их верхние стороны, а не нижние.

Сортировка блинов - это разговорный термин для математической задачи сортировки неупорядоченной стопки блинов по размеру, когда шпатель можно вставить в любую точку стопки и перевернуть все блины над ней. А блинчик номер - минимальное количество переворотов, необходимое для заданного количества блинов. В таком виде проблему впервые обсудили американские геометр Джейкоб Э. Гудман.[1] Один из вариантов проблемы связан с сгорел блины, у которых у каждого блина есть подгоревшая сторона, а все блины, кроме того, должны иметь подгоревшую сторону.

Все методы сортировки требуют сравнения пар элементов. Для традиционных проблема сортировки, обычная изучаемая задача - минимизировать количество сравнений, необходимых для сортировки списка. Количество фактических операций, таких как замена двух элементов, в этом случае не имеет значения. Для задач сортировки блинов, напротив, цель состоит в том, чтобы свести к минимуму количество операций, где единственными разрешенными операциями являются развороты элементов некоторых приставка последовательности. Теперь количество сравнений не имеет значения.

Блинные проблемы

Оригинальная блинная проблема

Минимальное количество переворачиваний, необходимое для сортировки любой стопки п было показано, что блины лежат между 15/14п и 18/11п (примерно 1,07п и 1,64п,), но точное значение неизвестно.[2]

Самый простой алгоритм сортировки блинов выполняет не более 2п − 3 переворачивает. В этом алгоритме своего рода сортировка выбора, одним флипом доводим до верха самый крупный еще не рассортированный блин; опустите его в конечное положение еще одним переворотом; и повторите этот процесс для оставшихся блинов.

В 1979 г. Билл Гейтс и Христос Пападимитриу[3] дал верхнюю границу (5п+5)/3. Спустя тридцать лет это было улучшено, чтобы 18/11п командой исследователей из Техасский университет в Далласе под руководством профессора-основателя Хэл Садборо.[4][5]

В 2011 году Лоран Бюльто, Гийом Фертин и Ирена Русу[6] доказал, что задача поиска кратчайшей последовательности флипов для заданной стопки блинов является NP-жесткий, тем самым отвечая на вопрос, который оставался открытым более трех десятилетий.

Проблема подгоревшего блина

В варианте, называемом проблема подгоревшего блина, дно каждого блина в стопке подгорело, и сортировка должна завершаться подгоревшей стороной каждого блина вниз. Это знаковая перестановка, а если блин я "сгоревшей стороной вверх" отрицательный элемент я ставится на место я в перестановке. В 2008 году группа студентов построила бактериальный компьютер который может решить простой пример проблемы сгоревшего блина, запрограммировав Кишечная палочка перевернуть сегменты ДНК, похожие на подгоревшие блины. ДНК имеет ориентацию (5 'и 3') и порядок (промотор перед кодированием). Несмотря на то, что вычислительная мощность, выражаемая с помощью переворотов ДНК, невелика, большое количество бактерий в культуре обеспечивает большую платформу для параллельных вычислений. Бактерии сообщают, когда они решили проблему, став устойчивыми к антибиотикам.[7]

Проблема одинаковой стопки блинов

Это навеяно индийским хлебом (роти или чапати ) готовится. Первоначально все роти укладываются в один столбик, и повар переворачивает роти лопаткой так, чтобы каждая сторона каждого роти в какой-то момент касалась основного огня, чтобы поджарить. Возможны несколько вариантов: гриль можно рассматривать как односторонний или двухсторонний, и может быть запрещено или не поджаривать одну и ту же сторону дважды. Эта версия проблемы была впервые исследована Аркой Ройчоудхури.[8]

Блинная задача на струнах

Приведенное выше обсуждение предполагает, что каждый блин уникален, то есть последовательность, в которой выполняются перестановки префиксов, является перестановка. Однако «строки» - это последовательности, в которых может повторяться символ, и это повторение может уменьшить количество обращений префикса, необходимых для сортировки. Читтури и Садборо (2010) и Hurkens et al. (2007) независимо показали, что сложность преобразования одной совместимой строки в другую с минимальным количеством обращений префикса равна НП-полный. Они также дали границы того же. Hurkens et al. дал точный алгоритм сортировки двоичных и троичных строк. Читтури[9] (2011) доказали, что сложность преобразования совместимой подписанной строки в другую с минимальным числом обращений подписанного префикса - проблема сгоревшего блина на строках - является NP-полной.

История

Проблема сортировки блинов была впервые поставлена Джейкоб Э. Гудман, пишущий под псевдонимом «Гарри Двайтер» («взволнованный официант»).[10]

Хотя сортировка блинчиков чаще рассматривается как обучающее устройство, она также появляется в приложениях в сетях с параллельными процессорами, в которых она может обеспечить эффективный алгоритм маршрутизации между процессорами.[11][12]

Проблема примечательна тем, что посвящена единственной известной математической статье автора Microsoft основатель Билл Гейтс (как Уильям Гейтс), озаглавленный «Границы для сортировки по изменению префикса». Опубликованный в 1979 году, он описывает эффективный алгоритм сортировки блинов.[3] Кроме того, наиболее заметная статья, опубликованная Футурама соавтор Дэвид X. Коэн (как Дэвид С. Коэн) касался проблемы сгоревших блинов.[13] Их сотрудники были Христос Пападимитриу (тогда в Гарвард, сейчас на Колумбия ) и Мануэль Блюм (тогда в Беркли, сейчас на Университет Карнеги Меллон ), соответственно.

Связанные проблемы знаковой сортировки обращениями и сортировки обращениями также изучались совсем недавно. В то время как для знаковой сортировки обращениями найдены эффективные точные алгоритмы,[14] Доказано, что проблема сортировки по разворотам трудна даже для аппроксимации с точностью до определенного постоянного множителя,[15] а также доказано, что его можно аппроксимировать за полиномиальное время с точностью до коэффициента аппроксимации 1,375.[16]

Блинные графики

Блинный граф P3
Блинный граф P4 можно построить рекурсивно из 4 копий P3 путем присвоения различных элементов из набора {1, 2, 3, 4} в качестве суффикса каждой копии.
Основная статья: Блинный график

An п-блинный график является графом, вершинами которого являются перестановки п символы от 1 до п а его ребра задаются между перестановками транзитивными перестановками префиксов. Это регулярный график с н! вершин, его степень n - 1. Проблема сортировки блинов и проблема получения диаметр блинного графа эквивалентен.[17]

Блинный график размерности п, Пп могут быть построены рекурсивно из n копий Pп-1, назначая другой элемент из набора {1, 2,…, n} в качестве суффикса для каждой копии.

Их обхват:

.

Γ (Pп) род из Pп является:[18]

Поскольку графы-блины обладают множеством интересных свойств, таких как симметричные и рекурсивные структуры, малые степени и диаметры по сравнению с размером графа, им уделяется большое внимание как модели взаимосвязанных сетей для параллельных компьютеров.[19][20][21] Когда мы рассматриваем блинные графы как модель взаимосвязанных сетей, диаметр графа является мерой, которая представляет задержку связи.[22][23]

Блинные графики Графики Кэли (таким образом вершинно-транзитивный ) и особенно привлекательны для параллельной обработки. Они имеют сублогарифмическую степень и диаметр и относительно редкий (по сравнению, например, с гиперкубы ).[18]

Связанные целочисленные последовательности

Количество стопок заданной высоты п которые требуют уникальных сальто k сортировать
Высота
п		k
0123456789101112131415
11
211
31221
4136113
51412354820
61520791992811332
7163014954313571903101635
817422511191428110561150118520455
918563912278106663801593585132697793795804
101972575396322825106461377863919365130975681467873232
11110908096429438912527371174766412651599810731425047191236489563546
1211111010999883779375333973064788141419294933725211842004316933221311105006613032704167
1311213214511455613009610305057046318403095551849922756397834751525125357218305656614586536481868748522001

Последовательности из Интернет-энциклопедия целочисленных последовательностей:

  • OEIS: A058986 - максимальное количество флипов
  • OEIS: A067607 - количество стопок, требующих максимального количества флипов (см. Выше)
  • OEIS: A078941 - максимальное количество флипов для «сгоревшей» стопки
  • OEIS: A078942 - количество переворотов для отсортированной стопки «сгоревшая сторона на вершине»
  • OEIS: A092113 - указанный выше треугольник, читаемый по строкам

[9]

Рекомендации

  1. ^ Саймон Сингх (14 ноября 2013 г.). «Переворачивать блины с математикой». Хранитель. Получено 25 марта, 2014.
  2. ^ Fertin, G .; Labarre, A .; Rusu, I .; Tannier, E .; Виалетте, С. (2009). Комбинаторика перестроек генома. MIT Press. ISBN  9780262062824.
  3. ^ а б Гейтс, В.; Пападимитриу, К. (1979). «Границы для сортировки по изменению префикса» (PDF). Дискретная математика. 27: 47–57. Дои:10.1016 / 0012-365X (79) 90068-2. Архивировано из оригинал (PDF) 10 июня 2007 г.. Получено 31 марта, 2007.
  4. ^ «Команда побеждает молодого Билла Гейтса улучшенным ответом на так называемую задачу« Блин »по математике». Техасский университет в Центре новостей Далласа. 17 сентября 2008 г. Архивировано с оригинал 5 апреля 2012 г.. Получено 10 ноября, 2008. Команда студентов Университета Калифорнии в Далласе, изучающих информатику, и их научный руководитель усовершенствовали давнее решение математической головоломки, известной как проблема блинов. Предыдущее лучшее решение, просуществовавшее почти 30 лет, было разработано Биллом Гейтсом и одним из его преподавателей в Гарварде Христосом Пападимитриу за несколько лет до основания Microsoft.
  5. ^ Chitturi, B .; Fahle, W .; Meng, Z .; Morales, L .; Shields, C.O .; Sudborough, I.H .; Войт, В. (31 августа 2009 г.). «Верхняя граница (18/11) n для сортировки по перестановкам префиксов». Теоретическая информатика. Графики, игры и вычисления: Посвящается профессору Буркхарду Моньену по случаю его 65-летия. 410 (36): 3372–3390. Дои:10.1016 / j.tcs.2008.04.045.
  6. ^ Бюльто, Лоран; Фертин, Гийом; Русу, Ирена (2015). «Блин листать сложно». Журнал компьютерных и системных наук. 81 (8): 1556–1574. arXiv:1111.0434. Дои:10.1016 / j.jcss.2015.02.003.
  7. ^ Хейнс, Кармелла А; Бродерик, Мэриан Л; Браун, Адам Д; Батнер, Тревор Л; Диксон, Джеймс О; Харден, У. Лэнс; Слышал, переулок H; Джессен, Эрик Л; Маллой, Келли Дж; Огден, Брэд Дж; Розмонд, Сабрия; Симпсон, Саманта; Цвак, Эрин; Кэмпбелл, Малкольм; Экдал, Тодд Т.; Хейер, Лори Дж.; Поэт, Джеффри Л. (2008). «Создание бактерий для решения проблемы сгоревших блинов». Журнал биологической инженерии. 2: 8. Дои:10.1186/1754-1611-2-8. ЧВК  2427008. PMID  18492232.
  8. ^ Ройчоудхури, Арка (18 марта 2015 г.). "Itunes: блины". Crazy1S.
  9. ^ а б Читтури, Бхадрачалам (2011). «ЗАПИСКА О СЛОЖНОСТИ ГЕНЕТИЧЕСКИХ МУТАЦИЙ». Дискретная математика, алгоритмы и приложения. 03 (3): 269–286. Дои:10.1142 / S1793830911001206.
  10. ^ Двайтер, Гарри (1975), «Элементарная проблема E2569», Амер. Математика. Ежемесячно, 82 (10): 1009–1010, Дои:10.2307/2318260, JSTOR  2318260
  11. ^ Gargano, L .; Vaccaro, U .; Возелла, А. (1993). «Отказоустойчивая маршрутизация в сетях межсоединений типа« звезда »и« блинов ». Письма об обработке информации. 45 (6): 315–320. CiteSeerX  10.1.1.35.9056. Дои:10.1016/0020-0190(93)90043-9. Г-Н  1216942..
  12. ^ Канеко, К .; Пэн, С. (2006). «Маршрутизация непересекающихся путей в блинных графах». Материалы седьмой Международной конференции по параллельным и распределенным вычислениям, приложениям и технологиям, 2006 г. (PDCAT '06). С. 254–259. Дои:10.1109 / PDCAT.2006.56. ISBN  978-0-7695-2736-9..
  13. ^ Коэн, Д.; Блюм, М. (1995). «К вопросу о сортировке подгоревших блинов». Дискретная прикладная математика. 61 (2): 105. Дои:10.1016 / 0166-218X (94) 00009-3.
  14. ^ Kaplan, H .; Шамир, Р .; Тарьян, Р. (1997). «Более быстрый и простой алгоритм сортировки перестановок со знаком по переворачиванию». Proc. 8-я ACM-SIAM SODA: 178–87.
  15. ^ Berman, P .; Карпинский, М. (1999). "О некоторых более жестких результатах несовместимости". Proc. 26-й ICALP (1999) LNCS 1644: 200–09.
  16. ^ Berman, P .; Карпинский, М.; Ханненхалли, С. (2002). «1.375-Аппроксимационные алгоритмы сортировки по разворотам». Proc. 10-е ESA (2002), LNCS 2461: 200–10.
  17. ^ Асаи, Сёго; Куноике, Юсуке; Синано, Юдзи; Канеко, Кейчи (1 сентября 2006 г.). Вычисление диаметра 17-блинного графа с использованием кластера ПК. Euro-Par 2006 Параллельная обработка: 12-я Международная конференция Euro-Par. Конспект лекций по информатике. 4128. С. 1114–1124. Дои:10.1007/11823285_117. ISBN  978-3-540-37783-2.
  18. ^ а б Нгуен, Куан; Беттайеб, Саид (5 ноября 2009 г.). «О роде блинной сети» (PDF). Международный арабский журнал информационных технологий. 8 (3): 289–292.
  19. ^ Akl, S.G .; Qiu, K .; Стойменович, И. (1993). «Фундаментальные алгоритмы для сетей межсоединений типа« звезда »и« блин »с приложениями к вычислительной геометрии». Сети. 23 (4): 215–225. CiteSeerX  10.1.1.363.4949. Дои:10.1002 / нетто.3230230403.
  20. ^ Bass, D.W .; Садборо, И. (Март 2003 г.). «Блин проблемы с ограниченным обращением префиксов и некоторыми соответствующими сетями Кэли». Журнал параллельных и распределенных вычислений. 63 (3): 327–336. CiteSeerX  10.1.1.27.7009. Дои:10.1016 / S0743-7315 (03) 00033-9.
  21. ^ Berthomé, P .; Ferreira, A .; Переннес, С. (декабрь 1996 г.). «Оптимальное распространение информации в звездных и блинных сетях». Транзакции IEEE в параллельных и распределенных системах. 7 (12): 1292–1300. CiteSeerX  10.1.1.44.6681. Дои:10.1109/71.553290.
  22. ^ Кумар, В .; Грама, А .; Gupta, A .; Карипис, Г. (1994). Введение в параллельные вычисления: проектирование и анализ алгоритмов. Бенджамин / Каммингс.
  23. ^ Куинн, М.Дж. (1994). Параллельные вычисления: теория и практика (второе изд.). Макгроу-Хилл.

дальнейшее чтение

внешняя ссылка