Кельманов, А. В. Рандомизированный алгоритм для одной задачи двухкластерного разбиения множества векторов [Текст] / А. В. Кельманов, В. И. Хандеев // Журнал вычислительной математики и математической физики. - 2015. - Т. 55, № 2. - С. 335-344. - Библиогр.: c. 343-344 . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): NP-трудность -- асимптотические точности -- двухкластерное разбиение множества -- задачи кластерного анализа -- квадраты евклидовых расстояний -- множества векторов -- рандомизированные алгоритмы Аннотация: Обоснован рандомизированный алгоритм для NP-трудной в сильном смысле задачи разбиения конечного множества векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы квадратов расстояний от элементов кластеров до их центров. Предполагается, что центр одного из кластеров является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. Центр другого кластера фиксирован в начале координат. Предложенный алгоритм при заданных относительной ошибке и вероятности несрабатывания для установленного значения параметра находит приближенное решение задачи за линейное от размерности пространства и размера входа задачи время. Найдены условия, при которых алгоритм асимптотически точен и позволяет находить решение за время, линейное от размерности пространства и квадратичное от размера входа задачи. Доп.точки доступа: Хандеев, В. И. Нет сведений об экземплярах (Источник в БД не найден) |
Гасников, А. В. Об эффективных рандомизированных алгоритмах поиска вектора PageRank [Текст] / А. В. Гасников, Д. Ю. Дмитриев // Журнал вычислительной математики и математической физики. - 2015. - Т. 55, № 3. - С. 355-371. - Библиогр.: c. 370-371 . - ISSN 0044-4669
Рубрики: Математика Вычислительная математика Кл.слова (ненормированные): Markov chain Carlo -- PageRank -- Кнута-Яо алгоритм -- алгоритм Кнута-Яо -- метод зеркального спуска -- поиск вектора PageRank -- поиск ранжирующего вектора -- рандомизация -- рандомизированные алгоритмы -- стохастическая оптимизация Аннотация: В работе рассматриваются два рандомизированных способа поиска вектора PageRank. На основе современных неравенств концентрации меры в работе приводятся новые оценки времени работы такого метода, учитывающие специфику матрицы P. В основе второго способа лежит идея сведения поиска ранжирующего вектора к поиску равновесия в антагонистической матричной игре. Доп.точки доступа: Дмитриев, Д. Ю. Нет сведений об экземплярах (Источник в БД не найден) |
Рандомизированное вычисление инвариантных нулей модели электроэнергетической системы, заданной в дескрипторной форме [Текст] / М. Г. Гаджиев [и др.] // Известия Российской академии наук. Энергетика. - 2019. - № 2. - С. 127-134 : ил. - Библиогр.: с. 133-134 (21 назв.). - Заглавие, аннотация, ключевые слова на русском и английском языках . - ISSN 0002-3310
Рубрики: Математика Вычислительная математика Энергетика Электрические системы в целом Кл.слова (ненормированные): Розенброка матрицы -- инвариантные нули -- матрицы Розенброка -- обобщенные пучки матриц -- пучки матриц -- рандомизация -- рандомизированное квадрирование -- рандомизированные алгоритмы -- рандомизированные вычисления -- электроэнергетические системы Аннотация: Предложен рандомизированный алгоритм вычисления инвариантных нулей модели электроэнергетической системы как динамической системы с многими входами и многими выходами, заданной в линейной дескрипторной форме. Определения инвариантных нулей осуществляется путем рандомизированного квадрирования представления исходной системы. Рандомизация позволяет сформировать достаточное по мощности семейство обобщенных матриц Розенброка (обобщенных пучков матриц), пересечение множеств конечных собственных значений которых совпадает с инвариантными нулями модели электроэнергетической системы. Доп.точки доступа: Гаджиев, М. Г.; Василенко, Н. Е.; Мисриханов, М. Ш.; Рябченко, В. Н. Нет сведений об экземплярах (Источник в БД не найден) |
Морозова, Елена Владимировна (кандидат технических наук). Способ сокращения размера подписи в рандомизированных алгоритмах ЭЦП [Текст] / Е. В. Морозова, А. А Костина, Д. Н. Молдовян // Вопросы защиты информации. - 2023. - № 1. - С. 29-34. - Библиогр.: с. 33 (14 назв. ) . - ISSN 2073-2600
Рубрики: Вычислительная техника Вычислительная техника в целом Кл.слова (ненормированные): компьютерная безопасность -- конечная ассоциативная алгебра -- некоммутативная алгебра -- постквантовая криптография -- рандомизированные алгоритмы -- скрытая группа -- хэш-функции -- электронные цифровые подписи Аннотация: Предложен способ уменьшения битовой длины подписи в рандомизированных алгоритмах ЭЦП двух разных типов, основанных на вычислительной трудности: задачи дискретного логарифмирования и решения систем многих квадратных уравнений с многими неизвестными. В рассмотренных алгоритмах ЭЦП рандомизирующий элемент подписи вычисляется как значение хэш-функции, поэтому для обеспечения L-битной стойкости к атакам на основе поиска коллизий требуется использовать хэш-функции с 2L-битными значениями. В предложенном способе используют две независимые хэш-функции с L-битными значениями. Одна из них служит для вычисления первого элемента подписи, а вторая - для вычисления значения хэш-функции h от подписываемого документа. Значение h входит в проверочное уравнение как степень при одном из множителей, что обеспечивает L-битный уровень стойкости к атакам на основе поиска коллизий при L-битном рандомизирующем элементе подписи. Доп.точки доступа: Костина, Анна Александровна; Молдовян, Дмитрий Николаевич (кандидат технических наук) Нет сведений об экземплярах (Источник в БД не найден) |