Алгоритмы *

Решал задачу на LeetCode (Word Search) и наткнулся на незнакомый мне термин "search pruning", либо "Prune and search". Немного погуглив, узнал, что это метод решения задач оптимизации, на Википедии есть соответствующая статья (ссылка). На русском языке я не нашел такого термина, только некоторые работы на studfile и автоматический корявый перевод на Wiki5, из-за чего решил перевести статью на Википедии, которую привел выше и немного пояснить, что этот термин означает. Перевод любительский и вольный, если будут ошибки, то поправьте, пожалуйста. Перевожу для ссылки из своего расширения LeetCode to Russian и для тех, кто наткнется на такой термин и решит погуглить его на русском языке. Если в русском языке существует похожее определение, но называется по-другому, то прошу написать в комментариях, чтобы я поправил статью.

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

В данной статье выполнен обзор метода анализа иерархий (МАИ) Т.Саати в части формирования экспертами матриц парных сравнений, выявлены недостатки и разработаны рекомендации по совершенствованию МАИ.

Один из недостатков МАИ - возможное существенное отклонение элементов матрицы парных сравнений, установленных экспертами, от своих рангов, что не предусматривается МАИ и привело Т. Саати к ошибке в демонстрационном примере выбора варианта покупки дома, которую он исправил в 2015 году. Метод парных сравнений основан на так называемой шкале относительной важности, имеющей серьезные противоречия в практической реализации конкретных проектов, закономерно приводящиеся к ошибкам, что продемонстрировано на конкретном примере. Элементы матриц парных сравнений (МПС), заполненные экспертами и вычисленные через промежуточные парные отношения соседних элементов МПС всегда будут отличаться, что является противоречием.

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

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

This article analyses T. Saaty's Analytic hierarchy process (AHP) in the part of formation of pairwise comparison matrices by experts, identifies shortcomings and develops recommendations to improve AHP.

Разобран алгоритм, ориентированный главным образом на решение неправильных судоку (9х9), и на примерах показано, как можно их «подправить».
Правильное судоку имеет единственное решение, которое печатается, например, в газетах в виде одной заполненной цифрами таблицы. Но многие генераторы судоку из интернета, да и газеты часто приводят головоломки судоку с одним (но вовсе не единственным) ответом на судоку. Получить нетривиальное правильное судоку непросто. Поэтому уместно, взяв за основу опубликованные неправильные судоку, «подправить» их, дополнив некоторыми условиями, и получить подправленные судоку с одним решением, которое можно представить (и напечатать) в виде одной таблицы как ответ на судоку.

Данная публикация является продолжением первой части кодирования кириллицы в микрокодах версии М3.

 Этап 5. Применение полученного алгоритма для M3 АБВГ (второй тип библиотек в сети Интернет)

 Так как аналогично предыдущему этапу для M3 АБВГ заготовлена битовая последовательность также заранее, а основной алгоритм очень схож (необходимо будет поменять только маску и функцию комбинации итогового кода), то воспользуемся данным обстоятельством и просто продублируем страницу М3 АБВГДЕ на M3 АБВГ с учетом замены исходного микрокода.

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

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

В мире есть много вещей, которые интуитивно понятны и очевидны для нас. Например, если перед нами два похожих цветка, мы можем определить их принадлежность одному виду, даже не зная названий этих растений. Этот навык позволяет нам распознавать объекты и определять их в группы. Разумеется, подобные алгоритмы уже давно существуют в современных поисковиках Google, Яндекс и прочих. Но что, если вы проектируете обособленную систему с собственной базой изображений одной или нескольких конкретных тематик и вам необходим функционал поиска похожих изображений?

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

Полезный алгоритм построения плоскости по облаку точек МНК. Я проверял этот алгоритм на устойчивость к самым разным наборам входных данных.

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

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

В этой статье разберёмся, как работает xor-фильтр, в чём особенность чанкового хеш-индекса и как overload controller повышает стабильность работы. Все примеры разберём на примере YTsaurus, но они будут полезны любому разработчику СУБД.

Прошлый год в Computer Vision запомнился тем, что появилось множество больших претрейненных сетей (Fondation Models). Самая известная - GPT4v (ChatGPT с обработкой изображений).
В статье я попробую простым языком объяснить что это такое (для тех кто пропустил), как меняет индустрию. Какие задачи стало проще решать. Какие продукты появились в последнее время и появятся в будущем.
И можно ли уже выгнать на мороз лишних "ресерчеров"?!

• О чем на самом деле спрашивают на собеседовании по System Design в МО и почему (инсайдерская информация!).
• 7 основных шагов для решения любой задачи МО, предлагаемой на собеседовании.
• 10 вопросов из реальных собеседований по System Design в МО с подробным разбором ответов.
• 211 диаграмм, которые наглядно объясняют, как работают различные системы.

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

Привет, Хабр! Меня зовут Ричард, я работаю в команде kPHP в VK, занимаюсь разработкой kPHP, плагинов для IDE, а также другого инструментария, делая жизнь разработчиков проще. В своей работе мне приходится иметь дело с PSI деревьями, AST, самописными структурами данных и их модификациями, и даже QuickSelect (и более сложные алгоритмы) мне доводилось реализовывать. Хочу немного поговорить про один из краеугольных, пожалуй, камней в IT, а именно про «алгоритмы и структуры данных» — тема не теряет актуальности со времен появления Хабра. Заранее оговорюсь, мой пост на 90% состоит из личного опыта во время обучения, работы и преподавания.

Задание: необходимо прочитать Micro QR Code версии М3, содержащий кодовое слово, на примере закодированных слов – АБВГДЕ, абвгде, АБВГ и абвг (почему именно такое количество символов будет расшифровано далее), на основе алгоритмов, приведенных в ГОСТ Р ИСО/МЭК 18004-2015 (п. 7.4, алфавитно-цифровой и/или байтовый режим). Аналогично версий М1 и М2 данный режим невозможно прочитать стандартными ресурсами мобильных устройств, производимых GAFAM (Ассоциация отказалась и от этого режима).

Примечание: здесь и далее будет использоваться информация ГОСТ Р ИСО/МЭК
18004-2015, в оригинале ISO/IEC 18004:2015 кодовой таблицы кириллицы не существует...

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

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

В данной статье речь пойдет о продаже авиабилетов, но материал также может быть полезен всем, кто заинтересован в оптимальном ценообразовании.

Cитуация, когда недостаток производительности пытаются покрыть новым железом, не редка. Важно понимать, однако, что железо, которое мы использовали и используем сегодня, содержит в себе множество механизмов, способных актуализировать наш код на года вперед. В моем понимании программист, умеющий грамотно оперировать этими механизмами(в частности в терминах бизнес процессов, требующих 'Здесь и Сейчас', терминах поиска золотой середины между Скоростью и Дизайном) - профессионал. В этой статье речь пойдет про довольно изъезженную и, казалось бы, понятную тему - тему сортировок, но с одним небольшим дополнением - SIMD. Эту тему я выбрал не случайно: в процессе решения довольно важной для индустрии задачи возникла следующая подзадача: есть входное множество целых чисел. Каждому множеству сопоставлено свое уникальное значение. При этом множества элементов, которые отличаются между собой только порядком следования элементов, а не их значениями, считаются одинаковыми и должны возвращать одно и тоже значение. Одно из решений - посортировать множества, а затем использовать результат как ключ в Хеш Таблице. Одно из важных ограничений - количество элементов в множестве не превышает 128 элементов. Под катом рассказываю о том, как сортировать такие множества быстро.

Продолжаем публикацию лекций Олега Степановича Козлова с кафедры Ядерные Энергетические Установки МГТУ им. Баумана. Вторая часть лекции про качество САР и модель реактора как бонус.

В предыдущих сериях:

1. Введение в теорию автоматического управления.2. Математическое описание систем автоматического управления 2.1 — 2.3, 2.3 — 2.8, 2.9 — 2.13. 

3. Частотные характеристики звеньев и систем автоматического управления регулирования. 3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ. 3.2. Типовые звенья систем автоматического управления регулирования. Классификация типовых звеньев. Простейшие типовые звенья. 3.3. Апериодическое звено 1–го порядка инерционное звено. На примере входной камеры ядерного реактора. 3.4. Апериодическое звено 2-го порядка. 3.5. Колебательное звено. 3.6. Инерционно-дифференцирующее звено. 3.7. Форсирующее звено.  3.8. Инерционно-интегрирующее звено (интегрирующее звено с замедлением). 3.9. Изодромное звено (изодром). 3.10 Минимально-фазовые и не минимально-фазовые звенья. 3.11 Математическая модель кинетики нейтронов в «точечном» реакторе «нулевой» мощности. 

4. Структурные преобразования систем автоматического регулирования.

5. Передаточные функции и уравнения динамики замкнутых систем автоматического регулирования (САР).

6. Устойчивость систем автоматического регулирования. 6.1 Понятие об устойчивости САР. Теорема Ляпунова. 6.2 Необходимые условия устойчивости линейных и линеаризованных САР. 6.3 Алгебраический критерий устойчивости Гурвица. 6.4 Частотный критерий устойчивости Михайлова. 6.5 Критерий Найквиста.

7. Точность систем автоматического управления. Часть 1 и Часть 2

8. Качество переходного процесса ч.1

Вам когда-нибудь приходилось задаваться вопросом, как работает компилятор, но так руки и не дошли разобраться? Тогда этот текст для вас. Мне тоже не доводилось заглядывать под капот, но тут так случилось, что мне нужно прочитать курс лекций о компиляторах местным третьекурсникам. Кто встречался с некомпетентными преподавателями? Здравствуйте, это я :)

Итак, чтобы самому разобраться в теме, я собираюсь написать транслятор с эзотерического языка программирования wend (сокращение от week-end), который я только что сам придумал, в обычный ассемблер. Задача уложиться в несколько сотен строк питоновского кода. Основной репозиторий живёт на гитхабе (не забудьте заглянуть в мой профиль и посмотреть другие tiny* репозитории).

Формализация бизнес-процессов алгебраическими выражениями полвека будоражит умы математиков и методологов BPM (Business Process Management, ранее называемое CASE). Однако появление разнообразных алгебр процессов не добавили в практику BPM алгебраического формализма.

Алгебра алгоритмов (алгоритмическая алгебра Глушкова [GLU78], включая формализацию параллелизма), Алгебра \ исчисление процессов (CCS \ pi-calculus, CSP, ACP и др.), «Исчисление функций» (УФО, [UFO14]) не позволяют говорить о формальной (математической) теории BPM, а также инструменте, применимым бизнес-аналитиком на практике, т.е. об Алгебрах \ исчислениях бизнес-процессов - как математических абстракциях, формализующих workflow \ docflow и другие составляющие бизнес-процессов (Алгебре \ исчислении workflow).

Всем салют!

Хочу рассказать вам историю о том, как я начинал с уровня — «не могу решить даже 1 easy задачу из 10» до уровня — «могу решить каждую вторую medium задачу» и прошел несколько coding сессий в таких компаниях как Meta, Booking, Careem, Avito...

Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.

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