Алгоритмы *

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

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

Прошлая статья привлекла большой интерес. И даже, на некоторое время, стала лучшей за 24 часа. У меня появилось несколько идей и на часть вопросов в комментариях нужно ответить более развернуто.

Если в одном из моих прошлых постов речь шла о довольно современном подходе к построению сбалансированных деревьев поиска, то этот пост посвящен реализации АВЛ-деревьев — наверное, самого первого вида сбалансированных двоичных деревьев поиска, придуманных еще в 1962 году нашими (тогда советскими) учеными Адельсон-Вельским и Ландисом. В сети можно найти много реализаций АВЛ-деревьев (например, тут), но все, что лично я видел, не внушает особенного оптимизма, особенно, если пытаешься разобраться во всем с нуля. Везде утверждается, что АВЛ-деревья проще красно-черных деревьев, но глядя на прилагаемый к этому код, начинаешь сомневаться в данном утверждении. Собственно, желание объяснить на пальцах, как устроены АВЛ-деревья, и послужило мотивацией к написанию данного поста. Изложение иллюстрируется кодом на С++.

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

 

Введение

Когда в разговорах между людьми речь заходит о мобильных приложениях, часто приходиться слышать об астрономических суммах, которые зарабатывают те или иные всемирно известные разработчики или об огромном числе загрузок того или иного приложения. СМИ то и дело сообщают о запуске на МКС плюшевых свиней из Angry Birds, а в США и вовсе Цукерберг купил Instagram за 1 000 000 000 долларов.

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

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

Эти данные оказалось совсем не просто найти…

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

Этот пост — продолжение разбора алгоритмов сортировки (в прошлый раз был Hacker News). В этот раз, мы разберем как работает сортировка постов и комментариев на Reddit. Алгоритмы у Реддита достаточно простые, чтобы понять их и реализовать.

Первая часть этой записи будет сфокусирована на сортировке постов, а вторая на сортировке комментариев. Они довольно сильно различаются, и за идеей способа сортировки комментариев стоит Randall Munroe (автор xkcd).

Разбираем сортировку постов

Реддит open-source-ный проект и его код полностью доступен на гитхабе. Он написан на питоне, исходники вы можете увидеть тут. Их алгоритмы сортировки написаны под Pyrex, для дальнейшей компиляции (трансляции) в C-код. Pyrex был выбран из-за производительности. Я переписал их реализации на чистый питон, чтобы они легче читались.

Написать этот пост меня привлекла эта статья. Многие ее помнят по вот этой картинке.

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

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

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

Алгоритмы сортировки. Их не много, но и не мало. Есть часто используемые, есть никому не нужные. Я решил произвести обзор этих алгоритмов, чтоб освежить и свою память, и память хабрапользователей. И начнём с редкоиспользуемого алгоритма Gnome Sort(гномья сортировка).

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

Гомоморфное шифрование — криптографическая система, которая позволяет проводить определенные математические действия с открытым текстом путем произведения операций с зашифрованным текстом.

Долгое время полностью гомоморфная криптосистема оставалась для всех криптографов мира священным Граалем, недостижимым идеалом. И вот в 2009 году Craig Gentry в своей диссертации впервые описал полностью рабочую схему гомоморфного шифрования.
Несколько математических подробностей идеи Gentry а также пример реализации его алгоритма вы найдете под катом.

Всем привет.

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

В этот раз мне на глаза попались статьи по cache oblivious алгоритмам. Это такие алгоритмы, которые изначально более оптимизированы для работы с подсистемой кэширования современных процессоров.

Одним из представителей этой группы является Unrolled linked list.

Что же это такое?

Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.

kNN расшифровывается как k Nearest Neighbor или k Ближайших Соседей — это один из самых простых алгоритмов классификации, также иногда используемый в задачах регрессии. Благодаря своей простоте, он является хорошим примером, с которого можно начать знакомство с областью Machine Learning. В данной статье рассмотрен пример написания кода такого классификатора на python, а также визуализация полученных результатов.

Sentiment analysis (по-русски, анализ тональности) — это область компьютерной лингвистики, которая занимается изучением мнений и эмоций в текстовых документах. Недавно на хабре появилась статья про использование машинного обучения для анализа тональности, однако, она была настолько плохо составлена, что я решил написать свою версию. Итак, в этой статье я постараюсь доступно объяснить, что такое анализ тональности, и как реализовать подобную систему для русского языка.

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

Именно о лесенках хотелось бы немного поговорить. Есть такая относительно распространенная задача с программистских собеседований:

Вы поднимаетесь по лестнице. На каждом шаге вы можете подняться либо на 1 ступеньку, либо на 2. Всего лестница имеет n ступенек. Сколькими разными способами вы можете дойти до конца лестницы?

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

Пару месяцев назад я рассказывал о приближенных результатах в задаче о сворачивании РНК. Напомню требуется свернуть вироидный рибозим NC_003540 организма Chrysanthemum chlorotic mottle viroid, третичная структура которого неизвестна.

И вот оно свершилось — рибозим свернулся ! (В нем образованы все имеющиеся водородные связи)

Смотрим его конечное состояние, а под катом еще его траекторию сворачивания, а также подводим итоги.

Вместо вступления

Лень — двигатель прогресса. Не хочешь сам молоть зерно — сделай мельницу, не хочешь сам кидать во врагов камни — сооруди катапульту, надоело гореть на кострах инквизиции и гнуть спину под феодалом — замути с ребятами ренессанс… впрочем, о чем это я.
Автоматизация, господа. Берешь какой-нибудь полезный процесс, в котором участвует человек, заменяешь человека на сложный механизм, получаешь профит. Относительно недавно также стало модно заменять человека куском кода. О, сколько благородных профессий может пасть под натиском информатизации. Особенно если учесть, что кусок кода в наше время способен не только на заранее определенное поведение, но и на «обучение» какому-то поведению.

Введение

Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

Постановка задачи

Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).