Алгоритмы *

Сегодня Яндекс присоединился к ЦЕРНу. Наше партнёрство с Европейским центром ядерных исследований переходит на новую стадию развития: у ученых из ЦЕРНа появится доступ к технологии машинного обучения Матрикснет от Яндекса, а также новым вычислительным мощностям. А Яндекс становится ассоциированным членом европейского Центра ядерных исследований в рамках проекта CERN openlab. Кроме него членами openlab являются Intel, HP, Oracle, Siemens и Huawei.

Сотрудничество Яндекса с Центром началось в 2011 году, когда мы впервые предоставили ЦЕРНу свои серверные мощности. А в апреле прошлого года наши разработчики создали поиск по событиям эксперимента LHCb. LHCb — один из четырёх основных экспериментов ЦЕРНа и один из примеров того, насколько важными в современной науке стали не только данные опытов, но и их обработка. В ходе опытов LHCb исследуются соударения b-кварка (b от английского beauty, по-русски его называют прелестным). Объём информации об этих событиях только за год достигает тысяч терабайт. Благодаря созданнному нами поисковому индексу у учёных ЦЕРНа появилась возможность мгновенно получать нужную информацию.

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



Мы расспросили Андрея Устюжанина, руководителя проекта партнёрства с ЦЕРНом в Яндексе, о подробностях того, для чего именно ЦЕРНу нужна помощь Яндекса и как устроена работа с данными экспериментов. Смотрите видео и читайте более подробную текстовую версию после ката.

Как заядлый читатель HAD я был заинтересован этим постом, описывающим способ взлома аудиокапчи MintEye. Графическая версия также выглядела довольно интересно, так что я подумал, что будет забавно взломать и её.

Вот один из примеров графической капчи MintEye:

В комментариях к моему посту про курс 6.002x MITx мне задавали вопрос — пригодилось ли изученное в жизни. И я отвечал — да, конечно, вот тут утром пока зубы чистил, RC-константу посчитал… Но пруфов не было. С тех пор я закончил еще два курса — UC Berkeley CS188.1x Introduction to Artificial Intelligence (открыта регистрация на 18 февраля) и MITx: 6.00x Introduction to Computer Science and Programming. И если после CS188.1x я просто был полон эмоций и не знал, куда бы приткнуть свежеполученные знания (кроме как решить задачу о ходе коня), то после прохождения 6.00x подвернулся случай блеснуть.

Приветствую вас еще раз, дорогие хабражители!
_{Эта статья выкладывается в разгар сессии, так что я могу пропасть из комментариев.}

1. Первое знакомство

2. Симуляция и простейший бот

Сегодня разберёмся с настройками симуляции и посмотрим на простейшего бота (или робота, как вам будет удобно). Нет, я не буду досконально рассматривать интерфейс программы – это будет вашим домашним заданием:-) И да, само понятие «генетический алгоритм» четко расписано в Википедии, поэтому опустим это объяснение.

Предыстория

Пару лет назад, в процессе выполнения одного проекта, связанного с выделением и сопровождением движущихся объектов, было просмотрено немало алгоритмов вычитания фона, и в итоге одним из самых интересных оказался тот, о котором дальше и пойдет речь. Основной его недостаток — куча патентов, которыми он защищен. Но одно из несомненных достоинств — наличие библиотеки под Linux, которую разрешено использовать в некоммерческих проектах. На странице с его описанием можно найти эту самую библиотеку, а также demo-программы под Windows и Android, ссылки на патенты (где и можно найти основные описания алгоритма) и прочую интересную информацию.

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

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

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

На первый взгляд это может показаться тривиальной задачей, не так ли? Если сторонами треугольника являются x и y, то, формально, формулой для вычисления гипотенузы будет:

sqrt(x*x + y*y)

Это работает теоретически, но на практике данный подход может приводить к ошибке. Если значение x достаточно велико, то вычисление x*x может привести к переполнению типа данных (ни один тип данных от этого не застрахован, если не рассматривать длинную арифметику), и результатом вычислений будет бесконечность.

Как и в прошлом году, в 2012-2013 году проводится Заочная олимпиада ФУПМ по программированию. Подробности на сайте judge.mipt.ru

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

Будут задачи разного уровня от самых простых до совсем сложных, чтобы всем было интересно. Победители получат призы и сувениры от факультета и спонсоров. Турнир доступен до 18 февраля.

Составителями контеста являются тренеры и часть состава команд MIPT Waterogers, золотых медалистов ACM ICPC 2011-2012 годов и MIPT Lambda, финалистов ACM ICPC 2012-2013. Все мы являемся аспирантами и выпускниками факультета управления и прикладной математики МФТИ.

Желаем успехов и надеемся, что задачи вам понравятся!
P.S. Вопросы задавайте через проверяющую систему.

1. Пролог

Недавно я прочитал замечательную статью [1]. В ней автор рассказывает о том, что не всегда вычислительные машины были двоичными. На заре компьютерной эры существовали машины, которые использовали десятичную и троичную систему счисления.
Десятичная система удобна человеку, но ее достаточно сложно реализовать на существующей элементной базе. Кроме того, десятичная система подвержена ошибкам в результате искажения сигнала при передаче. Троичную систему реализовать не на много сложнее двоичной ([2]), но она способна дать как минимум три преимущества.

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

Я обсудил свои затруднения с девушкой-гуманитарием, и спросил, какие ей известны способы ориентации в пространстве. По её словам, в Лондонском музее науки она застала экспозицию, посвящённую ориентации муравьёв по виду вертикально вверх над головой. Посетителям предлагалось взять зеркало и идти по комнате, разглядывая в это зеркало узоры на потолке и ориентируясь лишь по ним. (Карта потолка прилагалась.)

Я решил проверить: что видит на потолке склада мой робот?

Я начну с провокационного заявления — «биологи не публикуют детали своих исследований». Казалось бы столько статей, столько исследований… но где описание и детализация информации, которая получена? Её в принципе нет. А статьи без такой информации пусты и спорны. Каждый нахваливает свой метод, но много ли кто озаботился верификацией чужих данных, а главное смог ли он её сделать?

Можно лишь приветствовать появление таких биоинформационных баз как NCBI genomes и PDB, в которые исследователи помещают данные о секвенированных геномах и структурах РНК, белков. И главное, некоторые ученные прежде чем опубликовать статью, прежде помещают данные в биоинформационные базы.

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

Конечно, так оно выглядит только для таких дилетантов как я. У настоящих же профессионалов все как в аптеке. Поэтому можете не утруждать себя ответом на эти пафосные заявления. Мы просто поговорим как выглядит биоинформатика в её частных областях глазами дилетанта. Но может и вас эта история к чему нибудь побудит.

Мы поговорим ниже о построение дерева эволюции согласно Дарвину, посмотрим на сколько это справедливо и таки я в итоге дам полное дерево (в рамках имеющейся информации) эволюции бактерий на основании самых консервативных генов тРНК. И дам пояснение о методе построения такого дерева.

Специалистам в биоинформатике рекомендую читать с раздела №5, пропустив весь мой пафос.

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

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

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

Честно говоря, я не ожидал такого количества решений: за 24 часа было прислано 265 решений, из которых после удаления повторных отправок осталось 183.

Из 183 решений у 11 был превышен допустимый размер решения, в 19 случаях — не удалось скомпилировать (об этих ошибках подробнее ниже). Далее 47 дали неправильные ответы на простых тестах (1..1000000), 8 не успели посчитать ответ за минуту (образец решения из условия задачи для 1млн работал 5 минут 36 секунд).

На сложных тестах — 5 решений выдали неверный ответ, и 12 — не уложились в одну минуту. 86 — успешно прошли все тесты.

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

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

Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке:

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

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

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

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

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

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

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

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

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