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

Данная статья посвящена разработке метода учета временных ограничений при оптимизации быстродействия схем на этапе размещения элементов на программируемых логических интегральных схемах (ПЛИС). Поскольку ресурсы ПЛИС ограничены, ключевой задачей разработки систем автоматизированного проектирования (САПР) для ПЛИС является оптимизация эффективности использования этих ресурсов. Решение этой задачи подразумевает разработку новых алгоритмов, позволяющих учитывать архитектурные особенности проектируемых схем. В данной работе рассматриваются основные проблемы, связанные с задачей размещения на ПЛИС с оптимизацией задержек, и существующие подходы к их решению. В данной работе предложен новый метод оценки критичности соединений для оптимизации проектируемых схем на этапе размещения с учетом пользовательских временных ограничений. Представлен алгоритм размещения на основе предложенного метода, а также результаты анализа его эффективности. Эксперименты показали, что применение предложенного метода позволяет сократить задержки критических путей в схеме на 4,32% относительно классического подхода к оценке критичности соединений.

Декомпозиция сложных систем – широко распространённый метод анализа и преобразований, применяемый в различных областях. Декомпозиция в менее сложные подсистемы, помимо того, что уменьшает в целом представление исходной системы (при этом, возможно, оптимизируются и другие её характеристики), позволяет выявить скрытую структуру системы, что, в частности, позволяет провести её более глубокий анализ и преобразования. В статье рассмотрен подход к декомпозиции Ашенхёрста для таблично заданных булевых функций (это могут быть таблицы истинности, характеристические вектора нулей и единиц и так далее), основанный на интерпретации композиции таких функций как их соединения-с-равенством (аналогично SQL оператору JOIN ON с равенством). Задача декомпозиции сведена к задаче решения с использованием базисов Грёбнера системы квадратных уравнений над конечным полем порядка 2 для некоторых специально введённых параметров. Решение системы индуцирует разбиение входных переменных исходной функции на связанные и свободные переменные, что, в свою очередь, позволяет определить функции-компоненты декомпозиции, при этом сами вычисленные параметры связывают их, выступая для одной в качестве значений результата, а для другой значений аргумента. Приведены результаты экспериментов по декомпозиции в системе компьютерной алгебры Maple. Рассмотрены варианты обобщения данного подхода.

Ошибки в исходном коде, часто являющиеся причиной уязвимостей, могут быть найдены с помощью разных методов статического анализа. Однако методы на основе анализа помеченных данных имеют ряд преимуществ. В работе предложен комплекс методов, которые в совокупности с алгоритмом на основе IFDS для распространения помеченных данных позволяют превзойти результаты существующих промышленных инструментов. Комплекс методов реализован в промышленном статическом анализаторе SharpChecker и протестирован как на наборе тестов для статических анализаторов, таких как Juliet и WebGoat, для оценки полноты, так и на реальных проектах для оценки точности и производительности. Приведены результаты сравнения с популярными инструментами InferSharp, Security Code Scan, а также коммерческими анализаторами. Показаны относительно высокие значения полноты и точности анализатора SharpChecker. Результаты сравнения позволяют заключить, что предложенный комплекс методов имеет высокую практическую значимость при поиске уязвимостей.

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

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

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

Исследуется влияние метода аугментации и балансировки некомплектной выборки, содержащей пропущенные значения признаков, на точность прогноза. Результаты для некомплектной выборки сравниваются с результатами для выборки, значения признаков которой полностью заполнены. Предложен новый алгоритм сэмплирования с удалением для аугментации и балансировки некомплектной выборки. В рамках теории вероятностно приближенно корректного (ВПК) обучения авторами была исследована задача обучения на некомплектной выборке. Был оценен рост размерности Вапника-Червоненкиса множества функций при заполнении пропущенных значений фиксированным значением из конечного множества. Было доказано, что требуемый размер выборки для ВПК обучения с достаточной точностью, растет логарифмически медленно с ростом размера этого множества. Установлено, что метод аугментации сэмплированием с удалением, позволяет получить наиболее высокую сбалансированную точность для некомплектных линейно разделимых выборок малого размера. При обучении на выборках среднего и большого размера, во всех рассмотренных случаях, аугментация позволяет получить большее увеличение целевых метрик для некомплектных выборок, чем для полностью заполненных. Таким образом, особенно эффективна аугментация при обучении на некомплектной выборке.

В работе рассматривается решение задачи предсказания паразитной ёмкости цепей при проектировании цифровых блоков СБИС до этапа трассировки на основе данных о размещении стандартных ячеек. Реальные значения паразитной ёмкости могут быть получены только после детальной трассировки и экстракции паразитных параметров в специализированном САПР, что занимает длительное время и не позволяет на раннем этапе проектирования точно оценить быстродействие блока. Классические методы оценки ёмкости не позволяют достичь баланса между точностью модели и времязатратами. В работе для решения этой задачи предложен ряд моделей машинного обучения (МО): многослойные линейные регрессионные модели с одним выходом и реализующие многозадачную регрессию, а также модели на основе градиентного бустинга над решающими деревьями – XGBoost и CatBoost. Для обучения и валидации моделей был собран набор данных, содержащий признаки и метки цепей, полученных из топологии 35 блоков по техпроцессу 40 нм. При обучении моделей использовалась кросс-валидация, метрики точности – MAE, MAPE и коэффициент детерминации R². Наибольшую точность продемонстрировала модель XGBoost_M_A на основе градиентного бустинга в режиме мультизадачной регрессии – MAE 0,57 фФ, MAPE 10,3%, что на порядок ниже ошибки, полученной классическим методом на основе Wireload-модели. Среднее ускорение получения паразитных параметров по сравнению с эталонным методом после трассировки – 90 раз. Предсказанные ёмкости цепей были использованы для оценки финальной частоты блока на этапе размещения – точность оценки составила 99,1%, а среднее ускорение расчёта в 86 раз по сравнению с оценкой после проведения детальной трассировки. Предложенные методы на основе машинного обучения позволяют с высокой точностью и скоростью оценить на раннем этапе проектирования паразитные ёмкости цепей, а также оценить частоту работы блока СБИС.

В статье анализируется система временных (темпоральных) показателей глагола в вах-васюганском хантыйском. Цель исследования заключается в установление спектра значений глагольных темпоральных суффиксов с точки зрения их типологического своеобразия по сравнению с подобными маркерами других диалектов хантыйского. Установлено, что временная система вах-васюганского хантыйского представлена двучленной оппозицией по типу «прошедшее/непрошедшее», суффиксальные репрезентанты которой неравномерно распределяются по соответствующим фрагментам временного поля. Непрошедшее время маркируется суффиксами -l/-w/-wəl/-wӛl, в то время как для обозначения действия в прошлом требуется выбрать суффиксальный показатель -s, -ɣas/-ɣäs или -ɣal/-ɣäl, указывающих на различную отдаленность прошлого действия от момента речи. Семантика нулевого маркера Ø представляется наиболее сложной для интерпретации, поскольку языковой материал указывает на способность данной граммемы относить действие как прошедшему, так и настоящему времени. Все четыре маркера прошедшего времени стабильно употребляются в образцах современной речи вах-васюганских ханты. Вычисления на платформе ЛингвоДок показывают, что маркер прошедшего времени на -s самый частоупотребимый.

Целью исследования является разработка воспроизводимого протокола для аннотации и акустического анализа русских гласных, обеспечивающего сопоставимость данных из разнородных речевых корпусов. Предложена система трехуровневой слоговой разметки с фиксацией ударности, позиции в границах интонационной фразы и структуры слога. Протокол реализован в среде Praat и включает автоматизированное извлечение акустических параметров с использованием программного обеспечения на Python. Акустический анализ сочетает статические измерения формант (F1, F2) в средней точке гласного и динамические показатели, описывающие траектории изменения формант во времени. Для учёта вариативности применяется двухэтапная нормализация (глобальная стандартизация и стабилизация параметров по говорящим). На основе обобщения данных литературы определены эталонные диапазоны F1-F2 для основных русских гласных, используемые для автоматического присвоения фонемных категорий. Результатом является стандартизированный и автоматизированный метод обработки, применимый к крупным массивам данных. Разработанный подход позволяет проводить сопоставимый акустический анализ гласных, что значимо для исследований в области экспериментальной фонетики и прикладных задач обработки речи.

Рассмотрены методы оптимизации вычислительной сложности современных моделей машинного обучения, с акцентом на глубокие нейронные сети (DNN). Особое внимание уделено проблемам, связанным с экспоненциальным ростом числа параметров в нейросетевых архитектурах, которые ограничивают их практическое применение, особенно в условиях ограниченных вычислительных ресурсов. Одним из предложенных решений является использование тензорного разложения в формате Tensor Train (TT). Этот метод позволяет эффективно сжимать параметры нейронных сетей, снижая вычислительные затраты и требования к памяти при минимальной потере точности. Методы на основе Tensor Train (TT) демонстрируют высокую эффективность в задачах робототехнической оптимизации, включая инверсную кинематику и планирование движения, обеспечивая компактное представление для мультимодальных вычислений. Описаны основные математические принципы TT-разложения, его преимущества по сравнению с традиционными методами, такими как обрезка параметров (pruning), квантизация и дистилляция знаний. В статье приведены экспериментальные результаты применения TT-разложения к сверточным и полносвязным нейронным сетям, демонстрирующие значительное сокращение объема данных и ситуативное ускорение вычислений при контролируемом уровне точности.

Для повышения эффективности работы удалённых рабочих столов ключевое значение имеет оптимизация передачи видеоданных, обеспечивающая стабильность и качество изображения при ограниченных ресурсах сети и клиента. Современные подходы включают использование специализированных протоколов передачи данных и видеокодеков, оптимизированных для работы в реальном времени. Целью данной работы является исследование и оптимизация задержек в процессе передачи видео в системе предоставления доступа к удалённым рабочим столам с использованием GStreamer для обработки видео и WebRTC для передачи данных по сети. В результате работы выявлены основные источники задержек внутри конвейеров подготовки видео удалённого рабочего стола. Проведён сравнительный анализ поведения различных конвейеров в различных сценариях и выявлены их преимущества и недостатки в контексте оптимизации трансляции изображения рабочего стола. В ходе анализа эффективности и предсказуемости рассматриваемых GStreamer-конвейеров иллюстрируются подходы и инструменты оценки данного класса конвейеров подготовки кадров. Отдельным результатом являются полученные методы оптимизации, перечисленные в разделе 3.

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

Современные модели сверхразрешения (SR) реального времени плохо справляются с особенностями сжатого видео. Часто используемые наборы данных не отражают в полной мере характеристики стримингового контента, что снижает релевантность существующих бенчмарков. Авторами предложен новый набор данных StreamSR, собранный из видеороликов с платформы YouTube и охватывающий широкий спектр жанров и разрешений видео, характерных для реальных сценариев. Протестировано 11 современных моделей сверхразрешения, работающих в реальном времени, оценена их эффективность для задач стримингового вещания. В работе демонстрируется, что дообучение других моделей на представленном наборе данных приводит к значительному повышению качества, которое хорошо обобщается на стандартные бенчмарки. Предлагается EfRLFN – эффективная модель сверхразрешения, в которую интегрированы Efficient Channel Attention и гиперболический тангенс в качестве функции активации, что является новым решением в контексте сверхразрешения в реальном времени. Архитектура оптимизирована для максимизации эффективности, также разработана составная функция потерь, улучшающая сходимость обучения. EfRLFN объединяет преимущества существующих архитектур, одновременно улучшая как визуальное качество, так и производительность.

Оценка качества изображения с эталоном (FR-IQA) имеет важное значение для сжатия, восстановления и генеративного моделирования изображений, однако существующие нейронные метрики по-прежнему работают медленно и очень уязвимы для враждебных возмущений. Мы представляем Anchored Adversarial Training (AnAT) – теоретически обоснованную стратегию защиты, которая использует чистые «якорные» образцы и ранжирование для явного ограничения точечной ошибки прогнозирования при атаках. AnAT может быть легко интегрирован в существующие архитектуры FR-IQA для повышения их надежности без значительного ухудшения производительности на чистых данных. Обширные эксперименты на пяти общедоступных тестовых наборах FR-IQA демонстрируют, что AnAT значительно улучшает устойчивость к невиданным атакам типа «белый ящик», повышая SROCC с 0,30–0,57 до 0,60–0,84 на KADID-10k, при этом сохраняя или превосходя точность незащищенных базовых моделей. Насколько нам известно, это первая техника состязательного обучения, разработанная для моделей FR-IQA.

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

В данной работе мы сосредоточились на задаче извлечения информации с веб-страниц, содержащих множество записей, задаче, приобретающей всё большую актуальность в эпоху больших объёмов веб-данных. В последнее время развитие методов машинного обучения повысило качество извлечения информации с веб-страниц. Тем не менее, большинство исследований и наборов данных направлены на изучение страниц, содержащих одну запись. Это привело к тому, что страницы со списками (они же страницы, содержащие множество записей) изучены недостаточно, несмотря на их широкое распространение и практическую значимость. Чтобы восполнить этот пробел, мы создали новый большой набор данных с открытым доступом, специально разработанный для страниц со списками. Это первый набор данных для этой задачи на русском языке. Наш набор данных содержит 13 120 веб-страниц со списками новостей, что значительно превосходит существующие наборы данных как по масштабу, так и по полноте. Наш набор данных содержит атрибуты различных типов, включая необязательные и многозначные, что обеспечивает реалистичное представление страниц со списками. Эти особенности делают наш набор данных ценным ресурсом для изучения извлечения информации со страниц, содержащих множество записей. Кроме того, мы предложили собственные методы многоэтапного извлечения информации. В этой работе мы исследуем и демонстрируем несколько стратегий применения MarkupLM к решению специфических задач извлечения информации из веб-страниц с несколькими записями. Наши эксперименты подтверждают преимущества наших методов. Публикуя наш набор данных в открытом доступе (https://github.com/ispras/news-page-dataset), мы стремимся к развитию области извлечения информации из страниц с несколькими записями.