Алгоритмы *

Алгоритм Шора позволит квантовым компьютерам будущего быстро факторизовывать большие числа, нарушая многие протоколы онлайн-безопасности. Теперь учёные показали, как сделать это ещё быстрее. 

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

Как правильно использовать возможности параллельного программирования?
Зачем программистам математика и зачем знать алгоритмы?

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

Весь код из статьи находится здесь.

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

На связи участница профессионального сообщества NTA Ульянова Дарья.

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

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

Добрый день, уважаемые читатели Хабра!

CatBoost – алгоритм, разработанный специалистами из Yandex, представляет собой нечто большее, чем просто ещё один инструмент в арсенале данных науки. CatBoost – это гармоничное сочетание инноваций и эффективности, особенно когда дело доходит до работы с категориальными данными.

Первые шаги CatBoost были сделаны в 2017 году, когда мир уже знал о таких гигантах, как XGBoost и LightGBM. В чем же заключается уникальность CatBoost? Его разработка была направлена на решение специфических проблем, связанных с категориальными данными – той самой головной боли многих специалистов в области машинного обучения. С тех пор CatBoost прошёл долгий путь развития и совершенствования, став не просто эффективным инструментом, но и частью больших исследовательских проектов в различных сферах от финансов до биоинформатики.

CatBoost выделяется на фоне других алгоритмов градиентного бустинга благодаря ряду ключевых особенностей:

С вами Алексей Ложкинс, эксперт по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем цифровые продукты для логистической отрасли, в первую очередь, для ж/д перевозок.

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

Моделирование маршрута в виде задачи коммивояжера позволит построить маршрут по всем запланированным локациям без повторений с заданным критерием качества (время, стоимость). Рассмотрим несколько подходов к решению оптимизационной задачи (TSP) с использованием пакета ORTools.

Привет, Хабр! Иногда сидишь, решаешь задачу, и, в процессе решения, чтобы продвинуться на следующий шаг, нужно придумать как сделать что-то очень простое - ну, то что наверняка уже делалось тысячи раз другими людьми. Кинувшись в поисковик перелопачиваешь какое-то количество литературы и вдруг понимаешь что либо ты просто искать не умеешь, либо это действительно никто до тебя не делал, или делал но об этом не писал. В какой-то момент проще просто взять и решить задачу самому…

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

Традиционное определение для операции возведения в натуральную степень (или целую положительную) вводится примерно следующим образом:

Возведе́ние в сте́пень — арифметическая операция, первоначально определяемая как результат многократного умножения числа на себя.

Но более точная формулировка всё же другая:

Возведение числа X в целочисленную степень N — арифметическая операция, определяемая как результат многократного [N по модулю раз] умножения либо деления единицы на число X.

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

В этой статье я расскажу об алгоритме процедурной генерации лабиринтов методом поиска в глубину (Randomized depth-first search with recursive backtracking).

Привет, Хабр! Меня зовут Владислав, и один из моих проектов — интернет‑магазин карликовых кроликов. Сегодня по приглашению коллег из ChatApp, я расскажу, как автоматизировал свой бизнес. Нет, речи ни о каком роботизированном выращивании кроликов не пойдет — только о продажах. Для меня это был интересный опыт, который в итоге помог прийти к значительному росту показателей. В этой статье мы поговорим о программировании чат‑ботов, об особенностях ведения бизнеса на АВИТО, а также немного о ботовой этике и эстетике. Текст будет интересен тем, кто является владельцем или открывает свой интернет‑магазин, тем, кто сомневается, что чат‑бот может быть этичным и удобным решением как для покупателя, так и для продавца.

Давайте поговорим о лексическом анализе. Сначала я собирался назвать этот пост «Реализуем токенайзер», но ветер переменился, времена изменились… и, чтобы не утонуть в потоке комментариев вида «фыр, а где мой BPE-токенизатор LLama, который вы мне обещали», ограничимся пока лексическим анализом.

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

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

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

Довольно слов, приступим.

Всем маткульт-привет! В этой статье мы продолжаем и заканчиваем написание консольного инженерного калькулятора.

В прошлой части мы научились разбивать исходное математическое выражение формата (log2(18)/3.14)*sqrt(0.11^(-3)/0.02)на токены. На выходе мы получаем массив токенов, каждый их которых содержит информацию о типе (оператор, скобка, число, ...) и об ассоциативности, если он таковую имеет.

Теперь мы хотим привести выражение к виду обратной польской записи (RPN), чтобы затем удобно его посчитать. Это нам позволяет сделать изобретенный Эдсгером Дейкстрой алгоритм сортировочной станции.

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

Я решил всерьёз выяснить, чему равна эта вероятность в зависимости от длины случайной строки? Можно ли получить явную математическую формулу для ответа? Что, если взять другое слово? Что, если взять другой алфавит?

Обо всём по порядку.

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

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

Доброго времени суток, когда вы в последний раз играли в крестики-нолики? Вспомните поле которое вы рисовали на бумаге: 3x3? 5x5? А что вы скажете насчёт 19x19? "Долго будем играть!" - и это только часть проблемы. Передо мной встала такая задача в ходе хакатона от компании Тинькофф - написать бота для игры в крестики-нолики на доске 19x19 с поиском самого лучшего хода за небольшое время.

Полая Луна. ChatGPT не уверен в себе. Это короткая статья, в которой сначала я приведу мнение ChatGPT по поводу того, что луна это полая сфера. Он уверен что Луна НЕ полая.
И после нескольких словесных манипуляций его мнение меняется. Он уже не уверен и считает что Луна вполне может быть и полой. Манипуляции это просто наводящие вопросы и подсовывание доказательств на основе собственных ответов ChatGPT.

Вот с чего ИИ начал: "Гипотеза о пустоте внутренней части Луны противоречит данным, полученным от различных космических миссий "

А вот к чему пришел: "В настоящее время отсутствуют непреложные доказательства, подтверждающие или опровергающие полую структуру Луны."

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

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

Двумерное преобразование Фурье — один из важнейших алгоритмов компьютерной науки этого столетия. Он нашел широкое применение в нашей повседневной жизни — от фильтров Instagram до обработки MP3-файлов.

Наиболее частой реализацией, используемой рядовым пользователем, иногда даже неосознанно, является адаптация из NumPy. Однако, несмотря на популярность, их алгоритм не является самым эффективным. С помощью нескольких простых манипуляций и статьи 2015 года мы обошли алгоритм NumPy по производительности аж на 30-60%. Основная проблема этой реализации заключается в том, что она изначально основана на слабом с точки зрения производительности алгоритме.

По своей сути алгоритм, реализуемый NumPy, является поочередным применением обычного одномерного БПФ (FFT) к двум измерениям, что очевидно не может быть оптимальным решением.

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