Алгоритмы *

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

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

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

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

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

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

Hello, world! Это вторая часть хабростатьи Smart Engines про быструю фильтрацию изображений. Да-да, создавая топовый продукт по распознаванию документов, нам приходится разбираться в методах обработки изображений на экспертном уровне (иначе не получилось бы распознать изображение паспорта за 150 мс на мобильном телефон). В предыдущей части мы начали обсуждать быстрые аппроксимации гауссовского фильтра, которым была посвящена наша недавняя публикация в научном журнале MDPI Applied Sciences [1]. О том, как работает оригинальный фильтр Гаусса, мы уже писали, сейчас мы только напомним о его использовании всюду, где возникает обработка изображений: от редактирования фотографий на смартфоне – для размытия фона за объектом в режиме "портрет", до анализа рентгеновских снимков – чтобы убрать шум и улучшить читаемость изображения.

[Прим. пер.: на Хабре уже был перевод этой статьи, но незавершённый примерно на четверть.]

Неправда.

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

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

На изображении выше показан калькулятор из iOS.

Заметили что-нибудь?

Он посчитал неправильно.

(10¹⁰⁰) + 1 − (10¹⁰⁰) равно 1, а не 0.

Android считает правильно. А причина, по которой он это делает, абсолютно безумна.

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

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

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

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

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

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

Всем привет👋🏻

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

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

Присаживайтесь поудобнее, заварите кофейку и запаситесь печеньки, нам предстоит интересный путь🍪

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

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

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

Приветствую, Хабр!

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

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

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

В этом посте мы расскажем о пяти способах рендеринга контура вокруг объекта.

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

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

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

Сегодняшняя задача заставила попотеть и разработать различные способы оптимизации рекурсивного запроса как по количеству итераций, так и по объему используемой памяти.

Привет, друзья!

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

Сегодня мы поговорим об алгоритмах сортировки.

Код, представленный в этой и других статьях серии, можно найти в этом репозитории.

Интересно? Тогда прошу под кат.

Недавно меня попросили написать отзыв на автореферат кандидатской диссертации, в которой обсуждалось моделирование случайных величин с использованием Python и C++. Я разбираюсь в моделировании, но не в программировании. Обсуждая работу, я поинтересовался у соискателя, почему он выбрал эти инструменты и не рассматривал ли Excel. Он ответил, что в их среде Excel не используется. «А жаль», — подумал я. Особенно учитывая, что в работе выборки не превышали сотни элементов. Excel легко справляется даже с миллионом и имеет десятки встроенных функций для таких целей.

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

Хоть современный ИИ уже почти в состоянии написать симфонию и превратить холст в шедевр, некоторые простые задачи все еще не так просты, если наложить ограничения на решение. Так как главной задачей у нас, в Smart Engines, является распознавание и оцифровка документов, то для нас ограничениями являются скорость работы и возможность запуска системы на вычислительно слабых конечных устройствах. В этой статье мы вспомним об одной классической задаче обработки изображений – бинаризации документов. А также расскажем, как нам удалось существенно оптимизировать нейросетевую модель бинаризации, сохранив исходное качество, и причем тут современные модели детекции текста.

Привет! Недавно в ранний доступ в Steam вышла наша игра Clayers: Prologue. Это рогалик в глиняном стиле, где нужно подбирать и смешивать цвета, чтобы убивать врагов. В этой статье разберём наш подход к генерации волн с учётом сложности противников.

Привет! Меня зовут Евгений, и сегодня я представляю курс «Алгоритмы и структуры данных» Яндекс Практикума. В этой статье хочу вам рассказать про задачу, которая долгое время была проблемой для многих наших студентов. В том числе расскажу про несколько вариантов решения и о том, как их можно доработать.

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