Как стать автором
Обновить
210.19

Алгоритмы *

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

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

Интернет-математика от Яндекса

Время на прочтение1 мин
Количество просмотров1.4K
Яндекс второй раз в этом году проводит конкурс «Интернет-математика».

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

Как и раньше, участвовать можно в одиночку или командой, за первые три места участников ждет денежный приз (до 5000$). Лучшему российскому участнику мы оплатим полет в Сиэтл, США, где пройдет презентация лучших решений (на WSCD 2012 workshop), и регистрацию на ведущую конференцию по веб поиску – WSDM 2012.

Подробная информация о конкурсе, данные и рейтинг решений — на сайте, общение участников — в клубе.

Обзор статей по теме.

P.S.: Зарегистрировалось уже более 200 участников.

Среднеквадратичное приближение функций

Время на прочтение3 мин
Количество просмотров61K
На днях нужно было написать программу, вычисляющую среднеквадратичное приближение функции, заданной таблично, по степенному базису — методом наименьших квадратов. Сразу оговорюсь, что тригонометрический базис я не рассматривал и в этой статье его брать не буду. В конце статьи можно найти исходник программы на C#.
Читать дальше →

Двумерное дерево отрезков (с групповой модификацией элементов)

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

Предисловие и постановка задачи


Думаю, многие читатели этого сайта слышали о такой полезной структуре, как дерево отрезков. А если нет, то о нем в интернете можно отыскать множество интересного материала (здесь, статьи на Хабре: раз и два, google, наконец).
Здесь я разберу обобщение дерева отрезков на двумерный случай, причем (в отличие от этой статьи) рассмотрю реализацию дерева именно с поддержкой групповой модификации элементов.
Читать дальше →

Рециркуляционные нейронные сети

Время на прочтение4 мин
Количество просмотров24K
Рециркуляционные нейронные сети представляют собой многослойные нейронные сети с обратным распространение информации. При этом обратное распространение информации происходит по двунаправленным связям, которые имеют в различных направлениях разные весовые коэффициенты. При обратном распространении сигналов, в таких сетях осуществляется преобразование их с целью восстановления входного образа. В случае прямого распространения сигналов происходит сжатие входных данных. Обучение рециркуляционных сетей производится без учителя.
Читать дальше →

Арифметическое кодирование

Время на прочтение3 мин
Количество просмотров103K
Сейчас существует множество алгоритмов сжатия информации. Большинство из них широко известны, но есть и некоторые весьма эффективные, но, тем не менее, малоизвестные алгоритмы. Эта статья рассказывает о методе арифметического кодирования, который является лучшим из энтропийных, но тем не менее мало кто о нём знает.
Читать дальше →

Неблокирующие очереди: обмен сообщениями между потоками

Время на прочтение6 мин
Количество просмотров14K
Идею к написанию подобного модуля породил PLM нашего корпоративного продукта. Инспектируя нашу дизайн-документацию, нам сказали, что наш код ни в коем случае не должен блокировать таску из которой он вызывается, и вообще отнимать как можно меньше ее времени, такова особенность построения системы
Читать дальше →

Re: Проблема «maximum-subarray» на примере курса доллара

Время на прочтение2 мин
Количество просмотров3.4K
После прочтения недавней статьи «Проблема «maximum-subarray» на примере курса доллара» 3 раза, мне захотелось плеваться. В статье предлагается найти промежуток дат, за который можно было заработать больше всего на разнице в курсе доллара к рублю за последние 5 лет. Автор предлагает свое «красивое» решение этой задачи, которое он нашел сам (разделяй и властвуй называется, ага), и которое работает за O(n lg n)…

Товарищи, это стыд и срам в блог «Алгоритмы» публиковать очевидно не оптимальное решение тривиальной задачи. Максимальная сумма элементов подмассива в массиве ищется за O(n)! Хоть бы википедию почитали по этой задаче.

Нормальное решение под катом.
Читать дальше →

Алгоритмы отсечения

Время на прочтение5 мин
Количество просмотров56K
С ростом мощности компьютеров всё большая часть людей пробует работать с графикой. На первый взгляд многие алгоритмы кажутся интуитивно понятными, но, если вы хотите, чтобы ваше приложение работало с приемлемой скоростью, вам придётся изучить классические алгоритмы.

Этот пост посвящён разбору нескольких алгоритмов, направленных на одну и ту же задачу, задачу отсечения отрезков. При генерации изображений могут получаться фигуры произвольной формы и размеров. Зачастую мониторы не могут отобразить сгенерированные изображения целиком. Также иногда возникают ситуации, когда необходимо задать область изображения на экране и выводить изображения только внутри этой области. Для решения этих задач и придуманы алгоритмы отсечения.
Читать дальше →

Проблема «maximum-subarray» на примере курса доллара

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

В чём суть


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

Соединение компьютер-компьютер через интернет с динамическими IP

Время на прочтение3 мин
Количество просмотров144K
Очень часто мы слышим о том, что установить соединение компьютер-компьютер через интернет с динамическими IP – нереально без внешнего сервера.
А также думал, до определенного времени. Потом у меня закрались подозрения… А после мне стало известно очень многое и тайное.

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

Все совпадения случайны, цифры изначально выдуманы.

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

Почему в WiMax и LTE используют OFDM

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


Аббревиатура OFDM расшифровывается как Orthogonal frequency-division multiplexing. В русскоязычной литературе встречается несколько различных переводов, несущих, в принципе, один смысл: OFDM — это механизм мультиплексирования (уплотнения) посредством ортогональных поднесущих.



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





Иллюстраций: 18, символов: 27 399, строк кода: 99.



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

Сжатие изображений с использованием вейвлет

Время на прочтение11 мин
Количество просмотров27K
Вейвлетное сжатие — общее название класса методов кодирования изображений, использующих двумерное вейвлет-разложение кодируемого изображения. Обычно подразумевается сжатие с потерей качества. В статье не будет приведено сложных математических формул, всю теорию можно почитать по ссылкам внизу статьи. Здесь только практика!

Отличие от JPEG


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

Пример


Для примера сильно сожмем одно и тоже изображение приблизительно до одного размера:

В начале с использованием JPEG:
7959 байт
(7959 байт)

затем алгоритмом вейвлетного сжатия JPEG 2000:
7813 байт
(7813 байт)

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

Алкотестер от facebook

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

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

Итак, алкотестер. Он же breathalyzer. Это задачка snack-сложности по классификации facebook, т.е. по их меркам она совсем не сложная. Что не помешало мне потратить на её решение добрых пару недель(отчасти из-за принципиального желания решить её на Ruby). Эту задачу я делал второй по-очереди, и именно она натолкнула меня на основную идею, побудившую меня прикладывать кучу усилий для поиска решения. А идея была в следующем — я не умею программировать…
Читать дальше →

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

Дерево отрезков

Время на прочтение5 мин
Количество просмотров41K
Я расскажу о структуре под названием дерево отрезков и приведу его простую реализацию на языке С++. Эта структура весьма полезна в случаях, когда необходимо часто искать значение какой-то функции на отрезках линейного массива и иметь возможность быстро изменять значения группы подряд идущих элементов.
Типичный пример задачи на дерево отрезков:
Есть линейный массив, изначально заполненный некоторыми данными. Далее приходят 2 типа запросов:
1й тип — найти значение максимального элемента на отрезке массива [a..b].
2й тип — заменить iй элемент массива на x.
Возможен запрос «добавить х ко всем элементам на отрезке [a..b]», но в данной статье я его не рассматриваю.
С помощью дерева отрезков можно искать не только максимум чисел, но и любую функцию, удовлетворяющую свойству ассоциативности.
image
Это ограничение связано с тем, что используется предпросчет значений для некоторых отрезков.
Читать дальше →

Alpha-blending за одно умножение на пиксель на Windows Mobile

Время на прочтение4 мин
Количество просмотров3.7K
Те, кто занимался графикой на Windows Mobile, наверняка слышали о графической библиотеке GapiDraw. Если заглянуть в их Feature List, то в разделе High Performance можно обнаружить следующие слова: «drawing surfaces with opacity will only require one multiplication per pixel». То есть, они утверждают, что для рисования полупрозрачных картинок требуется всего по одному умножению на каждый пиксель.

В данной статье я попытаюсь объяснить, как это возможно.
Читать дальше →

Генетический алгоритм. Просто о сложном. Рассказ Марка Андреева

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

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.
Читать дальше →

Вычисление числа Пи методом Монте-Карло

Время на прочтение2 мин
Количество просмотров88K
Существует много способов вычисления числа Пи. Самым простым и понятным является численный метод Монте-Карло, суть которого сводится к простейшему перебору точек на площади. Суть расчета заключается в том, что мы берем квадрат со стороной a = 2 R, вписываем в него круг радиусом R. И начинаем наугад ставить точки внутри квадрата. Геометрически, вероятность P1 того, чтот точка попадет в круг, равна отношению площадей круга и квадрата:
P1=Sкруг / Sквадрата = πR2 / a 2 = πR2 / (2 R ) 2= πR2 / (2 R) 2 = π / 4 (1)
Выглядит это так:

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

Построение цифрового фильтра с конечной импульсной характеристикой

Время на прочтение3 мин
Количество просмотров130K
Вступление издалека

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

Естественная сортировка строк на JavaScript

Время на прочтение14 мин
Количество просмотров47K
Задача сортировки является едва ли не наиболее часто решаемой программистами проблемой. Несмотря на то, что распространённых алгоритмов не так много и все они давно написаны и оптимизированы для любых языков и платформ, в исходниках то и дело мелькают методы SortList() и им подобные. Наверное, каждый из нас не раз писал сортировку пузырьком и удивлялся, почему же она не работает с первого раза.

Однако речь сейчас не об алгоритме сортировки, а о способе сравнения строк. Казалось бы, здесь всё тривиально — достаточно сравнить первые с начала различающиеся символы. А если в строках есть числа? Тогда такая сортировка (лексикографическая) преобразует последовательность [ 'file2', 'file10', 'file1' ] в [ 'file1', 'file10', 'file2' ]. Но человек при чтении текста воспринимает числа отдельно, и эта же последовательность, упорядоченная интуитивно, выглядит так: [ 'file1', 'file2', 'file10' ]. Такая сортировка и называется естественной (natural sort).

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

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

Неблокируемая очередь сообщений для двух потоков

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

Подробности под катом.
Читать дальше →

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