В последнее время в научных публикациях всё чаще упоминается алгоритм достижения консенсуса в распределенных системах под названием Paxos. Среди таких публикаций ряд работ сотрудников Google (Chubby, Megastore, Spanner) ранее уже частично освещенных на хабре, архитектуры систем WANdisco, Ceph и пр. В то же время, сам алгоритм Paxos считается сложным для понимания, хоть и основывается он на элементарных принципах.

В этой статье я постараюсь исправить эту ситуацию и рассказать об этом алгоритме понятным языком, как когда-то это попытался сделать автор алгоритма Лесли Лэмпорт.

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

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

Итак, начнем с постановки задачи классификации. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. Существует неизвестная целевая зависимость — отображение , значения которой известны только на объектах конечной обучающей выборки . Требуется построить алгоритм , способный классифицировать произвольный объект x∈X. Однако более распространенным является вероятностная постановка задачи. Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. На множестве пар «объект, класс» X×Y определена вероятностная мера P. Имеется конечная обучающая выборка независимых наблюдений , полученных согласно вероятностной мере P.

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

Причина побудившая автора к публикации

Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

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

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

1. Выбрать случайное значение из массива
2. Выбрать случайное значение из массива на основании веса значений

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

Для решения я буду использовать псевдокод, чем-то похожий на Javascript. Потому, мой метод random() будет возвращать значение от 0 до 1.

Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

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





Если вспомнить фильм «Терминатор» и технологии, которыми по сюжету пользовались киборги, то можно будет выделить и нейронные сети, и возможность беспроводной связи с внешним источником интеллекта (Skynet), и компьютерное зрение, и распознавание звука, понимание различных языков. На момент выхода фильма на экраны все это было абсолютной фантастикой, технологиями далекого будущего. Но сегодня большая часть этих технологий реализована в том или ином виде. Попробуем разобраться, что же из всего перечисленного уже используется.

В этой моей статье, как и в предыдущей рассматривается цифровая схемотехника с точки зрения программиста. Но в этот раз будет разобрана «более алгоритмическая» задача сортировки чисел, с разбором verilog-кода. Рассматриваемое аппаратное решение позволяет отсортировать n чисел за время 2*n. На картинке ДПВ показан вывод на монитор от тестового проекта для ПЛИС, там каждой линии соответствует один тик сортировщика, сначала n тиков случайные числа записываются в сортировщик, затем n тиков выводятся числа отсортированные.

Ранее в нашем блоге уже поднималась тема производных финансовых инструментов (деривативов) и описывались некоторые их классы. Очень часто именно о покупке или продаже таких биржевых инструментов говорят как о «продаже воздуха» и очевидно вредных спекуляциях. На самом же деле, важность тех же опционов и фьючерсов для фондового рынка и, шире, для экономики страны, трудно переоценить. Сегодня речь пойдет именно о фьючерсных контрактах и логике работы с ними.

В этой статье речь пойдёт о бенчмарке алгоритмов сортировки, написанном на PHP.

Всего представлено 14 алгоритмов:

• quickSort
• countingSort
• combSort
• heapSort
• mergeSort
• shellSort
• selectionSort
• insertSort
• gnomeSort
• combinedBubbleSort
• cocktailSort
• bubbleSort
• oddEvenSort
• bubbleSortWithFlag

Уже пару раз на Хабре возникали дискуссии на тему того, как сейчас работает распознавание номеров. Но статьи, где были бы показаны разные подходы к распознаванию номеров, на Хабре пока не было. Так что здесь попробуем разобраться, как все это работает. А потом, если статья вызовет интерес, продолжим и выложим работающую модель, которую можно будет поисследовать.

В жизни каждого мужчины наступает момент, когда трафик растёт и сервак умирает необходимо задуматься об оптимизации. В последнем дайджесте PHP (№ 40) была упомянута ссылкой статья «How GZIP Compression Works». Исходя из статистики, 56% веб-сайтов используют GZIP. Я надеюсь, эта статья раскроет перед читателем достоинства этой технологии.

Введение

Прочитав статьи TimeCoder — «Путешествия во времени и программирование» [1, 2] я вспомнил свои скромные практические исследования в программировании, связанные с реализацией разветвляющихся миров. Однажды товарищ по работе подкинул мне интересную задачу, но решить я ее до сих пор не смог. Задача о том, как нагрузить станки на производстве. Даже не программисту было понятно, что нужен простой перебор, но я так и не смог придумать подходящую структуру данных для обеспечения вычисляющего алгоритма. Задача из реального мира, поэтому я решил попробовать реализовать в программе реальный мир в той части, который требуется для вычисления задачи. Каждый раз, когда в дальнейших вычислениях стоял выбор между двумя действиями — происходило «создание двух новых миров» с разным решением в каждом. Дальше каждый мир развивался своим путем.

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

Генетические алгоритмы были изобретены в 1950-х годах как результат первых экспериментов по моделированию естественной эволюции на компьютере. С тех пор они используются для решения самых разнообразных оптимизационных задач, где градиентные методы почему-то не подходят. Биологическая составляющая генетических алгоритмов имеет здесь очень упрощенный вид и речь в данном случае идет скорее о следовании общей идее эволюционного отбора, чем полноценному его моделированию. Тем не менее, иногда результаты работы ГА получается интерпретировать в биологическом смысле. В нашей статье мы рассказываем об опыте применения генетических алгоритмов для задачи распознавания лиц с целью получения «регионов важности» лица. Применение этого подхода позволило в среднем на 20% повысить точность распознавания нашей системы распознавания лиц.

Добрый день.
В рамках набора на курс «Multicore programming in Java» я делаю серию переводов классических статей по многопоточности в Java. Всякое изучение многопоточности должно начинаться с введения в модель памяти Java (New JMM), основным источником от авторов модели является «The Java Memory Model» home page, где для старта предлагается ознакомится с JSR 133 (Java Memory Model) FAQ. Вот с перевода этой статьи я и решил начать серию.
Я позволил себе несколько вставок «от себя», которые, по моему мнению, проясняют ситуацию.
Я являюсь специалистом по Java и многопоточности, а не филологом или переводчиком, посему допускаю определенные вольности или переформулировки при переводе. В случае, если Вы предложите лучший вариант — с удовольствием сделаю правку.
Этот статья также подходит в качестве учебного материала к лекции «Лекция #5.2: JMM (volatile, final, synchronized)».

Также я веду курс «Scala for Java Developers» на платформе для онлайн-образования udemy.com (аналог Coursera/EdX).

Ну и да, приходите учиться ко мне!

---

JSR 133 (Java Memory Model) FAQ

Jeremy Manson и Brian Goetz, февраль 2004

Содержание:
Что такое модель памяти, в конце концов?
Другие языки, такие как C++, имеют модель памяти?
Что такое JSR 133?
Что подразумевается под «переупорядочением» (reordering)?
Что было не так со старой моделью памяти?
Что вы подразумеваете под «некорректно синхронизированы»?
Что делает синхронизация?
Как может случиться, что финальная поля меняют значения?
How do final fields work under the new JMM?
Что делает volatile?
Решила ли новая модель памяти «double-checked locking» проблему?
Что если я пишу виртуальную машину?
Почему я должен беспокоиться?

Пирамидальная сортировка (она же сортировка кучей) – классический алгоритм который, пожалуй, должен знать любой программист. Старая добрая «пирамидка» примечательна тем, что в независимости от набора данных у неё одна и та же сложность по времени (причём, очень пристойная) – O(n log n). Лучших и вырожденных случаев для неё нет.

С момента изобретения метода (а в этом году алгоритм празднует свой полувековой юбилей) было немало охочих кардинально оптимизировать процесс накладывания сортирующих куч. Тернарная пирамидальная сортировка, плавная сортировка, сортировка декартовым деревом – вот неполный список инноваций. Перечисленные алгоритмы хотя при тестировании и опережают оригинал по абсолютной скорости кто на 12, а кто и на 25%, в оценке временной сложности всё равно крутятся вокруг O(n log n). При этом данные методы весьма изощрённо реализованы.

Своё видение пирамидальной сортировки предложил и скромный труженик Университета Манитобы Джейсон Моррисон. При этом способ в некоторых случаях по скорости приближается к O(n).

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

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

Поскольку побеждать Великий Китайский Роскомнадзор наша штука для обхода блокировок в интернете пока не особенно научилась, а рассказать что-нибудь странное про свою работу все равно хочется, расскажу про реимплементацию похожего на Readability алгоритма при помощи Node.js и Бэйцзинского технологического института.

Что это вообще такое

Readability — это радикальное продолжение идеи AdBlock убирать с веб-сайтов лишние элементы. Там, где AdBlock старается снести только самые бесполезные для пользователя вещи (в основном рекламу), Readability удаляет заодно скрипты, стили, навигацию и все остальное ненужное. Раньше такой вид страницы называли «версия для печати», хотя на самом-то деле текст предназначен для чтения (отсюда название Readability – «Удобочитаемость»).

Лирическое отступление про парсеры

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

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

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

Для слаженной работы миниатюрных роботов ученые используют магнитное поле (Diamagnetic Micro Manipulation, DM3) с использованием печатных плат (PCB). Микророботы создаются из недорогих магнитов. Все это позволяет задешево создавать большое количество подобных систем. Специальная программа манипулирует магнитным полем, которое, в свою очередь, управляет роботами.