Идентификация звёзд и при чём тут сингулярное разложение

И знаете, с этим трудно не согласиться! Сингулярное разложение матриц (Singular Value Decomposition) используется в алгоритмах сжатия данных, теории автоматического управления, машинного обучения и много где ещё. Поскольку SVD не является главным объектом исследования данной статьи, я предоставляю читателю возможность самостоятельно ознакомиться с примерами ниже. Если же сингулярное разложение не вызывает вопросов, то перейдём к самому интересному!

https://habr.com/ru/articles/990722/

Алгоритмы и Структуры данных

Вероятности и .NET: сравниваем библиотечные решения для оценки спортивных событий и не только

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

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

В этой статье рассказываю, как формулируется гипотеза, как из неё строится модель, почему это важнее, чем «просто посчитать формулу», и как мы выбирали между несколькими .NET-библиотеками по точности и скорости. Всё на примере тенниса. Это один из самых сложных видов спорта для моделирования: стандартные подходы здесь не работают, счёт специфический, а сила игрока выражается не в счёте, а в вероятности взять очко на своей подаче.

https://habr.com/ru/articles/990002/

Алгоритмы и Структуры данных

Как научиться решать алгоритмические задачи?

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

https://proglib.io/p/algorithmic-tasks

Алгоритмы и Структуры данных

Задача коммивояжёра — ещё немного больше, ещё немного быстрее

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

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

https://habr.com/ru/articles/740984/

Алгоритмы и Структуры данных

Разделяй и властвуй. Повышение эффективности алгоритмов. Часть 2

На примере из прошлой части, попробуем сформулировать и обобщить принцип «Разделяй и властвуй». Мы беремся за проблему, размера n, делим эту проблему на подзадачи размером n/b. Количество таких подзадач обозначим числом a. И еще имеется задача скомпоновать результаты выполнения этих a задач размером n/b в итоговый результат для задачи размера n, который будем считать задачей полиномиальной сложности степени c, O(nc) . Если задача компоновки будет не полиномиальной, то все изложение резко усложнится. Поэтому, давайте позволим задаче компоновки быть полиномиальной, тем более в это попадает очень большое количество алгоритмов.

https://habr.com/ru/articles/742404/

Алгоритмы и Структуры данных

Задача о нижней оценке на поиск в таблице Юнга

Читателю не столь хорошо знакомому с теоретической информатикой может показаться удивительным, что нижние оценки известны лишь для малого числа задач. Когда оценивают сложность алгоритма, используют O-нотацию — асимптотически верхнюю оценку на сложность алгоритма. Так, хорошо известно, что у сортировки слиянием сложность O(n \log n).Из теории известно, что ни одна сортировка сравнениями не может сортировать асимптотически лучше чем за n \log n(пишут \Omega(n \log n)), отсюда для сортировки слиянием берётся нижняя оценка. Верхняя оценка сложности алгоритма, решающего задачу, является и верхней оценкой сложности самой задачи, поэтому сортировки сравнениями имеют точную асимптотическую оценку \Theta (n \log n).

https://habr.com/ru/articles/742622/

Алгоритмы и Структуры данных

5 страшилок об искусственном интеллекте

Разработки на основе искусственного интеллекта нередко вызывают беспокойство широкой общественности. Чувство отторжения и неприязни, которое вызывает человекоподобие искусственного интеллекта, получило собственное красивое хоррор-название - "эффект зловещей долины" (термин из эссе Bukimi No Tani 1970 года). Собрали несколько реальных историй, сильно напоминающих сюжеты сериала «Черное зеркало» об угрожающих миру технологиях.

https://habr.com/ru/companies/mvideo/articles/741008/

Алгоритмы и Структуры данных

Я создал вдвое более быстрый лексер, но обнаружил, что узким местом был ввод-вывод

Я создал лексер ассемблера ARM64 (ну, точнее, сгенерировал его из моего собственного генератора парсера, но пост не об этом), обрабатывающий код на Dart вдвое быстрее официального сканера. Этого результата я добился при помощи статистических методик надёжного измерения малых различий в производительности. Затем я провёл его бенчмарк на 104000 файлов и обнаружил, что узким местом был не мой лексер, а ввод-вывод. Это история о том, как я случайно узнал, почему pub.dev хранит пакеты в виде файлов tar.gz.

https://habr.com/ru/articles/989588/

Алгоритмы и Структуры данных

Пишем игру-головоломку под macOS на SwiftUI [StarDust Collector]

В прошлой статье я поделился опытом, как писал с помощью ИИ кастомный TO-DO-лист под macOS. Опыт оказался противоречивым, но приложение всё-таки получилось и даже работало.

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

https://habr.com/ru/articles/991402/

Алгоритмы и Структуры данных

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

Подмести весь супермаркет Albert Heijn? Звучит несложно. Собственно, так и должно быть.

Но я студент-информатик, и у меня есть одна проблема — склонность оптимизировать процессы, которые, быть может, оптимизации не требуют.

Поэтому вместо того, чтобы просто делать свою работу, ну то есть… подметать… я поступил так, как поступил бы любой здравомыслящий человек: превратил план этажа супермаркета в решётчатый граф, создал визуальный редактор и написал на C++ оптимизатор пути, используя алгоритм имитации отжига (simulated annealing).

Но прежде, чем переходить к рассказу о том, как всё пошло наперекосяк, и как я осознал, что из-за таких вот вещей страдаем мы все, задам вам один вопрос:

Если бы вы на один день взялись делать мою работу (я бы не советовал, но чисто теоретически), и вам нужно было бы подмести весь этаж в Albert Heijin, какой бы маршрут вы выбрали — А или B?

https://habr.com/ru/companies/ruvds/articles/990594/

Алгоритмы и Структуры данных

Noise-Based Logic: Введение в шумовую логику

- Как передавать тысячи бит данных параллельно по одному электрическому проводу?
- Как снизить энергопотребление чипов на 2-3 порядка и навсегда забыть про утечку по сторонним каналам?
Эти кликбейтные вопросы перестанут восприниматься таковыми после прочтения этой статьи.

Я постараюсь объяснить, что за инопланетная технология скрывается за термином “Noise-Based Logic” (NBL). Подробно изложу только теоретические основы, чтобы понять идею, основные принципы и возможности. В любом случае, рекомендую вам самостоятельно ознакомиться с оригинальными статьями, и возможно, внести свой вклад. Это очень перспективная область исследований с относительно низким порогом входа, что само по себе редкость в наше время.

https://habr.com/ru/articles/991506/

Алгоритмы и Структуры данных

Платформа очередей для клиентского сервиса в кровавом энтерпрайзе

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

https://habr.com/ru/articles/991552/

Алгоритмы и Структуры данных

Антирекурсия. Часть 1

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

https://habr.com/ru/articles/991708/

Алгоритмы и Структуры данных

Как я пытался сжимать смыслы вместо байтов

Два часа ночи. Я пытаюсь впихнуть документацию проекта в контекст Claude. 847 страниц. Где-то 1.2 миллиона токенов. Контекстное окно — 200 тысяч.

Делаю то, что делают все: режу, суммаризирую, выбрасываю «неважное». Каждый раз теряю что-то критичное. Это уже третий час, кофе кончился, и в голову приходит идея, которая кажется гениальной.

https://habr.com/ru/articles/991800/

Алгоритмы и Структуры данных

Как веб-камера и нейросеть помогают удалённо измерять частоту дыхания

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

Метод Алексея Протопопова решает эту проблему. В его основе лежит сегментация изображения тела нейросетью и продвинутая фильтрация помех. Метод протестировали на видеозаписях 14 добровольцев: 8 мужчин и 6 женщин в возрасте от 20 до 65 лет. Общая продолжительность записей превысила 2,5 часа.

https://habr.com/ru/companies/kryptonite/articles/991902/

Алгоритмы и Структуры данных

Треугольник Серпинского — Canvas, JS

Треугольник Серпинского — фрактал, математическое описание которого опубликовал польский математик Вацлав Серпинский в 1915 году.

В этом посте мы напишем рекурсивный алгоритм отрисовки данного известного фрактала в canvas с помощью JS

https://habr.com/ru/articles/740658/

Алгоритмы и Структуры данных

Метод наименьших квадратов Гаусса с весовыми коэффициентами отклонений

В моей практике метод наименьших квадратов Гаусса используется в двух случаях.

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

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

В качестве примера возьму измерение МДС (магнитодвижущая сила) срабатывания геркона.

Согласно ГОСТ 25810 «Контакты магнитоуправляемые герметизированные. Методы измерения электрических параметров» МДС срабатывания определяется по значению тока, протекающего через измерительную катушку в момент срабатывания геркона.

https://habr.com/ru/articles/992372

Алгоритмы и Структуры данных

Вопросы по алгоритмам с собеседований

Вопросы по алгоритмам – обычное явление на собеседовании. Мы собрали для вас рекомендации, которые помогут ответить на большинство вопросов.

https://proglib.io/p/algorithm-questions

Алгоритмы и Структуры данных

По данным McKinsey, генеративный AI экономит до 30% рабочего времени. Проблема в том, что лидеры рынка меняются каждые пару месяцев — и вместе с этим растёт количество вкладок, аккаунтов и подписок.

MetaMind решает это: все основные нейросети для текста и изображений собраны в одном телеграм-боте.

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

Метод наименьших квадратов Гаусса с весовыми коэффициентами отклонений

В моей практике метод наименьших квадратов Гаусса используется в двух случаях.

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

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

В качестве примера возьму измерение МДС (магнитодвижущая сила) срабатывания геркона.

Согласно ГОСТ 25810 «Контакты магнитоуправляемые герметизированные. Методы измерения электрических параметров» МДС срабатывания определяется по значению тока, протекающего через измерительную катушку в момент срабатывания геркона.

https://habr.com/ru/articles/992372/

Алгоритмы и Структуры данных

Разбираю статью про FS-Researcher: как учёные научили ИИ вести конспекты

Наткнулся на свежую статью из University of Science and Technology of China, и она меня зацепила. Не потому что там какой-то прорыв в архитектуре нейросетей — как раз наоборот. Решение настолько простое, что удивляешься: почему раньше так не делали?

Проблема, которую они решают, знакома каждому, кто пытался использовать ChatGPT или Claude для серьёзного ресёрча. Вы просите модель изучить тему, она начинает искать, читать страницы, накапливать информацию... и в какой-то момент контекстное окно заполняется. Новые факты начинают вытеснять старые. Отчёт получается поверхностным, потому что модель буквально забывает, что нашла в начале.

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

https://habr.com/ru/articles/992836/

Алгоритмы и Структуры данных