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

Чего вы не найдёте здесь:

• Сложных уравнений. Цель данной публикации является представление идей и видение задачи. И как любое видение оно во многом абстрактно;
• Каких либо генераторов фрактальных изображений. Такие изображения выглядят интересно, но мня интересуют реальные задачи.

Что вы найдёте здесь:

1. Краткий обзор применения фрактальных преобразований к задаче сжатия данных с потерями;
2. Необычная интерпретация фрактальных преобразований;
3. Ссылки на реальный код компрессора и декомпрессора аудио данных посредством фрактальных преобразований (декомпрессор представлен в форме плагина для аудио плейера Winamp);
4. Описание нового формата для хранения сжатых аудио данных с пятью уникальными свойствами, отличающими новый формат от многих хорошо известных индустриальных аудио форматов.

В этой статье я расскажу и покажу свой способ сегментации строк на слова. Если вам не интересна жизнь сибиряка в тропиках, можете смело пропускать вступление.

Принципы и приёмы обработки очередей

Константин Осипов (Mail.ru)

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

Для начала о себе — я занимаюсь разработкой СУБД Tarantool в Mail.ru. Этот доклад будет об обработке очередей. У нас много очередей внутри системы, фактически вся база данных построена как система массового обслуживания.

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

Команда FlyElephant приглашает всех c 8 по 9 октября в Харьков на III Международнаю конференцию АI Ukraine, которая посвящена вопросам Data Science, Machine Learning, Big Data и Artificial Intelligence.

На конференции будут рассмотрены темы из различных областей Data Science и Machine Learning:

• глубокое обучение нейронных сетей;
• компьютерное зрение;
• обработка естественного языка;
• рекомендательные системы;
• использование Machine Learning в биоинформатике;
• Big Data инструменты: Hadoop, Spark и др.

Я буду рад видеть всех на нашем стенде, а также на докладе, в котором расскажу об инфраструктуре для работы Data Scientist’а.

Регистрация и все подробности на сайте конференции. Для читателей нашего блога действует скидочный промокод на 7%: flyelephant.

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

Пожалуй, во время теста не особо интересно спрашивать у машины: когда была Куликовская битва. Гораздо интереснее что она скажет, например, о том: зачем мы нажимаем сильнее на кнопки пульта, у которого садятся батарейки?

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

Математика — весьма интересная и занимательная наука, особое место в которой занимает вычисление числа Pi. История его вычисления занимает более 2х тысячелетий, а точность вычисления колеблется от 256/81 в древнем Египте и 339/108 в Ведах, до Джамшида ал-Каши, вычислившего 16 знаков в 15м веке. Чего стоит хотя бы история Вильяма Шенкса, который потратил 20 лет на вычисление 700 знаков числа Пи, но уже потом выяснилось, что во второй части расчетов он ошибся… Но текст в общем-то не об этом, а об алгоритмах. Стало интересно, можно ли вычислить Пи на iPhone? И если да, то с какой точностью?


Можно сказать сразу — миллион не предел. Можно и больше. Подробности и реализация под катом.

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



Но чтобы светлое завтра наступило, уже сегодня нужно решать связанные с ним практические задачи. Так что мы занялись технологией, которая будет делать сайты за людей. Нет, не за специалистов, создающих сложные и высоконагруженные системы. А за ребят с “сайтом-визиткой за 3000” — потому что ИИ, как минимум, не пропадет на месяц после предоплаты.

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

Городская библиотека Стокгольма. Фото minotauria.

В этой статье я хочу рассказать о том, что оценивать время обращения к памяти как O(1) — это очень плохая идея, и вместо этого мы должны использовать O(√N). Вначале мы рассмотрим практическую сторону вопроса, потом математическую, на основе теоретической физики, а потом рассмотрим последствия и выводы.

Введение

Если вы изучали информатику и анализ алгоритмической сложности, то знаете, что проход по связному списку это O(N), двоичный поиск это O(log(N)), а поиск элемента в хеш-таблице это O(1). Что, если я скажу вам, что все это неправда? Что, если проход по связному списку на самом деле O(N√N), а поиск в хеш-таблице это O(√N)?

Не верите? Я вас сейчас буду убеждать. Я покажу, что доступ к памяти это не O(1), а O(√N). Этот результат справедлив и в теории, и на практике. Давайте начнем с практики.

Измеряем

Давайте сначала определимся с определениями. Нотация “О” большое применима ко многим вещам, от использования памяти до запущенных инструкций. В рамках этой статьи мы O(f(N)) будет означать, что f(N) — это верхняя граница (худший случай) по времени, которое необходимо для получения доступа к N байтов памяти (или, соответственно, N одинаковых по размеру элементов). Я использую Big O для анализа времени, но не операций, и это важно. Мы увидим, что центральный процессор подолгу ждет медленную память. Лично меня не волнует, что делает процессор пока ждет. Меня волнует лишь время, как долго выполняется та или иная задача, поэтому я ограничиваюсь определением выше.

Привет, Хабражитель!
Не так давно, вышло очередное дополнение World of Warcraft Legion. Первым делом я принялся прокачивать шамана. В оплоте шаманов я забрел к Мастеру головоломок Ло и увидел то, что вы подумали — головоломку.

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

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

Вполне естественно, что понимание того, как выглядят следы памяти – основной вопрос изучения мозга. Без этого невозможно построить никакую биологически достоверную модель его работы. Понимание строения памяти непосредственно связано с пониманием того, как мозг кодирует информацию и как он ей оперирует. Все это, пока, — неразгаданная загадка.

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

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

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

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

В какой-то момент, знакомясь с представленным в 2015 году методом Batch Normalization от компании Google мне, для решения задачи связанной с распознаванием лиц, удалось существенно улучшить скорость работы нейросети.

За подробностями прошу под кат.

Всем привет! Недавно возникла практическая необходимость использовать интерполяцию для замкнутых кривых. Проект разрабатывался под .Net на C#, а готовых реализаций алгоритма я не обнаружил, впрочем, как и для других языков и технологий. В результате пришлось самому изучить мат.часть существующих методов и написать свою библиотеку. Наработками и готовым решением готов поделиться с вами.

Доброго всем времени суток, уважаемые посетители сайта Хабрахабр. В данной статье я бы хотел рассказать вам о том, что такое диаграмма Вороного (изображена на картинке ниже), о различных алгоритмах её построения (за , — пересечение полуплоскостей, — алгоритм Форчуна) и некоторых тонкостях реализации (на языке C++).



Также будет рассмотрено много интересных применений диаграммы и несколько любопытных фактов о ней. Будет интересно!

Сегодня мы расскажем о проекте, нацеленном на распознавание некоторых видов физической активности человека. Делается это с помощью платы Intel Edison, к которой подключён акселерометр ADXL345.


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

В нашем проекте для анализа данных акселерометра используется метод опорных векторов (Support Vector Machine, SVM). Программная часть реализована с применением популярной библиотеки LIBSVM. Код написан в двух вариантах: на Python и Node.js.

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

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

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

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

Привет Хабр! Недавно пришло интересное задание:

Имеется многогигабайтный файл, содержащий массив целых чисел от 1 до 10000. Элементы расположены хаотично с повторениями. Необходимо его отсортировать. Принять во внимание ограниченность в ресурсах.

Самым ленивым способом отсортировать можно используя «внешнюю сортировку со слиянием», но это весьма тяжёлый и долгий метод. В этой публикации я расскажу, какой метод пришёл мне в голову — я не смог не поделиться им.

Всем привет! Давно не писал статьи на любимую тематику и наконец-то созрел на что-то более-менее приличное и стоящее. В этой статье речь пойдет об очень интересной задаче, с которой инженер-разработчик сталкивается чуть ли не каждый день. Предлагаю вам посмотреть, каким образом можно использовать всю мощь и простоту TCL скриптов для проектирования на FPGA. В данной статье описание базируется на ПЛИС фирмы Xilinx, но это не отменяет возможностей TCL скриптов для кристаллов ПЛИС других производителей.


Интересно? Поехали…

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