10 самых странных, блестящих алгоритмов, когда-либо придуманных и что они на самом деле делают

Вы когда-нибудь пытались извлечь многоугольную сетку из 3D дискретного скалярного поля? Нет ли? Хорошо, еще в 1987 году два программиста в General Electric сделали это — и они в конечном итоге изобрели алгоритм Марширующих кубиков. В этом и состоит сила алгоритма. Некоторые алгоритмы быстры, некоторые элегантны, а некоторые настолько странны, что они чувствуют себя как колдовство. Whenever you instruct a machine to solve a problem with code, you’re designing a procedure to transform bits into meaning В этой истории мы погружаемся в десять самых странных, самых блестящих алгоритмов, когда-либо придуманных — тех, которые помогают искать миллиарды строк кода за миллисекунды, генерировать бесконечные карты из ничего и превращать квантовую странность в практическую логику. #1 - Функция коллапса волны Одной из самых странных вещей в науке является эксперимент с двойным разрывом: частицы ведут себя как волны, когда вы не смотрите, но в тот момент, когда вы их наблюдаете, они попадают на место, как частицы. Эта идея «функции коллапса волн» звучит абстрактно, но она была превращена в удивительно практичный алгоритм. Представьте, что вы разрабатываете карту видеоигр с боковым прокручиванием. Вы хотите, чтобы мир чувствовал себя ручной, но также и навсегда. Вначале каждая плитка карты похожа на «волну» — это еще не что-то конкретное. Она полна возможностей. Но по мере того, как игрок движется вперед — наблюдая за миром — алгоритм «коллапса» этой неопределенности. Это случайность с целью, все без единого куска генеративного ИИ. #2 Модель распространения Это странно, это действительно странно. Возьмем модели диффузии — технологию, лежащую в основе таких генераторов изображений, как DALL·E и Stable Diffusion. Они основаны на идее из термодинамики: диффузия, где частицы естественным образом распространяются из областей с более высокой концентрацией в области с более низкой концентрацией. В машинном обучении этот процесс переворачивается. Вместо того чтобы переходить от порядка к хаосу, алгоритм начинается с чистого шума — как изображение кошки — и учится постепенно перерабатывать его в значимое изображение. Но вам нужна модель, чтобы сделать это хорошо. Алгоритм диффузии работает в две фазы. Во-первых, во время тренировок модель берет реальные изображения и постепенно добавляет шум в процесс вперед, пока они не станут неузнаваемыми. Делайте это на миллионах изображений с этикетками, и вы получите модель, которая может мечтать о новых изображениях с нуля. Кошки в космосе. Древний Рим в стиле Pixar. Гиперреалистичные стулья из авокадо. Диффузия уже переформатирует то, как мы генерируем музыку, аудио, и далее — видео. #3 Симулированный аннелинг Одна из самых разочаровывающих частей программирования заключается в том, что редко существует одно правильное решение — просто море хороших, и несколько отличных.Как организация склада Amazon: десятки способов сделать это, но только несколько, которые действительно имеют смысл в масштабе. Симулированное осаждение берет свое название от металлургии, где металлы неоднократно нагреваются и охлаждаются для устранения дефектов. Такая же концепция применяется к оптимизации. Вы пытаетесь найти лучшее решение в хаотичном ландшафте, полном местных вершин и долин. Представьте, что вы ищете самый высокий пик в горном диапазоне. Базовый алгоритм подъема на холм заставит вас застрять на первом ударе, который выглядит многообещающим. Но симулированное загорание умнее. Он начинается с высокой «температуры», что означает, что он свободно исследует — иногда даже принимая худшие пути, чтобы избежать местных ловушек. По мере постепенного снижения температуры он становится более насыщенным, устанавливая только лучшие движения. Компромисс - это исследование против эксплуатации. И это не только полезно в коде - это хорошая метафора для обучения кодированию, тоже. #4 Спящий Вы не можете говорить об алгоритмах, не приводя к сортировке — и, возможно, самый абсурдно умный (и совершенно бесполезный) из когда-либо придуманных . Спящий черный Традиционные алгоритмы сортировки, такие как или Используйте стратегии разделения и завоевания, чтобы рекурсивно разбивать массивы на подмассивы и эффективно их сортировать. но где-то на 4chan сумасшедший гений предложил совершенно другой подход. Quicksort Мерседес Вот как это работает: для каждого числа в массиве начните новую нить. Каждая нить спит на количество миллисекунд, равное ее значению, а затем печатает число, когда оно просыпается. Умная часть? Она пропускает всю привычную логику и превращает программист нитей CPU в сортировочный двигатель. Нет сравнений. Нет рекурсии. Просто спите и печатайте. Но это дико непрактично. Он разрывается с отрицательными числами, дубликатами или большими значениями. Он также неэффективен, создавая одну нить за число. И это зависит от времени сна, который не очень точен. #5 Божественный пол BogoSort - это алгоритм шуток: он случайно перемешивает массив снова и снова, пока, по чистой удаче, результат не будет сортирован. Теперь представьте, что это сочетается с идеей квантовой механики и мультивселенной.Теоретически, если все возможные результаты существуют в бесконечном количестве параллельных вселенных, то есть Вселенная, в которой ваша матрица уже сортирована. Некоторые Технология еще не совсем там, но «Квантовый БогоСорт» будет работать, создавая все эти возможности сразу, а затем мгновенно впадая во вселенную, где сортируется массив — по сути, позволяя квантовой случайности выполнять работу за вас. Конечно, это научная фантастика, а не компьютерная наука.Мы не можем наблюдать или разрушить мультивселенную по своему желанию.Но это играющий мысленный эксперимент о случайности грубой силы, взятой в ее логическую (и абсурдную) крайность. # 6 — Боуи И вот мой любимый.Что мне действительно круто об алгоритмах, так это то, как они иногда могут отражать природу.Возьмите программу Бойдс Крейг Рейнольдс из 1986 года — это была одна из первых искусственных симуляций жизни и она имитирует то, как птицы стают. Так живым Чувствуешь Каждая птица (или «боуид») следует всего трем правилам: избегайте столкновений с соседями (отделение), согласуйтесь с их направлением (равновесие) и двигайтесь к центру местной группы (совместимость). Но когда вы имитируете кучу этих простых поведений вместе, вы получаете увлекательные, органические паттерны, которые сдвигаются и протекают как настоящая стада. Красота здесь не в коде - это в том, что Эти сложные групповые динамики не должны быть явно запрограммированы. они просто происходят. Это как столкновение с кодом природы для децентрализованной координации. Появление # 7 — Алгоритм SHOR Идея о том, чтобы позволить людям замкнуть свои почтовые ящики и подписать свои письма уникальной подписью, основана на важной концепции в криптографии: сложности факторирования больших чисел. Безопасность большинства методов шифрования опирается на эту простую математическую реальность — умножение больших чисел вместе легко, но выяснить два оригинальных первичных числа за продуктом Проблема, известная как Это чрезвычайно сложно и потребляет время. — prime factorization — На самом деле, это настолько сложно, что для решения вашего ноутбука могут потребоваться сотни триллионов лет, если, конечно, мы не начнем использовать квантовые компьютеры.Квантовые компьютеры имеют потенциал для решения проблемы факторизации целых чисел экспоненциально быстрее, чем любой классический алгоритм, благодаря алгоритмам, таким как алгоритм Шора. Алгоритм Шора может разбить большие числа на свои основные факторы намного быстрее, чем обычные методы. В основе алгоритма Шора лежат концепции квантовой механики, такие как кубиты, перекрытие и запутанность.Эти концепции позволяют квантовым компьютерам выполнять массивные расчеты параллельно, что классические компьютеры даже не могут приблизиться. Хотя сам алгоритм является законным, его применение в реальном мире все еще находится на ранних стадиях.На самом деле, самое большое число, когда-либо считанное с использованием квантовых вычислений, составляет всего 21. Недавно китайской команде удалось вычислить огромное число с помощью квантового компьютера, но они использовали алгоритм, который не масштабируется хорошо для гораздо больших чисел, а это означает, что он еще не практичен для общего использования. Однако, если квантовые компьютеры становятся достаточно мощными и кто-то выясняет, как масштабировать эти алгоритмы до действительно больших чисел, ожидайте серьезного срыва в мире кибербезопасности. # 8 — Марширующие кубики В начале этой истории мы упоминали алгоритм Марширующих кубиков, но в него стоит погрузиться, потому что это был важный поворотный момент для визуализации 3D-данных, особенно в медицине. Представьте, что у вас есть 3D-сканирование человеческого тела, как с МРТ. МРТ дает вам не 3D-модель, а гигантский кубик чисел — 3D-скалярное поле. Каждая точка в этом поле имеет значение, которое представляет нечто вроде плотности тканей или интенсивности сигнала.Эти данные непрерывны в пространстве, но нам нужно превратить его в что-то визуальное — поверхность, форму, что-то, что компьютер может нарисовать. Алгоритм берет это 3D-поле и проходит через него один небольшой кубик за раз. Каждый кубик формируется восьми соседних точек данных в поле. Теперь вот умный кусок: каждая из этих восьми точек находится либо выше, либо ниже порога (например, там, где кожа превращается в кость). Это дает вам 8-битное число — 256 возможных комбинаций для каждого небольшого куба. Для каждой из этих комбинаций была предварительно вычислена конкретная схема треугольников и хранится в таблице поиска. Эти треугольники используются для приближения поверхности, проходящей через этот куб. Повторяя этот процесс — прохождение через кубик за кубиком, подключение значений, поиск форм — алгоритм постепенно создает полную 3D сетку. Это было новаторским в 1980-х годах, потому что оно превратило плоские резьбы для МРТ или КТ в реальные 3D-модели, которые врачи могли вращать, увеличивать и анализировать. # 9 — Практическая византийская толерантность к ошибкам В современных вычислениях мы часто работаем с распределенными системами — сетями компьютеров, распространенными по облаку, что приводит нас к одной из самых известных проблем распределенных вычислений: проблеме византийских генералов. Представьте это: несколько генералов из византийской армии окружают город. Им нужно координировать и атаковать одновременно, чтобы победить. Но они могут общаться только путем отправки сообщений, и некоторые из этих генералов могут быть предателями, пытающимися саботировать план. Компьютеры сталкиваются с одной и той же проблемой.В распределенной системе некоторые машины могут рухнуть, быть медленными или даже быть взломанными.Как остальная часть сети может договориться о том, что делать, когда они не могут доверять всем? Это место, где входят алгоритмы консенсуса, такие как PBFT — Практическая византийская толерантность к ошибкам. PBFT предназначен для решения подобных неудач. Он работает, предлагая одному узлу действие, передавая сообщение «предварительно подготовленный». Другие узлы реагируют с признаниями. Как только определенное количество узлов (обычно две трети или более) соглашаются, они достигают консенсуса. Наконец, первоначальный узл посылает сообщение «обязаться», говоря всем выполнить действие. Даже если до одной трети узлов являются дефектными или вредоносными, система все равно может функционировать правильно. Алгоритмы, такие как PBFT, являются основой блокчейн-систем и распределенных облачных баз данных, помогая им оставаться последовательными и надежными — даже когда все идет не так. #10 — Бойер Мур И, наконец, это приводит нас к старинному алгоритму, который тихо управляет некоторыми из самых быстрых инструментов, которые мы используем сегодня — например, grep. Это получается. быстрее Вот как это работает.Большинство базовых алгоритмов поиска идут слева направо, проверяя каждый символ один за другим. внутри шаблона поиска, и он использует два умных трюка, чтобы пропустить большие кусочки текста. «В огромном блоке текста. right to left “needle 1. Bad character rule: Если вы ищете «нож» и текущий текстовый символ является «z» — тогда нет никакого способа, чтобы матч мог начаться в этой точке или раньше. 2. Good suffix rule: Если вы ищете «недельку» и только что совпали с «dle» в конце — но следующий персонаж разрывает матч — алгоритм не начинается с следующей буквы. Вместо этого он спрашивает: появляется ли «dle» раньше в «needle»? Если да, он меняет шаблон так, что предыдущие «dle» строки. Если нет, он пропускает всю часть «dle» полностью. Эти эвристические стратегии пропуска не идеальны, но они более эффективными, чем методы грубой силы. Путь По мере того, как текст становится длиннее, алгоритм, как правило, пропускает все больше и больше символов, делая его быстрее по сравнению с размером ввода. Когда логика встречает воображение: истинная сила алгоритмов Будь то превращение квантовой неопределенности в практическое генерирование изображений, подражание биологическому поведению с помощью трех простых правил или поиск текста назад, чтобы найти шаблоны быстрее, эти подходы показывают, что самые нетрадиционные идеи часто приводят к самым мощным решениям. Что делает эти алгоритмы блестящими, это не их эффективность или новизна, а их смелость.Они бросают вызов предположениям.Они переворачивают проблемы на свои головы.Они превращают случайность в структуру, хаос в порядок, а абстрактную теорию в реальное влияние. Больше, чем элегантные математические инструменты — эти 10 странных алгоритмов . are a testament to human ingenuity Хотите услышать от меня чаще? ! Connect with me on LinkedIn Свяжитесь со мной на LinkedIn Я делюсь действия, советы и обновления, которые помогут вам избежать дорогостоящих ошибок и оставаться впереди в мире ИИ. Дневной Вы технический профессионал, который хочет увеличить свою аудиторию через письмо? ! Don’t miss my newsletter Не пропустите наш информационный бюллетень Моя Он полон действенных стратегий copywriting и аудитории, которые помогли сотням профессионалов выделиться и ускорить их рост. Tech Audience Accelerator