WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Одна операция блинной сортировки (вариант с подгоревшими блинами)

Блинная сортировка (от англ. pancake sorting) — алгоритм сортировки. Единственная операция, допустимая в алгоритме — переворот элементов последовательности до какого-либо индекса. В отличие от традиционных алгоритмов, в которых минимизируют количество сравнений, в блинной сортировке требуется сделать как можно меньше переворотов. Процесс можно визуально представить как стопку блинов, которую тасуют путём взятия нескольких блинов сверху и их переворачивания.

Алгоритм

Простейший алгоритм (вариант сортировки выбором) даёт не более переворотов, однако требует поиска наибольшего элемента[1]. В 1979 году Билл Гейтс и Христос Пападимитриу представили свой алгоритм и доказали достаточность переворотов и необходимость [2]. В 1997 году Хейдари и Судборог показали нижнюю границу в . Они представили точные значения вплоть до , для которого требуется 15 переворотов[3]. Значительно (до ) превзойти результат Гейтса и Пападимитриу получилось только в 2008 году у группы исследователей из Техасского университета в Далласе[en] под руководством Судборога[4][5].

Задача о подгоревших блинах

Усложнённый вариант представляет собой блинную сортировку последовательности, элементы которой содержат дополнительный бинарный параметр. Эту задачу предложили Билл Гейтс и Христос Пападимитриу в 1979 году[2]. Она стала известна как «задача о подгоревших блинах» (англ. burnt pancake problem):

Каждый блин в стопке подгорел с одной стороны. Требуется отсортировать блины по возрастанию (убыванию) диаметра так, чтобы они все лежали на тарелке подгоревшей стороной вниз.

В 2007 году группа студентов создала биокомпьютер на основе генетически модифицированной кишечной палочки (E. coli), который решал задачу о подгорелых блинах. Роль блинов играли фрагменты дезоксирибонуклеиновой кислоты (3′- и 5′-концы которых обозначали разные стороны блина). Бактерия, выстроив фрагменты в нужном порядке, приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента[6][7].

Реализация

Примечания

  1. Douglas B. West. The Pancake Problems (1975, 1979, 1973) (англ.). Проверено 16 августа 2009. Архивировано 5 апреля 2012 года.
  2. 1 2 William H. Gates; Christos H. Papadimitriou. Bounds for sorting by prefix reversal (англ.) // Discrete Mathematics. — 1979. Iss. 27. P. 47—57.
  3. Mohammad H. Heydari; I. Hal Sudborough. On the diameter of the pancake network (англ.) // Journal of Algorithms. Дулут: Academic Press, Inc, 1997. Vol. 25, iss. 1. P. 67—94.
  4. Team Bests Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics (англ.) (17.09.2008). Проверено 16 августа 2009. Архивировано 5 апреля 2012 года.
  5. B. Chitturi, W. Fahle, Z. Meng, L. Morales, C. O. Shields, I. H. Sudborough, W. Voit. An (18/11)n upper bound for sorting by prefix reversals (англ.) // Theoretical Computer Science. Эссекс: Elsevier Science Publishers Ltd., 2009. Vol. 410, iss. 36. P. 3372—3390.
  6. Karmella A. Haynes, Marian L. Broderick, Adam D. Brown et al. Engineering bacteria to solve the Burnt Pancake Problem (англ.) // Journal of Biological Engineering. — 2008. Vol. 2, iss. 8.
  7. Анимационный ролик, объясняющий решение задачи биологическим компьютером (англ.). Проверено 16 августа 2009. Архивировано 5 апреля 2012 года.

См. также

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

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

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии