Все потоки
Поиск
Написать публикацию
Обновить
174.71

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

«Эти глаза напротив»: история внедрения биометрического решения в X5 Group

Время на прочтение11 мин
Количество просмотров9.2K

Привет, Хабр! Мы уже рассказывали о магазине с полностью автоматизированной системой покупок, который получил название «Пятерочки #налету». Но это далеко не все технологические проекты компании. Практически одновременно с новыми автономными «Пятёрочками» мы начали разрабатывать и систему биометрической оплаты. Покупателю достаточно посмотреть в камеру и всё — покупка оплачена. О том, как этот проект внедрялся и что из себя представляет, читайте в нашем новом материале – собрали всю начинку!

Читать далее

Методы детоксификации текстов для русского языка

Время на прочтение9 мин
Количество просмотров10K

ВНИМАНИЕ! В статье есть примеры текстов, содержащие мат и грубые выражения. Мы ни в коем случае не хотим оскорбить наших читателей, все подобные тексты приведены лишь в научных целях в качестве примеров токсичности в реальных текстах из Интернета.





Всем привет! Меня зовут Дарина Дементьева, я являюсь аспиранткой в Сколковской лаборатории обработки естественного языка (Skoltech NLP), где занимаюсь исследовательскими проектами совместной лаборатории Skoltech NLP и MTS AI. В рамках работы в совместной лаборатории мы провели серию исследований, посвященных важной социальной проблеме – борьбе с токсичной речью в Интернете или детоксификации текстов.

В этой статье мы расскажем про результаты исследований методов детоксификаций для русского языка. Эта работа была опубликована и презентована на конференции Диалог, а также принята в журнал MDPI. Результаты экспериментов на английском языке приняли для презентации на одной из ведущих конференций в области обработки естественного языка EMNLP. Мы представляем вам краткую выжимку с описанием моделей, постановкой и результатами экспериментов, а в конце вы сможете самостоятельно ̶п̶о̶м̶а̶т̶е̶р̶и̶т̶ь̶с̶я̶ ̶в̶ ̶ч̶а̶т̶е̶ протестировать модели в бою. Теперь – добро пожаловать под кат!
Читать дальше →

Танцы без бубнов или как я реализовал автомат на ПЛИС

Время на прочтение6 мин
Количество просмотров4.9K

Всем привет, дорогие хабровчане! Сегодня я хочу поделиться своей «больной» идеей реализовать калькулятор на ПЛИС на основе конечного автомата. Почему больной? Потому что уж очень мудрёно получается: всё-таки реализация автоматов на ПЛИС – дорогая практика в смысле ресурсов. Почему хочу поделиться? Потому что вишенкой на торте в этом проекте является автоматическая генерация кода с помощью такого мощного средства, как HDL Coder в MATLAB, что в купе со Stateflow очень интересно смотрится: создание железного кода на основе графического составления графа системы – ни это ли верх мечтаний разработчика, которому необходимо реализовать сложнейший граф с кучей разных переходов и условий ?!

Итак, задачу перед собой я поставил следующую: у меня есть «китайский» кит с FPGA Spartan 6 на борту и старенький клавиатурный интерфейс PS/2. Я собираюсь залить проект калькулятора-автомата на ПЛИС вместе с выбранным интерфейсом и с клавиатуры осуществлять ввод данных. Вывод результата и текущего ввода будем наблюдать на 8-ми cемисегментных дисплеях, которые также имеются на отладочной плате.

В первой части мы познакомимся с пакетом Stateflow, как собиралась модель в SIMULINK и сгенерируем HDL-описание. Во второй части мы немного скорректируем проект для получения синтезируемого HDL кода.

Читать далее

Получаем кривую плотности распределения вероятности случайного процесса

Время на прочтение8 мин
Количество просмотров9.3K

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

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

Читать далее

Шифры замены

Время на прочтение9 мин
Количество просмотров7.2K

В предыдущей статье были рассмотрены простые шифры, использующие алфавиты естественных языков (ЕЯ). Автоматическая обработка сообщений в компьютерных и сетях связи предусматривает использование искусственных языков (ИЯ), что более эффективно во многих отношениях. Ранее описывалась классификация шифров и для некоторых из них было показано как они применяются в области информационной безопасности. Здесь продолжим такое рассмотрение, но для более сложных шифров.

Читать далее

Взлом ГПСЧ с помощью машинного обучения

Время на прочтение6 мин
Количество просмотров23K

Выдача XORShift кажется случайной

Исследователь Мостафа Хассан (Mostafa Hassan) сумел взломать два генератора псведослучайных чисел (ГПСЧ) с помощью машинного обучения. Обученная двуслойная нейросеть предсказала выдачу генератора xorshift128 с точностью 100%.

Во второй части своей работы Мостафа описал ещё одну нейросеть, которая взломала популярный генератор Mersenne Twister (вихрь Мерсенна, MT, MT19937) тоже с точностью 100%.
Читать дальше →

«Ижора»: клеточный автомат-компьютер

Время на прочтение9 мин
Количество просмотров9.7K

Хотелось бы поделиться с читателями Хабра довольно необычной разработкой: настоящим компьютером, сделанном в виде клеточного автомата, действующего по простому правилу Fireworld2 с четырьмя состояниями клеток. Текущая базовая версия компьютера называется "Ижора 1". Еще с 1950-х годов существует такая традиция: давать компьютерам географические названия.

Паттерн, состоящий из более 6 миллионов клеток, содержит 256 килобайт памяти и снабжен монохромным экраном 128x64 пикселей, отражающим состояние экранного раздела ОЗУ, примерно как в ZX Spectrum и других популярных исторических моделях персональных компьютеров. Программы можно писать на ассемблере, компилировать в машинный код, тестировать на эмуляторе и вводить специальной утилитой в сам клеточный автомат. Другая утилита позволяет сохранять текущее состояние компьютера. Для запуска компьютера необходима программа Golly - лучшая на сегодня площадка для подобного рода исследований.

Ассемблер и эмулятор написаны на языке Common Lisp, скрипты для ввода программ в сам клеточный автомат и сохранения его состояния - в Python. Компьютер имеет 32-битную архитектуру и на данный момент в нем все один регистр и одна операция: вычитание с условным переходом в случае отрицательного или нулевого результата (Subleq). Несмотря на примитивность такой модели, давно доказана ее универсальность. Существует даже операционная система Dawn OS, написанная для эмулятора Subleq-процессора.

Итак, суммируем: виртуальный компьютер с экзотической моделью программирования и ресурсами уровня древних ПК 1980-х, исполняющий всего около 10 операций в секунду, требующий современный компьютер с несколькими гигабайтами памяти (рекомендуемый минимум - 8 гигабайт), с эмулятором и ассемблером на Лиспе. Зачем и кому это нужно? Очень краткий ответ: ради хака и ретрокомпьютинга. Ниже - более подробно.

Читать далее:

Затачиваем маршрут GPS: несколько способов отфильтровать данные

Время на прочтение7 мин
Количество просмотров8.5K

Привет, меня зовут Сергей и я разработчик в команде мобильного бэкенда в компании ATI.SU. Не так давно в мою жизнь пришла задача. В ней нужно было принять координаты от приложения на Android и отобразить их на карте.

В разных приложениях мы каждый день видим красивые маршруты из разряда "где везут мою шаверму" или "как я пробежал по парку маршрут в виде котика", но если просто соединить линиями точки, которые приходят от телефона, то мы увидим что-то вдохновленное произведением Fatboy Slim - Ya Mama. Как превратить исходные данные в красивую картинку, разберемся в статье.

Читать далее

Обзор методов улучшения речи и шумоподавления: от классики к SotA

Время на прочтение10 мин
Количество просмотров16K

Всем привет! Меня зовут Оля Яковенко, я разработчик в MTS AI, занимаюсь задачами по автоматической обработке сигналов. В частности, на данный момент я исследую различные подходы шумоподавления для последующего распознавания речи, и сегодня я хотела бы поделиться с вами обзором и некоторыми находками на эту тему.

Читать далее

Приближение многочленом с условием прохождения через точки

Время на прочтение6 мин
Количество просмотров10K

При моделировании данных методом наименьших квадратов, кривая обычно не проходит через точки измерений (рис. 1).

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

Тогда читаем дальше

Увлекательная история о раскрашивании парных скобок — как VSCode ускорил раскраску в 10,000 раз

Время на прочтение26 мин
Количество просмотров27K

Прим. Wunder Fund: в этой статье из блога VSCode рассказана увлекательная алгоритмическая история о решении проблемы раскрашивания скобок. Господам удалось достичь значительногоускорения этого процесса. Нам самим очень нравится решать подобные задачи при работе над торговой системой, а если они вам тоже интересны, то пишите:)

Когда имеешь дело с глубоко вложенными скобками в Visual Studio Code — может быть непросто понять то, у каких скобок есть пары, а у каких — нет.

Для того чтобы упростить решение этой задачи, в 2006 году пользователь CoenraadS разработал восхитительное расширение для VS Code — Bracket Pair Colorizer, позволяющее раскрашивать парные скобки, и опубликовал его в VS Code Marketplace. Это расширение стало весьма популярным, теперь оно, с более чем 6 миллионами установок, входит в 10 самых скачиваемых расширений.

Для того чтобы решить проблемы, касающиеся производительности и точности работы расширения, в 2018 году CoenraadS выпустил расширение Bracket Pair Colorizer 2, которое тоже стало популярным и было установлено более 3 миллионов раз.

Читать далее

Шифры замены и табличного гаммирования

Время на прочтение17 мин
Количество просмотров30K

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

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

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

Читать далее

Ближайшие события

Антиплагиат исходного кода: гибридный подход с использованием парсера ANTLR

Время на прочтение10 мин
Количество просмотров24K

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

Читать далее

Идеальная экономика

Время на прочтение8 мин
Количество просмотров7.2K

Я не экономист, но в свете текущих событий с криптовалютами и в принципе с экономикой, хотел бы поделиться мыслями о некой идеальной экономике, вокруг которой всё сейчас и происходит.

Подробнее далее...

Логистика. Часть 3. Еще одна модель динамического ценообразования

Время на прочтение41 мин
Количество просмотров6.8K
Бывает так, что попадается какая-то задача, находится ее решение, причем довольно неплохое, но потом эта задача все равно не отпускает. Появляется навязчивая мысль о том, что у нее должно быть более оптимальное решение. Примерно так и получилось с задачей динамического ценообразования для авиабилетов, которую мы описывали более года назад в прошлой статье. Решение основывалось на алгоритме семплирования Томпсона. Компьютерное моделирование продаж показывало превосходные результаты, а тот факт, что такие гиганты как Walmart и Amazon уже давным давно и более чем успешно используют различные модификации этого алгоритма, только укрепляло уверенность в том, что мы на верном пути и иных способов оптимального решения задачи просто нет. Но в подавляющем большинстве случаев то, что отлично и везде работает, в авиаотрасли должно работать лучше. Не потому что так хочется, а потому что в этом действительно есть сильная потребность. Должно быть меньше экспериментов с ценой, она не должна меняться очень часто, а сам процесс поиска оптимальной цены должен быть еще быстрее. Но самое главное, алгоритм семплирования Томпсона не позволяет получить более-менее адекватную вероятностную модель спроса, без которой невозможно в полной мере использовать стохастическое программирование и заняться задачами глобальной оптимизации.


Читать дальше →

Формы глаголов в английском языке

Время на прочтение2 мин
Количество просмотров15K

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

Каждое из 16 времен (каждое время – в двух вариантах: действительный и страдательный залог) может быть охарактеризовано наличием или отсутствием каждого из следующих 5 признаков.

Читать далее

Спортивное программирование — социальный лифт в IT. Как его использовать школьнику, родителям школьника и разработчику?

Время на прочтение12 мин
Количество просмотров13K

С какого возраста можно обучать ребенка программированию и какой язык лучше выбрать? Как попасть на самые крутые IT-направления в лучшие вузы? Становятся ли дети разработчиков разработчиками? Как попасть на стажировку в Яндекс или на работу в Google?

Обо всем этом нам рассказывает Михаил Рубинчик — лидер и главный тренер по спортивному программированию в Уральском федеральном университете и основатель онлайн-школы по спортивному программированию SPGuide. Подробности под катом

Читать далее

Копнем поглубже: сравниваем популярные алгоритмы оптимизации с менее известными. Часть 2

Время на прочтение6 мин
Количество просмотров6.2K


Еще раз здравствуй, Хабр! Меня зовут Мария Белялова, и я занимаюсь data science в мобильном фоторедакторе Prequel. Кстати, именно в нём и обработана фотография из шапки поста.

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

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

Парадокс Монти Холла не работает

Время на прочтение3 мин
Количество просмотров29K

Недавно на просторах интернета увидел отрывок из фильма "Двадцать одно". В этом отрывке говорится о том, что парадокс Монти Холла действительно работает!

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

В голову приходили разные вопросы: чем отличается дверь без приза по отношению к другой двери без приза, как если мы выбрали именно её? А что если после первой итерации выбора двери к тебе придут Люди в чёрном и сотрут из твоей памяти это первоначальное решение? Куда тогда исчезнут лишние проценты, ведь теперь выбор останется между двумя дверьми?

Читать далее

Вклад авторов