Алгоритмы *

Мы потратили семь лет на эксперименты с ИИ для царской игры Ура, и, наконец, пришли к сильному решению по правилам Финкеля, Блица и Мастерса! В конечном итоге, для этого понадобилась пара красивых уравнений, которые я объясню в статье.

На самом деле, мы не «просто» нашли сильное решение игры. Для сильного решения необходимо находить наилучший ход из каждой позиции. Мы сделали это, плюс вычислили точную вероятность победы каждого игрока при оптимальной игре из каждой позиции. Для этого мы воспользовались нашей опенсорсной библиотекой RoyalUr-Java.

Ниже мы опишем, как это работает. Также мы написали технический отчёт.

Мы продолжаем рассказывать о проектах Зимней школы RISC-V, организованной YADRO. Возможно ли создать программный генератор на базе открытой архитектуры, используя физически неклонируемые функции (PUF) динамической памяти? Команда из БГУИР — Никита Малявко, Ксения Трубач, Михаил Кулик, Павел Шлык — в своем проекте проверила гипотезу о наличии PUF в динамической памяти и создала модель одноканального источника шума. Затем реализовала постобработку и тестирование, измерила производительность генератора и оптимизировала код.

Константин Шибков (на Хабре sendelust)  —  эксперт Skillbox и Java-разработчик, который искренне любит собеседования. Не только проходить их сам, но и обсуждать чужие. Он расспрашивает знакомых, какие им попались задачи, а потом разбирает их вместе с участниками своего алгоритмического клуба JavaKeyFrame. Ведёт телеграм-канал «Три монитора», где делится личным опытом. Мы поговорили с Константином о том, почему техническое интервью — это не пытка, а интеллектуальное удовольствие, как проводить собесы по-человечески, зачем нужны задачки «на подумать» и почему иногда лучше не отвечать сходу, а сначала задать встречный вопрос.

— Слушай, а что тебе вообще в этом нравится? Слушать про собесы, разбирать задачи, самому ходить. В чём кайф?

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

— А есть примеры самых необычных заданий, которые тебе или участникам клуба попадались? Что прям запомнилось?

— Честно говоря, чего-то супернеобычного, наверное, не вспомню. Больше всего удивляет, когда... вообще ничего нет. Вот человек рассказывает: «Пришёл на собес, они такие — пойдём пообедаем. Сходили в кафешку, поболтали». И всё. Никаких задач, ничего. Вот это реально выбивает.

А вот когда дают задачи сложные или вообще непонятные, зачем они нужны — это уже другое удивление. Такое, скорее, отрицательное. Типа: «Ну и зачем это всё было? Зачем я сюда пришёл? Какой в этом смысл?» Такое чувство пустой траты времени.

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

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

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

Дональд Кнут (с)

Как известно, на машине Тьюринга (далее МТ) запрограммировать можно всё, что мы вообще считаем программируемым, но в реальности программы на МТ настолько громоздкие, что МТ редко используется даже в академических примерах. И тем не менее в некоторых отдельных случаях с помощью МТ получается написать небольшую программу, на КДПВ изображена программа из 5 состояний на алфавите из 3 символом. Если вы изучали программирование, то задачу, которую решает эта программа, вы скорее всего встречали. Если я сумел вас заинтересовать, то приглашаю в небольшое приключение по реверс инженирингу МТ.

Материал статьи предоставлен Владимиром Пинаевым

Содержание текста статьи у некоторых читателей Хабра вызвало определенный интерес (судя по комментариям). Что в общем-то не удивительно, так как тема статьи весьма актуальная для современного общества – информационная безопасность. Специалисты проявляют интерес и активно разрабатывают тему с момента открытия двухключевой криптографии и односторонних функций (около 50 лет).

На самом деле проблема гораздо шире границ предметной области – информационная безопасность, что можно понять уже из рассмотрения частной задачи – факторизации числа. Математики в разных частях и странах мира на протяжении многих тысячелетий пытаются решить задачу разложения большого числа (ЗРБЧ) на множители – найти операцию обратную умножению, но до сих пор без особого успеха. Числа с разрядностью нескольких сотен пока разложить на множители не удается. 

Известно несколько подходов к решению проблемы (алгоритм Ферма, числовое решето, эллиптические кривые, CFRAC, CLASNO, SQUFOF, Вильямса, Шенкса и др.), которые критикуются и не кажутся перспективными и которые даже не претендуют на универсальность. Автором публикации предлагается оригинальный подход к решению проблемы с претензией на универсальность, т.е. без каких либо ограничений на факторизуемые числа, в частности, ограничений на разрядность чисел.

Появилась уверенность, что по крайней мере читатели domix 32; wataru; Naf2000 понимают, что в моих статьях идет речь о модели, так как вопросы задаются осмысленные.
Здесь важно понимать в рамках какой модели числа разрабатывается алгоритм поиска делителей (сомножителей) заданного составного числа, допущения, ограничения, требования и другие условия модели. Понимать какое влияние они оказывают на характеристики, в частности, на длительность процесса поиска решения.

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

Хабр привет!

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

Давайте определим из чего у нас будет состоять наш гибрид (как можно понять из названия) - это:

1) Обычный проход градиентного спуска ...

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

Я хотел сканер, который понимает. Сканер, который учится. Сканер, который адаптируется.

Так начался проект AI-Scanner — не как плагин к существующему решению, а как попытка вырастить нечто живое: обучаемую систему, способную эволюционировать, предсказывать, ошибаться и исправляться.

Меня зовут Дмитрий Ольшанский, я ведущий инженер Т-Банка. Расскажу о новом (насколько мне известно) алгоритме поиска текста по шаблону. Такая задача возникла в рамках проекта Sage — observability-платформы от Т-Банка, для которой мы строим новый бэкэнд для структурированных логов, SageDB. 

Попалась мне недавно статья Синус, косинус, квадратный корень FixedPoint. Автор размышляет как можно не затратно рассчитывать координаты и углы в микроконтроллере. Попробовал я подсказать автору пару аппроксимаций, но он оказался разговорчив только на тему "упадка автоматизации в РФ", а по делу как то не сложился диалог. Посмотрел, такие статьи не редкость. Например, очень хорошая статья Как посчитать синус быстрее всех на Xабре. В общем разгрузил себе голову на майских праздниках от главного хобби - геометрической алгебры.

В процессе изучения всего этого, возник у меня вопрос - а зачем вообще нужно аппроксимировать sin,cos, arctan и еще и в привязке к числу в двоичной системе, если есть декартовы координаты?

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

Автоматическим дифференцированием можно назвать любую конечную разность, например dy=(y(x+ε)-y(x-ε))/(2*ε). Разность взята центральная, так как она дает меньшую погрешность.

 ε это машинный ноль. За счет округления до младшего бита его главное свойство: ε^2=0.

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

Исследователи из МiT, Microsoft и Goggle создали фреймворк, который может изменить подход к разработке алгоритмов машинного обучения - I-Con (Information Contrastive Learning).

Он объединил и систематизировал более 20 классических методов ML — от кластеризации до контрастивного обучения в единую структуру, напоминающую периодическую таблицу. Как и ее химический прародитель, эта таблица не только упорядочивает известные алгоритмы, но и указывает на пробелы, где могут существовать еще не открытые методы.

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

Вопросы о CLIP-моделях встречаются почти на каждом техническом собеседовании.
Неважно, занимаетесь ли вы видеоаналитикой, создаёте генеративные модели или работаете над поиском по изображениям — CLIP и его потомки (BLIP , SigLIP ) стали стандартом де-факто в задачах связи визуальных и текстовых данных. Почему? Потому что они позволяют решать задачи, которые ранее требовали значительных усилий

Всё началось невинно. Шёл 2009 год, и я просто хотел портировать Earcut на Flash - для своей мини-игры. Тогда это сработало, но с годами стало понятно: простые решения перестают работать, как только хочешь выжать из них максимум.

Алгоритм сортировочной станции (Shunting Yard) был предложен Дейкстрой ещё в 1961 году и служит для преобразования математических выражений из привычной всем инфиксной записи (где операторы стоят между операндами, как в 1 + 2 * 3) в постфиксную (обратную польскую нотацию, 1 2 3 * +), удобную для дальнейшего вычисления. Однако есть один важный момент, который почти всегда упускается или замалчивается: алгоритм предполагает, что входное выражение уже синтаксически корректно.

Ни в Википедии, ни в большинстве обучающих статей вы не встретите слов о том, что выражения вроде + (1 2, 3 * 4 + ) или sin(+) должны вызывать ошибку. В лучшем случае они просто не вычисляются (что будет понятно лишь на этапе обработки в обратной польской записи), в худшем – дают бессмысленный результат. Алгоритм продолжает работать, даже если выражение изначально некорректно – и мало кто задумывается, почему это плохо.

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

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

И так, давайте сначала разберемся что же такое зависимость?

Зависимость - это объект (или функция, в Python все - это объект), который нужен другому объекту или функции для их нормальной работы. Почти в каждого объекта есть одна или несколько зависимостей. Существует 2 основных метода их получение: создание зависимости непосредственно внутри функции либо же инъекция (внедрение).

В этой статье хочу рассказать про нерандомность модуля random в стандартной библиотеке Python. С точки зрения криптографии и математики числа, генерируемые этим модулем, случайные лишь на вид — они порождаются детерминированным алгоритмом, что делает их псевдослучайными. Рассмотрим, как устроен генератор на основе алгоритма Mersenne Twister (MT19937), почему его выходы «нерандомны» в формальном смысле и какие практические следствия это имеет.

написано для новичков и плохо посвященных в тему людей…

Теперь всё, что раньше делали люди — создание курсов, проверку ответов, адаптацию персонализированных заданий — почти полностью взял на себя ИИ.

Duolingo — это уже давно не просто приложение с разноцветными совами и скучными заданиями. В 2025-м генеративный ИИ позволил Duolingo быстро создавать новые курсы, и за год почти удвоить число языковых курсов! Как им это удалось и что это значит лично для тебя — рассказываем подробнее...