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

Середина 1970-х. Гарвард. Новоиспеченный профессор Гарри Льюис читает курс лекций по прикладной математике. На паре по комбинаторике он дает студентам хитрую задачу. Сразу никто не находит ответа. Однако спустя пару дней к Льюису является растрепанный второкурсник — очевидно, после бессонных ночей за формулами — и предлагает решение, которое лучше всех известных на тот момент. Имя парня — Билл Гейтс.

А головоломка, которую профессор Льюис задавал своим подопечным, называется блинная сортировка 🥞 Формулировка ее бытовая:

Простейшая демонстрация, как это работает, где числа обозначают диаметры блинчиков:

32|41 → 234|1 → 4321| → 1234

При наивном методе решения требуется не более 2 движений на каждый блин. Но Гейтс нашел способ побыстрее. Впечатленный Льюис отправил юное дарование к своему другу, алгоритмисту Христосу Пападимитриу. И не прогадал. В 1979 году в престижном журнале Discrete Mathematics вышла статья за авторством Гейтса и Пападимитриу, где они доказали, что задачу можно решить всего за 1,67n переворачиваний. Рекорд продержался три десятилетия! Только в конце нулевых алгоритм был улучшен, да и то на пару процентов. А в 2011 году было показано, что оптимизационная задача блинной сортировки (или по-умному, нахождения кратчайшей последовательности префиксных переворотов) — NP-трудная. Но подождите, к чему сегодня столько математики?

🧬 Дело в том, что биоинформатики давно заметили, что у сортировки блинов много общего с перестройками генома. Больше всего на подбрасывания блинчиков похожи инверсии, когда фрагмент ДНК вырезается и встраивается назад в обращенном на 180° виде. Но есть нюансы. Если с панкейками мы работаем просто лопаткой, то для генома пригодится лопатка-щипцы. Правда, мы уже не ограничены краями. Теперь разрешено брать, зажимать и разворачивать блоки внутри стопки. Благодаря этому, а также тому факту, что гены имеют ориентацию, задача для хромосом становится проще блинной. Поэтому Павлу Певзнеру с коллегами удалось создать эффективные полиномиальные алгоритмы для разных типов перестроек. С их помощью можно находить минимальное количество шагов, которое, скажем, «превращает» геном мыши в геном человека, оценивать эволюционные дистанции, строить филогенетические деревья, изучать синтению 🐭

Но тогда, в конце 70-х, Билл Гейтс явно не задумывался о том, какой долгоиграющей окажется его единственная научная статья. Когда ему позвонил Пападимитриу, чтобы поздравить с выходом публикации, Билл не проявил никакого интереса. Он уже бросил Гарвард и делал свою IT-компанию.

Как вам такие блинчики?