Add to Quick Collection
All 22 Results
Showing items 1 - 15 of 22.
Add All Items to Quick Collection
Source: Прикладная дискретная математика. 2023. № 62. С. 119-123
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы извлечения квадратного корня по простому модулю. Вопрос о вычислительной сложности этой проблемы до сих пор открыт. Однако известны алгоритмы (например, алгор
... More
Source: Прикладная дискретная математика. 2023. № 60. С. 114-119
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы кластеризации графов с ограничением p на размеры кластеров при p > 3. В этой задаче структура взаимосвязей объектов задаётся с помощью графа, вершины которого
... More
Source: Прикладная дискретная математика. 2023. № 61. С. 121-126
Type: статьи в журналах
Date: 2023
Description:
Изучается генерическая сложность проблемы факторизации целых чисел. Данная проблема, восходящая ещё к Гауссу, имеет важное значение для современной криптографии. Например, на предположении о её трудно
... More
Source: Прикладная дискретная математика. 2022. № 57. С. 91-97
Type: статьи в журналах
Date: 2022
Description:
Изучается генерическая сложность проблемы кластеризации графов с ограничениями на число кластеров. В этой проблеме структура взаимосвязей объектов задаётся с помощью графа, вершины которого соответств
... More
Source: Прикладная дискретная математика. 2022. № 55. С. 95-101
Type: статьи в журналах
Date: 2022
Description:
Проблема вхождения в конечно порождённую подгруппу (подполугруппу) для групп (полугрупп) является классической алгоритмической проблемой в алгебре, активно изучаемой многие десятилетия. Уже для достат
... More
Source: Прикладная дискретная математика. 2022. № 58. С. 105-111
Type: статьи в журналах
Date: 2022
Description:
NP-полнота проблемы разбиения графа на треугольники доказана Шейфером в 1974 г. и содержится в классической монографии М. Гэри и Д. Джонсона. В данной работе изучается генерическая сложность этой проб
... More
Source: Прикладная дискретная математика. 2021. № 51. С. 120-128
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы изоморфизма конечных полугрупп. В этой проблеме по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли
... More
Source: Прикладная дискретная математика. Приложение. 2021. № 14. С. 178-180
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы изоморфизма конечных полугрупп: по любым двум полугруппам одинакового порядка, заданным таблицами умножения, требуется определить, являются ли они изоморфными
... More
Source: Прикладная дискретная математика. 2021. № 53. С. 120-126
Type: статьи в журналах
Date: 2021
Description:
Изучается генерическая сложность проблемы распознавания гамильтоновых путей в конечных графах. Путь в графе называется гамильтоновым, если он проходит через все вершины ровно по одному разу. Доказывае
... More
Source: Прикладная дискретная математика. 2020. № 47. С. 101-107
Type: статьи в журналах
Date: 2020
Description:
Генерический подход к алгоритмическим проблемам предложен Каповичем, Мясниковым, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода алгоритмическая проблема рассматривается не на всём множестве вхо
... More
Source: Прикладная дискретная математика. 2020. № 50. С. 118-126
Type: статьи в журналах
Date: 2020
Description:
В 2003 г. Каповичем, Мясниковым, Шуппом и Шпильрайном была предложена теория генерической вычислимости и сложности вычислений. В рамках этого подхода алгоритмическая проблема рассматривается не на всё
... More
Source: Прикладная дискретная математика. 2020. № 48. С. 93-99
Type: статьи в журналах
Date: 2020
Description:
Генерический подход к алгоритмическим проблемам был предложен Мясниковым, Каповичем, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода рассматривается поведение алгоритмов на множествах почти всех
... More
Source: Прикладная дискретная математика. Приложение. 2020. № 13. С. 111-113
Type: статьи в журналах
Date: 2020
Description:
Изучается генерическая сложность проблемы представимости натуральных чисел суммой двух квадратов. Эта проблема, восходящая ещё к Ферма и Эйлеру, тесно связана с проблемами факторизации целых чисел и р
... More
Source: Прикладная дискретная математика. 2020. № 49. С. 120-126
Type: статьи в журналах
Date: 2020
Description:
Многие задачи о конечных графах и конечных полях могут быть сформулированы на языке универсальной алгебраической геометрии, в рамках которой эти объекты рассмативаются как алгебраические системы в зад
... More
Source: Прикладная дискретная математика. 2019. № 44. С. 107-112
Type: статьи в журналах
Date: 2019
Description:
Генерический подход к алгоритмическим проблемам предложен Каповичем, Мясниковым, Шуппом и Шпильрайном в 2003 г. В рамках этого подхода изучается поведение алгоритмов на множестве «почти всех» входов (
... More
