Информатика, вычислительная техника и упровление. Рубрика в журнале - Труды Московского физико-технического института
О неускоренных эффективных методах решения разреженных задач квадратичной оптимизации
Статья научная
В работе исследуется класс разреженных задач квадратичной оптимизации и его обобщения, на которых будут эффективно работать специальные модификации обычного (неускоренного) прямого градиентного метода с l1-нормой и метода условного градиента (Франк-Вульфа).
Бесплатно
Обеспечение секретности передачи данных в беспроводных сетях с сетевым кодированием
Статья научная
В этой статье мы рассмотрим схему, позволяющую обеспечить анонимности в сети с использованием сетевого кодирования. Предлагаемый метод основывается на методе COPE, который обычно используется для повышения эффективности и пропускной способности передачи данных. Данный метод был подвергнут модификации для достижения анонимности контрагентов при передаче сообщений. Идея предлагаемых модификаций состоит в том, что в рассматриваемой схеме адрес получателя невозможно узнать, не получив всех частей исходного сообщения.
Бесплатно
Оптимальное управление системой скважин на основе уравнений двухфазной фильтрации
Статья научная
Предложена оригинальная вычислительная технология для решения задач управления режимами работы скважин и назначений скважин (нагнетательная/добывающая) при известном их местоположении. Технология включает в себя разработанный метод определения оптимального управления режимами работы скважин, известный метод Л.С. Понтрягина и новый алгоритм направленного перебора вариантов назначения скважин для определения наилучшего варианта. С использованием предложенной технологии определены наилучшие варианты назначения скважин в симметричных элементах различных схем их расстановки. Целевой функционал полагался равным объему извлекаемой нефти за определенный период времени. Показано преимущество нового алгоритма по сравнению с ранее известными.
Бесплатно
Оптимальные и субоптимальные подпространственные коды-спреды
Статья научная
Работа посвящена подпространственным кодам с максимальным кодовым расстоя- нием, которые называются спредами. Представлены конструкции многокомпонентных кодов с нулевым префиксом (МНП) и оценены их мощности. Показано, что при опреде- лённых условиях мощность МНП кодов-спредов достигает верхней границы, в других случаях находится вблизи верхней границы. Соответственно этим данным такие ко- ды названы оптимальными или субоптимальными. Оценена эффективность в виде отношения мощности кода к верхней границе. Расчёты показали, что для многих па-раметров субоптимальных кодов эффективность ≥ 0.99.
Бесплатно
Оптимизация алгоритма KNN для классификации текстов
Статья научная
Рассмотрены два подхода повышения быстродействия алгоритма KNN для классификации текстов: уменьшение количества потенциальных ближайших соседей и использование двоичной кучи при поиске K ближайших соседей.
Бесплатно
Статья научная
В статье собраны вместе основные современные конструкции работы с алгоритмами (численными методами) решения задач выпуклой оптимизации. В частности, с помощью искусственного введения неточности в вычисление градиента, следуя Ю.Е. Нестерову, рассматривается «адаптивная игра на гладкости задачи», позволяющая использовать методы, настроенные на гладкие задачи для решения негладких задач; рассматривается конструкция рестартов, позволяющая получить из численного метода, ищущего решение задачи выпуклой оптимизации, метод, пригодный к использованию для задач сильно выпуклой оптимизации; рассматривается прием регуляризации, позволяющий сводить любую выпуклую задачу к сильно выпуклой. Все эти (и некоторые другие) конструкции (например, композитной оптимизации) описываются, исходя из одной общей линии - руководствуясь принципом «бритвы Оккама»: попытаться изложить современное состояние «оптимальных» численных методов выпуклой оптимизации в пространствах больших размеров (для детерминированных постановок: размерность пространства больше необходимого числа итераций). Статья написана по просьбам коллег и студентов, планирующих использовать собранные в статье конструкции в своей работе.
Бесплатно
Статья научная
Рассматриваются особенности функционирования системы радиолокационного автосопровождения космических объектов по дальности, связанные с использованием зондирующих сигналов с линейной частотной модуляцией. Оцениваются границы устойчивости и точностные характеристики алгоритма оценки параметров движения входящих в атмосферу космических объектов, реализующего процесс автосопровождения по дальности.
Бесплатно
Статья научная
В статье рассматриваются принципы работы поисковой системы «Кортекс», кото- рая основана на повышении производительности и надёжности работы за счёт большо- го количества дешёвых ПК, объединённых в одну локальную сеть и управляемую сер- вером. Описаны принципы формирования запросов в конечный ПК, методы обработки ответов. В статье также описывается метод поиска неисправностей и автоматического их исправления путём введения в эксплуатацию резервных вычислительных машин.
Бесплатно
Статья научная
Помехоустойчивая обработка речевых сигналов является одной из основных проблем практической реализации систем распознавания речи (СРР). Предлагаемый алгоритм помехоустойчивой обработки представляет собой фильтрацию речевых сигналов с использованием методов комплементарной множественной декомпозиции на эмпирические моды (КМДЭМ) и независимого компонентного анализа (НКА). Зашумленный речевой сигнал адаптивно раскладывается на частотные составляющие - эмпирические моды (ЭМ) - с помощью метода КМДЭМ. Применение метода КМДЭМ для разложения сигналов позволяет исключить явление смешивания ЭМ, возникающее при обработке сигналов, содержащих кратковременные и несоизмеримые по масштабу участки. Из полученного набора ЭМ определяется мода, содержащая основной шум, посредством оценки весовых энергетических и шумовых коэффициентов мод. Далее исходный зашумленный речевой сигнал и ЭМ с основным шумом подвергаются обработке с помощью метода НКА. В результате выделяется отфильтрованный речевой сигнал. Применение предложенного алгоритма фильтрации способствует повышению устойчивости к шумам СРР и точности распознавания соответственно. Результаты исследований предложенного алгоритма демонстрируют эффективное подавление шума, в том числе и для малых значений отношения сигнал/шум.
Бесплатно
Построение метода упругой миграции сейсмических данных в приближении Борна
Статья научная
Ввиду того, что нефть и природный газ являются ключевыми топливными ресурсами, поиск и разведка их месторождений является приоритетной задачей. Для её решения применяются полевые исследования, называемые сейсмической разведкой, задачей которых является восстановление структуры подповерхностного пространства. Огромное значение имеет задача миграции - определение положений отражающих горизонтов по известной опорной модели среды. Для её решения в акустическом приближении разработано множество методов, например, метод Кирхгофа, метод Борна, миграция конечными разностями и т.д. Целью настоящей статьи являлось исследование сейсмических полей в полной упругой постановке, которая с большей точностью описывает динамические процессы, происходящие в реальных гелогических средах. Авторами предложен метод упругой миграции, основанный на приближении Борна для однородной фоновой модели среды. Проведено его тестирование на модели, схожей по структуре отражающих границ с моделью Marmousi, широко используемой для тестирования методов компьютерного моделирования сейсмических процессов.
Бесплатно
Статья научная
Рассматривается применение технологий параллельного программирования OpenMP и POSIX Threads для решения гиперболических систем уравнений. Данные технологии предназначены для систем с общей памятью. Кроме этого, рассматривается увеличение производительности при использовании векторных инструкциий процессора. Решается задача распространения динамических волновых возмущений в геологической среде в упругой постановке в двумерном случае. Для численного решения используется сеточно-характеристический метод. Исследуется влияние привязки потоков к определенным ядрам процессора в NUMA-системах.
Бесплатно
Разработка линзовой антенны в виде волноводной решетки с веерной диаграммой направленности
Статья научная
Рассматривается задача моделирования линзовой антенны, которая формирует косекансный луч. Особенностью антенны является то, что луч поворачивается за счет механического поворота линзы при неподвижном облучателе. Задача формирования веерного луча осуществляется путем профилирования поверхности линзы, которая состоит из волноводов квадратного сечения.
Бесплатно
Разработка сети на кристалле для перспективных многоядерных микропроцессоров
Статья научная
Описана проблема эффективной организации соединений на кристалле многоядер- ного микропроцессора с распределённым общим кэшем. От сети соединений требуются высокая частота передачи пакетов, низкие задержки, поддержка качества обслужива- ния и сохранение порядка пакетов. Предложено решение на основе топологии сетка, деления сети на строки и столбцы и экспресс-виртуальных каналов с доработками их механизма предотвращения «голодания». Для размеров сети от 4 × 4 до 16 × 16 оцене- ны производительность и размер роутеров предложенной схемы и нескольких тради- ционных. Только предложенная схема продемонстрировала все требуемые качества в сочетании с хорошей масштабируемостью.
Бесплатно
Статья научная
В работе исследуются различные рандомизации метода зеркального спуска для задач huge-scale оптимизации с разреженной структурой. В качестве одного из примеров приложения приводится задача PageRank.
Бесплатно
Статья научная
В статье рассмотрена задача распознавания жестов, выполняемых жезлом (палоч- кой), находящимся в руке человека, на основе анализа потока данных с инерциального модуля, встроенного внутрь палочки. Для анализа использована рекуррентная ней- ронная сеть с долгой краткосрочной памятью. Приведены результаты эксперимента по распознаванию четырех простейших жестов. Для результатов распознавания даны традиционные метрики, описывающие их качество.
Бесплатно
Свёрточная нейронная сеть для решения задачи классификации
Статья научная
В данной работе рассмотрена свёрточная нейронная сеть для решения задачи классификации, ее структуру, метод обучения и преимущества перед полносвязной нейронной сетью.
Бесплатно
Семантика и семантически эквивалентные трансформации UML-диаграмм классов
Статья научная
В статье формализуются такие понятия, как объектно-ориентированная архитектура ПС, диаграмма классов, класс, интерфейс, отношение наследования, агрегация и т.д. В статье описывается формальная семантика UML-диаграмм классов, на основе которой возможно выполнять сравнение двух диаграмм классов между собой, производить трансформации, проверяя инвариантность семантического значения.
Бесплатно
Статья научная
Изложены основные положения новой концепции предварительной сравнительной оценки адаптивности сетей с произвольной топологией. В основе подхода - эквивалент- ность сети и хаотического ансамбля связанных отображений. Структуру связей сети всегда можно представить в виде матрицы. Описан алгоритм создания ансамбля логи- стических отображений с матрицей связей, структурно сопряженной исследуемой сети. Утверждается, что анализ перегрузки хаотического ансамбля позволяет осуществить предварительную оценку адаптивности сетей с соответствующей топологией. Метод применён к сетям с линейной и простой кольцевой топологией. Продемонстрирована нечувствительность метода ко всем свойствам хаотического ансамбля, кроме перегруз- ки. Оказалось, что для достаточно длинных цепочек и колец адаптивность не зависит от количества узлов. Получено и проинтерпретировано иерархическое соотношение между скоростями разрушения динамики для разных конфигураций цепочек отображений.
Бесплатно
Стохастические градиентные методы с неточным оракулом
Статья научная
В работе предпринята попытка описать современное состояние методов проекции градиента (в том числе прямых методов и методов покомпонентного спуска) решения задач выпуклой стохастической оптимизации с неточным оракулом (неточность неслучайной природы), выдающим стохастический субградиент. Заметная часть приведенных в статье результатов была получена относительно недавно. Цель данной работы - собрать все вместе и посмотреть на разнообразные факты из этой области с единой позиции.
Бесплатно
Статья научная
Представлен обзор современных численных методов поиска барицентра Вассерштейна конечного семейства вероятностных мер с одинаковым конечным носителем. Такие задачи в последнее время стали очень популярны в связи с всевозможными приложениями к сравнительному анализу изображений, в частности, к обнаружению разладок в ряде изображений. Например, подобные задачи возникают при изучении деятельности головного мозга. В основном мы исходили из цикла работ M. Cuturi с соавторами. Общая идея этих работ - найти барицентр вероятностных мер согласно энтропийно-регуляризованному расстоянию Вассерштейна. Такое (регуляризованное) расстояние можно заметно эффективнее посчитать, чем исходное расстояние Вассерштейна. В одной из работ отмеченного цикла [8] содержалась идея сочетания метода Синхорна (балансировки) для решения внутренней задачи (расчета соответствующих регуляризованных расстояний и их субградиентов) и быстрого градиентного метода для решения внешней задачи (поиск барицентра). К сожалению, в описанном авторами виде метод оказался не пригодным для использования на практике (не было также никаких теоретических гарантий его сходимости). В [1] показано, как можно доработать данный метод (в частности, доказана сходимость предложенной модификации). Однако мы были сконцентрированы на другом приложении (к поиску равновесий в многостадийных транспортных моделях). В данной работе мы рассматриваем оба отмеченных приложения. Главным результатом работы является разработка в общем случае (не только для этих двух приложений) концепции суперпозиции методов, когда мы можем выделить в исходной задаче часть переменных, по которым задача эффективно решается внутреннем методом (но допускается, что лишь приближенно) при замороженных остальных переменных. А по оставшейся группе переменных запускается внешний метод, на каждой итерации которого требуется запускать внутренний метод. В статье получен частичный ответ на довольно общий вопрос: как оптимально сочетать эти методы (внутренней и внешний), т.е. насколько точно надо решать на каждой итерации внешнего метода внутреннюю задачу, чтобы минимизировать общее время работы метода при заданной точности решения, которую хотим получить?
Бесплатно
