Алгоритмы *

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

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

Привет, Хабр! Хочу рассказать о том, как я решал задачу связанную с обработкой и визуализацией томографических изображений, а именно — измерение и поиск кратчайшей траектории на поверхности 3D изображения. Одна из областей применения — измерение антропометрических данных на КТ/МРТ исследованиях.

Всем привет. Меня зовут Артур. Готовясь к выступлению на внутреннем митапе по теме особенности алгоритмов у CatBoost и LightGBM, я понял, что не смог найти единого места, где были бы понятным языком рассказаны основные особенности того, что алгоритмически работает под капотом у CatBoost и LightGBM. Причём не формальные записи алгоритмов на псевдокоде, а понятные пошаговые инструкции. Так появилась эта статья.

Квантовые компьютеры. С точки зрения традиционного программиста-математика.
Часть 1. Основы. Квантовый регистр.

О чем эта публикация

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

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

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

Недавно закончилось соревнование от американской национальной футбольной лиги (NFL), которая объединилась с AWS, чтобы прокачать системы спортивной видеоаналитики.

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

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

С логикой тесно связана разработанная сравнительно недавно алгебра кортежей (АК). Здесь будет показано, как с ее помощью решаются непростые логические задачи, а также обоснована связь между АК и семантикой. Более подробные сведения по теме данной статьи можно найти на сайте.

В основе АК лежат свойства Декартова (прямого) произведения множеств (ДП). Многие из этих свойств были впервые сформулированы и обоснованы в публикациях по АК. Для более понятного изложения свойств ДП и основных понятий АК будем использовать в качестве иллюстрации ПРИМЕР логической задачи.

ПРИМЕР

В данном ПРИМЕРе используются сюжеты некоторых задач из книги известного специалиста и популяризатора математической логики Раймонда Смаллиана «Принцесса или тигр?». В некотором царстве король заставлял узников решать логические задачи. В данном эпизоде (он отсутствует в книге Смаллиана) перед узником были три комнаты, в каждой из которых могла находиться одна из принцесс, либо поджидал свою добычу один из тигров. Могли быть и пустые комнаты. С помощью подсказок узник должен был решить, в какой комнате принцесса, и войти в нее. В этом случае он получал свободу и мог жениться на принцессе. Если он ошибался, то мог попасть в комнату с тигром. В данном случае в помощь ему были даны три подсказки, и также было известно, что одна из первых двух подсказок ложная (какая именно, неизвестно), а остальные две – истинные.

Подсказка 1: Во второй комнате нет тигра, а третья комната не пуста.

Подсказка 2: Первая комната не пуста, а во второй нет тигра.

Подсказка 3: Принцесса находится, по крайней мере, в одной из комнат. То же самое известно и о тиграх.

Патент RU_2676949_C2 со скромным названием «Система и способ определения дохода пользователя мобильного устройства» компании ООО ЯНДЕКС (RU) действует с  пятого апреля 2017 года. А вместе с патентом RU 2 637 431 C2 «Способ и система определения оптимального значения параметра аукциона для цифрового объекта» это дает возможность для персонального, ситуационного и точечного ценообразования, например на услуги такси. Не документальное ли это подтверждение возможности компании для топ-менеджера с последним iPhone ставить ценник дороже, чем для дизайнера с Xiaomi на идентичный по гео и времени заказ? «Вот тебе, бабушка, и Юзер и Экспирианс!»?

В 2015 году математик Ласло Бабай представил свой более эффективный алгоритм, решающий задачу изоморфизма графов (Graph Isomorphism, GI) за квазиполиномиальное время. На Хабре даже есть статья, освещающая это событие. Однако в дальнейшем сам учёный признал некоторую ошибочность своего подхода, что всё равно не повлияло на отношение большинства математиков к его открытию, поскольку даже получившийся вариант, решающий задачу за субэкспоненциальное время, оказался эффективнее существующих алгоритмов. Тем не менее учёный не остановился на этом и обнаружил ошибку. Опубликованные исправления алгоритма всё-таки привели к решению задачи изоморфизма за квазиполиномиальное время.

Проблема изоморфизма графов требует алгоритмов, которые могут определить, являются ли два графа структурно идентичными. На протяжении десятилетий эта задача занимала особый статус как одна из немногих естественно возникающих задач, уровень сложности которых трудно определить. Многие годы исследователи пытались выяснить, к чему она относится. Даже сейчас неизвестно, к какому классу относится задача, а абстрактно задачу рассматривают как нечто среднее — сложнее, чем P, но легче NP. Задачу из теории графов можно обобщить до общей проблемы изоморфизма, в смежных областях математики существуют идентичные задачи, например изоморфизм конечных групп.

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

По мере развития технологий в мире появляется все больше различных технологических алгоритмов. Часть из названы в честь ученых, имеющих отношение к их разработке, другая часть имеет простые (или не очень простые) «сухие» названия или же забавные наименования, например, коктейльная сортировка (Cocktail shaker sort), в русском языке называемая просто — «сортировка перемешиванием». Сегодня поговорим про алгоритмы, названные в честь различных представителей животного мира.

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

Исследовательская команда Microsoft, вдохновлённая этими идеями, провела эксперимент, отчёт о котором — Textbooks Are All You Need — можно найти на arXiv.org. В рамках эксперимента была создана большая языковая модель для генерирования кода, названная phi-1. Обучение этой модели проводилось с использованием специально подготовленного набора данных, качество которого сопоставимо с учебниками по программированию. В результате модель phi-1, при том, что в ней используется всего 1,3 миллиарда параметров, показала результаты, превосходящие то, на что способны самые совершенные большие языковые модели.

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

Приветствуем читателей Хабра! Мы, команда дата-сайентистов и дата-аналитиков компании «ДатаЛаб»* (ГК «Автомакон»), продолжаем рассказывать о насущных проблемах ML-разработки, делимся подходами к их решению и рассуждаем на актуальные темы.

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

В этой статье я хочу представить мой алгоритм оптимизации суммирования ряда чисел в массиве (на примере контейнера map). 

Итак, дано задание

Есть некая электронная книга, которую одновременно читает неограниченное количество читателей. Нужно сделать так, чтобы любой читатель в любой момент мог проверить, сколько еще читателей читают ту же страницу, что и он. Предложена наивное решение хранить в map<int,int> в качестве ключа номера страниц, в качестве значения- количество прочитавших их пользователей. Конечно, при таком подходе программа медленно работает с большими тестами потому, что количество итераций по контейнеру map равняется числу прочитанных пользователем страниц. То есть, если пользователь прочел 1000 страниц из 1000 возможных, то в цикле нужно будет сделать 1000 итераций, и это сильно замедляет программу.  

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

 Это вкратце, теперь перейдем к подробному описанию и для начала приведу код.

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

Должно быть, всем уже известно, что в Smart Engines мы, в частности, занимаемся разработкой томографического программного обеспечения. Чтобы заглянуть внутрь окружающих нас вещей и увидеть чуть больше и чуть точнее, чем дозволено человеческому глазу, мы работаем над совершенствованием алгоритмов реконструкции внутренней структуры объектов. Путь восстановления внутренности объекта тернист: часто томограф, на котором производятся измерения, неидеален, и получаемое изображение внутренности объекта имеет очевидные искажения, двоения, размытия, так называемые артефакты реконструкции объекта. Обнаруженные артефакты реконструкции мешают исследователю в изучении внутренности объекта, их наличие иногда “толкает” исследователя на неверные умозаключения. В связи с этим с артефактами реконструкции нужно бороться. В зоопарке артефактов томографической реконструкции в особом вольере обитают артефакты, возникающие от неверного определения положения оси, вокруг которой вращается объект в процессе сканирования или же вокруг которой обращается источник излучения, если объект неподвижен. Так что же это за звери такие - артефакты оси вращения? Об этих сущностях и методах их укрощения и пойдет речь в нашей сегодняшней статье. 

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

В данной статье разобран алгоритм монотонной кубической интерполяции, предложенный Фритчем и Карлосоном в работе [1].

На рисунке красным обозначен результат обычной кубической интерполяции Эрмита, а синим - монотонной, кругами - опорные точки траектории.

Примеры кода написаны на C++, исходники всей библиотеки лежат здесь. Также написана копия библиотеки на Java, исходники лежат здесь.

Привет, Хабр! Легендарная команда прогнозирования промо сети магазинов «Магнит» снова в эфире. Ранее мы успели рассказать о целях и задачах, которые мы решаем: «Магнитная аномалия: как предсказать продажи промо в ритейле», а также поделиться основными трудностями, с которыми приходится сталкиваться в нашем опасном бизнесе: «Божественная комедия», или Девять кругов прогнозирования промо в «Магните».

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

Рекомендательные системы стали неотъемлемой частью современного ритейла. Они помогают покупателям найти интересующие их товары и услуги, а также предсказывают, что они могут приобрести в будущем на основе их предыдущих покупок. Эти системы играют важную роль в улучшении пользовательского опыта, увеличении конверсии и повышении доходности компаний. В этой статье мы, команда «ДатаЛаб»* (ГК «Автомакон»), рассмотрим, как настроить рекомендательную систему для точного прогнозирования покупок на основе опыта покупателей, исследования закономерностей в покупках и других факторов.

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