dfyz


Иван Комаров

Colorless green ideas sleep furiously


[sticky post]Здесь никого нет
dfyz
Поскольку ЖЖ, похоже, окончательно всё, а пографоманить иногда отчаянно хочется, свалил в фейсбук, как место с наибольшей плотностью движухи на квадратный сантиметр.

Архив майских прогулок
dfyz
Вынес сюда ссылки на отчёты о моих майских прогулках, чтобы не потерялось.

ГодДистанция, кмПопутчики
200430родители, wutfish
200628
200750er_v, Ирина Низовцева
200850torrio
200933torrio, codenamed, amogilnikov
201050torrio, queueman_as, Игорь Чевдарь
201142torrio, queueman_as, mimoidochi
201232codenamed, artem_zyryanov, Лена Меньшикова

CSEDays
dfyz
So the CSEDays 2014 conference (dubbed "Strings, Languages, Automata") is over, and I thought I'd write briefly about two things that fascinated me the most. I'm no expert on neither combinatorics on words nor pattern matching algorithms, so my understanding doesn't go beyond superficial, but here it goes anyway.

Dejean's conjecture

If you take a finite string over some finite alphabet and repeat it twice, you get a square (e.g., abc^2 = abcabc). Similarly, a string repeated three times is a cube (e.g., abc^3 = abcabcabc). It's not too hard to extend this operation to allow the exponent to be a rational number (e.g., abc^(4/3) = abca). In general, if X = Y^r (X and Y are strings, r is a number), then X is called an r-power.

What we can do next is start building infinite strings (the alphabet is still finite) that avoid r-powers for some given r (i.e. no substring of our infinite string is an r-power). The well-known Thue-Morse string over the binary alphabet, for instance, avoids cubes and all powers strictly greater than two. No infinite binary string can avoid squares, though, so we say that the repetitive threshold for the binary alphabet is 2 (put another way, RT(2) = 2).

Françoise Dejean's conjecture gives the value of RT for all alphabet sizes (RT(3) = 7/4, RT(4) = 7/5, RT(k > 4) = k/(k - 1)). The absolutely stunning thing about the conjecture is the sheer number of researchers it took to prove it for various values of k (strictly speaking, it's not a conjecture anymore as it was proved, but old habits die hard, I guess, and the old name still prevails). The final result for the remaining values of k was obtained just recently, in 2009.

The proof techniques get progressively more complex for each alphabet size, so I'm not sure a layman like me can grasp the more recent papers, but the 1984 one from Pansiot (k = 4) seems approachable. The only problem is that it's in French. :-)

Burrows–Wheeler Transform

The BWT is fantastically beautiful and extremely useful algorithmic technique. The idea seems deceptively simple: you take a string, sort its cyclic shifts, and then form a new string consisting of the last characters of the shifts (in sorted order). The non-trivial observation is that this transform is invertible, and the inverse, as well as the BWT itself, can be computed efficiently (the naive implementation requires quadratic time/space and is not of much interest).

I used to think the BWT was mostly used for data compression, but it turned out it can do much more than that:

1. The FM-index data structure based on the BWT allows you to build a full-text index for a large string (the go-to example is the human genome, as always) that is way more efficient than suffix arrays/trees/DAWGs.

2. You can solve the inexact string matching problem for short patterns, which is exactly what is needed for short DNA read alignment.

Майерс
dfyz
Сходил на широко известного в узких кругах дедушку Майерса, написавшего несколько классических книжек по сиплюсплюс, послушал про C++11/14. Дедушка Майерс внезапно оказался одним из самых крутых, если не самым крутым техническим докладчиком из тех, что я видел.

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

Во-вторых, Скотт прекрасно объясняет. За все три дня мне захотелось задать серьёзный вопрос по существу всего один раз, в остальном все непонятные моменты можно было прояснить самостоятельно, за 3 минуты написав простую программку (хотя вопросов из зала было множество, и половину вопрошающих хотелось убивать топором во имя добра, но не будет о грустном). Те темы, про которые лично мне было особенно интересно послушать (lambdas, move semantics, variadic templates), были объяснены особенно здорово.

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

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

goto win;
dfyz
В этом году у меня такое ощущение, что про SSL/TLS снимают какой-то остросюжетный сериал. Новые серии выходят чуть ли не каждый месяц, и в каждой сюжет закручен ловчее предыдущей. Для тех, кто не в курсе:

  1. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-1266

  2. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-0092

  3. http://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-0160

Наблюдать за этим праздником жизни невероятно увлекательно и поучительно. Единственное, что удручает, -- в многочисленных обсуждениях очень сложно отделить ценные мнения пионеров-дебилов ("Как можно в XXI веке всё ещё писать на C? Надо переписать на нормальный язык!") от комментариев действительно шарящих в теме людей (которые обычно не так многословны). Есть некоторые способы облегчить себе жизнь (например, подписаться в твиттере на условного @tqbf), но всё равно мне кажется, что в интернетах нужно срочно начинать вводить профилактические массовые расстрелы.

Розалинд всё
dfyz
Тем временем задачки в основной секции Розалинды подошли к концу (осталась какая-то неинтересная ботва в других секциях, которую надо будет на досуге методично дорешать).

Знающие товарищи, а подскажите, пожалуйста, есть ли какой-то шанс простому промышленному программисту пойти дальше решения модельных задачек и заняться биоинформатикой на досуге как-то более серьёзно (но так, чтобы это не превращалось в полноценную работу)? Мне вот очень понравилась идея делать code review, но что-то я не видел, чтобы она полетела дальше пилотного проекта.

И немного в сторону: давно хотел написать про отличный фильм Contagion ("Заражение" в русском прокате). В нём широчайшим образом раскрыты интересные темы:

  • как в кризисных ситуациях учёные оказываются бессильны перед шарлатанами;

  • как через социальные сети распространяются ложь и обман;

  • на какие поступки идут люди в экстремальных условиях (спойлер: на не очень красивые);

  • чем CDC отличается от WHO, и зачем обе эти организации нужны;

  • и наконец, просто под отличный саундтрек по всей планете за какие-то дни распространяется СТРАШНЫЙ ВИРУС ПАНИКА КАРАНТИН ЧРЕЗВЫЧАЙНОЕ ПОЛОЖЕНИЕ НАСЕЛЕНИЕ УПОЛОВИНИВАЕТСЯ ШОК ГДЕ ЖЕ ВАКЦИНА ЧЁРТ ВОЗЬМИ.

Кому такое интересно -- очень рекомендую посмотреть.

Re: Что было в 2013?
dfyz
+ded-moroz@

Привет!

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

1 attachment: report.pdf

Электрическая музыка без регистрации и смс (нужен совет)
dfyz
Вышедший на прошлой неделе (безумно офигенный) альбом Filteria – Lost In The Wild и фоточки типа таких от того же Filteria всё больше и больше передвигают меня от состояния "аааа, как же офигенно" к состоянию "аааа, я хочу понять, как они все это делают". Хочется какой-нибудь курс про то, как делать электронную музыку (не с целью потом её писать самому, а с целью разобраться, как типичный EDM-трек устроен внутри). Пока что нашёл отличный курс, который идеален со всех точек зрения, кроме одной: стоит тысячу долларов. На курсере ничего похожего, но бесплатного я не нашёл. :-/ Никто не знает, такое вообще бывает?

Rosalind
dfyz
Добрый коллега показал сайтик Rosalind с задачами по биоинформатике ("биотимус", как его метко окрестил ещё один коллега), и я уже третью неделю угораю по филогениям, вторичной структуре РНК и выравниванию строк с белками (благо, курс Cryptography II на курсере перенесли на середину февраля).

Лично для меня Розалинду идеальной убийцей свободного времени делают три вещи:
1. Почти каждая задача начинается с введения, в котором сообщается, какие реальные биологические процессы с её помощью моделируются. Поэтому даже тривиальные с алгоритмической/математической точки зрения задачки решаются с удовольствием, ибо есть возможность много нового интересного узнать про современную биологию и генетику. Мне это особенно актуально, потому что последнее моё пересечение с этими замечательными областями человеческого знания состоялось где-то так в десятом или одиннадцатом классе.
2. Создатели выстроили лучшую из виденных мной на обучающих сайтах игровую систему, которая затягивает с неимоверной скоростью. Все задачки объединены в одно общее дерево (чтобы начать решать задачу, нужно сначала решить всех её предков), за игровую активность дают левелы (примерно как на Project Euler), ачивки (решил определённое количество задачек из двух разных тем) и беджики (строковые алгоритмы 3 уровня).
3. Ну и наконец, очень приятно видеть задачки на строковые алгоритмы (хотя биоинформатика, конечно, далеко не только про это). Всякие суффиксные массивы/автоматы и Z-функции мне на ACM-контестах в своё время нравились больше всего, но меня всегда удручали притянутые за уши искуственные формулировки и полная неприменимость всех этих декомпозиций Линдона за пределами соревнований. А тут внезапно оказывается, что длинные строки над небольшими алфавитами (ДНК/РНК – 4 символа, белки – 20 символов) вполне себе существуют в реальной жизни, и есть целый вагон задач, которые биологи хотели бы над этими строками решать. Прямо душа радуется.

Страх и ненависть в репозитории
dfyz
У нас были три разных версии строк, два пакета для работы с Юникодом, три фреймворка для логирования, пара функций для скачивания страниц по HTTP и целое множество контейнеров, а также libxml, glib, OpenSSL и протобуфы. Не то чтобы это всё нужно было для сборки проекта, но если уж начал собирать зависимости, то становится трудно остановиться. Единственное, что вызывало у меня опасения, — это boost. Нет ничего более беспомощного, безответственного и испорченного, чем программисты, использующие boost. Я знал, что рано или поздно мы перейдём и на эту дрянь.

?

Log in