Доброго времени суток, хабралюди! Частенько математики останавливаются на существовании решения, и получается что-то подобное.

В гостинице поселились инженер, физик, и математик. У каждого в номере возникает пожар.
Инженер выбегает в коридор, видит на стене пожарный шланг, хватает его, открывает воду, вбегает в номер и заливает очаг возгорания.
Физик, быстро прикинув объем горючих веществ, температуру пламени, теплоемкость воды и пара, атмосферное давление и т.п., наливает в стакан из графина строго определенное количество воды и заливает огонь этой водой.
Математик выскакивает в коридор, видит на стене огнетушитель, и, обрадованно воскликнув: “Решение существует!”, спокойно возвращается в номер.

А о том, какие грабли попадаются на пути «до победного конца», я расскажу под катом.

Все мы слышали поговорку: как новый год встретишь — так его и проведешь. Оливье в сторону!

Рассчитывать на 5 часов адского программирования в праздник было бы негуманно, потому задача всего одна и она весьма лапидарна:

Программа должна прочитать из стандартного потока ввода целое число N (от 1 до 2³⁰), и напечатать сумму простых чисел меньших либо равных N.

Побеждает тот, кто напишет самое быстрое решение, проходящее все тесты (хотя-бы один неправильный ответ — и решение отклоняется). Скорость решения оценивается на тестах в районе верхней границы допустимого диапазона N (но не ровно 2³⁰).

Победитель получает всеобщее признание, сотни кармы и приятное чувство что он порвал всех на Хабре. Долгие годы молодые поколения разработчиков будут восхищаться его кодом, а девушки — чепчики в воздух бросать. По меньшей мере первые 4 read-only пользователя будут приглашены на Хабр.

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

В этой статье приведён краткий обзор методов кластеризации числовых пространств данных. Она будет полезна тем, кто только начинает изучать Data Mining и кластерный анализ и поможет сориентироваться в многообразии современных алгоритмов кластеризации и получить о них общее представление. Статья не претендует на полноту изложения материала, напротив, описание алгоритмов в ней максимально упрощено. Для более подробного изучения того или иного алгоритма рекомендуется использовать научную работу, в которой он был представлен (см. список литературы в конце статьи).

Алгоритм ACOR

Привет, хабра. Хочу поделиться имеющийся у меня информацией по методам непрерывной оптимизации, а именно по оптимизации методом колонии муравьев, тем более материала по данной теме на русском очень мало. В данной статье представлен алгоритм ACOR (Ant Colony Optimization for continuous domain). В будущем планирую представить еще несколько алгоритмов колонии муравьев. Может быть кому-нибудь пригодиться в университете или по работе.

Основные принципы соответствия

Простым критерием проверки соответствия является Гугл поиск.
Вы должны вводить полные слова, т.к. не существует производных слов (например, joh не будет соответствовать john.smith@gmail.com). Тоже справедливо и для множественного числа (например, app не будет соответствовать apps@example.com).

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

Этот алгоритм является улучшенным алгоритмом поиска пути A*. JPS ускоряет поиск пути, “перепрыгивая” многие места, которые должны быть просмотрены.  В отличие от подобных алгоритмов JPS не требует предварительной обработки и дополнительных затрат памяти. Данный алгоритм представлен в 2011 году, а в 2012 получил высокие отклики. Что из себя представляет данный алгоритм и его реализацию можно прочитать дальше в статье.

С 29 июня по 1 июля 2013 г. в Екатеринбурге пройдёт международная студенческая школа CSEDays по алгоритмам и теории сложности. Список преподавателей получился очень внушительным, давайте я о них здесь буквально в двух словах расскажу.

	Константин Макарычев (Microsoft Research) Молодой, но уже очень успешный учёный. Специалист по приближённым алгоритмам и Unique games conjecture (гипотезе, из которой выводятся результаты о неприближаемости для многих NP-трудных задач).
	Александр Шень (Montpellier Laboratory of Informatics, Robotics, and Microelectronics и ИППИ РАН) Наверное, не нуждается в представлении. Специалист в области теории сложности.Автор многих замечательных учебников — таких, например, как «Программирование: теоремы и задачи». Также является редактором перевода (и, на самом деле, главным переводчиком) первого издания классического учебника Кормена, Лейзерсона, Ривеста «Алгоритмы: построение и анализ».
	Mario Szegedy (Rutgers University) Дважды лауреат Премии Гёделя, присуждающейся ежегодно за выдающиеся статьи в области theoretical computer science. Первый раз — за вклад в доказательство PCP-теоремы (вероятностно проверяемых доказательств) и её применение к результатам о неприближаемости, второй — за работы в области streaming algorithms.
	Ryan Williams (Stanford University) Тоже молодая звезда. Его недавний результат о том, что класс NEXP не содержится в классе ACC0, называют одним из самых значительных достижений в области схемной сложности за последние 20 лет. И это далеко не единственный его результат. Ещё, например, он показал, как найти максимальный разрез в графе быстрее полного перебора с неожиданным и элегантным использованием быстрого умножения матриц.

В общем, очень-преочень рекомендую.

Это продолжение поста про оффлайн алгоритмы упаковки.

Суть задачи: имеем полубесконечную полосу — как в тетрисе, только без game over'а, и конечный набор прямоугольников. Данные о прямоугольниках поступают в режиме реального времени; каждый новый прямоугольник необходимо немедленно разместить и больше не двигать с места. Цель — минимизировать общую высоту упакованных прямоугольников.
Это online-вариация задачи об упаковке прямоугольников в полуограниченную полосу (2 Dimensional Strip Packing, 2DSP).

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

Еще летом я запланировал эксперимент и написал статью Использование UML для эксперимента по эволюционной систематике прокариот, и косвенно о психологии ученых. Результаты по грубой обработки уже были готовы к концу лета (спасибо, mktums за помощь ).

Вот теперь образовалась пауза, и я добил эту тему, и представляю результаты.

Приветствую всех читателей!
Ниже идет моя точка зрения того, как я понял главу 14 из слайдов курса по Haskell у нас в университете.
Итак, сегодня мы поговорим о следующих двух темах:

• Принцип «Разделяй и властвуй»
• Работа с бесконеными потоками

Экспертов в этой области прошу комментировать и поправлять, если будут неточности. Буду рад ответить на вопросы в комментариях.

С недавнего времени у меня появилась настойчивая мысль, что профессиональное развитие сильно замедлилось и это хочется как-то исправить. Да, читаю книги, слушаю курсы, но в то же время приходит и понимание того, что возможно пришло время сменить работу, здесь вроде как все изучено, плавно уходим в рутину. Данная мысль сподвигла меня на рассылку своего резюме в несколько компаний — лидеров рынка. После прохождения собеседования в 3 из них, я решил, как водится внести свои 5 копеек в освещение обширной темы собеседования, а именно технических вопросов по Java коллекциям, с которыми приходится сталкиваться. Да, знаю, читатель скажет: «коллекции — избитая тема, сколько можно», но часть из приведенных ниже вопросов, я задавал своим знакомым разработчикам, которые занимают именно позиции разработчиков («крепких середнячков», по меркам недалекой от Москвы глубинки, которые уверенно справляются со своей работой на практике, а вот в теории скажем так есть пробелы, потому, что работа не требует решения каких-то нетривиальных задач, да и потому что не всем это интересно — изучать как внутри работает структура данных), вызывало растерянность. Думаю, что рассмотренный материал будет не очень интересен разработчикам выше уровня Junior (я попрошу их комментировать, дополнять и критиковать изложенный здесь материал), а вот Junior`ы уверен, найдут в этой статье интересное для себя.

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

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

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

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

1. Есть возможность удостовериться, что каждый подписант принадлежит к указанному кругу лиц.
2. Есть возможность проверить, что большинство подписей принадлежат разным лицам.
3. Нет возможности определить, кому именно принадлежит та или иная подпись.
4. Нет возможности определить, оставляло ли данное конкретное лицо свою подпись или нет.
5. Любой подписант может по своему желанию поставить вместо анонимной подписи персонализованную.
6. Любой анонимный подписант может впоследствии по своему желанию предоставить доказательства того, что именно он поставил подпись.

Система основана на асимметричной криптографии, алгоритмах цифровой подписи и сертификации ключей.

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

Предыстория

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

В этом году мы решили попробовать Microsoft Robotics Development Studio (MRDS), для продвижения которого Microsoft сформулировала спецификацию «MRDS Reference Platform» — набор оборудования и протокол управления «стандартным» роботом. Эта спецификация позволила бы роботолюбам создавать совместимых роботов и переносить между ними программы. По сравнению с аппаратным оснащением пылесоса, Reference Platform намного сложнее и мощнее: в спецификацию включён Kinect, три ИК-дальномера и два ультразвуковых, а также датчики вращения колёс (encoders). Реализацию MRDS RP пока что предлагает только фирма Parallax под названием Eddie (порядка £1000, не включая Kinect). Необычайное сходство Eddie с фотографиями робота-прототипа в спецификации MRDS RP наводит на мысли, что спецификация создавалась в тесном сотрудничестве с Parallax, иначе говоря — Parallax удалось добиться, что Microsoft приняли их платформу за эталонную.

Кроме разнообразия датчиков, Eddie обладает механически впечатляющей платформой (заявленная грузоподъёмность 20кг, а мощности моторов достаточно, чтобы толкать впереди себя складской погрузчик) и программируемым контроллером Parallax Propeller, т.е. критические куски кода можно зашить непосредственно в робота, а не только командовать им с компа.

Ровно месяц назад мы объявляли конкурс на создание приложения, реализующего несколько алгоритмов машинного зрения. Главным призом в этом конкурсе была поездка с нашей командой на Шри-Ланку для встречи либо конца света 21 декабря, либо Нового года (это уже как повезет). Но мы больше надеемся на Новый год и в любом случае постараемся организовать трансляцию с места событий.

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

Я и мои коллеги в Ivideon очень не хотели бы, чтобы кто-то из тех кто принял участие в нашем конкурсе пожалел о потраченном на него времени. И здесь речь идет о 9 потенциальных кандидатах, приславших работы.
Поэтому мы приняли решение, что 8 человек, которые по тем или иным причинам не заняли первое место — получат за свой труд мегапиксельную IP-камеру с поддержкой облака Ivideon на борту. Для тех кто не знает, это обычная IP-камера, в которой есть наш модуль, позволяющий напрямую подключать её к облаку Ivideon без дополнительных приложений и компьютеров. Мы не производим сами камеры. Мы предоставляем возможность встроить этот модуль всем производителям. Для удаленного доступа к такой камере не требуется внешнего IP-адреса и сетевых настроек вроде port-forwarding. Ну и она обладает всеми возможностями, которые предоставляет Ivideon. От записи видео в наше облако, до организации трансляции на своем сайте или в блоге. Очень надеемся, что эта камера станет достойной компенсацией за потраченное на наш конкурс время. Тем более помимо неё участники получили как минимум дополнительный опыт в разработке приложений видеоанализа.

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

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

print True if 1 > 2 else False

Четко и понятно «в лоб», с появлением его в python читал в блогах много рассуждений почему он такой, где же стандартный ? : подобный.

Давайте разберемся…

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

Прежде чем читать эту статью, нужно понимать, что такое декартово дерево по неявному ключу (это тема не одной статьи, поэтому об этом лучше почитать тут). Сжатие пространста — метод, используемый для сжатия на отрезке данных. Например, вместо того, чтобы хранить множество {1, 1, 1, 2, 2, 2, 3, 1, 1} будем хранить {1 x 3, 2 x 3, 3 x 1, 1 x 2}.
Теперь попробуем сжимать пространство с помощью такого метода и иметь возможность выполнять онлайн операции с любым отрезком.

Поворот растрового изображения на углы, кратные 90°, относительно геометрического центра изображения – задача тривиальная и решается без потери качества простым преобразованием координат каждого пикселя.

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

Ниже мы рассмотрим алгоритм прецизионного поворота растрового изображения на произвольный угол относительно произвольного центра с минимальными потерями.

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