Все потоки
Поиск
Написать публикацию
Обновить
165.8

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Конкурс по программированию на JS: Классификатор слов (окончательные результаты)

Время на прочтение1 мин
Количество просмотров9.1K
Сегодня мы публикуем окончательные результаты конкурса по программированию и награждаем победителей.

По случайности, все трое призёров предпочли участвовать под псевдонимами. Мне кажется, с такими результатами им нечего стесняться. Если вы хотите представиться в комментариях, милости просим!

Итак, призовые места заняли:
  1. Antelle — 83.67% правильных ответов. Приз 3000 USD.
  2. SHB — 83.11% правильных ответов. Приз 2000 USD.
  3. chianti — 83.00% правильных ответов. Приз 1000 USD.

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

Полную таблицу результатов смотрите в английской версии на GitHub.

Распутывая историю Ады Лавлейс (первого программиста в истории)

Время на прочтение43 мин
Количество просмотров85K

Перевод поста Стивена Вольфрама "Untangling the Tale of Ada Lovelace".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации.

Содержание


Ранние годы Ады
Чарльз Бэббидж
Уровень развития этой области
Возвращаемся к Аде
Возвращаясь к Бэббиджу
Статья Ады
После статьи
После смерти Ады
Что стало с Бэббиджем?
Повторное открытие
О чем на самом деле писала Ада
Вычисление чисел Бернулли
Бэббидж vs. Ада?
Секретный ингредиент Бэббиджа
В большем масштабе
А что, если...
Какими они были?
Заключение
Ада Лавлейс родилась 200 лет назад. Для некоторых она является знаменательной фигурой в истории вычислительной техники; для других — изрядно переоцененной личностью. В течение долгого времени я пытался разобраться, как всё было на самом деле. И вот, к её двухсотлетию, я решил разобраться в том, что называл для себя "тайной Ады".

Получилось намного сложнее, чем я ожидал. Историки расходятся во мнениях. Личности в истории сложно изучать. Технологии трудно понять. Вся история переплетается с обычаями 19-го века британского высшего общества. И есть удивительное количество ошибочных сведений и неверных трактовок.

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

Это сложная история, и чтобы в ней разобраться, нужно будет о многом рассказать.
Подробнее об Аде Лавлейс...

ComputerVision (Ruby & OpenCV)

Время на прочтение9 мин
Количество просмотров14K

Автор: Людмила Дежкина, Senior Full Stack developer

OpenCV — известная библиотека компьютерного зрения широкого назначения с открытым исходным кодом. Я расскажу, что можно делать с помощью OpenCV, как работает библиотека, как ее использовать на Ruby. Я успела поучаствовать в двух проектах, где она применялась. В обоих случаях мы использовали в конечном варианте не Ruby, но именно Ruby очень удобен на первом этапе, когда требуется создать прототип будущей системы, чтобы просто посмотреть, как OpenCV будет выполнять требуемые задачи. Если все в порядке, после этого приложение пишется с этим же алгоритмом на другом языке. А чтобы использовать OpenCV именно на Ruby, есть соответствующий гем.

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

  • интерпретация изображений;
  • калибровка камеры по эталону;
  • устранение оптических искажений;
  • определение сходства;
  • анализ перемещения объекта;
  • определение формы объекта и слежение за объектом;
  • 3D-реконструкция;
  • сегментация объекта;
  • распознавание жестов.


Сейчас OpenCV используется во многих сферах. Вот несколько интересных примеров:

  1. Google:
    1. Google self-driving car — в беспилотных автомобилях Google OpenCV используется для разработки прототипа распознавания окружающей обстановки;
      (сегодня построенная система основывается преимущественно на LIDAR — в связи с трудностями распознавания при плохом освещении)
    2. Google Glass — в этих очках 3D-реконструкция изображения построена на OpenCV;
    3. Google Mobile;

  2. Робототехника и Arduino;
  3. Промышленное производство — иногда какой-нибудь завод делает на OpenCV систему подсчета деталей или что-то вроде того.

Читать дальше →

Метрики качества ранжирования

Время на прочтение7 мин
Количество просмотров133K
В процессе подготовки задачи для вступительного испытания на летнюю школу GoTo, мы обнаружили, что на русском языке практически отсутствует качественное описание основных метрик ранжирования (задача касалась частного случая задачи ранжирования — построения рекомендательного алгоритма). Мы в E-Contenta активно используем различные метрики ранжирования, поэтому решили исправить это недоразуменее, написав эту статью.

Метрики качества ранжирования


Читать дальше →

Az.js: JavaScript-библиотека для обработки текстов на русском языке

Время на прочтение8 мин
Количество просмотров29K
Как чуден и глубок русский курлык
Генератор постов

Обработка естественного языка (natural language processing, NLP) — тема, на мой взгляд, очень интересная. Во-первых, задачи тут чисто алгоритмические: на вход принимаем совершенно примитивный объект, строчку, а извлечь пытаемся вложенный в него смысл (ну или хотя бы частичку смысла). Во-вторых, необязательно быть профессиональным лингвистом, чтобы решать эти задачи: достаточно знать родной язык на более-менее приличном уровне и любить его.

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

Бессвязность текстов в нынешней версии «Генератора» вызвана тем, что на самом деле никакого анализа он производить не умеет. Просто в одних случаях «предсказывает» продолжение предложения по собранным биграммам, а в других — заменяет в готовом предложении некоторые слова на другие, которые заканчиваются похоже. Вот и вся начинка.

Конечно, хочется сделать что-нибудь поинтереснее. Беда в том, что модные сейчас нейросети не очень-то применимы здесь: им нужно много ресурсов, большую обучающую выборку, а в браузере у пользователя соцсети всего этого нет. Поэтому я решил изучить вопрос работы с текстами с помощью алгоритмов. К сожалению, готовых инструментов для работы с русским языком на JavaScript найти не удалось, и я решил сделать свой маленький велосипед.
Читать дальше →

2-3-дерево. Наивная реализация

Время на прочтение15 мин
Количество просмотров66K
Недавно мне понадобилось написать 2-3-дерево и я начал искать информацию в русскоязычном интернете. К сожалению, ни на хабре, ни на других ресурсах я не смог найти достаточно полную информацию на русском языке. На всех ресурсах было одно и то же: свойства дерева, как вставляются ключи в дерево, поиск в дереве и иногда простой пример, как удаляется ключ из дерева; не было реализации.

Поэтому, после того, как я сделал то, что мне нужно, решил написать данную статью. Думаю, кому-нибудь будет полезна в образовательных целях, так как на практике обычно реализуют эквивалент 2-3- и 2-3-4-деревьев — красно-черное дерево.
Читать дальше →

Подключение MATLAB к Wolfram Mathematica

Время на прочтение7 мин
Количество просмотров7.6K


Вызов MATLAB из Mathematica с помощью MATLink


Как можно вызывать функции MATLAB напрямую из Mathematica и организовать обмен данными и переменными между двумя системами?

Для этого существует кроссплатформенный пакет под названием MATLink. С помощью него легко организовать вызов функций MATLAB прямо из Mathematica и передавать различные данные от одной системы другой.
Читать дальше →

Алгоритм расчёта вещественных корней полиномов

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

А теперь по порядку.
Читать дальше →

Генерирование паролей к играм Road Rash 1 и 2

Время на прочтение7 мин
Количество просмотров13K
Недавно я увидел на Хабрахабре пост про Road Rash и мне стало интересно: «А как устроена система паролей в двух других частях?». Своими наблюдениями и результатом я хотел бы поделиться с вами в этой статье.

image

Первый Road Rash


Теория

Пароль состоит из 20 позиций, каждая позиция состоит из 5 битов, итого 20*5= 100 битов. Эти биты сохраняют данные игровые параметры:
  • номер занятого места (0-15) на пяти разных трассах (0 означает, что на этой трассе ты ещё не ездил).
  • количество очков (0-10485750)
  • количество денег ((-83886070)-83886070)
  • текущий уровень (1-5)
  • мотоцикл (1-8)

Теперь посмотрим из чего состоит сырой пароль:
Читать дальше →

Machine Learning Boot Camp — как это было и как это будет

Время на прочтение9 мин
Количество просмотров11K


13 июня стартовал ML Boot Camp — состязание по машинному обучению от Mail.Ru Group. В связи с этим мы хотим поделиться с вами впечатлениями о его предыдущем запуске, историями успеха победителей и рассказываем, что нового ждет участников в этом году.
Читать дальше →

Человек не нужен: 30+ материалов об алгоритмической торговле и разработке финансового софта

Время на прочтение2 мин
Количество просмотров15K


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

Школа Данных «Билайн», без перерыва на лето

Время на прочтение1 мин
Количество просмотров2.9K


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

Отзывы по нашим предыдущим курсам можно почитать здесь.

К нам часто поступают вопросы касательно того, как подготовиться к нашему курсу, где изучить Python или математику.

Специально для тех, кто хотел бы развиваться в направлении анализа данных, но чувствует потребность подтянуть знания по математике или программированию мы запустили наш новый курс: Введение в Data Science.
Читать дальше →

Конкурс по программированию на JS: Классификатор слов (предварительные результаты)

Время на прочтение2 мин
Количество просмотров9.9K
Спасибо за ожидание! Публикуем предварительные результаты конкурса по программированию.

Протестировано 312 решений, из них 50 упало или зависло, ещё 3 оказались слишком медленными, чтобы пройти все тесты. Из оставшихся 259 решений 12 по разным причинам были объявлены «вне конкурса»: решения не работали без поправки типа файла данных (авторы забыли галочку «gzip») или были присланы сотрудниками Hola.

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

Решение победителя конкурса показало результат в 83.67% правильных ответов. Полные списки решений с результатами тестирования находятся в английской версии поста на GitHub.

Там же мы публикуем «сырые» машиночитаемые результаты тестирования каждого из решений, где разнообразной информации больше, чем в сводных таблицах. На основе этих данных Вы можете провести собственный анализ результатов, чему мы будем очень рады.
Читать дальше →

Ближайшие события

RDS, как это работает? Опускаемся на самый нижний уровень модели OSI

Время на прочтение6 мин
Количество просмотров122K
С системой RDS (Radio Data System) сталкивался хоть раз каждый, кто видел в автомагнитоле название станции вроде «Дорожное радио». Помимо названия, могут отображаться дополнительные данные — название воспроизводимой песни, температура, частота вещания и т.д.


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

Продолжение под катом (осторожно много картинок).
Читать дальше →

Теория графов в Игре Престолов

Время на прочтение19 мин
Количество просмотров66K


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

Всем кому интересно, добро пожаловать под кат.
Читать дальше →

Конкурс по программированию на JS: Классификатор слов (о ходе тестирования)

Время на прочтение7 мин
Количество просмотров13K
Прежде всего, мы приносим всем участникам конкурса по программированию извинения за задержку с результатами. Сегодня мы публикуем все присланные решения и официальные скрипты для генерации тестов и тестирования, а также рассказываем, как идут дела с проверкой решений.

Английская версия этого поста размещена на GitHub.

Протестировать 312 решений


Большое спасибо всем участникам! Мы получили 603 решения от 312 участников. Поскольку мы принимаем к тестированию самое последнее из присланных в срок решений, то протестировать надо 312 решений. Это был неожиданный результат. Надеюсь, это немного объясняет, почему это занимает так много времени.
Читать дальше →

О трехмерном Z-order замолвите слово

Время на прочтение9 мин
Количество просмотров8.4K

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

Вы спросите: «Кому вообще интересны эти небесные объекты?» и даже: «Ну и при чём здесь 2ГИС?» и будете отчасти правы. Ведь методы пространственного индексирования являются универсальной ценностью.

Обычно, имея дело с геоданными, мы работаем с локальной проекцией на плоскость и тем самым отмахиваемся от искажений. В масштабах планеты это сделать труднее — начинают выпирать астрономические проблемы.
Что касается объёмов данных, уже сейчас в OSM более 4 млрд точек и 300 млн дорог. Это соизмеримо с масштабами, характерными для звёздных объектов. Да и помимо всего прочего, звёздные атласы — отличный стенд для разработки и отладки пространственных алгоритмов.

Обещанные тонкости и выводы под катом.
Читать дальше →

xfcRS — оригинальный лаконичный шустрый рендер сглаженных тайлов, «expansion fast cell — Rounded Squares»

Время на прочтение13 мин
Количество просмотров4.4K
image

xfcRS — многофункциональный быстрый алгоритм, для тайлового рендера с гладкими переходами / для построения изоповерхности / для выделения края в растре / для постпроцессинга как пиксельный шейдер — для пиксельарт масштабирования 8х8 (для быстрой растеризации шрифтов, иной материал для upscale'инга без доработок не рекомендуется). Расшифровка акронима — «eXpansion Fast Cell — Rounded Squares»

В данной статье мы будем рассматривать его преимущественно в контексте рендера сглаженных тайлов:

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

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

— Marshing Squares – алгоритм генерации изолиний на двумерном скалярном поле. см. ru.wikipedia.org/wiki/Marching_squares
— Изолиния — Условная линия служащая для приближенного отражения положения точной.
— Апроксимация — Приближенное значение чего либо точного.


Забегая вперед, скажу сразу: это не улучшенный Marshing Squares,
Читать дальше →

На Amazon идёт война алгоритмов за позицию «лучшего» товара

Время на прочтение3 мин
Количество просмотров24K

В 2011 году два алгоритма, оставленные без присмотра, подняли цену книги до 23 миллионов долларов

Amazon начал как книжный магазин в 1994 году, но к настоящему времени превратился в настоящего монстра интернет-торговли. На площадке продаётся что угодно. Самое удобное — там можно сравнить цены разных продавцов и выбрать наиболее подходящее предложение. Более того, алгоритм Amazon выполняет такое сравнение за нас и находит «оптимальное предложение» (“Buy Box”), остаётся только нажать кнопку «Добавить в корзину».

Никто не знает, как работает алгоритм Amazon: формула включает в себя не только цену, но и количество положительных отзывов, и что-то ещё. Проблема в том, что торговцы активно манипулируют алгоритмом Amazon, чтобы попасть в заветный “Buy Box”. Причём задача торговца — не только попасть на оптимальную позицию, но и продать товар по максимально возможной цене, не теряя позицию. Наблюдать за битвой торговых ботов на Amazon с постоянными рывками цен весьма забавно: такое исследование провели специалисты из Северо-Восточного университета (США), pdf.
Читать дальше →

Фонтанные коды

Время на прочтение7 мин
Количество просмотров20K
Сегодня поговорим о фонтанных кодах. Их ещё называют «кодами нефиксированной скорости». Фонтанный код позволяет взять, например, какой-нибудь файл, и преобразовать его в практически неограниченное количество закодированных блоков. Имея некоторое подмножество этих блоков, можно восстановить исходный файл, при условии, что размер этого подмножества немного превышает размер файла. Другими словами, такой код позволяет создавать «фонтан» из кодируемых данных. Получатель может восстановить исходные данные, собрав достаточно «капель» из фонтана, при этом неважно – какие именно «капли» у него есть, и какие именно он пропустил.


Замечательное свойство фонтанных кодов заключается в том, что их применение позволяет отправлять данные по ненадёжным каналам связи, например – через интернет, не полагаясь на знание уровня потери пакетов, и не требуя от получателя связываться с отправителем для восстановления недостающих фрагментов данных. Легко заметить, что подобные возможности окажутся весьма кстати во множестве ситуаций. Среди них, например, отправка информации по широковещательным каналам связи, как в системах передачи видео по запросу. К той же категории задач относится работа протокола Bittorrent и других подобных, когда фрагменты файла распространяются среди большого количества пиров.
Читать дальше →

Вклад авторов