Алгоритмы *

Итак, если еще не устали от цикла «Hello, RNA World» — ловите последнюю статью сезона :)

В прошлой статье я обосновал, почему следует (или хотя бы целесообразно) отказаться от оценки энергии как целевой функции. Если кто не в курсе — целевая функция, это такая придуманная нами функция, по которой можно оценить приближаемся мы к поставленной нами цели или нет, т.е. «правильно» сворачивается РНК или нет.

Если энергия — это мало репрезентативная цель, тогда что более стабильно/чётче указывает куда двигаться? Если бы у нас была абсолютно формализованная и точная цель — это уже означало бы, что мы задачу решили, т.к. сама формализация целевой функции — есть не что иное как полноценное понимание процесса.

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

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

Но вначале хочу обратиться к специалистам в этой области:

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

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

Я даю произвольную (реально существующую) первичную последовательность до 100 нуклеотидов. Указываю все водородные связи которые нужно образовать. Вы на выходе даете мне файл .pdb, в котором третичная структура из указанной первичной последовательности и где образованы все требуемые водородные связи. Ни каких других требований.


Прошу или показать, что это просто или ответственно подтвердить, что эта задача скажем за неделю (или другой разумный срок) — не решается.

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

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

Изучая язык Haskell, я в очередной раз встал перед проблемой поиска какой-нибудь задачи для отработки новых навыков. После непродолжительных раздумий решено было реализовать написанный давным-давно на python алгоритм поиска в ширину для задачи о переправах миссионеров и каннибалов. Решение показалось мне довольно лаконичным, посему я решил поделиться им с людьми (а заодно и выслушать критику).

Интересующихся прошу проследовать под кат.

Это продолжение статьи Часть №1. Введение в биовычисления по сворачиванию. От белков к РНК. Здесь мы опишем ковалентные и водородные связи математически. Посмотрим какие углы мы будем вращать у РНК для сворачивания. И прикоснемся к вопросу «а в чем трудность то?»

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

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

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

Но введения хватит, далее с корабля на бал…

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

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



Вариантов реализации генератора псевдослучайных чисел достаточно много: Yarrow, использующий традиционные криптопримитивы, такие как AES-256, SHA-1, MD5; интерфейс CryptoAPI от Microsoft; экзотичные Chaos и PRAND и другие.

Но цель этой заметки иная. Здесь я хочу рассмотреть особенность практической реализации одного весьма популярного генератора псевдослучайных чисел, широко используемого к примеру в Unix среде в псевдоустройстве /dev/random, а также в электронике и при создании потоковых шифров. Речь пойдёт об LFSR (Linear Feedback Shift Register).

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

Введение, или зачем нужны синтаксические анализаторы

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

Эта часть посвящена базису, общей теории computer science. Возможно, что это даже преподаётся в школах/вузах России. Самая мякота пойдет со второй части.

Итак, зачем же кому-то может понадобиться писать парсер и что вообще это такое? Парсер — это код, который наделяет входящий набор символов семантическим смыслом. То есть, происходит анализ этих символов, и на основе этого анализа программа понимает как интерпретировать эти буквы и цифры. Простой пример — «1+2», после или во время процесса парсинга знак "+" это не просто символ плюса, но обозначение бинарноого оператора сложения, а в "+3" это унарный оператор знака числа. Большинству людей это очевидно, машине — нет.

Парсеры используются всюду — в Word'e для анализа приложений, словоформ, формул, etc; практически на любом сайте при валидации входных данных: email'а, телефонного номера, номера кредитки; конфигурационные файлы; сериализованные данные (например, в xml); во многих играх — скриптовые ролики, скрипты ИИ, консоль. В общем, это неотъемлемая часть computer science.

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

Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Отдельные игры других серий принадлежат к классу NP, а некоторые игры — к классу PSPACE.

Добрый день, Хабр!

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

1. Рекурсивные функции — что это?

Доброго времени суток, коллеги.
Этой статьей я продолжаю цикл посвященный EvoJ — Java фреймворку для решения задач генетическим алгоритмом.
В своей предыдущей заметке я познакомил читателей Хабра с основными принципами работы с EvoJ.

Сегодня мы рассмотрим, как при помощи EvoJ можно решить задачу упаковки в контейнеры.

Закончив изучение Таненбаума и ковыряние ядра Linux решил, что надо заняться чем-то дельным. По личным мотивам решил переделать ядро minix3 под планирование в жёстком реальном времени. Множество существующих алгоритмов планирования ввели меня в уныние, тем более, что хочется сделать ОС максимально универсальной и гибкой. Зацикленность на клиент-серверной модели привели к идеи о вынесении из ядра ОС механизмов планирования и разделение процессов на группы, управляемые: каждая своим планировщиком (в режиме ядра оставить только обработку deadline).
Основная проблема, которая стала очевидной сразу же — это выбор математической модели для построения алгоритма планирования. Очевидно, что подход разделения общего ресурса можно рассмотреть в аналогии с сетевыми протоколами разделения общего физического пространства.

Недавно, 19 декабря 2011г, Австралийское бюро по безопасности на транспорте выпустило отчёт об авиационном происшествии с самолётом А-330 (б/н VH-QPA) авиакомпании Qantas, которое произошло 7 октября 2008г.


(фотография Stefan Roesh planepictures.net)

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

Как вы наверно помните Яндекс с 22 октября по 22 декабря проводил конкурс Интернет-Математика (анонс был здесь, страница конкурса здесь). Сейчас мы уже подвели итоги конкурса и определили призеров:

1й приз: keinorhasen team, Botao Hu (Hong Kong University of Science and Technology), Nathan N. Liu (Hong Kong University of Science and Technology), Weizhu Chen (Microsoft Research Asia, Hong Kong University of Science and Technology)

2й приз: mmp team, Михаил Фигурнов (Московский Государственный Университет), Александр Кириллов (Московский Государственный Университет)

3й приз: S-n-D team, Сергей Гуда (Южный Федеральный Университет), Денис Рябов (Южный Федеральный Университет)

По итогам конкурса на одной из ведущих конференций по веб поиску WSDM 2012 был проведен семинар WSCD 2012 (на странице можно ознакомиться с отчетами участников).

Ждите анонсов следующих конкурсов

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

Постановка задачи

Пусть нам задан массив A[i], на который поступают запросы вида:

• посчитать сумму на отрезке [L; R] (позже, мы поймем, что аналогично можно вычислять функции min, max, gcd и др.
• добавить к элементу A[i], delta

Наивная реализация

Мы можем предрасчитать массив частичных сумм, а именно:

 for(int j = 0; j < i; j++) B[j] += A[i];

и тогда на запрос суммы [L; R], мы будем возвращать B[R]-B[L-1] за . Однако на запрос изменения, потребует пересчета частичных сумм (содержащих этот элемент) и в худшем случае составит асимптотику порядка , что не есть хорошо.

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

Здравствуйте, коллеги!

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

Вот уже пару лет я виде хобби разрабатываю Java-фреймворк EvoJ посвященный ГА. Когда я только начинал работу с ГА самое большое неудобство представляла необходимость векторизации переменных составляющих решение, поэтому в своем фреймворке я постарался сделать векторизацию переменных прозрачной для программиста, возложив всю грязную работу на плечи фреймворка. Кроме того, так как ГА очень хорошо поддается распараллеливанию, я постарался сделать переход к многопоточности не менее легким.

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

Одна из моих любимых тем в программировании – эволюционные вычисления и генетические алгоритмы в частности. Пару лет назад я поднимал эту (в целом уже заезженную) тему на Хабре, но сейчас глядя на то видео немного стыдно – слишком уж туманно и сумбурно было объяснение.

Сегодня я постараюсь объяснить генетические алгоритмы проще и нагляднее, а заодно рассказать вкратце о прототипе очень простого JavaScript-фреймворка для распределенных генетических вычислений degas.js. В двух словах – degas.js запускает генетический алгоритм в виде «треда» в браузере клиента используя web workers и обменивается информацией о полученных в ходе эволюции индивидуумах с сервером и другими клиентами с помощью web sockets. Сервер использует node.js.

Degas.js пока в супер-зародышевом состоянии, функционал еще примитивен, а код некрасив, но если кто-то захочет присоединиться к разработке – было бы здорово.

Я долгое время думал, что написать сортировку массива слиянием так, чтобы она не использовала дополнительной памяти, но чтобы время работы оставалось равным O(N*log(N)), невозможно. Поэтому, когда karlicos поделился ссылкой на описание такого алгоритма, меня это заинтересовало. Поиск по сети показал, что про алгоритм люди знают, но никто им особо не интересуется, его считают сложным и малоэффективным. Хотя, может быть, они имеют в виду какую-то «стабильную» версию этого алгоритма, но нестабильная при этом все равно никому не нужна.

Но я все-таки решил попробовать.

Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

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

Кому интресно, прошу под кат.