Алгоритмы *

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



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

Например вот такая забавная оптимизация набора арифметических инструкций (взятых из какой-то подвернувшейся под руку математической библиотеки), соответствующих формулам: , которая на 6 джаве с выключенным JIT у меня давала около 10% ускорения, при этом на первый взгляд даже не очевидно что эти формулы эквивалентны (ОТКУДА ТУТ OR? ЭТО ВООБЩЕ ЗАКОННО?!), хотя это так. Под катом я расскажу, как именно получались такие результаты и каким образом компьютер придумывал лучший код чем тот, который мог написать я сам.

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



Простейший алгоритм, который приходит в голову, выглядит так:

• Определяем несколько базовых цветов картинки. RGB компоненты этих цветов будем использовать как базисные вектора.
• Цвет каждого пикселя разлагаем в линейную комбинацию базисных.
• Выводим изображение для каждого базисного цвета.
• Самооценка автоматически повышается.

Далее, более подробно по каждому пункту.

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

В данной работе примеры приведены на языке програмиирования C.

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

Например — распознавание естественного языка, динамическое обучение системы, построение и оценка гипотез. Все это позволило IBM Watson научиться давать прямые корректные ответы (с высокой степенью достоверности) на вопросы оператора. При этом когнитивная система умеет использовать для работы большие массивы глобальных неструктурированных данных, Big Data. Каковы основные принципы работы IBM Watson с языком? Об этом — в продолжении.

Как многие помнят, я работаю в лаборатории, где мы работаем с живыми и не очень организмами. Науку двигаем, короче. Обычно вперед. Иногда в качестве образцов нам достаются мертвые обезьяны, ткани которых потом идут на экспериментальные задачи. Выглядит обычно это крайне жизнерадостно. Раздается звонок в 11 часов вечера, и тебе сообщают, что в питомнике обезьянка убилась. Почти не поврежденная, соседи только сердце съели. Вздыхаем, лезем в расписание рейсов и едем в аэропорт. На месте тебе выдают нужные запчасти убиенной и складывают в прозрачный контейнер с консервационным раствором. В аэропорт с этим тащиться уже нельзя, так как ограничен провоз жидкостей. Идем на ж/д вокзал на экспресс до Краснодара. Милые девушки на контроле как правило приобретают восхитительный салатовый оттенок при виде медленно кружащихся органов в нежно-розовом растворе.
В-общем, привезли, нарезали все, что нужно ломтиками, покрасили… Но тут оказывается, что полученные исходники нужно обработать и посчитать в автоматическом режиме… Сразу хочу уточнить, что я врач-исследователь, а не профессиональный программист или математик. Поэтому, если что-то покажется ошибочным — буду рад правкам.

Предисловие

Цифровая фотография или иное растровое изображение представляет собой массив чисел, зафиксированных сенсорами уровней яркости, в двумерной плоскости. Зная что с математической точки зрения тонкая линза выполняет преобразование Фурье изображений, размещённых в фокальных плоскостях, можно создать алгоритмы обработки изображений, являющихся аналогами обработки изображений классической оптической системой.

Формула таких алгоритмов будет выглядеть следующим образом:

1. Z=FFT(X) – прямое двухмерное преобразование Фурье
2. Z′=T(Z) – применение функции или транспаранта к Фурье-образу изображения
3. Y=BFT(Z′) – обратное двухмерное преобразование Фурье

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

Примеры реализации

• Алгоритм размытия изображения
• Алгоритм повышения резкости изображения
• Алгоритм масштабирования изображения

Реализованные алгоритмы являются частью библиотеки с открытым исходным кодом FFTTools. Интернет-адрес: github.com/dprotopopov/FFTTools

По поисковому запросу шум перлина сразу попадается этот перевод на Хабре. Как справедливо заметили в комментариях к публикации, речь идёт вовсе не о шуме Перлина. Возможно, автор перевода и сам был не в курсе.

Чем выгодно отличается шум Перлина, легко можно заметить, если сравнить картинки.

Обычный шум (из той самой статьи):


Шум Перлина:


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

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

Привет, Хабр! В этой части мы опишем вам алгоритм, с помощью которого были получены цвета на графах из первой части. В основе алгоритма лежит k-medoids — довольно простой и прозрачный метод. Он представляет собой вариант популярного k-means, про который наверняка большинство из вас уже имеет представление.

В отличие от k-means, в k-medoids в качестве центроидов может выступать не любая точка, а только какие-то из имеющихся наблюдений. Так как в графе между вершинами расстояние определить можно, k-medoids годится для кластеризации графа. Главная проблема этого метода — необходимость явного задания числа кластеров, то есть это не выделение сообществ (сommunity detection), а оптимальное разбиение на заданное количество частей (graph partitioning).

С этим можно бороться двумя путями:

Этой осенью СПб АУ РАН и CS центр предлагают несколько новых бесплатных онлайн-курсов на разные темы: от теории графов до программирования на языке Haskell, и перезапускают некоторые из прочитанных ранее. Год назад состоялся первый запуск онлайн-курсов CS центра. Сначала появились курсы по программированию, а весной их дополнили курсы по математике, подготовленные вместе с Академическим университетом. Все онлайн-курсы разработаны на платформе Stepic.org.

• Java. Базовый курс (А. А. Владыкин)
• Алгоритмы: теория и практика. Методы (А. С. Куликов)
• Введение в архитектуру ЭВМ. Элементы операционных систем (К. В. Кринкин)
• Введение в математический анализ (А. И. Храбров)
• Ликбез по дискретной математике (А. В. Омельченко)
• Основы перечислительной комбинаторики (А. В. Омельченко)
• Основы теории графов (А. В. Омельченко)
• Погружение в СУБД (Д. В. Барашев)
• Программирование на языке C++ (А. В. Смаль)
• Функциональное программирование на языке Haskell (Д. Н. Москвин)

Часть курсов входит в годовую онлайн-программу по основам программирования.

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

Сегодня я поделюсь своей наработкой игры «Maze». В этой игре реализован алгоритм DFS. На днях мне поручили сделать курсовую работу по Алгоритмам, а именно по DFS в лабиринтах. Отказываться было нельзя. Пришел домой, выпил чашечку крепкого кофе и начал творить.

Вас интересуют игры? Хотите создать игру но не знаете с чего начать? Тогда вам сюда. В этой статье я рассмотрю простейший физический движок, с построения которого можно начать свой путь в GameDev'e. И да, движок будем писать с нуля.

Для идентификации материальных объектов придумано немало различных методов. Их можно разделить на две основные группы:

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

Рассматриваемый в данной публикации новый метод идентификации объектов с помощью оптического маркера, по формальным признакам можно отнести ко второй группе, однако в нем также можно найти и признаки первой группы методов.

Занятия в осеннем семестре в Computer Science клубе начнутся уже на первой неделе сентября! Как всегда, все лекции клуба открыты, регистрация не требуется. Приглашаются все желающие. Список курсов и подробное расписание ищите на сайте клуба: compsciclub.ru

2 сентября в 18:00 Иван Близнец начнёт читать курс по параметризованным алгоритмам. Данная область изучает сложность алгоритмов в зависимости не только от размера входных данных, но и от различных дополнительных параметров. За последнее десятилетие в этой области появилось много новых красивых результатов. Курс будет читаться по недавней книге «Parameterized Algorithms», выпущенной в 2015 году М. Цыганом, Ф. Фоминым, Л. Коваликом, Д. Марксом, М. Филипчуком, М. Филипчуком и С. Саурабом: link.springer.com/book/10.1007%2F978-3-319-21275-3
Предварительное расписание курса (может поменяться! следите за новостями и заходите на страницу расписания): среда, 18:00.
Страница курса:
compsciclub.ru/courses/parameterizedalgorithms

В процессе работы над match-3 проектом рано или поздно обязательно встает вопрос — как оценивать сложность созданных уровней и общий баланс игры?

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

Ниже рассказ о том, как мы это сделали в нашей инди-матч3-игре, над которой сейчас заканчиваем работать. (Осторожно — портянка!)

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



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

С 19 по 25 июля проходил хакатон Deephack, где участники улучшали алгоритм обучения с подкреплением на базе Google Deepmind. Цель хакатона — научиться лучше играть в классические игры Atari (Space Invaders, Breakout и др.). Мы хотим рассказать, почему это важно и как это было.

Авторы статьи: Иван Лобов IvanLobov, Константин Киселев mrKonstantin, Георгий Овчинников ovchinnikoff.
Фотографии мероприятия: Мария Молокова, Политехнический музей.

Почему хакатон по обучению с подкреплением это круто:

• Это первый в России хакатон с использованием глубокого обучения и обучения с подкреплением;
• Алгоритм Google Deepmind — одно из последних достижений в области обучения с подкреплением;
• Если вас интересует искусственный интеллект, то эта тема — очень близка к этому понятию (хотя мы сами и не хотели бы называть это ИИ).

Добрый день. Последний год я занимаюсь в проекте «МойОфис» вопросами совместного редактирования (collaboration). Оглядываясь назад, могу констатировать, что это непростая и очень интересная задача. Поэтому я хотел бы подробно рассказать о ней и дать ответы на следующие вопросы:

1. Какие существуют подходы к обеспечению совместного редактирования?
2. Насколько они сложны в реализации?
3. Можно ли взять готовую библиотеку и использовать ее в своем проекте?
4. Можно ли вести разработку без оглядки на совместное редактирование?

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

Недавно у меня с коллегой вышла дискуссия — влияет ли объём данных на трудоёмкость разработки.

В сухом остатке осталось:

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

Для разработчика, прямо скажем, выводы получились не очень весёлые и однозначные.

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

Цель публикации — поделиться опытом как, за приемлемое время, обработать два связанных списка по миллиарду записей в каждом.