Блинчики и Билл Гейтс

В честь начала Масленицы поговорим о блинах! Точнее, об алгоритме их сортировки.
Кроме шуток — существует, так называемая, “The pancake problem". Это задача, в которой нужно упорядочить блинчики по убыванию размера. При этом можно только брать стопку из нескольких блинчиков сверху и переворачивать её. Подробнее о задаче вот в этом видео, рекомендуем к просмотру! Там же и рассказывают, при чём тут Билл Гейтс (да, тот самый).

Дело, конечно же, не ограничивается кулинарией. Блинчики — это красивая интерпретация абстрактной задачи. С точки зрения математики, речь об алгоритме сортировки, в котором единственная допустимая операция — переворот элементов последовательности до какого-либо индекса. Реализацию алгоритма на Python можно посмотреть, например, здесь.

У этой задачи есть модификация — задача о подгоревших блинах (о ней тоже есть в видео). В 2008 году группа студентов создала биокомпьютер, который мог решать простейший вариант этой задачи. Он работал на основе генетически модифицированной кишечной палочки: роль блинов здесь играли фрагменты дезоксирибонуклеиновой кислоты. Бактерия выстраивала фрагменты в нужном порядке — так она приобретала устойчивость к антибиотику и не погибала. Время, затраченное на поиск правильной комбинации, показывало минимально необходимое число переворотов фрагмента.

Вот так одна математическая задача объединяет блинчики, алгоритмы и умные бактерии!