Алгоритмы *

Некоторые оптимальные алгоритмы, оказывается, можно вывести из неоптимальных, пользуясь эквивалентными преобразованиями алгоритма. Бёрд и Меертенс разработали формализм, который устанавливает свойства функций высшего порядка map, fold, scan, позволяющие преобразовывать алгоритмы в эквивалентные. (См. также на Вики). Ниже представлен вольный перевод статьи Бёрда.

Рассмотрим задачу поиска максимальной суммы сегмента массива. Эту задачу можно переформулировать в виде математически точного ответа:

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

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

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

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

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

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

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

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

Я расскажу, как в 2ГИС устроен алгоритм построения маршрутов в целом и как мы адаптировали его под грузовики — например, учили его строить неоптимальные по времени маршруты.

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

Материал может представлять интерес для инженеров, связанных с проектированием и разработкой в области 3D.

В последнее время я часто писал о вычислительной сложности, алгоритмах и моделях (например 1, 2, 3). Вычислительные модели лежат в основе вычислительной науки и не только её, и всё же немногие обладают чётким представлением о том, что такое вычислительная модель на самом деле. Это программное обеспечение? Или алгоритм? Как это связано с математическими моделями? Какие языки или обозначения подходят для описания вычислительной модели? Сделает ли ИИ вычислительные модели устаревшими? В процессе обсуждения с некоторыми товарищами сформулировалось достаточно подробное и, надеюсь, понятное описание, которое я и хотел бы представить в этой статье.

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

Если свести процесс научного исследования к его основам, то он предполагает создание и итеративное совершенствование моделей, описывающих эмпирические наблюдения. Таким образом, модели и наблюдения являются основными понятиями науки. Две давние специализации многих дисциплин — это теоретик, придумывающий и совершенствующий модели, и практик, проектирующий конкретные установки для проведения наблюдений.

Путешествие от шифра Цезаря до RSA. Прикладная теория чисел.

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

Меня зовут Александр Певненко, я Java developer в СберТехе. Вместе с командой развиваю Platform V DataSpace — BaaS-продукт, обеспечивающий базовые сервисы для работы с данными.

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

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

Поэтому здесь я приведу несколько «базовых» алгоритмов, знание которых помогает мне работать с прицелом на эффективность кода, и дополню примерами на Python и Java.

Публикация является продолжением обсуждения алгоритмов вычисления первой производной дискретной функции (функции, заданной массивом {аргумент: значение}, или массивом узловых значений). В части первой обсуждались функции из библиотеки NumPy, и был предложен альтернативный алгоритм, повышающий точность расчетов на границах области определения функции. В настоящей публикации предложены 2 алгоритма на основе метода конечных элементов (МКЭ, Finite Elements Method), один из которых показал на тестовых функциях лучшие результаты в сравнении с альтернативами.

Продолжаем разбирать подходы призеров Kaggle-соревнований от американской национальной футбольной лиги (NFL). Участники этого челленджа детектировали столкновения игроков в американском футболе, анализируя данные с видеокамер и датчиков, прикрепленных к форме футболистов. В продолжении первой части статьи расскажу про самые успешные подходы к этой задаче.

template <class ForwardIt, class T, class Compare>
constexpr ForwardIt sb_lower_bound(
      ForwardIt first, ForwardIt last, const T& value, Compare comp) {
   auto length = last - first;
   while (length > 0) {
      auto rem = length % 2;
      length /= 2;
      if (comp(first[length], value)) {
         first += length + rem;
      }
   }
   return first;
}

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

За последние десять лет масса технологий, имеющих хоть какое-либо отношение к информационным, претерпела массу изменений. Более того, многие сферы жизни, изначально не имеющие к IT никакого отношения, также преобразились до неузнаваемости и приобрели некий IT-шный бэкграунд. Немаловажную роль в этих процессах информатизации сыграла концепция Интернета вещей (IoT). С самого появления этой концепции было понятно, что она серьёзно повлияет на все сферы деятельности человека, экономические и социальные процессы, а спустя несколько лет после её появления технология оказалась на карандаше Национального разведывательного совета США и была занесена в список «подрывных инноваций».

По мере развития технологии IoT, ставшей устойчивой тенденцией на протяжении последних десяти лет, она наполнялась технологическим содержанием и практическими стандартами. При этом до некоторого времени комплексная информационная безопасность этой технологии вообще никого не интересовала. Если внедрялись какие-то меры безопасности, то по крайне остаточному принципу. Учитывая, что изначально никто никаких специальных стандартов для устройств IoT не разрабатывал, в основном использовали то, что было. Понятно, что «взрослые» варианты стандартов подходят для IoT не в полной мере. Требуются технологии, обладающие высокой производительностью в ограниченных средах. Устройства IoT связаны достаточно жёсткими ограничениями по питанию, памяти и вычислительным ресурсам.

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

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

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

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

В последнее время весьма актуальным является вопрос противодействия БПЛА типа «квадро/гексо/октокоптер», использующих для своего полета бесколлекторные двигатели (БКД). Одним из основных путей противодействия таким БПЛА (кроме, конечно, физического воздействия ракетным или стрелковым оружием) является постановка помех каналам управления и навигации посредством радиоэлектронного излучения сигналов с определенными характеристиками.

Конечно, использование классического метода постановки так называемой «заградительной» помехи является наиболее простым способом радиоэлектронного подавления, когда в заданном частотном диапазоне формируется мощный сигнал, препятствующий нормальному функционированию БПЛА, включая, конечно, подавление сигналов системы глобального позиционирования. Однако у этого метода есть и недостатки, основной из которых – необходимость значительных энергозатрат и связанные с ними повышенные риски обнаружения источника помех средствами радиомониторинга противника и вероятного последующего огневого поражения. Следовательно, в интересах сохранения эффективности радиоэлектронного воздействия при снижении уровня излучаемой мощности помеховых сигналов необходимо формировать такой сигнал не в виде сплошного спектра в заданной полосе частот, а в виде какой-то «оптимальной» структуры, обеспечивающей наибольшую степень влияния на оригинальный сигнал в системе управления. Общеизвестно, что оптимальная помеха по своей структуре должна быть близка к структуре подавляемого сигнала. Однако есть много нюансов такого соответствия. В данной статье как раз рассматриваются особенности воздействия помехового сигнала на управляющий для частного случая в области борьбы с БПЛА – воздействия непосредственно на контроллер управления вращением бесколлекторного двигателя, что может расширить возможности противодействия этим БПЛА, фактически нарушая управление даже при сохранении командной связи при использовании вероятным противником специальных мер защиты.

Всем привет! Меня зовут Нурислам aka tonitaga, данная статья является продолжением статьи Базовые алгоритмы на графах.

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

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

Привет, Хабр! Я недавно начал свой путь в data science, хочу поделиться реализацией алгоритмов по обработке матриц.

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

Как подтвердит любой, кому когда-либо доводилось проходить собеседование по программированию, при наличии арифметической и геометрической прогрессии геометрическая всегда возобладает. При горизонтальном масштабировании расходы растут линейно (арифметически). Но по закону Мура вычислительные мощности со временем растут экспоненциально (геометрически). Это означает, что можно несколько лет ничего не делать, а затем масштабировать систему вертикально и получать улучшение на порядки. За двадцать лет плотность транзисторов возросла в  1000 раз. Это значит, что такая задача, для решения которой в 2002 году потребовались бы тысячи машин, сегодня выполнима всего на одной.