Алгоритмы *

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

Зачем в наши дни нужна сортировка пузырьком?
Она ведь практически самая медленная.
У нее самый высокий (квадратичный) алгоритм сложности.

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

Результаты научных исследований, полученные в последние годы в задачах распознавания речи [1], машинного перевода [2], определения оттенка предложения [3] и частей речи [4] показали перспективность нейросетевых алгоритмов глубокого обучения в сравнении с классическими методами обработки естественного языка (natural language processing). Однако, в области вопросно-ответных и диалоговых систем еще остается много нерешенных задач [5, 6]. В данной статье дан обзор результатов применения современных алгоритмов для задач обработки и понимания естественного языка. Обзор содержит описание нескольких разных подходов и не претендует на полноту исследований.

Human: how many legs does a cat have ?
Machine: four, i think .
Human: What do you think about messi ?
Machine: he ’s a great player .
Human: where are you now ?
Machine: i ’m in the middle of nowhere .

(из статьи A Neural Conversational Model. КДПВ из фильма Ex Machina)

.В сравнении с нативным JS на элементах DOM, реализация анимационных алгоритмов на Canvas обычно производительнее во много раз. Это известный факт (но с особенностями для малого числа частиц, как выяснится позже), и он может найти реализацию так всем мешающего традиционного под НГ, но гонимого рациональными пользователями «падающего снега». Чтобы нагрузки было мало, в последние годы считается хорошим тоном «запускать» снег на сайте едва заметным, с минимальным количеством снежинок (5-15). Тут и эффект есть, и нагрузки на процессор почти никакой.

Поэтому, пока до НГ ещё несколько дней ещё зима, предлагаю устроить хакатончик по реализации лучших алгоритмов на канвасе и их аналогов на DOM, взяв за основу в основном древние нативные алгоритмы, которые как максимум обёртывались в плагин jQuery, чтобы было удобно подключать. Большая часть этих алгоритмов не соразмеряет нагрузку на процессор или сделана неэффективно, поэтому даже при малом числе снежинок грузят процессор на 100%. Вот пример обзорной статьи, где рассмотрены более 10 реализаций, не все, встречающиеся в природе. В дополнение, рассмотрим несколько избранных, чтобы получить задел на развитие алгоритма и реализацию его с хорошей эффективностью (получится ещё 5-6 вариантов). На этой основе можно построить доработку. Github с 12 демо (ссылки повторяются ниже) и несколькими алгоритмами.

Привет, хабр!

В данном посте речь пойдет о моем участии в конкурсе Ludum Dare 34, который был около трех недель назад.

В результате получился пазл под названием Growing Sakura, геймплей которой можно видеть на гифке (не пугайтесь, она весит всего 300Кб):


Кратко о правилах игры: изначально у нас есть гексагональное поле и несколько корневых бутонов (или один, как на гифке выше). Из него можно пустить 3 ветки (двумя способами — кликая левой или правой кнопкой мыши). Из каждого бутона на ветке левым кликом мыши можно сделать Y-разветвление, а правым — просто продолжить ветку дальше (I-разветвление). Если в каком либо направлении ветка расти не может (соответствующая клетка занята или в нужном направлении нет клетки) — то ветка не растет. В соответствии с последним условием нужно правильно выбирать порядкок «разворачивания» веток. В итоге получится дерево (или несколько деревьев) такое, что между двумя смежными ветками нет острых углов. Цель игры — покрыть все клетки игрового поля.

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

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

Мы никогда не видели большинство из них в глаза, все, что мы имели – списки застрахованных, где пол иногда был указан (с большим количеством ошибок), но чаще – не указан вообще. Большинство компаний имеют свою специфику работы и профессиональные традиции, в силу чего, в их коллективах преобладают люди одного пола. Даже небольшая ошибка могла сделать потенциально прибыльный договор убыточным (или наоборот, но на такое, по странному стечению обстоятельств, случалось с нашими клиентами гораздо реже). В целом, при объеме портфеля договоров в несколько миллиардов, и характерном количестве ошибок около процента, цена корректного определения пола по ФИО была в районе нескольких десятков миллионов.

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

Предлагаю порешать в кругу прекрасных дам-программистов традиционную новогоднюю задачу про 2016 год. Надо расставить знаки и скобки, чтобы получилось любое число от 1 до 100.
Например

20*(-1+6)=100

Или

2+0-1^6=1

Факториалы и степени милостиво допускаются.

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

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

Пример реализации представлен в виде Android приложения, а исходным изображением является скриншот текста, с введенным ключевым словом, для решения задачи применяются различные алгоритмы обработки и распознавания изображений.

Привет Хабр,

Итак, мы провели Фестиваль Данных на выставке новых технологий SMIT в Музее Москвы, о котором писали здесь.

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

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

В английском есть такая аббревиатура — TIFU. Привести здесь её точное значение мы не можем, но вы без труда найдёте его в Сети. А после «литературной обработки» TIFU можно перевести как «сегодня я всё испортил». В контексте этого поста данная фраза относится к использованию функции Math.random() в JavaScript-движке V8. Хотя случилось это не сегодня, а пару лет назад. Да и дров я наломал не по своей вине, корень зла таится в самой этой функции.

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

Дональд Кнут, «Искусство программирования», том 2.

Надеюсь, что к концу этого поста вы согласитесь с двумя утверждениями:

• Мы были идиотами, поскольку использовали генератор псевдослучайных чисел в V8, не понимая его ограничений. И если очень лень, то безопаснее использовать криптографически стойкие генераторы псевдослучайных чисел.
• В V8 необходима новая реализация Math.random(). Работу текущего алгоритма, кочующего от одного программиста к другому, нельзя считать удовлетворительной из-за слабой, неочевидной деградации, часто встречающейся в реальных проектах.

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

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

Анализу темы социологии финансовых алгоритмов посвящено исследование профессора Высшей школы социальных наук Эдинбурга Дональда МакКензи. Мы представляем вам самые интересные мысли этой работы — в первой части речь идет о предпосылках возникновения HFT-трейдинга и классификации схем его применения.

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

Всем привет!

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

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

Большинство аудиоформатов хранит информацию в виде зависимости амплитуды от времени (например, .wav) или в виде коэффициентов частотного преобразования (.mp3, .aac, .ogg), однако современные сложные алгоритмы цифровой обработки сигналов работают с частотной составляющей звуков. Приходится иметь дело с двойным переходом, из амплитудной области в частотную, затем обратно. На данный момент осуществление такого переход без потерь в качестве является достаточно распространенной проблемой с множеством неоднозначных решений.

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

Алгоритмы сортировок очень широко применяются в программировании, но иногда программисты даже не задумываются какой алгоритм работает лучше всех (под понятием «лучше всех» имеется ввиду сочетание быстродействия и сложности как написания, так и выполнения).

В данной статье постараемся это выяснить. Для обеспечения наилучших результатов все представленные алгоритмы будут сортировать целочисленный массив из 200 элементов. Компьютер, на котором будет проводится тестирование имеет следующие характеристики: процессор AMD A6-3400M 4x1.4 GHz, оперативная память 8 GB, операционная система Windows 10 x64 build 10586.36.

26 декабря наша команда FlyElephant примет участие во встречи Hub AI&BigData meetup, посвященной большим данным и искусственному интеллекту. Мероприятие будет проходить в Одессе и начнется в 11.00. Для всех, кто не сможет прийти, будет организована онлайн-трансляция.

Когда я первый раз столкнулся с темой бинарных деревьев в программировании, то сразу нашел на Хабре ответы почти на все возникшие у меня вопросы, но время шло, вопросов становилось больше и совсем недавно я нашел тему, которую еще не осветили на данном ресурсе — это 2-3-4 деревья. Есть отличная статья на тему 2-3 деревьев, в которой можно найти ответы на вопросы «Что такое куча?», «Что такое 2-3 деревья», а также информацию про основные операции со структурой, поэтому я не буду повторяться и сразу перейду к главной теме.

Итак, главное отличие 2-3-4 деревьев от 2-3 состоит в том, что они могут содержать более трех дочерних узлов, что дает возможность создавать четырехместные узлы (узлы, имеющие четыре дочерних узла и три элемента данных). Можно увидеть отличия визуально на гифке под эти текстом.На первом слайде показано 2-3 дерево, на втором — 2-3-4.

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

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

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

Перевод поста Stephen Wolfram "I Wrote a Book—To Teach the Wolfram Language".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации

---

Книга «Элементарное введение в язык Wolfram Language» доступна для вас в печатной форме, бесплатно в Интернете, а также в других формах.



Я не был уверен, что когда-нибудь напишу еще одну книгу. Моя последняя книга — Новый вид науки — заняла у меня более десяти лет интенсивной сосредоточенной работы и является моим крупнейшим проектом из всех, что я когда-либо делал.

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

Результат — книга Элементарное введение в язык Wolfram Language, вышедшая сегодня в печать. Она также свободно доступна в Интернете, и в других формах.

Сопроцессоры Intel Xeon Phi(TM) представляют собой PCI Express устройство и имеют x86 архитектуру, обеспечивая высокую пиковую производительности — до 1,2 терафлопс (триллион операций с плавающей запятой в секунду) двойной точности на сопроцессор. Xeon Phi(TM) может обеспечивать одновременную работу до 244 потоков, и это нужно учитывать при программировании для достижения максимальной эффективности.

Недавно мы вместе с компанией Intel проводили небольшое исследование эффективности реализации алгоритма Штрассена для сопроцессора Intel Xeon Phi(TM). Кому интересны тонкости работы с этим устройством и просто любящих параллельное программирование, прошу под кат.