Алгоритмы *

Введение

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

Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|

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

В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

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

Если позволите, начну без вступления и предыстории.

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

На известной шуточной конференции SIGBOVIK2013, которая проходила 1-го апреля 2013-го года и представляет собой, как правило, фальшивые шуточные исследования д-р Том Мерфи подготовил работу, которая, на мой взгляд, довольно интересна.
Если вкратце — он научил программу играть в старые добрые денди-игры на NES-эмуляторе. Как это происходит?

Привет. В этом посте мы продолжим экспериментировать с ограниченной машиной Больцмана. В предыдущем посте о регуляризации в РБМ мы увидели как можно получить более локальные фичи, которые обладают большей обобщающей способностью. Но мы не оценили их робастность по сравнению с более простыми и быстрыми алгоритмами. Для этого эксперимента мы обратимся к линейному методу главных компонент (вы можете ознакомиться с этим методом и глянуть реализацию на c# в моем первом посте). Желающим ознакомиться с первоисточником по теории сжатия размерности с использованием РБМ рекомендую глянуть статьи Джеффри Хинтона тут и тут. Мы же продолжим тестирование на множестве печатных больших букв: обучим РБМ, построим главные компоненты, сгенерируем сжатые представления данных, а из них восстановим первоначальные изображения, и затем оценим разницу между оригинальными изображениями и восстановленными.

Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

Чем больше люди постигали тайны Вселенной, тем ближе они приближались к той точке незнания, в которой их предки все приписывали богам. Теперь это называется – случайность. И хотя Эйнштейн не верил в случайность – он говорил «Бог не играет в кости», – он в числе первых из списка: Эйнштейн, Шредингер, Лаплас…

В наш век цифровых технологий и огромной роли информации в развитии человечества защита информации – актуальнейшая задача. Технологическое решение этой задачи предполагает привлечение «случайности», а именно – генерацию случайных чисел. При этом от качества используемых генераторов напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

К услугам программ-проксификаторов прибегали многие, но как они работают знают не все. Я расскажу об алгоритме положенному в их основу и практической реализации.

Группа учёных, работающих в Австралийском Центре Устройств Сверхвысокой Пропускной Способности для Оптических Систем (CUDOS), разработала алгоритм кодирования данных, который может существенно увеличить эффективность существующих оптических сетей. По утверждению исследователей, их разработка позволит передавать весь мировой трафик по единственному волокну!

Привет. В этом посте мы проведем эксперимент, в котором протестируем два типа регуляризации в ограниченной машине Больцмана. Как оказалось, RBM очень чувствительна к параметрам модели, таким как момент и локальное поле нейрона (более подробно обо всех параметрах можно прочитать в практическом руководстве в RBM Джеффри Хинтона). Но мне для полной картины и для получения шаблонов наподобие таких вот, не хватало еще одного параметра — регуляризации. К ограниченным машинам Больцмана можно относиться и как к разновидности сети Маркова, и как к очередной нейроной сети, но если копнуть глубже, то будет видна аналогия и со зрением. Подобно первичной зрительной коре, получающей информацию от сетчатки через зрительный нерв (да простят меня биологи за такое упрощение), RBM ищет простые шаблоны во входном изображении. На этом аналогия не заканчивается, если очень малые и нулевые веса интерпретировать как отсутствие веса, то мы получим, что каждый скрытый нейрон RBM формирует некоторое рецептивное поле, а сформированная из обученных RBM глубокая сеть формирует из простых образов более комплексные признаки; чем-то подобным, в принципе, и занимается зрительная кора головного мозга, правда, вероятно, как то посложнее =)

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


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!

Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретил людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра математических и информационных технологий АУ и сейчас ведет набор новых магистрантов, в частности, по направлению «теоретическая информатика».
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

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



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

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

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

Вводная

Тем из нас, кому приходится тратить полчаса-час на путешествие из Москвы в Москву, приходится искать, чем занять и разогреть ещё не до конца проснувшийся мозг. Кто-то читает, кто-то кидает птичек, кто-то решает математические головоломки. Например, классическая задачка: среди шести цифр автобусного билета расставить скобки и операторы так, чтобы получилось число 100. Бывает так, что ну никак не удаётся найти решение, и конкретная задачка не отпускает весь оставшийся день. Поневоле задумаешься над алгоритмом.
Решение «в лоб» подстановкой скобок и операторов и проверка на каком-нибудь математическом движке не устраивало, генетические алгоритмы, по которым я с ума схожу, не подходили из-за склонности скапливаться в локальных экстремумах. В итоге задача свелась к перебору всех возможных двоичных деревьев с заданным числом листьев (для шести их ровно 42).

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



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

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

Свои вопросы пишите в комментарии, ибо уже определились со вторым постом.

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



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

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

Сначала немного статистики для того, чтобы показать важность настоящего исследования. Около 50% пользователей нашей системы регистрируются с привязкой аккаунтов социальных сетей vkontakte (VK) и facebook (FB). Причем из зарегистрированных через социальные сети 71% приходится на VK и 29% на FB.

API FB и API VK позволяют извлекать некоторые данные об интересах и предпочтениях пользователя. Но не все так просто, как может показаться. Для получения данных пользователя нужно получить особые права, согласие на которые дает сам пользователь при регистрации в системе. Здесь возникает тонкий момент. С одной стороны, мы ходим вытянуть как можно больше информации о пользователе. С другой стороны, просить слишком много прав — наглость, которая может отпугнуть пользователя. Нужно найти компромисс — тонкое равновесие между полезностью получаемых данных для улучшения рекомендаций и «суммой» кредита доверия от пользователя, который соглашается, чтобы мы залезли в его персональные данные.

Практически каждая новость от DARPA, связанная с роботами и искусственным интеллектом, неизбежно сопровождается набившими оскомину комментариями про Скайнет. Но на этот раз они будут на удивление уместны. Новая исследовательская программа Агентства посвящена вероятностному программированию для решения продвинутых задач машинного обучения (Probabilistic Programming for Advanced Machine Learning или PPAML). По словам руководителя программы Кэтлин Фишер, DARPA намерено ни много ни мало «Сделать для машинного обучения то, что появление языков высокого уровня 50 лет назад сделало для программирования в целом».

Алгоритмы машинного обучения уже широко используются в потребительских технологиях — борьбе со спамом, распознавании речи, автомобилях-роботах и для анализа гигантских объёмов данных в медицине или финансах. Естественно, перспективы машинного обучения интересны и военным. При этом пока не существует общепринятых универсальных инструментов для создания интеллектуальных систем. Из-за этого приходится постоянно изобретать велосипеды, раз за разом реализовывать похожие как две капли воды алгоритмы, строить с нуля архитектуру.

Введение

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

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

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