Алгоритмы *

Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно съездили, как вы могли видеть.

Я — Макс Ахмедов. Мне предложили поделиться с общественностью, что представляют собой подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти здесь. К слову, это наиболее простая из трёх задач в тот день :-)

Легенда

В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче д’Эсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.

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

Такая вот захватывающая история.

Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.

Прошел первый раунд отбора участников в школу программистов HeadHunter, анонс на хабре
Где после заполнения анкеты предлагалось решить 5 задачек

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

Недавно Реймонд Чен завершил серию постов, начатую ещё полтора года назад, и посвящённую управлению виртуальной памятью безо всякой поддержки со стороны процессора: Windows до версии 3.0 включительно поддерживала реальный режим 8086. В этом режиме трансляция адреса из «виртуального» (видимого программе) в физический (выдаваемый на системную шину) осуществляется бесхитростным сложением сегмента и смещения — никакой «проверки доступа», никаких «недопустимых адресов». Все адреса доступны всем. При этом в Windows могли одновременно работать несколько программ и не мешать друг другу; Windows могла перемещать их сегменты в памяти, выгружать неиспользуемые, и по мере необходимости подгружать назад, возможно — по другим адресам.

(Интересно, всегдашние холиворщики «это была графическая оболочка, а не операционная система» в курсе об этих её необычайных способностях?)

Предвидя негодование по поводу использования слова «креатив», спешу заметить, что в контексте этой статьи трудно использовать синоним. Честно.
Основная мысль — алгоритмизировать можно абсолютно любой мозговой процесс. Я взял рекламу в качестве примера для доказательства потому, что:

1. Понять и оценить интересную рекламу может каждый человек;
2. Реклама сильно завязана на творчестве и нестандартном мышлении, которое обычно представляется хаотичным и слабо поддающимся алгоритмизации;
3. Я просто очень сильно люблю рекламу. И алгоритмы.

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

За последнюю неделю Хабр пополнился сразу несколькими статьями об игре «Жизнь». Что ж, тогда и я поделюсь своими наработками по этой теме.

Предисловие

Минувшим летом мне довелось побывать на летней школе по параллельному программированию, проводимой НГУ. В рамках школы каждый студент должен был подготовить какой-либо проект по одной из тематик, озвученных на лекциях. Меня заинтересовали клеточные автоматы. У меня первая ассоциация при фразе «клеточный автомат» это именно «Жизнь».
Я понимал, что никому не будет интересно наблюдать за черными клеточками, живущими на экране. Да и слишком просто это для такого проекта. Нужно было придумать что-то принципиально новое. Я решил расширить диапазон своих мыслей и выйти за пределы двухмерного пространства. В прямом смысле. Я подумал, а почему бы не сделать эту игру трехмерной? Ведь это гораздо интереснее!

Есть такая штука — машина Тьюринга. Представляет собой простейший компьютер, однако писать под него хуже, чем на brainfuck'е. Решил я тут на днях побаловаться, но делать интерпретатор — не спортивно, да интерпретаторов этих — вагон. Потом меня посетила еще более странная идея — а чего бы не сделать это на Асме? (я его знаю паршиво, как раз решил потренироваться, так что сильно не пинайтесь).

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

Второй этап я собирался начать со сворачивания тРНК. Тут оказались некоторые проблемы. С другой стороны, есть интересный алгоритм CRA, который должен помочь решить мне эти проблемы. Он сложный и я его не понимаю. Но он реализован в некоторых ПО в основном для Linux. Что есть большое фи. В общем обо всем по порядку.

P.S. Ищу тех кто понимает математику и сможет помочь мне разобраться с алгоритмом CRA. С другой стороны, нуждаюсь в помощи тех кто использовал Gromacs.

Немецкий учёный Штефан Рафлер создал интересную модификацию «Жизни» — клеточного автомата, придуманного в 1970 году Джоном Конвеем, в которой вместо дискретной прямоугольной сетки жизнь развивается в непрерывной среде. «Клетки» в ней имеют форму дисков, планеры могут летать в любых направлениях и водить хороводы — получается совершенно завораживающая картина.



Вот слайд-шоу с кратким описанием алгоритма, документ с более глубоким погружением в детали и исходники.

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

Ну да, ещё и с мутациями. Моделировать, так моделировать.

Подробности, как водится, под катом.

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

Моя реализация здесь. На картинке изображено 10! = 3628800, хотя всех деталей, разумеется, не видно.

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

Вот так выглядит 700:


По расположению точек несложно заметить, что всего их здесь 7*5*5*2*2.

Далее описание того, как это работает.

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

Я задумался об игре «Жизнь», которую на Хабре не так давно вспоминали. Мне стало обидно за несчастные клетки, которые живут и умирают в зависимости от одних только начальных условий, и ничего сами для своего выживания сделать не могут. В результате я придумал расширение для правил игры, с которым можно моделировать не только изменение численности популяции, но и естественный отбор внутри неё.

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

Как и обещал, пишу продолжение статьи, посвященной обучению на курсе Algorithms.

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

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


Затем, чтобы помогать водителям непосредственно во время движения, мы добавили в мобильные Яндекс.Карты (и, как следствие, в Яндекс.Навигатор) автоматическое перестроение маршрута. Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.

Собрав на десктопе и в мобильном информацию про «сейчас», мы перешли к решению вопроса «а как будет потом?»:


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



Неделю назад на Яндекс.Картах появилась возможность посмотреть изменения пробок в ближайший час — следующий наш шаг в решении вопроса про будущее. Для тех, кто в этом году не смог приехать на Yet another Conference, мы сегодня расскажем, что у нашего прогноза внутри, и как оно там оказалось.

Национальный институт стандартов и технологий США (NIST) выбрал победителя в конкурсе криптографических хэш-алгоритмов для стандарта SHA-3. В нём участвовало 64 претендента. Пять финалистов конкурса определились почти два года назад. Победителем стал алгоритм Keccak (читается «кэтчэк» или «кетчак» — устоявшегося варианта русского написания и произношения пока нет), созданный командой криптологов из Италии и Бельгии.

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

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

Представляю вашему вниманию заключительную статью из трилогии «Восстановление расфокусированных и смазанных изображений». Первые две вызвали заметный интерес — область, действительно, интересная. В этой части я рассмотрю семейство методов, которые дают лучшее качество, по сравнении со стандартным Винеровским фильтром — это методы, основанные на Total Variaton prior.
Также по традиции я выложил новую версию SmartDeblur (вместе с исходниками в open-source) в которой реализовал этот метод. Итоговое качество получилось на уровне коммерческих аналогов типа Topaz InFocus. Вот пример обработки реального изображения с очень большим размытием: