Алгоритмы *

Сегодня мы открыли запись на 10 новых бесплатных онлайн-курсов (MOOC) по предметам от линейной алгебры и дискретных структур до археологии фольклора и инвестиционного банкинга. В числе авторов – преподаватели и научные сотрудники из МФТИ, НИУ ВШЭ, МИАН, ГАИШ МГУ, СПбГУ и ИБ, МИСиС, ЕУ СПб. Большинство новых курсов разрабатывается по итогам конкурса Stepic Challenge, о котором мы писали ранее.

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

Список новых курсов:

1. Дискретные структуры (7 марта 2015)
2. Linear Algebra: Problems and Methods (April 3, 2015) (курс на английском языке)
3. Химическая эволюция Вселенной (15 апреля 2015)
4. Компьютерная графика: основы (9 марта 2015)
5. Основы статистики (15 февраля 2015)
6. Инвестиционный банкинг изнутри (6 апреля 2015)
7. Археология фольклора: мифологические мотивы на карте мира (2 февраля 2015)
8. Управление интеллектуальной собственностью. Основы для инженеров (20 апреля 2015)
9. Журналистика и медиаграмотность (31 марта 2015)
10. Базовый курс подготовки к ОГЭ по математике (1 февраля 2015)

Объект: веб-форма входа в систему.
Дана задача: усилить защиту аккаунта пользователя от подбора простого пароля к его аккаунту, используя минимум средств.

Что такое минимум средств? Это не использовать таблицы-справочники для блокировки по IP-адресу и User-Agent. Не использовать лишние запросы к системе, не захламлять систему авторизации лишними циклами.

И, выполнить совершенно волшебное требование — даже если бот введет нужные логин и пароль… не дать ему войти, а вот реального пользователя впустить.

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

ConcurrentQueue можно отнести к lock-free конкурентным структурам данных. В ее реализации нет блокировок (lock, Mutex…) и реализована она с использованием:
— классической функции CompareExchange;
— SpinWait
— volatile (используется как memory-barrier)
В основу ConcurrentQueue заложена структура ring-buffer (кольцевой буфер).

Привет всем. Я уже однажды писал про Distance Field и приводил реализацию «эвристическим» кодом, дающую неплохую скорость: «Честный glow и скорость».

Зачем он нужен?

DField можно применять:

• Для значительного повышения качества шрифтов
• Для эффектов например горения контура. Один из эффектов я приводил в своей предыдущей статье
• Для эффекта «metaballs» но в 2д и для любых сложных шейпов. (возможно я когда-нибудь приведу пример реализации этого эффекта)
• А в данный момент DField мне нужен для качественного сглаживания углов и удаления мелких деталей.

И если в первых двух случаях мы можем заранее вычислить DField, то для других эффектов нам нужно просчитывать его в реальном времени.
В статье будет рассмотрен наиболее популярный, я бы сказал классический Chamfer distance (CDA) с кучей картинок, объясняющих принцип его работы, а так же рассмотрен двухпроходный алгоритм на GPU.
Оба алгоритма реализованы в демонстрационных программах на FPC.

Все началось с одного собеседования, которое и натолкнуло меня к написанию данной статьи. Довольно большая часть разработчиков на платформе .Net не понимает базовые вещи, хотя и использует их повседневно, например lock-ом оборачивают все методы, использующие ConcurrentDictionary, хотя можно было бы обойтись обычным Dictionary<>.

В науке существуют 3 основных способа реализации конкурентных структур данных:
• Lock-free структуры данных;
• Fine-grained блокировка;
• Transactional memory implementation(транзакционная память);

ConcurrentDictionary<TKey, TValue> — это thread-safe аналог Dictionary<TKey, TValue>. В его основе лежит, так называемый Fine-grained блокировка.

Здравствуйте!
Всего месяц назад в издательстве Addison-Wesley вышла книга Александра Степанова — русско-американского учёного в области IT — «From Mathematics to Generic Programming».



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

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

• Введение
• Свойства особых точек
• Детекторы углов
  
  • Moravec
  • Harris
  • Shi-Tomasi
  • Förstner
  • SUSAN
  • Trajkovic
  • FAST
  • CSS
  • Детектор, основанный на глобальных и локальных свойствах кривизны
  • CPDA
• Выводы

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



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

Итого, мы оперируем тремя базовыми параметрами:

• Приемлемым временем ожидания
• Минимально необходимым количеством источников
• Дополнительным временем ожидания

С 4 по 12 декабря 2014 года проходит беспрецедентная акция Час Кода в России. — www.coderussia.ru

На Хабре даже об этом писали.



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

Добрый день, друзья!

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

Доброго времени суток.
В этом коротком посте хотел показать простой способ поиска объектов по цвету с OpenCV.

Для экспериментов использовал камеру Logitech WebCam C270

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

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

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

Думаю, что пришла пора рассказать об этом на Хабрахабре, создав статью о разрабатываемой коллекции ресурсов, которая будет постоянно расширяться и пополняться, и будет служить, по сути, русскоязычным аналогом страницы "Where can I find examples of good Mathematica programming practice?" на сайте Mathematica at StackExchange.com.

Статья будет состоять из 3х частей:
Пальчиковые деревья (часть 1. Представление)
Пальчиковые деревья (часть 2. Операции)
Пальчиковые деревья (часть 3. Применение)

Пальчиковые Деревья как Последовательности

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

Привет, друг! В этот раз я опять подниму вопрос о графике в ААА-играх. Я уже разобрал методику HDRR (не путать с HDRI) тут и чуть-чуть поговорил о коррекции цвета. Сегодня я расскажу, что такое SSLR (так же известная как SSPR, SSR): Screen Space Local Reflections. Кому интересно — под кат.

Предпосылки и мировая практика

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

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

1. Разработанная группа стандартов должна охватывать все отрасли и формировать надотраслевой «зонтик».
2. Разработанная группа стандартов должна обеспечивать возможность качественного скачка технологического и инновационного развития государства, и в первую очередь, приоритетных направлений развития, таких как:
2.1. Компьютерный инжиниринг, промышленный дизайн и инновационный инжиниринг автоматизированных систем процессного управления деятельностью и производством.
2.2. Наилучшие доступные технологии, в том числе, технологии аддитивного производства.
2.3. «Зелёные» и ресурсосберегающие технологии.
2.4. Интегральный менеджмент больших социотехнических систем.
3. Решать стратегические отраслевые задачи, такие как:
3.1. Разработка комплексной стратегии развития Наилучших Доступных Технологий;
3.2. Формирование требований для управления жизненным циклом изделий;
3.3. Создание экосистемы в области инжиниринга.
4. Формировать основу для международной и межгосударственной стандартизации.
5. Идеологической основой для разработки стандартов должен быть методологический подход на основе «Системного анализа и инженерии».
6. Обеспечение комплексного анализа в рамках жизненного цикла объектов исследования, таких например как:
6.1. Сложные инженерные комплексы и объекты жизненно, критически важной инфраструктуры энергетики и оборонного комплекса;
6.2. Электроника, прецизионное машиностроение, биоинженерия и лазерные технологии;
6.3. Строительство инфраструктурных объектов;
7. Обеспечение анализа и моделирования кибер-физических систем и био-кибернетических систем.

(Вычислительная машина с универсальной архитектурой)

Сказка ложь, да в ней намек…

• Найти Декарта;
• В стране Лилипутов;
• Бактериологическая почта;
• Арифмометр в юбке;
• Компьютер из маленьких фей.

Найти Декарта

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

Среди задач по программированию часто попадаются такие: дана последовательность однотипных элементов (обычно это числа), требуется за один проход по ней найти какую-нибудь характеристику (среднее квадратическое отклонение, количество минимальных элементов, непрерывный участок с наибольшей суммой...) Дополнительное ограничение — последовательность может быть очень длинной, и в память не поместится. Других ограничений на элементы последовательности, обычно, не накладывается.
С этими задачами всё, более или менее, понятно: нужно найти то, что на мехмате МГУ называют «индуктивным расширением» искомой функции, и реализовать её вычисление. Если найти не удалось (требуемый объём памяти слишком велик), то задача не решается.
Но попадаются и другие задачи. В них есть дополнительные ограничения на элементы последовательности в совокупности, и эти ограничения приходится существенно использовать для решения (и проверять их не надо). Простейшая такая задача выглядит так:

Задача 1. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число

Решение очевидно: просматриваем числа, находим их количество K и сумму S. По условию, N=K+1, значит, сумма чисел от 1 до N будет равна (K+1)*(K+2)/2, и пропущенное число равно (K+1)*(K+2)/2-S. Если вы почему-то боитесь переполнений, то работайте с беззнаковыми числами (там переполнения не страшны — но будьте осторожны при вычислении (K+1)*(K+2)/2 :) ), или вместо суммы ищите XOR всех чисел.

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

Наиболее распространенные из таких задач — определение количества взвешиваний для выявления фальшивой монеты, если:

1) неизвестно какая она по весу;
2) известно, что она легче/тяжелее остальных.

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