Алгоритмы *

Введение

Спортивная игра «Шашки» является одной из игр человечества, которые компьютер ещё не просчитал полностью. Есть новости о том, что ученые нашли стратегию, при которой компьютер никогда не проиграет. За свои 9 лет, посвящённых этой игре, я встретил лишь одну программу, которую никак не мог победить. Пожалуй, мой спортивный опыт позволит сделать предположение, что это была программа реализующая стратегию описанную выше. К моему большому удивлению, она занимала лишь 60 Мбайт. А может быть, там была хорошо обученная нейронная сеть в основе? Но всё же мне не верится, что просчитать их невозможно. Там всего лишь 10^20 позиций, неужели мой компьютер не справится с такой задачей? А также, неужели нет тактики, в которой в начале партии соперник отдаёт шашку и оказываются в тактическом преимуществе?! Ни одного дебюта такого я не встречал. Пойду проверю…

Александр 4110 Шаенко (экс-инженер Даурия Аэроспейс, ныне главарь проекта краудсорсингового спутника «Маяк») и Степан Тезюничев пишут открытый софт для моделирования теплового режима спутников.

Репозиторий тут.



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

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

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

Основную сложность ребята вроде решили, построив массивно-параллельный алгоритм расчета хода излучения с методом Монте-Карло на CUDA. Теперь они хотят использовать для интегрирования своей системы, а она большой размерности, порядка 100 тыс. неизвестных, и жесткая, подходящий метод интегрирования по времени. Обычные явные методы требуют слишком мелкого шага по времени, а неявные требуют много раз вычислять правую часть, что ресурсозатратно.

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

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

Самый простой способ разобраться во всех деталях — изучить открытые исходники. Я взялся изучать Verilog исходники FPGA-майнера. Это не единственный такой проект, есть еще несколько примеров на github, и все они, хоть и разных авторов, похоже работают приблизительно по одной схеме. Вполне возможно, что автор то у них всех изначально был один, просто разные разработчики адаптируют один и тот же код под разные чипы и разные платы… По крайней мере мне так показалось…

Вот и я, поизучав исходники Verilog, адаптировал проект с github к плате Марсоход3 на основе ПЛИС Altera MAX10, 50 тыс. логических элементов. Я смог запустить свой майнер и даже смог запустить процесс вычисления биткоинов, но бросил это дело через пол часа из-за бесперспективности. Слишком медленно по нынешним временам работает мой FPGA майнер. Ну и пусть.

Честно говоря, меня во всем этом проекте заинтересовали не сами биткоины (ну их, эти денежные суррогаты), но скорее математическая сторона алгоритма SHA256. Вот об этом я и хотел бы поговорить. Я провел несколько экспериментов с алгоритмом SHA256, может быть результаты этих экспериментов покажутся вам интересными.

В публикации «Сказка о потерянном времени» пользователь crea7or рассказал, как он опровергал Гипотезу Эйлера на современном CPU.

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

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

В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.

В этой статье я расскажу о своей попытке использования библиотеки GenStage, а в частности модуля Flow, для реализации одного из алгоритмов биоинформатики. На протяжении последних двух лет я занимался разработкой комплексной системы хранения и поиска результатов метагеномного анализа (метагеномика) углеводородного сырья. Наверное, для многих это китайская грамота. Фактически такой анализ означает выявление всех типов микроорганизмов, обитающих, к примеру, в залежах нефти. Некоторые из этих микроорганизмов, преимущественно бактерии, способны разъедать стальные трубы и создавать множество других неблагоприятных эффектов.

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

Lock-free list является основой многих интересных структур данных, — простейшего hash map, где lock-free list используется как список коллизий, split-ordered list, построенный целиком на списке с оригинальным алгоритмом расщепления bucket'а, многоуровневого skip list, являющегося по сути иерархическим списком списков. В предыдущей статье мы убедились, что можно придать такую внутреннюю структуру конкурентному контейнеру, чтобы он поддерживал thread-safe итераторы в динамичном мире lock-free контейнеров. Как мы выяснили, основным условием для того, чтобы lock-free контейнер стал итерабельным, является стабильность внутренней структуры: ноды не должны физически удаляться (delete). В этом случае итератор суть просто (быть может, составной) указатель на ноду с возможностью перехода к следующей (оператор инкремента).

Можно ли такой подход распространить на lock-free list?.. Посмотрим…

Знаете такую компанию — Facebook? Да-да, ту самую, у сайта которой 1,6 миллиардов пользователей. И если взять все посты-поздравления с днем рождения, ваши позорные детские фотографии (у меня они такие), того дальнего родственника, лайкающего каждый ваш статус, — и вот вам множество данных для анализа.

С точки зрения анализа изображений Facebook весьма далеко продвинулся со сверточными нейронными сетями (Convolutional Neural Network, CNN). В августе подразделение Facebook по исследованиям в области искусственного интеллекта (Facebook AI Research, сокращенно FAIR) опубликовала блог-пост об алгоритмах компьютерного зрения, которые лежат в основе некоторых их алгоритмов сегментации изображений. В этом посте мы кратко изложим и разъясним три статьи, на которые ссылается этот блог.

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

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



Правила против статистики

Машинный перевод, то есть автоматический перевод с одного человеческого языка на другой, зародился в середине прошлого века. Точкой отсчета принято считать Джорджтаунский эксперимент, проведенный 7 января 1954 года, в рамках которого более 60 фраз на русском языке были переведены компьютером на английский. По сути, это был вовсе и не эксперимент, а хорошо спланированная демонстрация: словарь включал не более 250 записей и работал с учетом лишь 6 правил. Тем не менее результаты впечатлили публику и подстегнули развитие машинного перевода.

Чтo мнe нpaвитcя вo вcякиx paзpaбoтчecкиx тулax, тaк этo тo, чтo oни нe тoлькo пoмoгaют peшaть кaкиe-тo зaдaчи, нo пopoй eщe и учaт пpoгpaммиpoвaнию. Tулa, пpo кoтopую я xoчу paccкaзaть — oнa имeннo тaкaя. СаllShаrр — тaк нaзывaeтcя мoй пpoeкт — пытaeтcя aлгopитмичecки вывecти цeпoчку вызoвoв нa ocнoвe нaбopa вxoдныx и oжидaeмыx выxoдныx дaнныx.

Здравствуйте, дорогие читатели. Сегодня пятница, а у нас на борту продолжается напряженный отсмотр и анализ новинок по C++, желательно с учетом C++ 17. В ходе этого увлекательного занятия мы набрели на блог Яцека Галовица (Jacek Galowicz). Из сравнительно свежих материалов нам особенно понравилась статья, размещенная под катом.

Приходит ветеринар к терапевту. Терапевт: — На что жалуетесь? Ветеринар: — Нет, ну так каждый может!

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

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

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



Под катом я расскажу о том, что такое наукастинг и как мы над ним работали.

"Обычно хакер пишет программы не ради выгоды,
а ради собственного удовольствия. Такая программа
может оказаться полезной, а может остаться
всего лишь игрой интеллекта."
Генри С. Уоррен. Алгоритмические трюки для программистов [1]

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

Однажды мы с коллегами заинтересовались, как самые простые методы оптимизации работают на Эльбрусе.

Это перевод обзора статьи «MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing» Fan et al. в Proceedings of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI’13), pdf тут

Чуваки (бывший гугловец, чувак из университета Карнеги Меллон и еще один из Интел лабс) сделали улучшенный Memcached-совместимый кеш (по факту просто допилили мемкеш), и у них классные результаты производительности. Мне очень понравился обзор этой статьи в блоге "The morning paper" — описание алгоритмов и прочее.

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


Из этого дерева понятно, что связаны слова «мама» и «мыла», а также «мыла» и «раму», а слова «мама» и «раму» напрямую не связаны.

Статья будет полезна тем, кому понадобился синтаксический анализатор, но не понятно, с чего начать.

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

Если честно, то не совсем и сказка, а суровая жизнь. Но время ведь потеряно совершенно настоящее, хоть и с пользой. А началось всё совершенно случайно. На одном сайте один умный товарищ написал пост о гипотезе Эйлера. Суть достаточно проста. Гипотеза Эйлера утверждает, что для любого натурального числа n>2 никакую n-ю степень натурального числа нельзя представить в виде суммы (n-1) n-х степеней других натуральных чисел. То есть, уравнения:


не имеют решения в натуральных числах.

Ну собственно так оно и было до 1966 года…

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

В предыдущих частях опуса (1, 2, 3) мы рассмотрели внутреннее строение lock-free map и убедились, что все основные операции — поиск, добавление и удаление ключа — могут быть выполнены без глобальных блокировок и даже в lock-free манере. Но стандартный std::map поддерживает ещё одну очень полезную абстракцию — итераторы. Возможно ли реализовать итерабельный lock-free map?
Ответ на этот вопрос — под катом.