Перевод статьи подготовлен специально для студентов курса «Алгоритмы для разработчиков».

---

Пирамидальная сортировка (или сортировка кучей, HeapSort) — это метод сортировки сравнением, основанный на такой структуре данных как двоичная куча. Она похожа на сортировку выбором, где мы сначала ищем максимальный элемент и помещаем его в конец. Далее мы повторяем ту же операцию для оставшихся элементов.

История квантовой криптографии началась не с технологий связи, а с попытки решить совершенно другую задачу — создать деньги, которые невозможно подделать.

Стивен Визнер из Колумбийского университета в 1983 году предложил создать квантовые банкноты государственного образца, которые нельзя скопировать даже в том случае, если у желающего сделать это есть типографское оборудование и бумага, при помощи которых изготавливался оригинал. Вероятность изготовления точной копии оригинала, защищенного квантовыми технологиями, стремится к нулю.

Навигация по лесу

Алгоритм поиска пути A* — это мощный инструмент для быстрой генерации оптимальных путей. Обычно A* демонстрируют при навигации по картам из сеток, но он может использоваться не только для сеток! Он может работать с любыми графами. Можно использовать A* для поиска пути в мире круглых препятствий.


В оригинале статьи все изображения интерактивны.

Как один алгоритм решает обе эти задачи? Давайте начнём с краткого описания того, как работает A*.

Алгоритм A*

Алгоритм A* находит оптимальный путь из начальной в конечную точку, избегая по дороге препятствия. Он реализует это, постепенно расширяя множество частичных путей. Каждый частичный путь — это серия шагов от начальной точки до какой-то промежуточной точки на дороге к цели. В процессе работы A* частичные пути становятся всё ближе конечной точке. Алгоритм прекращает работу тогда, когда находит полный путь, который лучше оставшихся вариантов, и это можно доказать.

На каждом шаге алгоритма A* оценивает множество частичных путей и генерирует новые пути, расширяя наиболее многообещающий путь из множества. Для этого A* хранит частичные пути в очереди с приоритетами, отсортированном по приблизительной длине — истинной измеренной длине пути плюс примерное оставшееся расстояние до цели. Это приближение должно быть недооценкой; то есть приближение может быть меньше истинного расстояния, но не больше него. В большинстве задач поиска пути хорошей преуменьшенной оценкой является геометрическое расстояние по прямой от конца частичного пути до конечной точки. Истинный наилучший путь до цели от конца частичного пути может быть длиннее, чем это расстояние по прямой, но не может быть короче.

В этой короткой статье я расскажу о паттерне в Rust, который позволяет "сохранять" для последующего использования тип, переданный через обобщенный метод. Этот паттерн встречается в исходниках Rust-библиотек и я тоже иногда его использую в своих проектах. Мне не удалось найти в сети публикаций о нем, поэтому я дал ему свое название: "Замыкание обобщенного типа", и в этой статье хочу рассказать, что он из себя представляет, зачем и как его можно использовать.

В этой статье описывается библиотека optlib, предназначенная для решения задач глобальной оптимизации на языке Rust. На момент написания этой статьи в этой библиотеке реализован генетический алгоритм нахождения глобального минимума функции. Библиотека optlib не привязана к конкретному типу входных данных для оптимизируемой функции. Также библиотека построена таким образом, что при использовании генетического алгоритма можно легко менять алгоритмы скрещивания, мутации, отбора и другие этапы работы генетического алгоритма. По сути генетический алгоритм собирается как бы из кубиков.

Дорогие мои друзья, отважные критики, тихие читатели и тайные почитатели, СДСМ заканчивается.



Я не могу похвастаться тем, что за 7 лет я затронул все темы сетевой сферы или тем, что хотя бы одну из них раскрыл полностью. Но это и не было целью. А целью этой серии статей было ввести юного студента за руку в этот мир и проводить его шаг за шагом по основной галерее, давая общее представление, и уберечь от болезненных скитаний по тёмным уголкам сознания Олифера и Олифера в мучительных попытках найти ответ на вопрос, как всё это применить в жизни.
СДСМ планировался коротким практическим курсом «как научиться в сети за месяц», а вылился в 16 (на самом деле 19) длинных выпусков, которые мы уже даже переименовали в «Сети Для Самых Суровых». Общее количество символов перевалило за 1 000 000.

27 марта мы в Mozilla объявили о начале стандартизации WASI, системного интерфейса WebAssembly (WebAssembly system interface).

Зачем: разработчики начали применять WebAssembly за пределам браузера, потому что WASM обеспечивает быстрый, масштабируемый, безопасный способ запуска одинакового кода на всех машинах. Но у нас пока нет прочного фундамента для такой разработки. Вне браузера нужен некий способ общения с системой, то есть системный интерфейс. А у платформы WebAssembly его пока нет.

Что: WebAssembly — это ассемблер для концептуальной, а не физической машины. Он работает на различных архитектурах, поэтому и системный интерфейс нужен для концептуальной ОС, чтобы работать на разных операционных системах.

Вот что такое WASI: это системный интерфейс для платформы WebAssembly.

Доброго времени суток!

В этой статье я подробно опишу алгоритм, который у меня получился в результате использования идеи «заметающей прямой» для построения триангуляции Делоне на плоскости. В нем есть несколько идей, которые я нигде не встречал, когда читал статьи про триангуляцию.
Возможно, кто-то тоже найдет их необычными. Я постараюсь сделать все в лучших традициях и включить в рассказ следующие вещи: описание используемых структур данных, описание шагов алгоритма, доказательство корректности, временные оценки, а также сравнение с итеративным алгоритмом, использующим kD-дерево.

Многабукафф о том, что квантовая химия думает о принципе работы мюонного катализа: как именно мюон понижает температуру требуемой плазмы. В двух частях.

Суть первой части выражается одним предложением: мюон тяжелее, чем электрон, поэтому его сложнее отодрать от протона.

Но те, кто хочет посмотреть на формулки, графики, и узреть концептуальную суть квантовой химии в применении к наипростейшим (квази)атомам, welcome под кат.

Вторая часть доступна по этой ссылке.

С недавних пор я активно заинтересовался темой переезда за границу, и в связи с этим изучил существующие сейчас сервисы, которые оказывают помощь в переезде ИТ-специалистам. К моему удивлению, далеко не так много проектов помогают потенциальным иммигрантам. Пока что я отобрал шесть сайтов, которые показались мне интересными.

В этой статье я расскажу о личном опыте разработки небольшой игры на Rust. На создание рабочей версии ушло около 24 часов (преимущественно я работала по вечерам или на выходных). Игра еще далека от завершения, но я думаю, что опыт будет полезным. Я расскажу, чему научилась, и о некоторых наблюдениях, сделанных при построении игры с нуля.

Не так давно я прочёл фантастический роман «Задача трёх тел» Лю Цысиня. В нём у одних инопланетян была проблема — они не умели, с достаточной для них точностью, вычислять траекторию своей родной планеты. В отличии от нас, они жили в системе из трёх звёзд, и от их взаимного расположения сильно зависела «погода» на планете — от испепеляющей жары до леденящего мороза. И я решил проверить, можем ли мы решать подобные задачи.

Neural Ordinary Differential Equations

Значительная доля процессов описывается дифференциальными уравнениями, это могут быть эволюция физической системы во времени, медицинское состояние пациента, фундаментальные характеристики фондового рынка и т.д. Данные о таких процессах последовательны и непрерывны по своей природе, в том смысле, что наблюдения — это просто проявления какого-то непрерывно изменяющегося состояния.

Есть также и другой тип последовательных данных, это дискретные данные, например, данные NLP задач. Состояния в таких данных меняется дискретно: от одного символа или слова к другому.

Сейчас оба типа таких последовательных данных обычно обрабатываются рекуррентными сетями, несмотря на то, что они отличны по своей природе, и похоже, требуют различных подходов.

На последней NIPS-конференции была представлена одна очень интересная статья, которая может помочь решить эту проблему. Авторы предлагают подход, который они назвали Нейронные Обыкновенные Дифференциальные Уравнения (Neural ODE).

Здесь я постарался воспроизвести и кратко изложить результаты этой статьи, чтобы сделать знакомство с ее идеей чуть более простым. Мне кажется, что эта новая архитектура вполне может найти место в стандартном инструментарии дата-сайентиста наряду со сверточными и рекуррентными сетями.

Всем привет! Сегодня я расскажу о своих экспериментах с системами частиц. Основной целью было нахождение простых правил, которые бы порождали интересное поведение.

Классический пример системы с простыми правилами и сложным поведением — клеточные автоматы, именно на них я и ориентировался, пытаясь подобрать правила. Конечно же, для клеточных автоматов правила будут в большинстве случаев проще. Но частицы могут быть красивее!

Под катом много мегабайт гифок.

Что такое шум Перлина?

Шум Перлина придуман в 1983 году Кеном Перлином (получившим за это достижение премию Американской Академии кинематографических искусств и наук). Видите ли, в те времена все стремились к фотореализму, но его всегда не хватало. Кен Перлин придуман этот алгоритм шума, чтобы избавиться от жалкого «компьютерного» внешнего вида 3D-моделей. Шум — это генератор случайных чисел в компьютерной графике. Это случайный неструктурированный паттерн, он полезен в тех случаях, когда требуется источник подробных деталей, недостающих в очевидной структуре¹. Шум Перлина — это многомерный алгоритм, используемый в процедурной генерации, текстурах, генерации рельефа, генерации карт, генерации поверхностей, генерации вершин, и так далее, и тому подобное.

Статья посвящена лучшим практикам написания кода Go. Она составлен в стиле презентации, но без обычных слайдов. Постараемся кратко и чётко пройтись по каждому пункту.

Для начала следует договориться, что значит лучшие практики для языка программирования. Здесь можно вспомнить слова Расса Кокса, технического руководителя Go:

Программная инженерия — то, что происходит с программированием, если добавить фактор времени и других программистов.

Таким образом, Расс различает понятия программирования и программной инженерии. В первом случае вы пишете программу для себя, во втором создаёте продукт, над которым со временем будут работать и другие программисты. Инженеры приходят и уходят. Команды растут или сокращаются. Добавляются новые функции и исправляются ошибки. Такова природа разработки программного обеспечения.

Несмотря на то, что подбор хороших цветов — это искусство, существует несколько трюков, позволяющих упростить выбор красивого цвета. Эта статья состоит из двух частей: в первой я расскажу, что делает палитру хорошей, а во второй выведу формулу, которую можно использовать для подбора красивой палитры.

Примечание: это далеко не единственный способ выбора хороших цветов, скорее, набор эвристик, которые я освоил самостоятельно. Надеюсь, что это поможет вам подбирать правильные цвета для вашего веб-сайта/приложения/игры.

Недавно я был совершенно сбит с толку этим твитом «Библиотеки Ферма»:


«Вот что получится, если в факториале не умножать, а делить.»

Когда я увидел его, мне пришлось бросить свои дела, схватить блокнот и проверить формулу. Результат в черновом виде казался логичным. Так как мультипликативная версия $$ при увеличении $$ стремится к бесконечности, то «делительная» версия должна стремиться к нулю. И $$ ведёт себя именно так; полиномиальная функция $$ растёт медленнее, чем степенная функция $$ для достаточно больших $$:

$$

Но почему результат деления принимает именно вид $$? Откуда берётся $$?

Наверно худшее, что случилось в области процедурной генерации контента (если считать, что это действительно область процедурной генерации контента, в чём я уверен не полностью) — это шум Перлина. Шум Перлина невероятно хорошо подходит (по крайней мере, если не приглядываться слишком внимательно) для генерации интересных ландшафтов. В сабреддите /r/proceduralgeneration недели не проходит без того, чтобы кто-нибудь не опубликовал «систему процедурной генерации», которая оказывается визуализированным разными цветами шумом Перлина. (За время написания этой статьи появилось два таких поста!)


Я не хочу унизить шум Перлина. Это невероятно полезный для процедурной генерации инструмент, ставший точкой входа в эту область для множества людей, в том числе и меня. Но в то же время он очень сбивает с толку, потому что подразумевает, что процедурная генерация намного проще, чем это есть на самом деле. Большинство еженедельных постов о «системах процедурной генерации» в /r/proceduralgeneration исчезают без следа, когда их авторы обнаруживают, что следующий шаг в процедурной генерации гораздо сложнее. Истина в том, что шум Перлина стал своего рода счастливой случайностью. Он отлично подходит для генерации интересных ландшафтов, но на то нет систематических или повторяемых причин.