Алгоритмы *

Небольшая иллюстрация того, как на языке C# реализовать монаду Maybe и зачем это вообще нужно. Смотреть видео рекоммендуется в разрешении 720p.



Сопутствующую статью можно найти тут (англ. яз.). Комментарии приветствуются!

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

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

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

Думаю, никому не нужно объяснять, насколько широко в играх (и не только) используются гексагональные сетки. Как для заданной шестиугольной ячейки найти координаты ее центра и вершин — достаточно очевидно. Обратное же преобразование (т.е. поиск ячейки, в которую попала данная точка с координатами x и y) уже не столь тривиально. О нём и пойдет речь в данном топике.

Эта статья продолжение двух других Интересные результаты о эволюционной систематике прокариот или «многовидовое происхождение», Геномы секвенированных организмов — ошибки в базах.

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

С другой поставить новый эксперимент. И было бы желательно привлечь к этому тех кто интересуется подобными вещами. Если у вас нет времени — может у вас есть свободное процессорное время :)?

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

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

В статье показывается на сколько массовы ошибки геномов, находящихся в NCBI и рассказывается как самому в этом убедится, и некоторые способы исправления.

На хабе появилось несколько топиков об «однострочниках» на разных языках, которые решали простые задачи. Я решил опубликовать несколько алгоритмов на языке C/С++.
Итак, поехали!

Посмотрев этот ролик 2-годичной давности, я вспомнил про беспилотники Google. Технология NAVTEQ True — это больше, чем просто фото улиц.

На борту фотомобиля:

• Фотокамеры
• GPS
• Лидар
• IMU (Inertial measurement unit)
• Энкодер на колесе

Вместе они позволяют получить:

• 360°-панорамы улиц
• Точную 3D-модель пространства
• Дорожные знаки и разметку
• Резкие повороты дороги

Всё это стоит увидеть в этом видео:

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

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

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

Известно, что в рибосомах прокариот и эукариот присутствуют 3 типа рРНК. Информационная емкость крупных молекул больше, но их труднее анализировать. Поэтому наиболее удобным оказался анализ молекул рРНК средней величины: 16S (~1600 нуклеотидов). Систематика основывается на расчете коэффициентов сходства сравниваемых организмов. Именно на основании анализа рРНК современная систематика выделяет три домена бактерии, археи и эукариоты, а так же на этом основывается систематика, бактерий и архей X издания Берги.

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

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

Смотрим, что из этого получилось.

Всем привет. Продолжая тему того, что Andrew Ng не успел рассказать в курсе по машинному обучению, приведу пример своей реализации алгоритма k-средних. У меня стояла задача реализовать алгоритм кластеризации, но мне необходимо было учитывать степень корреляции между величинами. Я решил использовать в качестве метрики расстояние Махаланобиса, замечу, что размер данных для кластеризации не так велик, и не было необходимости делать кэширование кластеров на диск. За реализацией прошу под кат.

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

В прошлую субботу, 16 июня, завершился отборочный раунд Russian Code Cup 2012. Задачи отборочного раунда посложнее, чем были на квалификации – ну на то он и полуфинал. Я уже рассказывал о том, что предлагалось участникам на предыдущих онлайн-турах, разбирал подробно варианты решений (Q1, Q2, Q3).

В отборочный раунд было приглашено 600 человек. 434 человек смогли решить хотя бы одну задачу. Все задачи решили только двое. 50 лучших перешли в финал. Всего за 3 часа тура было отправлено в проверяющую систему 3190 решений.

Итак, перейдем к самим задачам. Я пострался объяснить их так, чтобы решения были понятны даже делающим первые шаги в спортивном программировании (да и в программировании вообще).

Группа учёных из компании Google поставила интересный эксперимент: способна ли нейросеть самостоятельно выработать свойства высокого уровня на базе большого массива непомеченных данных. Например, если ей дать выборку из миллиона изображений, сможет ли она научиться находить на них лица? Идея в том, что система ни разу не видела изображение, которое было бы помечено как «лицо».

Вы, наверное, слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то предлагаю вам самостоятельно поискать в интернете — в этой статье я не буду донимать вас уроками истории или математики. Я попробую показать вам на практике, как применить этот алгоритм к текстовой строке. Наше приложение просто сгенерирует значения кода для символов из введенной строки и наборот — воссоздаст оригинальную строку из представленного кода.

Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.

Всем привет. На этой неделе в курсе по машинному обучению профессор Andrew Ng рассказал слушателям про метод главных компонент, с помощью которого можно уменьшить размерность пространства признаков ваших данных. Но к сожалению он не рассказал про метод вычисления собственных векторов и собственных чисел матрицы, просто сказал, что это сложно и посоветовал использовать матлаб/октавовскую функцию [U S V] = svd(a).

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

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

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

Недавно решал задачи по криптографии, и возникла необходимость переводить очень большие числа из одной системы счисления в другую. С двоичной, восьмеричной, десятичной и шестнадцатеричной системой справляется и стандартный калькулятор ОС. Но он не рассчитан на числа большой длины. А мне как раз необходимо работать с числами длиной >1000 знаков.
Для этих целей решил написать небольшой консольный конвертер, позволяющий работать с числами любой длины и любой системы счисления от 2 до 36.

Требования:

• Конвертер должен работать с числами любой длины.
• Конвертер должен работать в любой системе счисления от 2 до 36.
• Конвертер должен уметь работать с файлами.

В статье Распознавание лиц человеческим мозгом: 19 фактов, о которых должны знать исследователи компьютерного зрения упоминался экспериментальный факт: в мозге примата имеются нейроны, селективно реагирующие на изображение морды лица (человека, обезьяны и т.п.), причем средняя задержка составляет около 120 мс. Из чего в комментарии я сделал дилетантский вывод о том, что зрительный образ обрабатывается прямым распространением сигнала, и количество слоёв нейронной сети — около 12.

Предлагаю новое экспериментальное подтверждение этого факта, опубликованное concretely нашим любимым Andrew Ng.