Алгоритмы *

Хочется рассказать немного о технической части своего проекта, возможно для критики а может кто-то почерпнет что-то для себя.

Здравствуйте, уважаемые хабравчане! Это моя вторая статья, и мне хотелось бы поговорить о вычислительной геометрии.

Немного истории

Я являюсь студентом уже 4 курса математического факультета, и до того как я начал заниматься программированием, я считал себя математиком на 100 процентов.

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

Мне очень нравится подход моего преподавателя: «разберись с этой темой, а потом расскажи нам, да так чтоб мы все поняли».

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

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

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

Алгоритмы SR используют два подхода для вычисления результирующего изображения: 1) на базе множества кадров одного объекта; 2) самообучающаяся система с базой образцов.

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

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

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

Спустя два года разработки состоялся релиз библиотеки ccv 0.1, которая использует ряд современных алгоритмов компьютерного зрения.

Библиотека ccv написана на C и позиционируется как компактная, лёгкая альтернатива OpenCV, поэтому из неё старательно изъяты все несущественные функции. Таким образом, ccv предназначена не для экспериментов с разными алгоритмами, а для практического использования в конкретных приложениях.

Небольшая иллюстрация того, как на языке 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 решений.

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