Алгоритмы *

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

(Прим. пер.: приведённые в статье алгоритмы относятся к названиям степеней тысячи по короткой шкале.)

Некоторое время назад я получил возможность поучаствовать в разработке игры в жанре idle. Что же такое idle-игра? Если вы впервые слышите об этом быстро развивающемся жанре, попробуйте поиграть в Adventure Capitalist. На сайте Gamasutra также есть несколько статей (1, 2, 3, 4), позволяющих рассмотреть жанр немного глубже.

Привет Хабр! Это вторая часть перевода статьи про подсчет различных судоку.



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

Как обычно, мои комментарии выделены курсивом или спрятаны под спойлеры. Под спойлерами можно найти самое интересное — куски кода, которые верифицируют все числа, полученные в повествовании.

Введение

Представляем вторую статью в серии, задуманной, чтобы помочь быстро разобраться в технологии глубокого обучения; мы будем двигаться от базовых принципов к нетривиальным особенностям с целью получить достойную производительность на двух наборах данных: MNIST (классификация рукописных цифр) и CIFAR-10 (классификация небольших изображений по десяти классам: самолет, автомобиль, птица, кошка, олень, собака, лягушка, лошадь, корабль и грузовик).

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

О том, как сделать свой генератор простых задач на нахождение пределов/производных/интегралов и пойдёт речь после ката.

В предыдущей статье из цикла «Deep Learning» вы узнали о сравнении фреймворков для символьного глубокого обучения. В этом материале речь пойдет о глубокой настройке сверточных нейронных сетей для повышения средней точности и эффективности классификации медицинских изображений.

Бла-бла-бла

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

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

Вчера меня озарило после разговора с Пашей Бейзманом, выступавшим на днях с докладом на HighLoad++. Битовые операции!!! Да, я прекрасно понимаю мощь битовых операций, но я их неправильно готовил ;) Результаты тестов превзошли мои самые оптимистичные ожидания.

Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма не раз появлялось в рунете, в то время как о других алгоритмах (с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это недоразумение, а также является отличным дополнением к уже опубликованному ранее материалу.

Ниже я расскажу о алгоритме 'разделяй и властвуй' построения диаграммы Вороного за O(n*log(n)), а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа 'разделяй и властвуй' являются своего рода классикой программирования (думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются (если, конечно, знать основную идею алгоритма).

В данной статье я хотел бы рассмотреть на практике вариант построения простейшей рекомендательной системы основанной на схожести изображений товаров. Этот материал предназначен для тех, кто хотел бы попробовать применить Deep Learning, а именно свёрточные нейронные сети, в простом, интересном и практически применимом проекте, но не знает с чего начать.

Добро пожаловать в серию статьей «Марсоход», где мы будем использовать следующие практики:

• Monolithic Repositories — MonoRepo (Монолитные репозитории)
• Command/Query Responsibility Segregation — CQRS (Сегрегация ответственности на чтение и запись)
• Event Sourcing — ES (События как источник)
• Test Driven Development — TDD (Разработка через тестирование)

В этой вводной статье мы просто обозначим спецификации нашего марсохода.

Примечание. Этот пример является адаптированной для нужд серии статей версией упражнения, представленного на Dallas Hack Club, который сейчас, к сожалению, лежит.


Но сначала, давайте кратко пройдемся по упомянутым выше терминам.

Представляем первую статью в серии, задуманной, чтобы помочь быстро разобраться в технологии глубокого обучения; мы будем двигаться от базовых принципов к нетривиальным особенностям с целью получить достойную производительность на двух наборах данных: MNIST (классификация рукописных цифр) и CIFAR-10 (классификация небольших изображений по десяти классам: самолет, автомобиль, птица, кошка, олень, собака, лягушка, лошадь, корабль и грузовик).

Седьмого ноября стартует Russian AI Cup 2016. Это ежегодный чемпионат по программированию искуственного интеллекта, организуемый Mail.Ru Group. Russian AI Cup проводится в форме игры, чтобы получилось наглядно, понятно и просто. Вкратце: участники создают алгоритм, который описывает игровую стратегию. Получившийся бот сражается с другими такими же, а лучший из них побеждает в раунде. Таким образом, из серии раундов организуется турнир, проходящий в несколько этапов.

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

Привет Хабр! Данная публикация возникла после просматривания этого поста, в котором автор пытается посчитать количество различных судоку. Желая более точно разобраться в вопросе, я за пару минут нагуглил точный ответ, приведенный в данной статье. Текст этой статьи мне показался интересным сам по себе, поэтому я решил сделать перевод (в довольно вольном стиле).



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

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

Однако события в мире синтеза визуальных образов доказывают обратное. Да, компании еще несколько лет назад начали использовать нейросети для операций с изображениями — но это был не конец пути, а его начало. Недавно руководитель группы компьютерного зрения «Сколтеха» и большой друг Яндекса и ШАДа Виктор Лемпицкий рассказал о нескольких новых способах применения сетей к изображениям. Поскольку сегодняшняя лекция — про картинки, то она очень наглядная.


Под катом — расшифровка и большинство слайдов.

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

"Literate programming (грамотное программирование) — отношение к компьютерным программам, как к литературе: компьютерная программа пишется не столько для компьютера, сколько для людей, чтобы люди могли ее прочитать. И поскольку я пишу программы, то я, в некотором роде, учитель."



«Давайте изменим традиционные приоритеты в создании программ: вместо представления о нашей задаче как о создании инструкций «Что делать?» для компьютера сконцентрируемся на объяснении другим людям описаний нашего видения того, что под управлением программы должен делать компьютер.»

Прочтение публикации Упрощаем бинарный поиск в Excel сподвигло на дополнительное усовершенствование функции ВПР по сравнению с приведенным в статье.

Что не было учтено, и что хотелось бы добавить:

Глобальное освещение, динамический свет и декали (да, есть такое слово :) ) в действии.

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

Продолжаю цикл статей «Оптимизация на примере». В данной статье сравниваются два эвристических алгоритма на избитой симметричной задаче коммивояжера. Сегодня чуть углубимся в данную тему и разберем определенную модификацию муравьиного алгоритма.

Публикуем вторую часть статьи о типах архитектуры нейронных сетей. Вот первая.

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

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