Алгоритмы *

Многие алгоритмы являются детерминированными – то есть последовательность их действий зависит лишь от входных данных и программы. Но что будет, если разрешить алгоритму по ходу работы использовать случайные числа?

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

Доброго времени, Хабр!

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

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

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

Вы используете в своей работе SecureCRT? Вам много раз в день приходится заходить на различное оборудование в одном или нескольких пространствах ip адресов, отличающихся лишь одним-двумя конечными октетами и выполнять на них типовые задачи? Логин-пароль для входа на оборудование в вашей сети представлен одной-двумя комбинациями? Вы много думали над тем, как сделать так, чтобы все это делалось само, но боялись спросить? Или просто хотите вкратце узнать что в принципе можно сделать скриптом на SecureCRT? И так, SecureCRT + VBScript или «творчество в рутине». Добро пожаловать под кат.

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

Введение

Одним из важнейших процессов, наблюдаемых в природе, является пуассоновский точечный процесс. Поэтому важно понять, как такие процессы можно моделировать. Методы моделирования различаются в зависимости от типа пуассоновского точечного процесса, т. е. пространства, в котором протекает процесс и однородности или неоднородности процесса. Мы не будем заинтересованы развитием пуассоновского точечного потока или с важными приложениями его в различных областях. Чтобы этот материал показался интересным, читателю настоятельно рекомендуется прочитать соответствующие разделы в Феллере (1965) и Синларе (1975) для основной теории и некоторые разделы в Триведи (1982) для приложений в ИТ.

На первом шаге мы определим пуассоновский процесс на [0;+∞). Процесс полностью определяется семейством случайных событий, которые происходят в определённые случайные моменты времени 0 < T1 < T2 <… Эти события могут относиться ко множеству вещей, таких как ограбление банков, рождению пяти близнецов, и аварии с участием такси Монреаля. Если N(t1,t2) — это количество событий, происшедших за временной интервал (t1,t2), то часто выполнены два следующих условия:

Xombie — ракета, которая разработана компанией Masten Space Systems в 2009 году. Компания с этим проектом выиграла в конкурсе NASA (конкурс лунных аппаратов Lunar Lander Challenge).

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

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

Видимые вычисления

или… О пользе бесполезного

Люди спорят.
Люди любят спорить.
Они спорят об искусстве, еде, фильмах, работе, предметах, явлениях, людях и о том, как лучше спорить.
Если не с кем поспорить снаружи, спорят с тем, кто внутри.

Есть люди, которые не спорят, которые молчат… Это временно. Это люди под впечатлением. Потом, как очухаются, они найдут привычные точки опоры для критики, они снова заспорят. То, о чем люди молчат — недолговечно, но только как акт чистого восприятия. Оно не исчезает. Будут другие, будут молчать, будут потом говорить…

Всем привет!

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

Привет, Хабр!

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

В.А. Малых, Д.Л. Шоломов, В.В. Арлазаров

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

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

При работе с информацией часто возникают задачи парсинга веб-страниц. Одной из проблем в этом деле является определение похожих страниц. Хороший пример такого алгоритма — «Алгоритм шинглов для веб-документов».

Часть проекта по парсингу реализована на Node.JS, поэтому и алгоритм нужно было реализовать на нем. Реализаций на javascript или npm-пакетов я не нашел — пришлось писать свою.

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

Например, Маша, считает, что вечно опаздывающий на работу Вова — страшно неорганизованный человек, который не умеет управлять своим временем.
При этом Вова опаздывает на работу, потому что вынужден с утра умыть, накормить, одеть маленькую дочку и отвести ее в садик. Сама Маша приходит почти вовремя только на работу, во всех иных случаях она всегда опаздывает. Маша винит в своих опозданиях пробки на дорогах, не сработавший будильник, родственников, которые ее отвлекали.
95% бизнесменов терпят крах в первые 1-2,5 года, считая, что знают своего потребителя и могут заставить его купить свой товар. Мысль: «Я знаю, как думает мой покупатель», — главная ошибка начинающего бизнесмена.
На самом деле сам покупатель не знает, как он думает.
Именно поэтому большие компании содержат несколько маркетологов для реализации своей продукции.

Интернет-маркетологи, познавшие особенности когнитивного восприятия, выработали несколько механизмов, способных «включить» скрытые механизмы поведения.

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

Не так давно на Хабре был опубликован интересный пост «Как IT-специалисту сохранить свои финансы», к которому, в частности был прикреплен не менее интересный опрос. Его результаты показательны – большинство хабрапользователей не отличает фондовый рынок от рынка FOREX (хотя на самом деле различия есть), и даже идея инвестировать свои сбережения в стартапы куда более популярна, чем стать инвестором на бирже. Первое место, с огромным отрывом занимают банки, и это также можно понять – к сожалению, в нашей стране не так много людей действительно обладает обширными финансовыми знаниями, а в таком случае депозит в банке – это, пожалуй, лучшее, что можно придумать, чтобы сохранить свои средства.

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

Недавно kuznetsovin опубликовал пост об использовании Питона для анализа временных рядов в экономике. В качестве модели была выбрана «рабочая лошадка» эконометрики — ARIMA, пожалуй, одна из наиболее распространенных моделей для временных данных. В то же время, главный недостаток АRIMA-подобных моделей в том, что они не приспособлены для работы с нестационарными рядами. Например, если в данных присутствует тренд или сезонность, то математическое ожидание будет иметь разное значение в разных участках серии — , что не есть хорошо. Для избежания этого, АRIMA предполагает работать не с исходными данными, а с их разностью (так называемое дифференцирование — от «taking a difference»). Все бы хорошо, но тут возникают две проблемы — (а) мы возможно теряем значимую информацию беря разницу ряда, и (б) упускается возможность разложить ряд данных на составляющие компоненты — тренд, цикл, и т.п. Поэтому, в данной статье я хотел бы привести альтернативный метод анализа — State Space Modeling (SSM), в русском переводе — Модель Пространства Состояний.

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

Чтобы стало понятно о чем идет речь, представим, что нам необходимо протестировать какую-либо программу или сайт. Очень хорош пример с тестированием веб-формы, скажем, для регистрации или для поиска. Возникает вопрос, с какими ошибками в ней скорее всего встретится пользователь? Пускай у нас в форме имеется 6 вопросов, для каждого из которых возможны 10 вариантов ответа. Допустим, на страницу зашел целый миллион пользователей, и каждый из них ответил уникально. Теперь представим, что в форме для заполнения ответами скрывается ошибка. Если ошибка обнаруживается только при определенной комбинации ответов на все 6 вопросов, то на неё наткнется лишь один человек. Если же ошибка вылетает при наборе определенных ответов на какие-то 3 вопроса, то количество людей, обнаруживших ошибку возрастет до тысячи. Очевидно, что чем меньше элементов в комбинации, требуемой для ошибки, тем больше людей с ней встретится. Соответственно, перед нами теперь стоит задача: если мы не можем обнаружить все ошибки, то давайте хотя бы найдем самые критичные, то есть те, на которые наткнется больше всего пользователей.
Таким образом, мы должны сформировать тест-кейсы (и чем меньше, тем лучше), при переборе которых мы наткнемся на самые легкодоступные ошибки. Допустим, у нас имеется множество вопросов A, которое мы задаем количеством вариантов ответа на каждый из них: А = {2, 3, 5, 2, ...}. Пусть n — количество вопросов, а 1≤m≤n — степень критичности ошибок, она же степень покрытия или глубина покрывающего набора. Чем меньше значение m, тем критичнее ошибка. Задавая степень покрытия мы строим тестовый набор, который позволит обнаружить все ошибки, степень критичности которых меньше данного m. Если m = n, то поиск ошибок сводится к перебору всех вариантов. Чем меньше задаем степень, тем меньше тест-кейсов будет сформировано и тем меньше ошибок мы найдем.

Все животные равны, но некоторые животные равнее других. Скотный Двор, Джордж Оруэлл (оригинал).

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

(картинка сделана на основе хабра-статьи «Список скептика»).

Под катом рассказ, какие бывают сортировки комментариев, где они применяются и краткое рассуждение о том, как вообще можно сортировать комментарии (и зачем).

В этой статье я постараюсь максимально доходчиво рассказать о таком простом, но эффективном методе оптимизации, как имитация отжига (simulated annealing). А чтобы не быть причисленным к далёким от практики любителям теоретизировать, я покажу как применить этот метод для решения задачи коммивояжёра.

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

Это пост про небольшую игру «Крестики-нолики», которая была написана в целях пополнения опыта программирования на JS. Здесь применяются canvas и DojoBase. Библиотека используется для работы с событиями и для нахождения элементов по id(это очень удобно). Сanvas используется для отрисовки игрового поля.
Сама игра

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

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