Рубрика «Алгоритмы» - 64

image

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

Нобелевская премия

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

Я прошу прощения у экономистов в этом зале, я популярно изложу основы теории общего равновесия за 20 минут.

1950

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

Вступление

Мне кажется, что нам надо использовать меньше тригонометрии в компьютерной графике. Хорошее понимание проекций, отражений и векторных операций (как в истинном значении скалярного (dot) и векторного (cross) произведений векторов) обычно приходит с растущим чувством беспокойства при использованием тригонометрии. Точнее, я считаю, что тригонометрия хороша для ввода данных в алгоритм (для понятия углов это интуитивно понятный способ измерения ориентации), я чувствую, что что-то не так, когда вижу тригонометрию, находящуюся в глубинах какого-нибудь алгоритма 3D-рендеринга. На самом деле, я думаю, что где-то умирает котенок, когда туда закрадывается тригонометрия. И я не так беспокоюсь о скорости или точности, но с концептуальной элегантностью я считаю… Сейчас объясню.
Читать полностью »

При слове «криптография» некоторые вспоминают свой пароль WiFi, зелёный замочек рядом с адресом любимого сайта и то, как трудно залезть в чужую почту. Другие вспоминают череду уязвимостей последних лет с говорящими аббревиатурами (DROWN, FREAK, POODLE...), стильными логотипами и предупреждением срочно обновить браузер.

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

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

В этой статье рассмотрим "Алгоритм X" Кнута и его применение для решения судоку. Прелесть алгоритма в том, что судоку при этом решается быстро без программирования каких-то продвинутых техник решения.

Читать полностью »

Сбалансированные двоичные деревья поиска: реализация на Julia - 1
Иллюстрация из работы Г.М. Адельсон-Вельского и Е.М. Ландиса 1962 года

Деревья поиска — это структуры данных для упорядоченного хранения и простого поиска элементов. Широко применяются двоичные деревья поиска, в которых у каждого узла есть только два потомка. В этой статье рассмотрим два метода организации двоичных деревьев поиска: алгоритм Адельсон-Вельского и Ландиса (АВЛ-деревья) и ослабленные АВЛ-деревья (WAVL-деревья).

Читать полностью »

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

Как мы внедрили ML в приложение с почти 50 миллионами пользователей. Опыт Сбера - 1
Дизайн главного экрана мобильного приложения с рекомендациями

У нас было 2 сотни тысяч возможных вариантов платежей, 55 миллионов клиентов, 5 различных банковских источников, полсолонки разработчиков и гора банковской активности, алгоритмов и всего такого, всех цветов, а ещё литр рандомных сидов, ящик гиперпараметров, пол-литра поправочных коэффициентов и две дюжины библиотек. Не то чтобы это всё было нужно в работе, но раз начал улучшать жизнь клиентов, то иди в своём увлечении до конца. Под катом история о сражении за UX, о правильной постановке задачи, о борьбе с размерностью данных, о вкладе в open-source и наших результатах.

Читать полностью »

Этим постом я открываю серию, где мы с коллегами расскажем, как используется ML у нас в Поиске Mail.ru. Сегодня я объясню, как устроено ранжирование и как мы используем информацию о взаимодействии пользователей с нашей поисковой системой, чтобы сделать поисковик лучше.

Задача ранжирования

Что подразумевается под задачей ранжирования? Представим, что в обучающей выборке есть какое-то множество запросов, для которых известен порядок документов по релевантности. Например, вы знаете, какой документ самый релевантный, какой второй по релевантности и т.д. И вам нужно восстановить такой порядок для всей генеральной совокупности. То есть для всех запросов из генеральной совокупности на первое место поставить самый релевантный документ, а на последнее — самый нерелевантный.

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

Активное обучение ранжированию - 1

Читать полностью »

Раньше облака в играх рисовались обычными 2D спрайтами, которые всегда повернуты в направлении камеры, но последние годы новые модели видеокарт позволяют рисовать физически корректные облака без заметных потерь в производительности. Считается, что объемные облака в игры принесла студия Guerrilla Games вместе с игрой Horizon Zero Dawn. Конечно, такие облака умели рендерить и раньше, но студия сформировала что-то вроде промышленного стандарта на исходные ресурсы и используемые алгоритмы, и в настоящее время любая реализация объемных облаков так или иначе этому стандарту соответствует.

Реализация физически корректных объемных облаков как в игре Horizon Zero Dawn - 1
Читать полностью »

Новый метод кластерного анализа - 1
В работе предлагается новый метод кластерного анализа. Его преимущество в менее сложном с вычислительной точки зрения алгоритме. Метод основан на расчете голосов за то, что пара объектов находится в одном классе из информации о значении отдельных координат.
Читать полностью »

Домашний ПК с 32 ГБ RAM за четыре месяца решил кубик Рубика 32768×32768×32768 - 1

У обычного кубика Рубика по девять цветных плиток с каждой стороны. Алгоритм решения включает всего семь действий. Мировой рекорд по сборке кубика человеком двумя руками составляет 3,47 секунды, среднее по пяти попыткам — 5,69 с, а робот делает это за 0,38 секунды (если кубик не разлетается на составные части, что частенько случалось из-за скорости).

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js