Вступление

Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?

Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).

29 июля в Минске прошёл финальный раунд чемпионата по программированию Яндекс.Алгоритм. Победителем стал Егор EgorK Куликов — выпускник мехмата МГУ и бывший сотрудник Яндекса. Второе место — у Николы Йокича из Швейцарской высшей технической школы Цюриха. В составе команды школы он был финалистом ACM ICPC. Третье место занял Макото Соэдзима, выпускник Университета Токио. Геннадий Короткевич, победитель двух предыдущих Алгоритмов, занял шестое место.

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

В этом году мы получили на четверть больше заявок на участие в Алгоритме, чем год назад, — 4578. Среди участников пока немного девушек — 372. В списке зарегистрировавшихся есть представители 70 стран; больше всего соревнующихся — из России, Индии, Украины, Беларуси, Казахстана, США и Китая. В финале приняли участие 25 человек.

Задачи для Яндекс.Алгоритма составляют сотрудники Яндекса и приглашённые эксперты, среди которых — финалисты и призёры ACM ICPC. По условиям состязания, участники могут использовать разные языки программирования. Статистика Яндекс.Алгоритма показывает, что самый популярный язык — С++; его выбрали более двух тысяч человек. Второе место поделили Python и Java.

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

Некоторое время назад (о, боже, уже год прошёл!) на вопрос, будет ли кому-то интересен обзор по современным методам сегментации изображения страницы документа, я получил положительный ответ (от massimus). И сегодня наконец-то решил этот обзор сделать.

Но для начала – маленькое отступление. Систему распознавания текста в наших продуктах можно описать очень просто. У нас есть страница с текстом, мы разбираем ее на текстовые блоки, затем блоки разбираем на отдельные строчки, строчки на слова, слова на буквы, буквы распознаем, дальше по цепочке собираем все обратно в текст страницы. Задача сегментации ставится примерно так: есть страница, надо её декомпозировать на текстовые и нетекстовые элементы.

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

На странице есть текст и картинки. Требуется разбить на блоки текст и выделить картинки.

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

Системы поддержки принятия решений сейчас набирают обороты. Причем я не буду особо останавливаться на перечислении способов реализации. Оговорюсь только об основных свойствах. Я бы очень упрощенно и обобщенно назвал эти системы вероятностными. То есть они выдают рекомендации с известной долей вероятности используя накопленную и проанализированную статистику. Не скажу что это плохо. Тема BigData и Machine learning нынче в тренде. Так же эти системы работают по принципу черного ящика. Поэтому проверить достоверность работы заложенной модели не всегда можно выявить.

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

Как правило, статьи о кешировании начинаются за здравие, а заканчиваются LRU кешем. Попробуем переломить эту тенденцию? Начнем с того, чем LRU плох, а закончим за здравие. Я надеюсь.

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

Существует масса способов информационного сокрытия одних данных внутри других данных. Самое частое, что обычно вспоминают – это стеганографию в изображениях, аудио и видео информации.

Однако контейнеры этим не исчерпываются. Совместно с двумя разгильдяями очень талантливыми студентами (а именно с lancerx и с PavelBatusov) мы решили разработать простенький just4fun-проектик информационного сокрытия в электронных документах.

Ссылка на то, что получилось (не судите строго): pdf.stego.su
(примеры PDF можно взять здесь)

Интерфейс довольного пользователя представлен на кавайной картинке:

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

Исходное состояние – я руководил службой внедрения и сопровождения в частной медицинской компании. Филиальная сеть отделений в регионах, которая работает под управлением единой системы. Так же используется схожее оборудование на всех объектах. Фактически все оборудование подключено в систему и отдает данные (диализные аппараты, лабораторные анализаторы, аппараты УЗИ и кардиографы, измерители веса и давления, водоподготовка, система вентиляции, датчики температуры и влажности).

Сеть отделений постоянно расширяется. В каждом отделении есть ИТ-специалист. Далеко не всегда этот специалист компетентен в различных областях. Задача стояла достаточно масштабная по обеспечению работоспособности довольно сложной с точки реализации системы.

/ фото yuan2003 CC

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

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

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

UPD: 8 января 2017 статья переписана. теперь она понятнее и носит более общий характер, без углубления в одну из моделей понятия

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

Здравствуй, Хабр!

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

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



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

Введение

Издавна графические ускорители (ГПУ) были созданы для обработки изображения и видео. В какой то момент ГПУ стали использоваться для вычислений общего назначения. Но развитие центральных процессоров тоже не стояло на месте: компания Intel ведет активные разработки в сторону развития векторных расширений (AVX256, AVX512, AVX1024). В итоге, появляются разные процессоры — Core, Xeon, Xeon Phi. Обработку изображений можно отнести к такому классу алгоритмов, которые легко векторизуются.
Но как показывает практика, несмотря на довольно высокий уровень компиляторов и технологичность центральных процессоров и сопроцессоров Xeon Phi, сделать обработку изображения с использованием векторных инструкций не так просто, так как современные компиляторы плохо справляются с автоматической векторизацией, а использовать векторные intrinsic функции достаточно трудоемко. Также возникает вопрос о совмещении векторизованного вручную кода и скалярных участков.

Be my friend by oosDesign

Перед крупными интернет-компаниями часто встают такие сложные задачи, как обработка больших данных и анализ графов социальных сетей. Помогают в их решении фреймворки, но сперва необходимо проанализировать возможные варианты и выбрать подходящий. В лаборатории при Техносфере Mail.Ru мы изучаем эти вопросы на реальных примерах из проектов Mail.Ru Group (myTarget, Поиск Mail.Ru, Антиспам). Задачи могут быть как сугубо практические, так и с исследовательской составляющей. По мотивам одной из таких задач и появилась эта статья.

Во время сборки и запуска своего первого проекта на Giraph сотрудники лаборатории анализа данных Техносферы Mail.Ru столкнулись с рядом проблем, в связи с чем родилась идея написать краткий туториал, как же собрать и запустить свой первый Giraph-проект.

В этой статье мы расскажем, как создавать свои приложения под фреймворк Giraph, который является надстройкой над популярной системой обработки данных Hadoop.

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

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

Почему этот простой с виду алгоритм работает корректно?

Давным-давно посетила меня идея создать синтезатор речи с «голосом робота», как, например, в песне Die Roboter группы Kraftwerk. Поиски информации по «голосу робота» привели к историческому факту, что подобное звучание синтетической речи характерно для вокодеров, которые используются для сжатия речи (2400 — 9600 бит/c). Голос человека, синтезированный вокодером, отдает металлическим звучанием и становится похожим на тот самый «голос робота». Музыкантам понравился данный эффект искажения речи, и они стали активно его использовать в своем творчестве.

Недавно в финском городе Оулу завершилась встреча международной рабочей группы WG21 по стандартизации C++, в которой впервые официально участвовали сотрудники Яндекса. На ней утвердили черновой вариант C++17 со множеством новых классов, методов и полезных нововведений языка.



Во время поездки мы обедали с Бьярне Строуструпом, катались в лифте с Гербом Саттером, жали руку Беману Дейвсу, выходили «подышать воздухом» с Винцентом Боте, обсуждали онлайн-игры с Гором Нишановым, были на приёме в мэрии Оулу и общались с мэром. А ещё мы вместе со всеми с 8:30 до 17:30 работали над новым стандартом C++, зачастую собираясь в 20:00, чтобы ещё четыре часика поработать и успеть добавить пару хороших вещей.

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

Введение

При решении задач моделирования движения объектов в трехмерном пространстве практически всегда требуется использование операций пространственных преобразований, связанных с умножением матриц преобразований и векторов. Для задачи N тел эта операция используется многократно для задания поворота и смещения тела относительно начала координат. Матрица пространственного преобразования имеет размерность 4х4, а размерность вектора, к которому применяется преобразование, соответственно 4x1. Рассмотрим оптимизацию выполнения такой операции с большим числом матриц и векторов под архитектуру Intel® Xeon Phi™.

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

Продолжение цикла статей о физике в играх про Соника. В этом посте рассматриваются потеря колец и нахождение под водой.