Алгоритмы *

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

(версия 2, с исправленными опечатками — надеюсь, что всеми...)

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

Сейчас вот сидел, делал для товарища прототип генетического алгоритма. Навеяло поделиться оным, да и некоторыми другими мыслями…

Дано (клиент заказал): в некоем царстве складе есть 100 ячеек. В нем товар лежит. Как взять количество Х так, чтобы опустошить все задействованные ячейки до конца? Ну то есть, есть у вас типа ячейки [34, 10, 32, 32, 33, 41, 44, 4, 28, 23, 22, 28, 29, 14, 28, 15, 38, 49, 30, 24, 18, 9, 15, 8, 17, 9, 2, 7, 30, 29, 29, 2, 28, 23, 19, 4, 15, 30, 38, 3, 14, 21, 43, 50, 29, 14, 17, 12, 25, 15, 23, 28, 47, 38, 29, 7, 36, 45, 25, 6, 25, 11, 10, 1, 19, 37, 24, 27, 50, 12, 1, 1, 44, 22, 48, 13, 46, 49, 11, 33, 29, 4, 19, 33, 12, 3, 47, 27, 26, 45, 40, 37, 21, 2, 8, 41, 5, 1, 9, 5] — как набрать, скажем, 40

Ну можно перебором, наверняка есть что-то умное, а можно генетическим алгоритмом это решить…

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

Решето Сундарама входит в тройку известнейших методов генерации простых чисел. Сейчас к нему принято относиться как к некоторой экзотике по причине плохой вычислительной сложности: O(N(logN)). Однако асимптотика – асимптотикой, а на практике в 32-битном диапазоне просеивания Аткин, например, перегоняет Сундарама только при тщательной оптимизации.

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

Хеди Ламарр

Что общего между игрой на пианино в четыре руки, торпедами и «вай-фаем» в вашем гаджете? Ответ вы найдете в этой статье.

9 ноября 2014 года, отмечалось столетие со дня рождения голливудской звезды Хеди Ламарр. Фильмы с ее участием давно стали классикой Голливуда. Но не все знают, что она была не просто актриса. Без нее мы бы сейчас вряд ли говорили по мобильному телефону, ориентировались с помощью GPS и искали, где лучше ловится Wi-Fi. Но обо всем по порядку.

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

Статья будет состоять из нескольких разделов ниже:

• Функции
• Данные
• Результаты
• Выводы

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

Допустим, нам нужно сделать модель распознавания лиц для организации, в которой работает около 500 человек. Если делать такую модель с нуля на основе свёрточной нейросети (Convolutional Neural Network (CNN)), то для обучения модели и достижения хорошей точности распознавания нам понадобится много изображений каждого из этих 500 человек. Но очевидно, что такой датасет нам не собрать, поэтому не стоит делать модель на основе CNN или иного алгоритма глубокого обучения, если у нас нет достаточного количества данных. В подобных случаях можно воспользоваться сложным алгоритмом однократного обучения, наподобие сиамской сети, которая может обучаться на меньшем количестве данных.

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



Кстати, обо мне. Меня зовут Наташа, я работаю в Skyeng на позиции Data Scientist и вовлечена в разработку различных продуктов компании. Почему я заговорила о внезапных звонках? Общение голосом с клиентам, которые только хотят начать или по какой-то причине резко прервали обучение — часть модели работы в компании. Звонки помогают вовлечь и вернуть людей в процесс изучения языка, либо напрямую узнать, что же пошло не так. Одна из моих последних задач — анализ работы нашего колл-центра. Я помогла им подобрать оптимальное время для выхода на контакт со студентами по всей России и СНГ: потому что звонки в случайное время суток никто не любит, а бесить собственных пользователей — последнее дело.

Настроение людей в ходе таких звонков для нас крайне важно, потому что оно напрямую влияет на конверсию. Так что давайте я расскажу подробнее о том, как Skyeng звонит студентам и какую прогнозную модель я построила для того, чтобы нашим клиентам было хорошо и комфортно, а мы вышли на показатели конверсии в 60-70%.

Источник

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

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

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

Ура! Мы завершили формирование программы конференции UseData Conf 2019! Эта конференция для тех, кто решает практические задачи с помощью методов машинного обучения. Между идеальным алгоритмом в вакууме и его применением на реальных данных часто лежит пропасть. Мы хотим, чтобы те, кто умеет преодолевать эту пропасть, встретились и смогли обменяться опытом.



Магия машинного обучения для управленцев, истории применения ML для анализа эффективности рекламы в телевизоре, беспилотные игрушечные машинки, нефть и автомобильные номера — это лишь часть докладов на UseData 2019. Об этих и других темах подробнее под катом.

Многие кошельки биткоина при выборе монет для отправки предпочитают использовать крупную монету, баланс которой больше отправляемой суммы. После каждой такой транзакции образуется монета-сдача. Через какое-то время весь кошелёк зарастает такими монетами порядка 0.001 (~10 долларов на текущий момент), которые уже и не на что потратить. Когда в очередной раз мне понадобилось сделать транзакцию, мне пришла в голову мысль, а нельзя ли собрать транзакцию так, чтобы сдачи не было. Кошелёк упрямо предлагал «распилить» ещё одну более крупную монету, так что я решил руками выбрать монеты, чтобы насобирать необходимую сумму. Однако это оказалось не так просто: сумма или получалась меньше нужного значения или слишком сильно его превосходила. В итоге я решил, что должен быть алгоритм, с помощью которого из монет можно собрать нужную сумму или чуть больше. Оказалось, что это не только возможно, но работает настолько хорошо, что сподвигло меня написать эту статью. Но обо всём по порядку.

В данной статье описывается процесс синтаксического анализа предложения русского языка с использованием контекстно-свободной грамматики и алгоритма LR-анализа.

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

В общем, процесс анализа предложения естественного языка выглядит следующим образом: (1) разбиение предложения на синтаксические единицы — слова и словосочетания; (2) определение грамматических параметров каждой единицы; (3) определение синтаксической связи между единицами. На выходе — абстрактное дерево разбора.

Алгоритмы – одна из центральных тем в программировании, они повсюду (особенно на собеседованиях, ха-ха).


(Разве можно обойтись в таком посте без «баяна»?)

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

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

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

Предлагаем ознакомится с отрывком «Что такое фреймворк глубокого обучения?»

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

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



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

Под катом исследуется вопрос, как должен быть устроен хороший алгоритм многомерной индексации. На удивление, вариантов не так уж и много.

Поисковые подсказки — это здорово. Как часто мы набираем полный адрес сайта в адресной строке? А название товара в интернет-магазине? Для таких коротких запросов обычно хватает ввести несколько символов, если подсказки поиска хороши. И если вы не обладаете двадцатью пальцами или неимоверной скоростью набора текста, то наверняка будете ими пользоваться.
В этой статье мы расскажем о нашем новом сервисе подсказок для поиска по вакансиям hh.ru, который мы сделали в предыдущем выпуске Школы программистов.

У старого сервиса был ряд проблем:

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

В новом сервисе мы исправили эти недостатки (параллельно добавив новые).

Итак, представим. В комнате заперты 5 котов, и чтобы пойти разбудить хозяина им необходимо всем вместе договориться между собой об этом, ведь дверь они могут открыть только впятером навалившись на неё. Если один из котов – кот Шрёдингера, а остальные коты не знают о его решении, возникает вопрос: «Как они могут это сделать?»

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

Вы задавались когда-нибудь вопросом, как в играх наподобие Super Meat Boy реализована функция реплея? Один из способов её реализации — выполнять ввод точно так же, как это делал игрок, что, в свою очередь, означает, что ввод нужно как-то хранить. Для этого и многого другого можно использовать шаблон Command.

Шаблон Command («Команда») также полезен для создания функций «Отменить» (Undo) и «Повторить» (Redo) в стратегической игре.

В этом туториале мы реализуем шаблон Command на языке C# и используем его для того, чтобы провести персонажа-бота по трёхмерному лабиринту. Из туториала вы узнаете:

• Основы шаблона Command.
• Как реализовать шаблон Command
• Как создавать очередь команд ввода и откладывать их выполнение.

Я хотел бы поделиться воспоминаниями о своих попытках сделать «3D графический движок» «своими руками» практически в до-интернетную эпоху (он как бы уже где-то там конечно был, но у меня его фактически не было). Никакую Америку открыть не удалось, революции тоже не случилось, но было много старания, мучений и фана. С годами память о многих событиях стирается, исчезают детали, тускнеют впечатления — при многочисленных переездах коробка с дискетами были потеряна и никаких артефактов от описываемых событий не осталось.

В 2012 году Нобелевскую премия по экономике выдали Ллойду Шепли и Элвину Роту. «За теорию стабильного распределения и практики устройства рынков». Алексей Савватеев в 2012 году попытался просто и понятно рассказать в чем суть заслуг математиков. Предлагаю вашему вниманию конспект видеолекции.


Сегодня будет теоретическая лекция. Про эксперименты Эла Рота, в частности с донорством, я не буду рассказывать.

Когда объявили, что Ллойд Шепли (1923-2016) получил нобелевку, был стандартный вопрос: «Как!? Он ещё жив!?!?» Самый знаменитый его результат был получен в 1953 году.

Формально, премию дали за другое. За работу 1962 года за «теорему об устойчивом бракосочетании»: «Приём в колледжи и стабильность брака» (College Admission and the Stability of Marriage).

Об устойчивом бракосочетании

Matching (мэтчинг) — задача о нахождении соответствия.

Есть некая изолированная деревня. Там «m» молодых людей и «w» девушек. Нужно их друг на друге переженить. (Не обязательно одинаковое количество, может в итоге кто-то останется один.)

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

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