Алгоритмы *

Искусство live-coding в JavaScript становится все более важным для успешной карьеры веб-разработчика. Если ты стремишься преуспеть на собеседованиях и проявить свои навыки в реальном времени, то эта статья для тебя. Я предлагаю тебе углубиться в мир типовых задач на собеседованиях в разделе live-coding, где ты сможешь проявить свои знания JavaScript. В этой статье мы рассмотрим популярные задачи, подходы к их решению и дадим полезные советы, которые помогут тебе справиться с этим вызовом. Давай начнем погружение в мир JavaScript и подготовимся к успешным собеседованиям!

И снова здравствуйте, уважаемые читатели Хабра. Мы продолжаем наше путешествие в мир алгоритмов поиска оптимального пути.

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

Привет, Хабр!

В поисках варианта алгоритма FP Growth, который мог бы удовлетворить моим потребностям, я столкнулся с неожиданным и крайне удивительным обстоятельством - все решения из коробки не предполагали разбиения данных на батчи (относительно небольшие наборы элементов) и последующем обучении на них. Также они не были способны дообучаться на вновь полученных транзакциях да и в целом были заточены на единовременный анализ всей транзакционной базы данных. Меня это смутило - неужели в эпоху обработки больших данных не было подробно описано или хотя бы выложено на всеобщее обозрение ни одной реализации подобного алгоритма. Возможно, я не первый, кто придумал что-то подобное, и в кулуарах научных статей найдутся схожие идеи - что ж, в любом случае это мой личный опыт и я надеюсь в каком-либо приближении он окажется вам полезен или хотя бы интересен.

Разработки на основе искусственного интеллекта нередко вызывают беспокойство широкой общественности. Собрали несколько реальных историй, сильно напоминающих сюжеты сериала «Черное зеркало» об угрожающих миру технологиях.

Треугольник Серпинского — фрактал, математическое описание которого опубликовал польский математик Вацлав Серпинский в 1915 году.

В этом посте мы напишем рекурсивный алгоритм отрисовки данного известного фрактала в canvas с помощью JS

Вариационные автоэнкодеры в квантованном векторном пространстве стали довольно популярными в последние несколько лет и успешно применяются в широком спектре генеративных задач (Stable Diffusion, VQ Diffusion, VideoGPT и др.). VQVAE позволяет сжимать картинку в латентное пространство меньшей размерности, а затем восстанавливать это латентное представление изображения в RGB-состояние. Операции в латентном пространстве выполняются быстро, поэтому VQVAE получил широкое применение как в авторегрессионных мультимодальных архитектурах (DALLE, ruDALL-E, RUDOLPH), так и в диффузионных моделях (DALL-E 2, Kandinsky 2.1, Latent Diffusion). В первом случае вариационный автоэнкодер позволяет закодировать картинку в последовательность визуальных токенов, которые вместе с текстовыми токенами используются в обучении трансформера. Во втором случае VQVAE кодирует картинку в квантованное пространство малой размерности, позволяя выполнять диффузионный процесс в латентном пространстве (ввиду того, что диффузионный процесс является итеративным и скорость генерации напрямую зависит от числа шагов диффузии, вычислительная сложность каждого шага очень важна), который в сравнении с пиксельной диффузией выполняется быстрее и потребляет меньше памяти. 

Во всех перечисленных задачах качество генерации напрямую зависит от качества восстановления исходных картинок с помощью VQVAE. Пару лет назад мы уже проводили эксперименты и обучали SBER-VQGAN, который на тот момент давал лучшие результаты в сравнении c dVAE и ванильным VQGAN. Подробнее об этих экспериментах можно прочитать в статье на Хабре. Однако по-прежнему нам не хватало качества восстановления в сложных доменах, таких как текст и лица, поэтому мы попытались модифицировать и улучшить SBER-VQGAN, в результате получив SoTA среди моделей по кодированию изображений.

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

В этот раз я расскажу как удалось реализовать открытый бесшовный мир в горизонтально масштабируемой 2D онлайн игре, а так же поделюсь идеей управления разведывательными беспилотными летательными аппаратами на огромных территориях.

Глубокое понимание внутреннего устройства DRBD позволяет более тонко настраивать работу системы и правильно планировать ресурсы. К счастью, у команды DRBD уже есть отличная документация, которая довольно подробно разбирает эту тему. Мы опирались на нее в своей работе, и решили перевести и выложить в открытом доступе 17-ю главу — как удобную шпаргалку по внутреннему устройству DRBD. Так что это не обычная статья, а перевод части официальной документации (исходная нумерация разделов сохранена).

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

То, что ChatGPT может автоматически генерировать что-то, что хотя бы на первый взгляд похоже на написанный человеком текст, удивительно и неожиданно. Но как он это делает? И почему это работает? Цель этой статьи - дать приблизительное описание того, что происходит внутри ChatGPT, а затем исследовать, почему он может так хорошо справляться с созданием более-менее осмысленного текста. С самого начала я должен сказать, что собираюсь сосредоточиться на общей картине происходящего, и хотя я упомяну некоторые инженерные детали, но не буду глубоко в них вникать. (Примеры в статье применимы как к другим современным "большим языковым моделям" (LLM), так и к ChatGPT).

Приветствую, меня зовут Алёна. Недавно на математический основах информатики в университете мы проходили задачу сетевого планирования, с помощью которой можно смоделировать процесс производства изделий. Мне была интересна данная тема и я решила поделиться с вами, как решить задачу сетевого планирования с использованием языка Python.

Привет, Хабр! Это команда дата-сайентистов Magnus Tech. В этом посте мы расскажем, как работали над одним общественно полезным проектом — алгоритмом, который распознает ДТП по видео с дорожных камер. Кейс будет интересен широкому кругу разработчиков, которые занимаются технологиями машинного зрения и обучения. В нем — наш долгий путь из множества попыток сделать точный алгоритм, несмотря на его настойчивые попытки быть неточным.

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

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

Различные методы эволюции ключей (терминология не устоялась, предпочитаю использовать такой перевод словосочетания «key-evolving techniques») асимметричных криптоалгоритмов позволяют защититься от компрометации секретных ключей путем периодической модификации ключевых пар. Подобная защита направлена не на предотвращение компрометации секретного ключа, а на минимизацию последствий такой компрометации: поскольку ключи периодически модифицируются, эволюционируют, данные методы позволяют ограничиться отрицательным воздействием компрометации ключа на свойство целостности или конфиденциальности сообщений, зашифрованных или подписанных только в течение определенного, относительно короткого периода, оставляя защиту сообщений других периодов ненарушенной. Большинство протоколов с эволюцией ключей подразумевает достаточно активный обмен сообщениями между сторонами защищенного обмена данными. При этом бывают сценарии, когда возможности для интерактивного взаимодействия у сторон отсутствуют.

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

Привет, Хабр!

На связи участники профессионального сообщества NTA Кухтенко Андрей, Кравец Максим и Сиянов Артем.

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

Зачем нужна еще одна статья

Всем привет! В предыдущих двух статьях мы подробно рассмотрели технические и методологические аспекты A/B-тестирования в Ozon. А сейчас время перейти к не менее интересным темам. Так как наша команда занимается не только A/B-тестами, но и в целом развитием методов принятия решений с помощью causal inference, стоит уделить внимание многоруким бандитам. 

В этой статье мы рассмотрим методологию и границы применимости классических многоруких и контекстуальных бандитов, а также реализуем контекстного бандита, в основе которого будут сэмплирование Томпсона и нейронная сеть. Ну и, конечно, мы постараемся ответить на главный вопрос: могут ли многорукие бандиты заменить A/B-тесты? 

С увеличением спроса на операции, которые требуют больших объемов записи, традиционные базы данных, использующие B-дерево, становятся узким местом, поскольку обновление записей в b-дереве приводит к многочисленным беспорядочным операциям ввода-вывода (IO) и обновлению нескольких страниц на диске. B-дерево очень хорошо подходит для "тяжелых" операций чтения. Для операций с большими объемами записи у нас есть LSM-дерево.

Давайте попробуем понять, что такое LSM-дерево, как оно работает на самом деле.