Рубрика «Алгоритмы» - 216

От переводчика: В последние месяцы в жизнь многих людей прочно вошли новости сферы финансов. Одна из недавних тем — возможное отключение России от системы SWIFT. Угроза выглядит очень серьезно, но что на самом деле грозит стране, если события будут развиваться по этому сценарию? Наш сегодняшний материал призван помочь разобраться с тем, как все устроено в глобальном мире финансов.

На прошлой неделе [статья опубликована в ноябре 2013] Twitter сошел с ума из-за того, что кто-то перевел почти 150 миллионов долларов за одну транзакцию в криптовалюте. Появление такого твита было в порядке вещей:

Простое объяснение движения денег в банковской системе - 1

Транзакция 194 993 биткоинов стоимостью в 147 миллионов долларов порождает много тайн и спекуляций

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

С помощью этой статьи я попытаюсь изменить ситуацию и проведу простой, но, надеюсь, не слишком упрощенный, анализ в этой области.Читать полностью »

Нейропластичность в искусственных нейронных сетях - 1 Привет, давно не виделись. В этом посте мне хотелось бы рассказать о таком относительно новом понятии в машинном обучении, как transfer learning. Так как я не нашел какого-либо устоявшегося перевода этого термина, то и в названии поста фигурирует хоть и другой, но близкий по смыслу термин, который как бы является биологической предпосылкой к формализации теории передачи знаний от одной модели к другой. Итак, план такой: для начала рассмотрим биологические предпосылки; после коснемся отличия transfer learning от очень похожей идеи предобучения глубокой нейронной сети; а в конце обсудим реальную задачу семантического хеширования изображений. Для этого мы не будем скромничать и возьмем глубокую (19 слоев) сверточную нейросеть победителей конкурса imagenet 2014 года в разделе «локализация и классификация» (Visual Geometry Group, University of Oxford), сделаем ей небольшую трепанацию, извлечем часть слоев и используем их в своих целях. Поехали.
Читать полностью »

image

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

Под катом краткий обзор метода выделения гармоник из произвольного сигнала с помощью цифрового гетеродинирования, и немного особой, Фурье-магии.
Читать полностью »

Lock-free структуры данных. Concurrent maps: деревья - 1 Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.
Читать полностью »

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

В этом посте я расскажу, почему так получилось: чего мы не смогли предвидеть, когда придумывали первую версию ПО Яндекс.Диска, и как создавали новую.

Новый алгоритм синхронизации Яндекс.Диска: как не подавиться 900 000 файлов - 1

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

Каждый университет сталкивается с тем, что на некоторые темы в городе невозможно найти преподавателя, который бы являлся в этой теме специалистом. Один из вариантов решить эту проблему состоит в том, чтобы поручить подготовить курс на эту тему какому-нибудь из имеющихся преподавателей, который не является специалистом в этой области. Мы в Акадеическом университете стараемся пойти другим путем — пригласить специалиста для чтения курса. В прошлом году мы поучаствовали в конкурсе фонда Династия “приглашенный профессор”. Мы подали две заявки и обе выиграли, а также два наших преподавателя были приглашены в Уральский и Казанский федеральные университеты. В сентябре 2014 года Александр Охотин из университета Турку прочитал курс Формальные грамматики. А 18 марта начнет читать курс “Комбинаторика слов и ее приложения” профессор Уральского федерального университета Арсений Михайлович Шур. Мы приняли решение сделать этот курс полностью открытым для всех и провести его в рамках Computer Science клуба, нашего постоянного партнера.

Арсений Михайлович — активный исследователь в области комбинаторики слов, поэтому курс обещает быть очень интересным. Первое занятие состоится в среду 18 марта в 18-30 в Мраморном зале ПОМИ РАН (Санкт-Петербург, наб. реки Фонтанки д. 27), вход свободный, регистрация не требуется.

Подробное описание курса и расписание: тут.

Краткое описание курса
Читать полностью »

Предисловие

В 2013 году с целью популяризации робототехники в России и создания среды программистов и инженеров, ориентированных на данную тематику компания КРОК (г.Москва) организовала конкурс «Летающие роботы». Наша команда «iKar» (3 человека из Барнаула и 1 из Москвы) участвовала в 2013 году (конкурс «Улететь и вернуться») и 2014 году («Догнать и перегнать Крок») не победила, но добилась неплохих результатов.

1. С чего все началось или условия конкурса

Будучи по профессии программистом 1С, нередко приходится пользоваться форумом forum.mista.ru. Один из моих друзей-коллег первым заметил объявление на тему «Кому лимон» и предложил участвовать.

Условия конкурса выглядели заманчиво: необходимо было построить или купить летающего робота и научить его перемещаться/ ориентироваться в помещении-полигоне, автоматически взлетать и садиться и распознавать посадочные маркеры. Срок на всю работу 1 год, а приз — 1 миллион рублей.

История участия в конкурсе «Летающие роботы». Часть 1 - 1

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

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

image
Известный благодаря Google алгоритм ранжирования сущностей по числу взаимных ссылок между ними был применён двумя исследователями из Македонии для определения того, какая футбольная команда должна находиться на троне сильнейших. В итоге выяснилось, что математика как нельзя лучше соответствует действительности — вверху пьедестала оказалась Бразилия. Статья опубликована на arXiv.org.
Читать полностью »

На Хабре недавно была опубликована статья «Перевод времени в деньги и обратно». В дальнейшем я буду именовать её исходной, ибо отталкиваться буду в основном от высказанных там идей. Так вот, в той статье есть много моментов, которые хочется поправить. Данная статья задумывалась как статья-ответ.
Читать полностью »

Из этой статьи вы узнаете, что распознавание даже коротких звуковых фрагментов в зашумленной записи — вполне решаемая задача, а прототип так вообще реализуется за 30 строчек кода на Python. Мы увидим, как тут помогает преобразование Фурье, и наглядно посмотрим, как работает алгоритм поиска и сопоставления отпечатков. Статья будет полезна, если вы сами хотите написать подобную систему, или вам интересно, как она может быть устроена.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js