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

У биоинформатиков нет никаких пробирок, реагентов, бактерий, белых халатов. Главные инструменты у них – ноутбук, ручка с бумагой или белая доска с маркером – в общем, всё как у программистов. Да и сама работа очень сильно похожа на работу в IT компании, а лаборатория – на небольшой отдел разработки. А в чем же тогда отличия? Что ж, попробую ответить.

Что будет в этой статье

Продолжаем цикл статей о создании файловой системы в ядре Linux, основанный на материалах курса ОС в Академическом университете .

В прошлый раз мы настроили окружение, которое понадобится нам, чтобы знакомится с ядром. Затем мы взглянули на загружаемые модули ядра и написали простой «Hello, World!». Ну и наконец, мы написали простую и бесполезную файловую систему. Пришло время продолжить.

Главная цель этой статьи научить файловую систему читать с диска. Пока она будет читать только служебную информацию (суперблок и индексные узлы), так что пользоваться ей все еще довольно трудно.

Почему так мало? Дело в том, что в этом посте нам потребуется определить структуру нашей файловой системы — то как она будет хранится на диске. Кроме того мы столкнемся с парой интересных моментов, таких как SLAB и RCU. Все это потребует некоторых объяснений — много слов и мало кода, так что пост и так будет довольно объемным.

Недавно на Coursera произошло примечательное событие — вышла дублированная версия курса «Финансовые Рынки» (Financial Markets) о самых азах финансов.



И примечательно оно потому как раньше дублированных курсов на платформе не существовало, а первый появился именно на русском языке. Во-вторых, сделано это было на частное пожертвование. И в-третьих, курс прочитал профессор Йельского университета, нобелевский лауреат по экономике 2013 года – Роберт Шиллер.

Добрый день. Многие знают и пользуются известной площадкой для онлайн образования Coursera.org. Я тоже принадлежу к их числу. Пройдя пару курсов, я стал интересоваться внутренней кухней. Я связался с несколькими преподавателями и попросил их дать письменное интервью. О том что получилось читайте далее.

Гитхаб продолжает расширять области своего применения — руководство компании видит Гитхаб в будущем не только как инструмент для программистов, но и как универсальное хранилище любых текстовых данных. На нём уже есть репозитории, в которых пишутся книги, законопроекты, публикуются статистические данные. А на прошлой неделе появилась возможность присвоить любому своему репозиторию идентификатор DOI. Это позволит ссылаться на данные или код из репозиториев Гитхаба в научных работах и статьях общепринятым в научной среде способом.

Иногда возникает необходимость ускорить вычисления, причем желательно сразу в разы. При этом приходится отказываться от удобных, но медленных инструментов и прибегать к чему-то более низкоуровневому и быстрому. R имеет довольно развитые возможности для работы с динамическими бибиотеками, написанными на С/С++, Fortran или даже Java. Я по привычке предпочитаю С/С++.

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

К счастью, у астрофизиков есть доступ к более мощным машинам, чем домашний компьютер. В общем, все данные были обработаны на системе с 8 тысячами процессоров. И то, разработка такой модели заняла около пяти лет. Сам проект получил название Illustris.

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

Причина побудившая автора к публикации

Первая версия описания алгоритма было послана мною в институт математики им. С. Л. Соболева Сибирского отделения РАН, откуда был прислан ответ что указанный алгоритм известен давно. Цитирую:

Одно из его первых упоминаний в книге Кереллера Nemhauser, Ullman, Discrete dynamic programming and capital allocation, Management Science, 15 p. 494-505, 1969.

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

В развязке фильма «Бегущий по лезвию» герой Рутгера Хауэра говорит, что видел многое, что люди не могут себе даже представить — космические битвы, пылающие боевые корабли — но разве так уж трудно вообразить всё это современному человеку, избалованному компьютерной графикой? В то же время, нас окружает множество вещей, которые мы никогда не сможем рассмотреть в деталях, в силу фундаментальных физических ограничений. Более того — мы и сами состоим из таких вещей. Впрочем, хорошая новость в том, что эти объекты можно смоделировать и визуализировать, используя развитый в настоящее время 3D-инструментарий. А если собрать команду, в которой будут не только трехмерные моделлеры, визуализаторы и дизайнеры, но и ученые, можно максимально приблизить результат к реальности.

Под катом первая часть рассказа о нашем опыте создания научно достверных моделей вирусов.

В последнее время в научных публикациях всё чаще упоминается алгоритм достижения консенсуса в распределенных системах под названием Paxos. Среди таких публикаций ряд работ сотрудников Google (Chubby, Megastore, Spanner) ранее уже частично освещенных на хабре, архитектуры систем WANdisco, Ceph и пр. В то же время, сам алгоритм Paxos считается сложным для понимания, хоть и основывается он на элементарных принципах.

В этой статье я постараюсь исправить эту ситуацию и рассказать об этом алгоритме понятным языком, как когда-то это попытался сделать автор алгоритма Лесли Лэмпорт.

Наступила полночь и Шехрезада продолжила позволенные речи

Для начала замечание к предыдущей статье — я там позволили себе неуважительно высказаться по поводу ASSERT — поясню свою позицию. Мне не очень нравится. что проверка в ASSERT проводится только на этапе исполнения, проверка на этапе компиляции эффективнее. Мне в личку сообщили о существовании конструкции, позволяющей сделать необходимые проверки именно на этапе компиляции (я проверил — действительно работает), думаю, что пост на эту тему скоро появится в песочнице.
Итак, мы продолжаем…
Как было сказано выше, регистры внешних устройств характеризуются расположением в адресном пространстве (тут мы уже определились) и составом управляющих элементов. Дело в том что многие управляющие элементы недостаточно велики для того, чтобы занять целое слово конкретного МК и, чтобы сэкономить адресное пространство, несколько управляющих элементов могут быть упакованы в один регистр. Такое решение позволяет также в определенных условиях несколько увеличить скорость работы программ, взаимодействующих с данным внешним устройством, потому и встречается весьма часто. В то же время данное решение вызывает определенные проблемы в отношении языка программирования, о которых мы и поговорим.

Определение

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

• блокировки (mutex);
• алгоритмы без блокировки (lockless, lock-free);
• транзакционная память.

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

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

Эта область довольно неплохо покрыта в десктопной среде — фильтры вроде ffdshow raw video filter и madVR позволяют делать практически всё, что может потребоваться для приятного просмотра. К сожалению, веб не может похвастаться аналогичным тулкитом, и вы либо наслаждаетесь всеми недостатками очередного видео на YouTube, либо открываете его во внешнем приложении вроде MPC-BE, что не очень удобно. А было бы неплохо иметь одну волшебную кнопку, активирующую фильтрацию в месте, где она и должна быть — в вашем браузере.

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

В последнее время на слуху феномен «муков» (MOOC) – массовых открытых онлайн курсов. Платформ для них создано большое множество.

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

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

В этом посте я поделюсь личными соображениями о том, куда движется онлайн образование на примере MOOC-ов, в том числе по мотивам посещения Coursera Partners' Conference, прошедшей 4 недели назад в Лондоне.

Приветствую, уважаемое Хабрасообщество!

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

Сейчас библиотека выложена с парой примеров на GitHub, а под хабракатом хотелось бы осветить некоторые тонкости её применения и часть внутренней логики. Буду рад, если моя библиотека поможет кому-то сэкономить n-ое количество времени и позволит избежать изобретения собственного велосипеда.

Кому интересно — добро пожаловать под кат.

Для кого эта статья

Данная статья составлена по материалам практики по курсу операционных систем в Академическом университете . Материал готовился для студентов, и ничего сложного здесь не будет, достаточно базового знания командной строки, языка C, Makefile и общих теоретических знаний о файловых системах.

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

После завершения разработки под OS X может остаться ощущение незавершенности — для полного счастья хотелось бы видеть свое приложение в каталоге, тем более, что это, пожалуй, лучшая площадка для продажи десктопных приложений. На эту тему есть статья времен Qt 4.8 в официальном блоге, и еще более старая на хабре. К счастью, больше нет необходимости пересобирать Qt, однако с приходом OS X 10.9 некоторые баги стали критичными, приходится выкручиваться.

Disclaimer: речь — о давно существующей функции, но, судя по комментам на Хабре, недооцененной, поэтому решил все-таки написать.

Google Chrome позволяет очень сильно ускорить рутинные задачи, связанные с различным поиском. используя адресную строку.

Например:

• "ru nightingale" показывает русский перевод «nightingale» в Google Translate
• "ан соловей" или "fy соловей" переводит «соловей» на английский там же
• "j click" открывает документацию по jQuery.click
• "m Лесная 6" открывает адрес адрес «Лесная 6» на Яндекс.Картах

Каждый программист должен написать свою cms, framework, mmorpg. Именно этим мы и займемся.
Демо

Перед прочтением статьи рекомендую посмотреть посты про splay-деревья (1) и деревья по неявному ключу (2, 3, 4)

Динамические деревья (link/cut trees) мало освещены в русскоязычном интернете. Я нашел только краткое описание на алголисте. Тем не менее эта структура данных очень интересна. Она находится на стыке двух областей: потоки и динамические графы.

В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока. Улучшенные алгоритмы Диница и проталкивания предпотока работают за и соответственно. Если вы не знаете, что такое поток, и на лекциях у вас такого не было, спешите пополнить свои знания в Кормене.

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

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