Обновить
271.46

Алгоритмы *

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

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

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 и других подобных, когда фрагменты файла распространяются среди большого количества пиров.
Читать дальше →

Год с Runkeeper: Анализ и визуализация геоданных о ваших путешествиях

Время на прочтение5 мин
Охват и читатели13K

Перевод поста Bernat Espigulé-Pons "A Year of Runkeeper: Analysis and Visualization".
Код, приведенный в статье, можно скачать здесь, а дополнительные файлы здесь.
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации

Почти год назад я решил записывать все свои передвижения с помощью Runkeeper, и теперь хочу представить несколько вариантов визуализации моей годовой активности. Проект получается несложным: данные по своим передвижениям я буду подгружать из Runkeeper, а анализировать/визуализировать — в Wolfram Language. В этой анимации (см.ниже) показаны мои передвижения по Барселоне, и я покажу вам, как сделать такую же.


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

Разработка класса для работы с цепями Маркова

Время на прочтение5 мин
Охват и читатели26K
Сегодня я хотел бы поведать вам о написании класса для упрощения работы с цепями Маркова.

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

Как мы делали систему выделения информации из текста на естественном языке для банка АО «Банк ЦентрКредит» (Казахстан)

Время на прочтение5 мин
Охват и читатели13K
Некоторое время назад к нам обратился представитель банка АО «Банк ЦентрКредит» (Казахстан) с интересной задачей. Необходимо было интегрировать в конвейер обработки данных, представляющих из себя текст на естественном языке, дополнительный инструмент обработки. Всех деталей проекта мы раскрывать не можем, так как он находится в сфере безопасности банка и разрабатывается его службой безопасности. В освещении технологических аспектов задачи и способов их реализации заказчик не был против, что собственно мы и хотим сделать в рамках данной статьи.

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

Конкурс по классификации слов от Hola или «где взять ещё один процент?»

Время на прочтение4 мин
Охват и читатели5.8K
Увидел пост о конкурсе, когда прошло уже две недели после начала. Но задача показалась крайне увлекательной, и я не ошибся в этом, нырнув в решение с головой. Хочу поделиться решением на 80+% и своими впечатлениями в этом посте.

Всё моё участие прошло под вопросом «где взять ещё один процент?», но в ответ я чаще получал сотые доли процента или ничего. Итак, обо всём по порядку.
Читать дальше →

Отражение динамики в модели СКУД

Время на прочтение9 мин
Охват и читатели4.7K
В предыдущей статье рассматривалась структурная модель СКУД как совокупности ролей объектов и двойных связей между ними. Такая модель позволяет отразить результаты всех интересующих нас процессов, протекающих в системе. Процессы в системе выражаются через взаимодействия объектов, а результаты взаимодействий запоминаются в связях. Можно сказать, что связи — это память о взаимодействиях, но сами процессы взаимодействия в структурной модели никак не отражаются. Наблюдатель видит взаимодействия через изменения в поведении или изменения в состоянии объектов, которые мы будем называть устройствами. Например, при поднесении карты c RFID меткой к считывателю последний сообщает о считывании звуковым сигналом и миганием светодиода. Это может интерпретироваться как изменение состояния физического считывателя, при этом само взаимодействие между картой и считывателем, собственно чтение, не рассматривается. Предполагается, что считыватель проходит через ряд дискретных состояний. Такие дискретные состояния удобно моделировать при помощи машин состояний, но для этого нужно установить канал между физическим миром и виртуальным миром (компьютерной моделью). Такой канал, управляемый контроллером канала, передает физические сигналы от устройства, которые специальным модулем связи преобразуются в сигналы, управляющие машиной состояний устройства. Канал может быть двухсторонним:


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

Введение в продолжения и макросы на Scheme

Время на прочтение10 мин
Охват и читатели13K
Если вы не слышали о call/cc, то вам определённо стоит познакомиться с этим мощным инструментом! Поговорим о продолжении (call/cc), простой, но трудно понимаемой конструкции, обладающей огромной силой в правильных руках. Реализуем с их помощью механизм yield/next/for… in, аналогичный таковому в Python. Обернём внутренности с помощью макроса — ещё одного интересного механизма Scheme.

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

image

call-with-current-continuation

[PF] Печать PDF под .NET, векторный подход, практика

Время на прочтение13 мин
Охват и читатели6.8K

Как и обещал, продолжаю тему(раз, два) управляемой печати PDF из под .NET в векторном формате. О теоретических аспектах работы с PCL я рассказал в предыдущей статье, настало время разобрать программу для вывода на принтер PDF файла в векторе. Наше приложение будет полезно, например, когда нужно распечатать пачку многостраничных бланков или анкет на бумаге разных цветов и разной плотности. Если мы научимся управлять лотками принтера, избавим себя от ручного прокладывания страниц ;) В шаблоне будет указан номер лотка, из которого принтер заберет бумагу для текущей страницы. Причем шаблон будет применяться к документу циклически: если в документе 32 страницы, а в шаблоне 4, то шаблон повторится 8 раз для Simplex режима и 4 раза для Duplex.
Читать дальше →

Отпуск по-программистски, или как я не поучаствовал в конкурсе по программированию на JS. Часть вторая

Время на прочтение15 мин
Охват и читатели6.3K

В первой части этого описания попытки решения интересной конкурсной задачи я рассказал о подготовке данных для анализа и о нескольких экспериментах. Напомню, условие задачи заключалось в том, чтобы с наибольшей вероятностью определить наличие слова в словаре, не имея доступа к этому словарю в момент выполнения программы и с ограничением на объем программы (включая данные) в 64K.
image
Как и в прошлый раз, под катом много SQL, JS, а также нейронные сети и фильтр Блума.

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

Structure from motion

Время на прочтение10 мин
Охват и читатели21K

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

Отпуск по-программистски, или как я не поучаствовал в конкурсе по программированию на JS. Часть первая

Время на прочтение12 мин
Охват и читатели24K

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


image


Задача состояла в том, чтобы написать программу на JS, которая будет определять, есть слово с словаре английских слов или нет. Вроде бы просто, но есть пара ограничений, делающих задачу заведомо невыполнимой:
– Словом считается не просто любое правильное слово английского языка, а именно слово, которое есть в предоставленном словаре из 600K+ слов.
– Словаря в момент исполнения программы нет, скачать его нельзя, а размер программы, включая данные, не должен превышать 64К. Внешние библиотеки подключать также нельзя, но файл данных может быть заархивирован.
Благодаря этим условиям вместо однозначного ответа результатом может быть только определение наибольшей вероятности присутствия слова в словаре.


Сразу скажу, что решение я так и не отправил из-за неудовлетворённостью результатом (решение, которое давало хотя бы 80%, я смог поместить только в 120-130К, а без превышения размера в 64К выжал максимум 70%).
Тем не менее опыт считаю достаточно интересным и достойным статьи. Под катом много SQL,JS,Python, нейронные сети, а также печальная правда о производительности CPU на хостинге.

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

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

Методы генерация случайных чисел с равномерным законом распределения. Часть 1

Время на прочтение5 мин
Охват и читатели23K
Введение

Промышленность не стоит на месте. Еще в 1990 году псевдослучайные числа, длинной в целых 40 бит, сгенерированные на ЭВМ можно было угадать за несколько часов [1]. На сегодняшний же день, качественные характеристики псевдослучайных величин на ЭВМ поражает даже опытных математиков. Во многих областях применения алгоритмов генераций всевдослучайных чисел существует ряд ограничений, связанных с тем или иным недостатком методов их генерации. Совершенствованию существующих методов способствует высокий интерес к теме, который повышается с ростом числа публикаций. Пусть эта статья станет моим вкладом в развитие методов моделирования и генерации случайных процессов, так важных для моих исследований и разработок.
Читать дальше →

Новые производные функций Бесселя выведены с помощью языка Wolfram Language

Время на прочтение10 мин
Охват и читатели18K

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



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

BesselDerivativesBlogRussian_1.png
Читать дальше →

Применение статистических критериев при решении задач обнаружения в радиотехнике

Время на прочтение6 мин
Охват и читатели36K

Аннотация


В статье рассмотрены основы статистической обработки сигналов и методы их оптимальной обработки* на фоне шума.

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

**Процесс наблюдаемый на входе приёмника. Строго говоря, назвать его «Входной сигнал» нельзя, так как в теории связи «Шум» и «Сигнал» — антонимы.

Введение


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

На текущий момент, самый эффективный способ различения полезных сигналов на фоне шумов и помех является оптимальная обработка, реализуемая, как правило, сравнением принимаемой входной реализации с априорно известной формой полезного сигнала. При этом шумы, которые по своей природе процесс слабокоррелированный, вносят меньший вклад в величину, показывающую степень этого сравнения и называющуюся коэффициентом корреляции. Таким образом, любая задача обнаружения сводится к проверке минимум двух гипотез. В общем случае задача обнаружения состоит из двух гипотез: H_0 – сигнал отсутствует на входе приёмного устройства, H_1 – сигнал присутствует на входе приёмного устройства. Различные алгоритмы обнаружения обеспечивают различную вероятность правильного обнаружения P{d_1/H_1} при различных прочих статистических параметрах. Для сравнения эффективности алгоритмов обнаружения существуют критерии, а так как обрабатываются вероятностные величины, то характер этих критериев статистический. Иными словами критерий можно определить как мерило сравнения.
Читать дальше →

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

Время на прочтение3 мин
Охват и читатели18K
Спасибо всем, кто уже поучаствовал или собирается участвовать в нашем конкурсе по программированию!

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

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

Для отправки работ осталась ещё неделя. Если этот пост помог Вам найти ошибку, ещё есть время её исправить.

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

Часто задаваемые вопросы

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

Разжёвываем линейно-квадратичный регулятор для управления перевёрнутым маятником

Время на прочтение8 мин
Охват и читатели38K

Преамбула


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

Как обычно, я стараюсь разжевать математику по максимуму, чтобы материал был доступен заинтересованному школьнику. Я глубоко убеждён, что использование математики по-хорошему должно бы быть платным: любая формула должна быть использована только тогда, когда она призвана облегчить понимание, а не для того, чтобы выпендриваться.

Итак, это уже четвёртая статья, для лучшего понимания происходящего неплохо бы прочитать предыдущие три:


Вот фотография системы (кликабельно):


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

Яндекс.Алгоритм. Разбор прошлогоднего квалификационного раунда и последний шанс поучаствовать в чемпионате

Время на прочтение11 мин
Охват и читатели15K
Как вам известно, вчера завершился очередной чемпионат ACM ICPC. Поздравляем студентов МФТИ, ИТМО, УрФУ и ННГУ с отличным выступлением, ребят из СПбГУ — с 1-м местом. Теперь мы приглашаем всех желающих принять участие в Яндекс.Алгоритме 2016. В этом году финал чемпионата пройдет в Минске.

image

В этом году впервые помимо традиционных призов победители получат возможность попасть на стажировку в Яндекс. 22 мая регистрация закроется и останется только следить за другими участниками в отборочных раундах. Квалификационный раунд продлится в этом году двое суток — с 21 по 22 мая. Раунды вновь будут оцениваться по системе TCM/Time. Для тех, кому интересно, какой сложности задачи их ждут, мы разобрали тур прошлогодней квалификации. Также у вас есть возможность потренироваться на нем.

UPDATE: Уже начался квалификационный раунд Яндекс.Алгоритма 2016, приходите порешать задачи, которые мы обязательно разберем в будущем. На наш взгляд, задачки не хуже, чем в прошлом году.

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

Питерцы чемпионы мира! Не хоккеем, так программированием

Время на прочтение2 мин
Охват и читатели43K
image
В состав команды СПбГУ вошли Игорь Пышкин, Станислав Ершов, Алексей Гордеев и тренер Андрей Лопатин.

Первое место — СПбГУ.
Второе место — Шанхайский университет транспорта.
Третье место — Гарвардский университет.

Четвертое место — МФТИ.
Седьмое место — ИТМО.

Восьмое место — УрФУ.
Десятое место — ННГУ.

Мы наблюдаем за этой олимпиадой с 2003 года. Русскоговорящие программисты обычно забирают ~50% из первых 10 мест и часто побеждают всех (см. факт с кубком). EDISON поздравляет соотечественников с победой!
Читать дальше →

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