Введение
Математическая задача сортировки блинов — это математическая задача, заключающаяся в упорядочивании беспорядочно сложенных блинов по размеру, используя лопатку, которую можно вставить в любую точку стопки и перевернуть все блины, находящиеся над ней. Число блинов — это минимальное количество переворотов, необходимых для заданного числа блинов. Впервые в такой формулировке эту задачу рассмотрел американский геометр Джейкоб Э. Гудман. Существует вариант задачи, связанный с подгоревшими блинами, где у каждого блина есть подгоревшая сторона, и все блины должны быть расположены подгоревший стороной вниз. Все методы сортировки требуют сравнения пар элементов. В традиционной задаче сортировки обычно исследуется минимизация количества сравнений, необходимых для упорядочивания списка. Количество фактических операций, таких как обмен двух элементов, в этом случае не имеет значения. В отличие от этого, для задач сортировки блинов целью является минимизация количества операций, единственным разрешенным типом которых является переворачивание некоторого префикса последовательности. Количество сравнений при этом не учитывается.
Pancake sorting is the mathematical problem of sorting a disordered stack of pancakes in order of size when a spatula can be inserted at any point in the stack and used to flip all pancakes above it. A pancake number is the minimum number of flips required for a given number of pancakes. In this form, the problem was first discussed by American geometer Jacob E. Goodman. A variant of the problem is concerned with burnt pancakes, where each pancake has a burnt side and all pancakes must, in addition, end up with the burnt side on bottom. All sorting methods require pairs of elements to be compared. For the traditional sorting problem, the usual problem studied is to minimize the number of comparisons required to sort a list. The number of actual operations, such as swapping two elements, is then irrelevant. For pancake sorting problems, in contrast, the aim is to minimize the number of operations, where the only allowed operations are reversals of the elements of some prefix of the sequence. Now, the number of comparisons is irrelevant.
Проблема сгоревшего блина
В вариации, называемой задачей о подгоревших блинах, нижняя сторона каждого блина в стопке подгоревшая, и сортировку необходимо завершить, расположив подгоревшей стороной вниз каждый блин. Это знаковая перестановка, и если блин i перевернут подгоревшей стороной вверх, в перестановке на место i помещается отрицательный элемент i`. В 2008 году группа студентов разработала бактериальный компьютер, способный решить простой пример задачи о подгоревших блинах, запрограммировав E. coli на переворачивание сегментов ДНК, которые аналогичны подгоревшим блинам. ДНК имеет ориентацию (5' и 3') и порядок (промотор перед кодирующей последовательностью). Несмотря на то, что вычислительная мощность, обеспечиваемая переворотами ДНК, невелика, большое количество бактерий в культуре предоставляет масштабную параллельную вычислительную платформу. Бактерии сигнализируют о решении задачи, приобретая устойчивость к антибиотикам.
Проблема с пакетом одинаковых блинчиков
Это вдохновлено способом приготовления индийского хлеба (роти или чапати). Сначала все роти складываются в один столбик, и повар использует лопатку, чтобы переворачивать роти так, чтобы каждая сторона каждого роти соприкасалась с огнем, чтобы поджарить их. Существует несколько вариантов: роти можно рассматривать как односторонние или двусторонние, а также может быть запрещено или разрешено поджаривать одну и ту же сторону дважды. Эта версия задачи была впервые исследована Аркой Ройчоудхури.
Проблема блинчиков на струнах
В приведенном выше обсуждении предполагается, что каждый блин уникален, то есть последовательность, на которой выполняются обращения префиксов, является перестановкой. Однако "строки" – это последовательности, в которых символ может повторяться, и это повторение может уменьшить число обращений префиксов, необходимых для сортировки. Chitturi и Sudborough (2010) и Hurkens et al. (2007) независимо показали, что сложность преобразования совместимой строки в другую с минимальным количеством обращений префиксов является NP-полной задачей. Они также установили границы для этой сложности. Hurkens et al. предложили точный алгоритм для сортировки двоичных и троичных строк. Chitturi (2011) доказал, что сложность преобразования совместимой знакопеременной строки в другую с минимальным количеством обращений знакопеременного префикса – задача о "подгоревшем блине" для строк – является NP-полной.
История
Проблема сортировки блинов была впервые сформулирована Джейкобом Э. Гудманом под псевдонимом "Гарри Двейтер" ("замученный официант"). Хотя чаще рассматривается как учебное пособие, сортировка блинов также находит применение в параллельных процессорных сетях, где может служить эффективным алгоритмом маршрутизации между процессорами. Эта проблема известна как тема единственной широко известной математической работы основателя Microsoft Билла Гейтса (под именем Уильяма Гейтса) под названием "Оценки для сортировки перестановкой префиксов" в соавторстве с Христосом Пападимитриу. Опубликованная в 1979 году, она описывает эффективный алгоритм для сортировки блинов. Кроме того, наиболее значимая работа, опубликованная соавтором мультсериала "Футурама" Дэвидом Коэном (под именем Дэвида С. Коэна) в соавторстве с Мануэлем Блумом, была посвящена проблеме подгоревших блинов. Связанные задачи сортировки с учетом знака перестановками и сортировки перестановками также изучались в последнее время. В то время как для сортировки с учетом знака перестановками найдены эффективные точные алгоритмы, проблема сортировки перестановками оказалась сложной даже для приближенного решения с определенным постоянным коэффициентом, но при этом доказано, что ее можно приближенно решить за полиномиальное время с коэффициентом приближения 1.375.