Несудьба, интегрально-ролевая система

Правила универсальной нарративно-вычислительной ролевой системы, предназначенной как для соло игр, так и вождения партии. Использует калькулятор, теги с идентификаторами и строится на интерпретации ассоциаций.

https://habr.com/ru/articles/882258/

Алгоритмы и Структуры данных

Как устроены алгоритмы онлайн-кинотеатра. Разбираем на примере

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

https://habr.com/ru/articles/882000/

Алгоритмы и Структуры данных

5 способов нарисовать обводку

Рендеринг обводки (контуров) — это техника, часто используемая в играх или из эстетических, или из геймплейных соображений. Например, в игре Sable контуры применяются для создания стиля, напоминающего комиксы, а Last of Us контуры используются для выделения врагов, когда игрок переходит в режим скрытности.

https://habr.com/ru/articles/879788/

Алгоритмы и Структуры данных

Обзор постквантовых криптостандартов США со схемами и комментариями

Поскольку принятие стандартов на постквантовые криптоалгоритмы можно считать весьма значительным событием в сфере асимметричной криптографии, а также принимая во внимание предполагаемый переход с традиционных на вышеупомянутые стандарты на горизонте в несколько лет (причем не только в США, но и в той значительной части мира, которая ориентируется на стандарты США), предлагаю вашему вниманию в данной статье описание (помимо описаний, я попытался схематично изобразить основные преобразования – под катом много схем с пояснениями) алгоритмов, на которых основаны постквантовые криптостандарты США, а также краткое обсуждение ближайших перспектив выхода новых стандартов на постквантовые криптоалгоритмы и рекомендаций по переходу с традиционных криптографических алгоритмов на постквантовые. Перечень текущих стандартов и рекомендаций NIST в части асимметричной криптографии со ссылками на их официальные публикации приведен в списке литературы к данной статье.

https://habr.com/ru/companies/aktiv-company/articles/882490/

Алгоритмы и Структуры данных

Открытые книги по ML и работе с данными

Мы регулярно публикуем подборки литературы для специалистов: делали дайджест книг для желающих поближе познакомиться с Postgres и Kubernetes. Сегодня на очереди справочники и пособия по машинному обучению, которые можно найти в открытом доступе. Эти материалы помогут погрузиться в ML, разобраться в базовых математических концепциях, понять тренды опенсорсных технологий для систем ИИ и перейти к работе с ML-платформой.

https://habr.com/ru/companies/mws/articles/872230/

Алгоритмы и Структуры данных

Боль ML-проектов: как перестать ее чувствовать и начать доходить до прода

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

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

https://habr.com/ru/companies/tbank/articles/713210/

Алгоритмы и Структуры данных

Когда и как следует инвалидировать кэш

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

https://habr.com/ru/companies/piter/articles/690764/

Алгоритмы и Структуры данных

Выразить иерархически: вопрос как увидеть хамелеона

Проблема нейросетей - невозможность обучаться на единичных примерах. Справиться может табличное RL, но обучаться на данных большой размерности - иная неразрешимая сторона этой парадигмы https://habr.com/ru/post/437020/. Решение только в одном: видеть мир иерархически, где каждая его подчасть также может быть выражена иерархически.

https://habr.com/ru/articles/690518/

Алгоритмы и Структуры данных

Алгоритмы сортировки и их производительность

Здравствуйте, давно читаю Хабр и все хотел написать какую-нибудь статью, но не знал с чего начать и о чем писать. Однако решил, что тянуть кота за причинное место. Надо просто взять и написать обзор о чем то, что я знаю и что будет просто для начала. Поэтому решил описать алгоритмы сортировки в размере 37 штук. Я понимаю, что на Хабре есть подобные статьи, однако постараюсь их добавить количеством алгоритмов и приведением небольшого числа графиков.

https://habr.com/ru/articles/689738/

Алгоритмы и Структуры данных

Смогу ли я уложить оптимизирующий компилятор в тысячу строк питона? Прогон первый: mem2reg

Год назад мне пришлось взять на себя курс лекций по теории компиляторов. Вы встречались некомпетентными преподавателями? Это я, здравствуйте! Прежде чем учить других, я всё-таки решил заглянуть в учебник сам, и это вылилось в серию статей "компилятор за выходные" (да, я помню, что за мной должок с описанием лексера/парсера). В итоге я уложил компилятор со мной придуманного си-подобного языка на GNU ассемблер в шестьсот строк кода, причём без внешних зависимостей, включая парсинг.

Всё бы хорошо, вроде работает, но кажется, самое веселье осталось за бортом. Мой компилятор, по факту, это простой pretty print вокруг синтаксического дерева, подумаешь. А как работают оптимизирующие компиляторы? И поставил я себе задачу попробовать уложить игрушечный, но всё же рабочий оптимизирующий компилятор в тысячу строк кода. Как думаете, получится?

Итак, тема сегодняшнего разговора - вынос переменных из памяти в регистры, оно же оптимизационный проход mem2reg, см. кпдв.

https://habr.com/ru/articles/881192/

Алгоритмы и Структуры данных

Как полюбить задачи регрессии


У задач классификации, в отличие от задач регрессии, есть одно очень приятное свойство:
большинство ML алгоритмов решения задач классификации выдают не просто ответ, а некоторую оценку уверенности модели в ответе. То есть помимо метрик самой модели мы обладаем оценкой вероятности для конкретного ответа на конкретном примере. Это здорово помогает в принятии решений.

Неправда ли хотелось бы иметь что-то такое и для задач регрессии?

https://habr.com/ru/articles/689338/

Алгоритмы и Структуры данных

AStar Pathfinding для агентов различного размера с использованием пространственного хэширования

Наверное, большинству людей, связанных с программированием игр, известен алгоритм AStar.

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

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

Данный пробел я постараюсь восполнить в рамках этой статьи.

https://habr.com/ru/articles/883210/

Алгоритмы и Структуры данных

Сгенерировать 100 млн случайных строк менее чем за минуту

Зачастую в программисткой практике необходимо нагенерировать множество случайных строк. Либо для тестового примера, либо как источник обезличивания, либо просто, чтобы наполнить разработческую БД. Задача, в принципе, понятная и легкая для любого уровня программиста. Но если это нужно сделать быстро, например, если набор случайных строк нужен здесь и сейчас, то можно использовать предлагаемое решение. Строки получаются разной длины, со 100%-ной хаотичностью (полностью несортированные). Выглядят эти строки вот так (спойлер):

https://habr.com/ru/companies/alfa/articles/883226/

Алгоритмы и Структуры данных

Компилятор за выходные: синтаксический анализатор Уорли

Изначально, когда я решил написать компилятор за выходные, я решил, что нет смысла заморачиваться, и использовал сторонний лексический / синтаксический анализатор. Мой выбор пал на SLY, довольно известную библиотеку. И действительно, пара часов работы, и мой компилятор прекрасно строил синтаксические деревья из исходного кода на wend. Я пытался было заглянуть под капот, утонул в море технических терминов (LL(1), LR, LALR(1) и тому подобное), и решил, что парсинг своими руками - это не для меня, теория формальных языков меня слабо интересует. Однако же в итоге выяснилось, что базовый синтаксический анализатор - это не так сложно, и я закатал рукава. В основном меня на это мотивировало две вещи:

https://habr.com/ru/articles/883390/

Алгоритмы и Структуры данных

Калькулятор? Да его напишет кто угодно

Калькулятор должен показывать результат введённого математического выражения. А это намно-о-ого сложнее, чем кажется.

В этом посте я расскажу величайшую историю о разработке приложения-калькулятора.

https://habr.com/ru/articles/883366/

Алгоритмы и Структуры данных

Фильтр Гаусса на стероидах: подход на точность вычислений

В прошлый раз мы рассказали, что для аппроксимации фильтра Гаусса можно использовать КИХ- или БИХ-фильтры, и успели познакомить читателей с тремя вариантами КИХ-фильтров. Но не спешите закрывать этот текст, если эти термины вам не знакомы! Достаточно понимать следующее: КИХ-фильтр формирует выходной сигналy[n], опираясь только на входные значенияx[n], тогда как БИХ-фильтр, помимоx[n], задействует также предыдущие значенияy[k], k < n.

По сути, все рассмотренные в первой части методы приближали гауссиану композициями полиномов 0-го или 1-го порядков, за счет чего были очень быстрыми. Сейчас мы рассмотрим более сложные варианты: полиномы 2-го порядка, БИХ-фильтры, а также способ вычисления свертки через преобразование Фурье. Мы сгруппировали их вместе по принципу скорости — они работают чуть дольше, но итоговое приближение получается на порядок точнее.

https://habr.com/ru/companies/smartengines/articles/883340/

Алгоритмы и Структуры данных

Визуализация алгоритмов сортировки

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

https://habr.com/ru/companies/domclick/articles/689064/

Алгоритмы и Структуры данных

Судоку: моя попытка в новый алгоритм решения. Часть 2. Заполнение латинского квадрата

Итак, это продолжение моих попыток в новый алгоритм решения Судоку. Начало было тут, на текущий мой взгляд довольно глупое и неудачное.

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

https://habr.com/ru/articles/883922/

Алгоритмы и Структуры данных

Алгоритм большинства голосов Бойера — Мура

Решал задачки на LeetCode и вот небольшой переводик небольшой статьи про небольшой алгоритм.

Алгоритм голосования Бойера-Мура является одним из самых популярных и оптимальных алгоритмов, который используется для поиска преобладающего элемента среди заданных, который имеет более N / 2 вхождений. Алгоритм выполняет 2 обхода по заданным элементам, что работает при O (N) временной сложности и O (1) пространственной сложности.

https://habr.com/ru/articles/689492/

Алгоритмы и Структуры данных

Как уместить поиск по 30 тысячам слов в 64 КБ ОЗУ

Как уместить словарь размером 250 КБ в 64 КБ ОЗУ с возможностью выполнения быстрого поиска? Для справки: даже современные методики сжатия наподобие gzip -9 не могут сжать этот файл до размера меньше 85 КБ.

В 1970-х Дуглас Макилрой столкнулся с этой непростой задачей при реализации проверки правописания для Unix в AT&T. Из-за ограничений компьютера PDP-11 весь словарь должен был умещаться всего в 64 КБ ОЗУ. Кажется, подобную задачу решить невозможно.

Вместо того, чтобы использовать стандартные методики сжатия, Дуглас воспользовался преимуществами свойств данных, разработав алгоритм сжатия, превышавший теоретический минимум сжатия всего на 0,03 бита. И по сей день этот рекорд остаётся непревзойдённым.

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

https://habr.com/ru/articles/882952/

Алгоритмы и Структуры данных

B-Tree — сбалансированный куст поиска

Не знаю, одному мне так везёт, или нет, но буквально на каждом собеседовании на позицию BE разработчика я слышал и продолжаю слышать вопрос про индексы в реляционных СУБД. Затем речь часто заходит про "а что там под капотом?", и, как правило, сходу вспоминаются B-Tree и Hash, причём первый - это дефолт и собственно то, что мы чаще всего видим. Ну Hash это конечно Hash Map, да и с B-Tree по названию вроде всё логично и понятно: Tree в названии однозначно указывает на дерево, ну а В это, конечно, Binary? Или Balanced? Или Balanced Binary? Почему-то долгое время я полагал, что это Balanced Binary, и эта версия даже "прокатывала".

На самом деле Binary здесь, конечно, лишнее. B-Tree сбалансированное дерево поиска, но никак не бинарное. В статье я постараюсь привести базовую идею этой структуры, его преимущества и примеры использования. Для иллюстрации рассуждений также реализую Set с B-Tree под капотом на Java и сравню его с родным TreeSet (который в свою очередь "под капотом" имеет как раз таки бинарное Red-Black Tree).

https://habr.com/ru/articles/884232/

Алгоритмы и Структуры данных